Publication Details

On Nondeterminism in Programmed Grammars

MEDUNA, A.; VRÁBEL, L.; ZEMEK, P. On Nondeterminism in Programmed Grammars. 13th International Conference on Automata and Formal Languages. Debrecen: Computer and Automation Research Institute, Hungarian Academy of Sciences, 2011. p. 316-328. ISBN: 978-615-5097-19-5.

Czech title

O nedeterminismu v programovaných gramatikách

Type

conference paper

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Vrábel Lukáš, Ing.
Zemek Petr, Ing., Ph.D.

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

ISBN

978-615-5097-19-5

Publisher

Computer and Automation Research Institute, Hungarian Academy of Sciences

Place

Debrecen

BibTeX

@inproceedings{BUT76303,
  author="Alexandr {Meduna} and Lukáš {Vrábel} and Petr {Zemek}",
  title="On Nondeterminism in Programmed Grammars",
  booktitle="13th International Conference on Automata and Formal Languages",
  year="2011",
  pages="316--328",
  publisher="Computer and Automation Research Institute, Hungarian Academy of Sciences",
  address="Debrecen",
  isbn="978-615-5097-19-5"
}