Publication Details

Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses

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.
Czech title
Redukce generátorů vět předcházených jejich nejlevějšími rozbory
Type
conference paper
Language
english
Authors
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Techet Jiří, Ing., Ph.D. (DIFS FIT BUT)
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
Conference
9th International Workshop on Descriptional Complexity of Formal Systems, High Tatras, SK
ISBN
978-80-7097-688-3
Publisher
University of Pavol Jozef Šafárik
Place
High Tatras, SK
BibTeX 
@INPROCEEDINGS{FITPUB8361,
   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 = "https://www.fit.vut.cz/research/publication/8361"
}
Back to top