Petri net algorithms in the theory of matrix grammars (Q1342504): Difference between revisions

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.