Článek ve sborníku konference

 
Masopust, T., Meduna, A.: Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement, In: Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems, Magdeburg, DE, uni-magdeburg, 2009, s. 235-245, ISBN 978-3-940961-31-0
Jazyk publikace:angličtina
Název publikace:Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement
Název (cs):Popicná složitost gramatik s rozptýleným kontextem se třemi neterminály: vylepšení
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
Místo vydání:Magdeburg, DE
Rok:2009
ISBN:978-3-940961-31-0
Vydavatel:Otto-von-Guericke-Universität Magdeburg
URL:http://cgi.cse.unsw.edu.au/~rvg/eptcs/content.cgi?DCFS2009 [HTML]
Klíčová slova
Scattered context grammars, descriptional complexity, generative power
Anotace
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.
BibTeX:
@INPROCEEDINGS{
   author = {Tomáš 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 = {http://www.fit.vutbr.cz/research/view_pub.php?id=8940}
}