Přístupnostní navigace
E-application
Search Search Close
Publication detail
MEDUNA, A. TECHET, J.
Original Title
Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses
Type
conference paper
Language
English
Original Abstract
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.
Keywords
scattered context grammars, canonical derivations, parses, descriptional complexity
Authors
MEDUNA, A.; TECHET, J.
RIV year
2007
Released
20. 7. 2007
Publisher
University of Pavol Jozef Šafárik
Location
High Tatras
ISBN
978-80-7097-688-3
Book
Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems
Pages from
178
Pages to
185
Pages count
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" }