Detail publikace

Canonical Scattered Context Generators of Sentences with Their Parses

MEDUNA, A. TECHET, J.

Originální název

Canonical Scattered Context Generators of Sentences with Their Parses

Typ

článek v časopise - ostatní, Jost

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

scattered context grammars, canonical derivations, parses, descriptional complexity

Autoři

MEDUNA, A.; TECHET, J.

Rok RIV

2007

Vydáno

10. 12. 2007

ISSN

0304-3975

Periodikum

Theoretical Computer Science

Ročník

2007

Číslo

389

Stát

Nizozemsko

Strany od

73

Strany do

81

Strany počet

9

BibTex

@article{BUT45163,
  author="Alexandr {Meduna} and Jiří {Techet}",
  title="Canonical Scattered Context Generators of Sentences with Their Parses",
  journal="Theoretical Computer Science",
  year="2007",
  volume="2007",
  number="389",
  pages="73--81",
  issn="0304-3975"
}