×

Petri net algorithms in the theory of matrix grammars. (English) Zbl 0834.68064

This paper shows that the languages over a one-letter alphabet generated by context-free matrix grammars are always regular. Moreover we give a decision procedure for the question of whether a context-free matrix language is finite. Hereby we strengthen a result of E. Maekinen [Ann. Soc. Math. Pol., Ser. IV, Fundam. Inf. 16, No. 1, 93-97 (1992; Zbl 0754.68069)] and settle a number of open questions in [J. Dassow and G. Pǎun, Regular rewriting in formal language theory. (EATCS Monographs on Theoretical Computer Science) Berlin, Heidelberg, New York: Springer (1980)]. Both results are obtained by a reduction to Petri net problems.
Reviewer: D.Hauschildt

MSC:

68Q45 Formal languages and automata
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Citations:

Zbl 0754.68069
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Dassow, J., Pâun, G.: Regular rewriting in formal language theory. (EATCS Monographs on Theoretical Computer Science) Berlin, Heidelberg, New York: Springer 1989
[2] Ginsburg, S., Greibach, S., Harrison, M.A.: One-way stack automata. J. ACM14, 389-418 (1967) · Zbl 0171.14803
[3] Hauschildt, D. Semilinearity of the reachability set is decidable for Petri nets. Doctoral Thesis, Dept. of Computer Science, University of Hamburg (1990). Also appeared as: Dept. of Computer Science, University of Hamburg, Technical Report No. FBI-HH-B-146/90
[4] Kosaraju, S.R. Decidability of reachability in vector addition systems. Proc. 14th Ann. ACM STOC (1982), pp. 267-281
[5] Kleine Büning, H., Lettmann, T., Mayr, E.: Projections of vector addition system reachability sets are semilinear, TCS64, 343-350 (1989) · Zbl 0681.68080
[6] Lambert J.L.: Consequences of the decidability of the reachability problem for Petri nets. Rapport de recherche no 313, L.R.I., Universite de Paris-Sud (1986)
[7] Lambert, J.L.: Some Consequences of the decidability of the reachability problem for Petri nets. Advances in Petri Nets 1988 (Lect. Notes Comput. Sci., vol. 340, pp. 266-282) Berlin, Heidelberg, New York: Springer 1988 · Zbl 0667.68070
[8] Lambert, J.L.: Vector Addition Systems and Semi-Linearity. Prepublication de l’Universite Paris-Nord. Departement d’Informatique, N 90-8 (1990); also to appear in: SIAM J. Comput.
[9] Mayr, E. W.: An algorithm for the general Petri net reachability problem. SIAM J. Comput.13, 441-460 (1984) · Zbl 0563.68057
[10] Mäkinen, E.: On the generative capacity of context-free matrix grammars over one-letter alphabet. Fund. Inf.16, 93-97 (1992) · Zbl 0754.68069
[11] Gonczarowski, J., Warmuth, M.K.: Scattered versus context-sensitive rewriting. Acta Inf.27, 81-95 (1989) · Zbl 0664.68078
[12] Rosenkranz, D.J.: Programmed grammars and classes of formal languages. J. ACM16, 107-131 (1969) · Zbl 0182.02004
[13] Schwer, S.: The context-freeness of the language associated with vector addition systems is decidable. Theor. Comput. Sci.98, 199-247 (1992) · Zbl 0769.68067
[14] Leeuwen, J. van: Extremal properties of non-deterministic time complexity classes. In: Gelenbe, E., Poitier, D. (eds.) International Computing Symposium, pp. 61-64, Amsterdam: North-Holland/American Elsevier 1975 · Zbl 0324.68026
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.