Abstract
We examine both the modeling power of normal and sinkless Petri nets and the computational complexities of various classical decision problems with respect to these two classes. We argue that although neither normal nor sinkless Petri nets are strictly more powerful than persistent Petri nets, they nonetheless are both capable of modeling a more interesting class of problems. On the other hand, we give strong evidence that normal and sinkless Petri nets are easier to analyze than persistent Petri nets. In so doing, we apply techniques originally developed for conflict-free Petri nets — a class defined solely in terms of the structure of the net — to sinkless Petri nets — a class defined in terms of the behavior of the net. As a result, we give the first comprehensive complexity analysis of a class of potentially unbounded Petri nets defined in terms of their behavior.
This work was supported in part by National Science Foundation Grant No. CCR-8711579.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
H. Baker. Rabin's Proof of the Undecidability of the Reachability Set Inclusion Problem of Vector Addition Systems. Memo 79, MIT Project MAC, Computer Structure Group, 1973.
I. Borosh and L. Treybig. Bounds on positive integral solutions of linear Diophantine equations. Proc. AMS, 55:299–304, March 1976.
E. Cardoza, R. Lipton, and A. Meyer. Exponential space complete problems for Petri nets and commutative semigroups. In Proceedings of the 8th Annual ACM Symposium on Theory of Computing, pages 50–54, 1976.
S. Crespi-Reghizzi and D. Mandrioli. A decidability theorem for a class of vector addition systems. Information Processing Letters, 3:78–80, 1975.
J. Grabowski. The decidability of persistence for vector addition systems. Information Processing Letters, 11:20–23, 1980.
A. Ginzburg and M. Yoeli. Vector addition systems and regular languages. J. of Computer and System Sciences, 20:277–284, 1980.
M. Hack. Petri Net Languages. Memo 124, MIT Project MAC, Computer Structure Group, 1975.
M. Hack. The equality problem for vector addition systems is undecidable. Theoret. Comp. Sci., 2:77–95, 1976.
J. Hopcroft and J. Pansiot. On the reachability problem for 5-dimensional vector addition systems. Theoret. Comp. Sci., 8:135–159, 1979.
R. Howell and L. Rosier. Completeness results for conflict-free vector replacement systems. J. of Computer and System Sciences, 37:349–366, 1988.
R. Howell and L. Rosier. On questions of fairness and temporal logic for conflict-free Petri nets. In G. Rozenberg, editor, Advances in Petri Nets 1988, pages 200–226, Springer-Verlag, Berlin, 1988. LNCS 340.
R. Howell, L. Rosier, D. Huynh, and H. Yen. Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states. Theoret. Comp. Sci., 46:107–140, 1986.
R. Howell, L. Rosier, and H. Yen. An O(n1.5) algorithm to decide boundedness for conflict-free vector replacement systems. Information Processing Letters, 25:27–33, 1987.
R. Howell, L. Rosier, and H. Yen. Normal and Sinkless Petri Nets. Technical Report TR-CS-88-14, Kansas State University, Manhattan, Kansas 66506, 1988.
J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Mass., 1979.
D. Huynh. The complexity of semilinear sets. Elektronische Informationsverarbeitung und Kybernetik, 18:291–338, 1982.
D. Huynh. The complexity of the equivalence problem for commutative semigroups and symmetric vector addition systems. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing, pages 405–412, 1985.
D. Huynh. A simple proof for the σ P2 upper bound of the inequivalence problem for semilinear sets. Elektronische Informationsverarbeitung und Kybernetik, 22:147–156, 1986.
N. Jones, L. Landweber, and Y. Lien. Complexity of some problems in Petri nets. Theoret. Comp. Sci., 4:277–299, 1977.
R. Kosaraju. Decidability of reachability in vector addition systems. In Proceedings of the 14th Annual ACM Symposium on Theory of Computing, pages 267–280, 1982.
J. Lambert. Consequences of the decidability of the reachability problem for Petri nets. In Proceedings of the Eighth European Workshop on Application and Theory of Petri Nets, pages 451–470, 1987. To appear in Theoret. Comp. Sci.
R. Lipton. The Reachability Problem Requires Exponential Space. Technical Report 62, Yale University, Dept. of CS., Jan. 1976.
L. Landweber and E. Robertson. Properties of conflict-free and persistent Petri nets. JACM, 25:352–364, 1978.
E. Mayr. Persistence of vector replacement systems is decidable. Acta Informatica, 15:309–318, 1981.
E. Mayr. An algorithm for the general Petri net reachability problem. SIAM J. Comput., 13:441–460, 1984. A preliminary version of this paper was presented at the 13th Annual Symposium on Theory of Computing, 1981.
E. Mayr and A. Meyer. The complexity of the finite containment problem for Petri nets. JACM, 28:561–576, 1981.
E. Mayr and A. Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in Mathematics, 46:305–329, 1982.
H. Müller. On the reachability problem for persistent vector replacement systems. Computing, Suppl., 3:89–104, 1981.
J. Peterson. Petri Net Theory and the Modeling of Systems. Prentice Hall, Englewood Cliffs, NJ, 1981.
C. Rackoff. The covering and boundedness problems for vector addition systems. Theoret. Comp. Sci., 6:223–231, 1978.
W. Reisig. Petri Nets: An Introduction. Springer-Verlag, Heidelberg, 1985.
L. Stockmeyer. The polynomial-time hierarchy. Theoret. Comp. Sci., 3:1–22, 1977.
R. Valk and G. Vidal-Naquet. Petri nets and regular languages. J. of Computer and System Sciences, 23:299–325, 1981.
H. Yamasaki. Normal Petri nets. Theoret. Comp. Sci., 31:307–315, 1984.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Howell, R.R., Rosier, L.E., Yen, HC. (1989). Normal and sinkless Petri nets. In: Csirik, J., Demetrovics, J., Gécseg, F. (eds) Fundamentals of Computation Theory. FCT 1989. Lecture Notes in Computer Science, vol 380. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-51498-8_22
Download citation
DOI: https://doi.org/10.1007/3-540-51498-8_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51498-5
Online ISBN: 978-3-540-48180-5
eBook Packages: Springer Book Archive