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