Detail publikace

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

MASOPUST, T.; MEDUNA, A. Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement. Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems. Magdeburg: Otto-von-Guericke-University of Magdeburg, 2009. p. 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
anglicky
Autoři
Masopust Tomáš, doc. RNDr., Ph.D. (CK-SZZ)
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
URL
Klíčová slova

Scattered context grammars, descriptional complexity, generative power

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
ISBN
978-3-940961-31-0
Vydavatel
Otto-von-Guericke-University of Magdeburg
Místo
Magdeburg
BibTeX 
@inproceedings{BUT33782,
  author="Tomáš {Masopust} and Alexandr {Meduna}",
  title="Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement",
  booktitle="Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems",
  year="2009",
  pages="235--245",
  publisher="Otto-von-Guericke-University of Magdeburg",
  address="Magdeburg",
  isbn="978-3-940961-31-0",
  url="http://cgi.cse.unsw.edu.au/~rvg/eptcs/content.cgi?DCFS2009"
}
Nahoru