Petri nets, commutative context-free grammars, and basic parallel processes. (English) Zbl 1508.68241
Reichel, Horst (ed.), Fundamentals of computation theory. 10th international conference, FCT’95, Dresden, Germany, August 22–25, 1995. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 965, 221-232 (1995).
For the entire collection see [Zbl 0921.00030].
MSC:
| 68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |
| 68Q42 | Grammars and rewriting systems |
References:
| [1] | S. Christensen. Decidability and Decomposition in Process Algebras. Ph.D. Thesis, University of Edinburgh, CST-105-93, (1993). |
| [2] | S. Christensen, H. Hüttel, and C. Stirling. Bisimulation equivalence is decidable for all context-free processes. Proceedings of CONCUR ’92, LNCS 630, pp. 138-147 (1992). · Zbl 0833.68074 |
| [3] | S. Christensen, Y. Hirshfeld and F. Moller. Bisimulation equivalence is decidable for basic parallel processes. CONCUR ’93, LNCS 715, 143-157 (1993). |
| [4] | S. Eilenberg and M.P. Schützenberger. Rational sets in commutative monoids. Journal of Algebra 13, 173-191 (1969). · Zbl 0206.02703 |
| [5] | J. Esparza and M. Nielsen. Decidability Issues for Petri Nets—a Survey. EATCS Bulletin 52 (1994). Also: Journal of Information Processing and Cybernetics. · Zbl 0838.68082 |
| [6] | S. Ginsburg. The Mathematical Theory of Context-free Languages. McGraw-Hill (1966). · Zbl 0184.28401 |
| [7] | S. Ginsburg and E.H. Spanier. Semigroups, Presburger formulas and languages. Pacific Journal of Mathematics 16, pp. 285-296 (1966). · Zbl 0143.01602 |
| [8] | Y. Hirshfeld. Petri Nets and the Equivalence Problem. CSL ’93, LNCS 832 pp. 165-174 (1994). · Zbl 0953.68571 |
| [9] | Y. Hirshfeld and Faron Moller. Deciding Equivalences in Simple Process Algebras. In: “Modal Logic and Process Algebra: Proceedings of a 3-day Workshop on Bisimulation”, CSLI Press (1995). |
| [10] | Y. Hirshfeld, M. Jerrum and F. Moller. A polynomial algorithm for deciding bisimulation of normed basic parallel processes. LFCS report 94-288, Edinburgh University (1994). To appear in Journal of Mathematical Structures in Computer Science. · Zbl 0857.68042 |
| [11] | J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979). · Zbl 0426.68001 |
| [12] | D.T. Huynh. Commutative Grammars: The Complexity of Uniform Word Problems. Information and Control 57, 21-39 (1983). · Zbl 0541.68044 |
| [13] | P. Jančar. Decidability Questions for Bisimilarity of Petri Nets and Some Related Problems. STACS ’94, LNCS 775, pp. 581-592 (1994). To appear in Theoretical Computer Science. · Zbl 0941.68644 |
| [14] | R. Milner. Communication and Concurrency. Prentice-Hall (1989). · Zbl 0683.68008 |
| [15] | P.H. Starke. Analyse von Petri-Netz Modellen. Teubner (1990). · Zbl 0724.68002 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
