Detail publikace

On Nondeterminism in Programmed Grammars

MEDUNA, A. VRÁBEL, L. ZEMEK, P.

Originální název

On Nondeterminism in Programmed Grammars

Typ

článek ve sborníku mimo WoS a Scopus

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

Formal languages, Programmed grammars, Nondeterminism, Generative power

Autoři

MEDUNA, A.; VRÁBEL, L.; ZEMEK, P.

Rok RIV

2011

Vydáno

17. 8. 2011

Nakladatel

Computer and Automation Research Institute, Hungarian Academy of Sciences

Místo

Debrecen

ISBN

978-615-5097-19-5

Kniha

13th International Conference on Automata and Formal Languages

Strany od

316

Strany do

328

Strany počet

13

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"
}