Publication Details

Canonical Scattered Context Generators of Sentences with Their Parses

MEDUNA Alexander and TECHET Jiří. Canonical Scattered Context Generators of Sentences with Their Parses. Theoretical Computer Science, vol. 2007, no. 389, pp. 73-81. ISSN 0304-3975.

Czech title

Kanonické generování vět s jejich rozbory pomocí gramatik s rozptýleným kontextem

Type

journal article

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

Scattered context generators derive their sentences followed by the corresponding parses. This 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

2007

Pages

73-81

Journal

Theoretical Computer Science, vol. 2007, no. 389, ISSN 0304-3975

Publisher

Elsevier Science

BibTeX

@ARTICLE{FITPUB8377,
   author = "Alexander Meduna and Ji\v{r}\'{i} Techet",
   title = "Canonical Scattered Context Generators of Sentences with Their Parses",
   pages = "73--81",
   journal = "Theoretical Computer Science",
   volume = 2007,
   number = 389,
   year = 2007,
   ISSN = "0304-3975",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8377"
}