Publication Details
Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses
MEDUNA, A.; TECHET, J. Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses. Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems. High Tatras: University of Pavol Jozef Šafárik, 2007. p. 178-185. ISBN: 978-80-7097-688-3.
Czech title
Redukce generátorů vět předcházených jejich nejlevějšími rozbory
Type
conference paper
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc.
(DIFS)
Techet Jiří, Ing., Ph.D.
Techet Jiří, Ing., Ph.D.
Keywords
scattered context grammars, canonical derivations, parses, descriptional complexity
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.
Published
2007
Pages
178–185
Proceedings
Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems
ISBN
978-80-7097-688-3
Publisher
University of Pavol Jozef Šafárik
Place
High Tatras
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"
}