Publication Details

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

MEDUNA, A.; TECHET, J. Reduction of Scattered Context Generators of Sentences Preceded by Their Leftmost Parses. In Proceedings of 9th International Workshop on Descriptional Complexity of Formal Systems. High Tatras: University of Pavol Jozef Šafárik, 2007. p. 178-185. ISBN: 978-80-7097-688-3.

Czech title

Redukce generátorů vět předcházených jejich nejlevějšími rozbory

Type

conference paper

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Techet Jiří, Ing., Ph.D.

Keywords

scattered context grammars, canonical derivations, parses, descriptional complexity

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.

Published

2007

Pages

178–185

Proceedings

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

ISBN

978-80-7097-688-3

Publisher

University of Pavol Jozef Šafárik

Place

High Tatras

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