Properties of Conflict-Free and Persistent Petri Nets
Properties of Conflict-Free and Persistent Petri Nets
复制标题
DOI：
10.1145/322077.322079
复制
发表时间：
1978-07
期刊：
影响因子：
--
通讯作者：
L. Landweber;E. Robertson
中科院分区：
文献类型：
--
作者：
L. Landweber;E. Robertson
Petri网已被广泛研究，因为它们适合作为异步计算的模型。尽管这样的努力，Petri网的数学性质是不是很好地理解。在本文中，我们研究了两个重要的特殊类型的Petri网，无冲突网和持久网，前者是后者的真子集。我们的结果完全刻画了这类网可达标记集的性质。证明了持久网的可达标记集是半可达的。自由网的有界性判定的指数时间算法。判定任意网的有界性的最著名的上界是指数空间。用“少量”的非持久性实现
Petri nets have been extensively studied because of their suitability as models for asynchronous computing Despite this effort, the mathematical properties of Petrl nets are not very well understood In this paper we investigate two unportant special types of Petn nets, the conflict-free nets and the persistent nets, the former being a proper subset of the latter. Our results completely characterize the sets of reachable markings attainable by such nets Reachabihty sets of persistent nets are shown to be semllmear A stronger result is obtamed for conflict-free nets which results m an exponential time algorithm for deciding boundedness of such nets The best known upper bound for deciding boundedness of arbitrary nets is exponential space We conclude with a proof that all reachablhty sets of Petri nets may be realized with a "small amount" of nonperslstence