Conference paper

MEDUNA Alexander and TECHET Jiří. Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses. In: Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems. High Tatras: University of Pavol Jozef Šafárik, 2007, pp. 178-185. ISBN 978-80-7097-688-3.
Publication language:english
Original title:Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses
Title (cs):Redukce generátorů vět předcházených jejich nejlevějšími rozbory
Pages:178-185
Proceedings:Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems
Conference:9th International Workshop on Descriptional Complexity of Formal Systems
Place:High Tatras, SK
Year:2007
ISBN:978-80-7097-688-3
Publisher:University of Pavol Jozef Šafárik
Keywords
scattered context grammars, canonical derivations, parses, descriptional complexity
Annotation
This paper uses scattered context grammars to derive their sentences preceded by corresponding parses--the sequences of labels of productions used during the derivation. It discusses their canonical versions, which make this derivation in a leftmost way, and demonstrates that for every recursively enumerable language, L, there exists a scattered context generator whose language consists of L's sentences preceded by their leftmost parses. In fact, this demonstration is achieved based on generators with a reduced number of nonterminals.
BibTeX:
@INPROCEEDINGS{
   author = {Alexander Meduna and Ji{\v{r}}{\'{i}} Techet},
   title = {Reduction of Scattered Context Generators of Sentences
	Preceded by Their Leftmost Parses},
   pages = {178--185},
   booktitle = {Proceedings of 9th International Workshop on Descriptional
	Complexity of Formal Systems},
   year = {2007},
   location = {High Tatras, SK},
   publisher = {University of Pavol Jozef {\v{S}}af{\'{a}}rik},
   ISBN = {978-80-7097-688-3},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=8361}
}

Your IPv4 address: 54.158.217.43
Switch to IPv6 connection

DNSSEC [dnssec]