PETRI-NET ALGORITHMS IN THE THEORY OF MATRIX GRAMMARS

Authors
HAUSCHILDT D JANTZEN M
Citation
D. Hauschildt et M. Jantzen, PETRI-NET ALGORITHMS IN THE THEORY OF MATRIX GRAMMARS, Acta informatica, 31(8), 1994, pp. 719-728
Citations number
15
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Acta informatica → ACNP
ISSN journal
00015903
Volume
31
Issue
8
Year of publication
1994
Pages
719 - 728
Database
ISI
SICI code
0001-5903(1994)31:8<719:PAITTO>2.0.ZU;2-L
Abstract
This paper shows that the languages over a one-letter alphabet generat ed by context-free matrix grammars are always regular. Morover we give a decision procedure for the question of whether a context-free matri x language is finite. Hereby we strengthen a result of [Mk 92] and set tle a number of open questions in [DP 89]. Both results are obtained b y a reduction to Petri net problems.