Detail publikace

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

Originální název

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

Anglický název

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

Jazyk

en

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.

Anglický 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.

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