Publication result detail

Canonical Scattered Context Generators of Sentences with Their Parses

MEDUNA, A.; TECHET, J.

Original Title

Canonical Scattered Context Generators of Sentences with Their Parses

English Title

Canonical Scattered Context Generators of Sentences with Their Parses

Type

Peer-reviewed article not indexed in WoS or Scopus

Original 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.

English 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.

Keywords

scattered context grammars, canonical derivations, parses, descriptional complexity

Key words in English

scattered context grammars, canonical derivations, parses, descriptional complexity

Authors

MEDUNA, A.; TECHET, J.

Released

10.12.2007

ISBN

0304-3975

Periodical

Theoretical Computer Science

Volume

2007

Number

389

State

Kingdom of the Netherlands

Pages from

73

Pages to

81

Pages count

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