Petri net algorithms in the theory of matrix grammars
type: Item
instance of: scholarly article
title: Petri net algorithms in the theory of matrix grammars
zbMATH Open document ID: 0834.68064
DOI: 10.1007/BF01178731
author: Dirk Hauschildt
author: Matthias Jantzen
published in: Acta Informatica
publication date: 1995-02-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q85
zbMATH DE Number: 710531
MaRDI profile type: Publication
cites work: One-way stack automata
cites work: Projections of vector addition system reachability sets are semilinear
cites work: Q3820016
cites work: An Algorithm for the General Petri Net Reachability Problem
cites work: Q3993679
cites work: Scattered versus context-sensitive rewriting
cites work: Programmed Grammars and Classes of Formal Languages
cites work: The context-freeness of the languages associated with vector addition systems is decidable
cites work: Q4088273
description: scientific article; zbMATH DE number 710531