zbMATH — the first resource for mathematics

A structure to decide reachability in Petri nets. (English) Zbl 0769.68104
Summary: A new structure to analyze Petri nets and decide reachability is presented. Originated in Mayr’s regular constraint graphs with a consistent marking, it is simplified, cleared and made more flexible by the introduction of the new structure of precovering graph. With its help we prove new results for languages generated by a Petri net and initial and final marking constraints.

MSC:
 68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) 68R10 Graph theory (including graph drawing) in computer science
Full Text:
References:
 [1] Autebert, J.M., LES langages algébriques, (1987), Masson Paris [2] Dershowitz, N.; Manna, Z., Proving termination with multiset ordering, Comm. ACM, 22, 8, (1979) · Zbl 0404.68022 [3] Harrison, M.A., Introduction to formal language theory, (1978), Addison-Wesley Reading · Zbl 0411.68058 [4] Hopcroft, J.; Pansiot, J.J., On the reachability problem for 5-dimensional vector addition systems, Theoret. comput. sci., 8, 135-159, (1979) · Zbl 0466.68048 [5] Jantzen, J., On the hierarchy of Petri net languages, RAIRO inform. théor., 13, 1, 19-30, (1979) · Zbl 0404.68076 [6] Karp, R.M.; Miller, R.E., Parallel program schemata, J. comput. sci., 3, 147-195, (1969) · Zbl 0198.32603 [7] Kosaraju, S.R., Decidability of reachability in vector addition systems, Proc. 14th ann. ACM STOC, 267-281, (1982) [8] Lambert, J.L., Finding a partial solution to a linear system of equations in positive integers, Comput. math. appl., 15, 3, 209-212, (1988) · Zbl 0649.65033 [9] Lothaire, M., Combinatorics on words, () · Zbl 1001.68093 [10] Mayr, E.; Mayr, E., An algorithm for the general Petri net reachability problem, SIAM J. comput, Proc. 13th ann. ACM STOC, 13, 3, 238-246, (1981), Also in [11] Muller, H., The reachability problem for VAS, (), 376-391 [12] Parigot, M.; Pelz, E., A logical formalism for the study of the finite behaviour of Petri nets, (), 346-361 [13] Peterson, J.L., Petri net theory and the modeling of systems, (1981), Prentice-Hall Englewood Cliffs [14] Petri, C.A., Kommunikation mit automaten, (1962), Institut für Instrumentelle Mathematik Bonn, Schriften des IMM Nr 2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.