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

Techet Jiří, Ing., Ph.D. (DIFS FIT BUT)

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"
}