Detail publikace

Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement

MASOPUST Tomáš a MEDUNA Alexander. Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement. In: Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems. Magdeburg: Otto-von-Guericke-Universität Magdeburg, 2009, s. 235-245. ISBN 978-3-940961-31-0.
Název česky
Popicná složitost gramatik s rozptýleným kontextem se třemi neterminály: vylepšení
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Masopust Tomáš, RNDr., Ph.D. (UIFS FIT VUT)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
URL
Abstrakt

Nedávno bylo ukázáno, že každý rekurzívně spočetný jazyk lze generovat gramatikou s rozptýleným kontextem s nejvýše třemi neterminály. V této konstrukci však počet současně přepisovaných neterminálů zavisí na mnoha faktorech, jako je kardinalita abecedy generovaného jazyka a struktura daného jazyka vůbec. Tento článek vylepšuje původní konstrukci tak, že v každém kroku derivace se přepíše nejvýše fixní počet symbolů bez ohledu na generovaný jazyk.

Rok
2009
Strany
235-245
Sborník
Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems
Konference
11th International Workshop on Descriptional Complexity of Formal Systems, Magdeburg, DE
ISBN
978-3-940961-31-0
Vydavatel
Otto-von-Guericke-Universität Magdeburg
Místo
Magdeburg, DE
BibTeX 
@INPROCEEDINGS{FITPUB8940,
   author = "Tom\'{a}\v{s} Masopust and Alexander Meduna",
   title = "Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement",
   pages = "235--245",
   booktitle = "Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems",
   year = 2009,
   location = "Magdeburg, DE",
   publisher = "Otto-von-Guericke-University of Magdeburg",
   ISBN = "978-3-940961-31-0",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8940"
}
Nahoru