Conference paper

MEDUNA Alexander, VRÁBEL Lukáš and ZEMEK Petr. On Nondeterminism in Programmed Grammars. In: 13th International Conference on Automata and Formal Languages. Debrecen: Computer and Automation Research Institute, Hungarian Academy of Sciences, 2011, pp. 316-328. ISBN 978-615-5097-19-5.
Publication language:english
Original title:On Nondeterminism in Programmed Grammars
Title (cs):O nedeterminismu v programovaných gramatikách
Pages:316-328
Proceedings:13th International Conference on Automata and Formal Languages
Conference:13th International Conference on Automata and Formal Languages
Place:Debrecen, HU
Year:2011
ISBN:978-615-5097-19-5
Publisher:Computer and Automation Research Institute, Hungarian Academy of Sciences
Keywords
Formal languages, Programmed grammars, Nondeterminism, Generative power
Annotation
In the present paper, we discuss programmed grammars. More specifically, we discuss their nondeterministic behaviour and its reduction. We prove that for every programmed grammar, there exists an equivalent programmed grammar where only a single rule has more than one successor.  Furthermore, we establish an infinite hierarchy of language families resulting from the cardinality of successor sets. Open problem areas are formulated in the conclusion of the paper.
BibTeX:
@INPROCEEDINGS{
   author = {Alexander Meduna and Luk{\'{a}}{\v{s}} Vr{\'{a}}bel and Petr
	Zemek},
   title = {On Nondeterminism in Programmed Grammars},
   pages = {316--328},
   booktitle = {13th International Conference on Automata and Formal
	Languages},
   year = {2011},
   location = {Debrecen, HU},
   publisher = {Computer and Automation Research Institute, Hungarian
	Academy of Sciences},
   ISBN = {978-615-5097-19-5},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.en.iso-8859-2?id=9566}
}

Your IPv4 address: 107.20.115.174
Switch to IPv6 connection

DNSSEC [dnssec]