Petri net algorithms in the theory of matrix grammars (Q1342504)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Petri net algorithms in the theory of matrix grammars |
scientific article; zbMATH DE number 710531
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Petri net algorithms in the theory of matrix grammars |
scientific article; zbMATH DE number 710531 |
Statements
Petri net algorithms in the theory of matrix grammars (English)
0 references
16 February 1995
0 references
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 \textit{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 [\textit{J. Dassow} and \textit{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.
0 references
0 references
