Detail publikačního výsledku

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

Anglický název

Canonical Scattered Context Generators of Sentences with Their Parses

Druh

Článek recenzovaný mimo WoS a Scopus

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.

Anglický 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

Klíčová slova v angličtině

scattered context grammars, canonical derivations, parses, descriptional complexity

Autoři

MEDUNA, A.; TECHET, J.

Vydáno

10.12.2007

ISSN

0304-3975

Periodikum

Theoretical Computer Science

Svazek

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