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

Type

conference paper

Language

English

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.

Keywords

scattered context grammars, canonical derivations, parses, descriptional complexity

Authors

MEDUNA, A.; TECHET, J.

RIV year

2007

Released

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

BibTex

@inproceedings{BUT28797,
  author="Alexandr {Meduna} and Jiří {Techet}",
  title="Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses",
  booktitle="Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems",
  year="2007",
  pages="178--185",
  publisher="University of Pavol Jozef Šafárik",
  address="High Tatras",
  isbn="978-80-7097-688-3"
}