Prof. RNDr. Alexander Meduna, CSc.

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.
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{\'{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 = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=8940}
}

Vaše IPv4 adresa: 100.24.209.47
Přepnout na https