Detail výsledku

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.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Vrábel Lukáš, Ing., UIFS (FIT)
Zemek Petr, Ing., Ph.D., UIFS (FIT)
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

Rok
2011
Strany
316–328
Sborník
13th International Conference on Automata and Formal Languages
Konference
13th International Conference on Automata and Formal Languages
ISBN
978-615-5097-19-5
Vydavatel
Computer and Automation Research Institute, Hungarian Academy of Sciences
Místo
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"
}
Projekty
Pokročilé rozpoznávání a prezentace multimediálních dat, VUT, Vnitřní projekty VUT, FIT-S-11-2, zahájení: 2011-01-01, ukončení: 2013-12-31, ukončen
Výzkum informačních technologií z hlediska bezpečnosti, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, zahájení: 2007-01-01, ukončení: 2013-12-31, řešení
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru