Petri net algorithms in the theory of matrix grammars (Q1342504): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 03:59, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Petri net algorithms in the theory of matrix grammars |
scientific article |
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
