Detail publikace

On Nondeterminism in Programmed Grammars

MEDUNA Alexander, VRÁBEL Lukáš a 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, s. 316-328. ISBN 978-615-5097-19-5.
Název česky
O nedeterminismu v programovaných gramatikách
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Vrábel Lukáš, Ing. (UIFS FIT VUT)
Zemek Petr, Ing. (UIFS FIT VUT)
Klíčová slova

Formální jazyky, programované gramatiky, nedeterminismus, generativní síla

Abstrakt

V článku je studován vliv nedeterminismu na generativní sílu programovaných gramatik. Je ukázáno, že pro každou programovanou gramatiku existuje ekvivalentní programovaná gramatika, kde pouze jediné pravidlo má více než jednoho následníka. Je ustavena nekonečná hierarchie jazykových tříd vyplývající z počtu následníků pravidel. V závěru článku jsou formulovány otevřené problémy.

Rok
2011
Strany
316-328
Sborník
13th International Conference on Automata and Formal Languages
Konference
13th International Conference on Automata and Formal Languages, Debrecen, HU
ISBN
978-615-5097-19-5
Vydavatel
Computer and Automation Research Institute, Hungarian Academy of Sciences
Místo
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"
}
Nahoru