Properties of Conflict-Free and Persistent Petri Nets
- 1 July 1978
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 25 (3) , 352-364
- https://doi.org/10.1145/322077.322079
Abstract
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 nonperslstenceKeywords
This publication has 8 references indexed in Scilit:
- Complexity of some problems in Petri netsTheoretical Computer Science, 1977
- On the equivalence of mealy-type and moore-type automata and a relation between reducibility and moore-reducibilityJournal of Computer and System Sciences, 1977
- A decidability theorem for a class of vector-addition systemsInformation Processing Letters, 1975
- A fundamental theorem of asynchronous parallel computationPublished by Springer Nature ,1975
- The recursive equivalence of the reachability problem and the liveness problem for Petri nets and vector addition systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1974
- A partial solution to the reachability-problem for vector-addition systemsPublished by Association for Computing Machinery (ACM) ,1974
- Parallel program schemataJournal of Computer and System Sciences, 1969
- On Context-Free LanguagesJournal of the ACM, 1966