Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail publikace
MEDUNA, A. TECHET, J.
Originální název
Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses
Typ
článek ve sborníku ve WoS nebo Scopus
Jazyk
angličtina
Originální abstrakt
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.
Klíčová slova
scattered context grammars, canonical derivations, parses, descriptional complexity
Autoři
MEDUNA, A.; TECHET, J.
Rok RIV
2007
Vydáno
20. 7. 2007
Nakladatel
University of Pavol Jozef Šafárik
Místo
High Tatras
ISBN
978-80-7097-688-3
Kniha
Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems
Strany od
178
Strany do
185
Strany počet
8
BibTex
@inproceedings{BUT28797, author="Alexandr {Meduna} and Jiří {Techet}", title="Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses", booktitle="Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems", year="2007", pages="178--185", publisher="University of Pavol Jozef Šafárik", address="High Tatras", isbn="978-80-7097-688-3" }