Detail publikace

On Nondeterminism in Programmed Grammars

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

Originální název

On Nondeterminism in Programmed Grammars

Anglický název

On Nondeterminism in Programmed Grammars

Jazyk

en

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.

Anglický 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.

Dokumenty

BibTex 


@inproceedings{BUT76303,
  author="Alexandr {Meduna} and Lukáš {Vrábel} and Petr {Zemek}",
  title="On Nondeterminism in Programmed Grammars",
  annote="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.",
  address="Computer and Automation Research Institute, Hungarian Academy of Sciences",
  booktitle="13th International Conference on Automata and Formal Languages",
  chapter="76303",
  edition="NEUVEDEN",
  howpublished="print",
  institution="Computer and Automation Research Institute, Hungarian Academy of Sciences",
  year="2011",
  month="august",
  pages="316--328",
  publisher="Computer and Automation Research Institute, Hungarian Academy of Sciences",
  type="conference paper"
}