Publication Details

Canonical Scattered Context Generators of Sentences with Their Parses

TECHET Jiří. Canonical Scattered Context Generators of Sentences with Their Parses. In: HONEYWELL EMI 2005 Proceedings of the International Interdisciplinary Student Competition and Conference. Brno: Faculty of Electrical Engineering and Communication BUT, 2005, pp. 80-84. ISBN 80-214-2942-9.
Czech title
Kanonické generátory vět s jejich rozbory založené na gramatikách s rozptýleným kontextem
Type
conference paper
Language
english
Authors
Keywords

parsing, scattered context grammars, propagating scattered context grammars, canonical derivations, parses, descriptional complexity

Abstract

The scattered context generators derive their sentences followed by the corresponding parses.  The paper discusses their two canonical versions, which make this derivation either in a leftmost or rightmost way.  It demonstrates that for every recursively enumerable language, L, there exists a canonical scattered context generator whose language consists of L's sentences followed by their parses.  In fact, this result is established based on the generators containing no more than six nonterminals.

Published
2005
Pages
80-84
Proceedings
HONEYWELL EMI 2005 Proceedings of the International Interdisciplinary Student Competition and Conference
Conference
Honeywell EMI 2005, Brno, CZ
ISBN
80-214-2942-9
Publisher
Faculty of Electrical Engineering and Communication BUT
Place
Brno, CZ
BibTeX
@INPROCEEDINGS{FITPUB7960,
   author = "Ji\v{r}\'{i} Techet",
   title = "Canonical Scattered Context Generators of Sentences with Their Parses",
   pages = "80--84",
   booktitle = "HONEYWELL EMI 2005 Proceedings of the International Interdisciplinary Student Competition and Conference",
   year = 2005,
   location = "Brno, CZ",
   publisher = "Faculty of Electrical Engineering and Communication BUT",
   ISBN = "80-214-2942-9",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7960"
}
Back to top