Detail publikačního výsledku

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

Paper in proceedings outside WoS and Scopus

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

Key words in English

scattered context grammars, canonical derivations, parses, descriptional complexity

Authors

MEDUNA, A.; TECHET, J.

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

Full text in the Digital Library

http://hdl.handle.net/

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