Detail publikace

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

MEDUNA, A. TECHET, J.

Originální název

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

Typ

článek ve sborníku mimo WoS a Scopus

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

scattered context grammars, canonical derivations, parses, descriptional complexity

Autoři

MEDUNA, A.; TECHET, J.

Rok RIV

2007

Vydáno

20. 7. 2007

Nakladatel

University of Pavol Jozef Šafárik

Místo

High Tatras

ISBN

978-80-7097-688-3

Kniha

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

Strany od

178

Strany do

185

Strany počet

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