Publication Details

On Nondeterminism in Programmed Grammars

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.
Czech title
O nedeterminismu v programovaných gramatikách
Type
conference paper
Language
english
Authors
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Vrábel Lukáš, Ing. (DIFS FIT BUT)
Zemek Petr, Ing. (DIFS FIT BUT)
Keywords

Formal languages, Programmed grammars, Nondeterminism, Generative power

Abstract

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.

Published
2011
Pages
316-328
Proceedings
13th International Conference on Automata and Formal Languages
Conference
13th International Conference on Automata and Formal Languages, Debrecen, HU
ISBN
978-615-5097-19-5
Publisher
Computer and Automation Research Institute, Hungarian Academy of Sciences
Place
Debrecen, HU
BibTeX 
@INPROCEEDINGS{FITPUB9566,
   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 = "https://www.fit.vut.cz/research/publication/9566"
}
Back to top