Publication detail

Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses

MEDUNA, A. TECHET, J.

Original Title

Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses

English Title

Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses

Type

conference paper

Language

en

Original Abstract

This paper uses scattered context grammars to derive their sentences preceded by corresponding parses--the sequences of labels of productions used during the derivation. It discusses their canonical versions, which make this derivation in a leftmost way, and demonstrates that for every recursively enumerable language, L, there exists a scattered context generator whose language consists of L's sentences preceded by their leftmost parses. In fact, this demonstration is achieved based on generators with a reduced number of nonterminals.

English abstract

This paper uses scattered context grammars to derive their sentences preceded by corresponding parses--the sequences of labels of productions used during the derivation. It discusses their canonical versions, which make this derivation in a leftmost way, and demonstrates that for every recursively enumerable language, L, there exists a scattered context generator whose language consists of L's sentences preceded by their leftmost parses. In fact, this demonstration is achieved based on generators with a reduced number of nonterminals.

Keywords

scattered context grammars, canonical derivations, parses, descriptional complexity

RIV year

2007

Released

20.07.2007

Publisher

University of Pavol Jozef Šafárik

Location

High Tatras

ISBN

978-80-7097-688-3

Book

Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems

Pages from

178

Pages to

185

Pages count

8

Documents

BibTex


@inproceedings{BUT28797,
  author="Alexandr {Meduna} and Jiří {Techet}",
  title="Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses",
  annote="This paper uses scattered context grammars to derive their sentences preceded by
corresponding parses--the sequences of labels of productions used during the
derivation. It discusses their canonical versions, which make this derivation in
a leftmost way, and demonstrates that for every recursively enumerable language,
L, there exists a scattered context generator whose language consists of L's
sentences preceded by their leftmost parses. In fact, this demonstration is
achieved based on generators with a reduced number of nonterminals.",
  address="University of Pavol Jozef Šafárik",
  booktitle="Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems",
  chapter="28797",
  howpublished="print",
  institution="University of Pavol Jozef Šafárik",
  year="2007",
  month="july",
  pages="178--185",
  publisher="University of Pavol Jozef Šafárik",
  type="conference paper"
}