Publication result detail

Bidirectional Contextual Grammars

TECHET, J.

Original Title

Bidirectional Contextual Grammars

English Title

Bidirectional Contextual Grammars

Type

Paper in proceedings outside WoS and Scopus

Original Abstract

The present paper introduces and discusses bidirectional contextualgrammars as a straightforward generalization of externally generatingcontextual grammars without choice. In essence, besides ordinaryderivation steps, the bidirectional contextual grammars can also makereduction steps, which shorten the rewritten strings. This paperdemonstrates that these grammars characterize the family of recursivelyenumerable languages. In fact, this characterization holds even interms of one-turn bidirectional contextual grammars, which can changederivations steps to reduction steps during the generation process nomore than once.

English abstract

The present paper introduces and discusses bidirectional contextualgrammars as a straightforward generalization of externally generatingcontextual grammars without choice. In essence, besides ordinaryderivation steps, the bidirectional contextual grammars can also makereduction steps, which shorten the rewritten strings. This paperdemonstrates that these grammars characterize the family of recursivelyenumerable languages. In fact, this characterization holds even interms of one-turn bidirectional contextual grammars, which can changederivations steps to reduction steps during the generation process nomore than once.

Keywords

contextual grammars, bidirectional grammars, generative power, recursively enumerable languages

Key words in English

contextual grammars, bidirectional grammars, generative power, recursively enumerable languages

Authors

TECHET, J.

Released

26.04.2006

Publisher

Marq software s.r.o.

Location

Přerov

ISBN

80-86840-20-4

Book

Proceedings of 1st International Workshop WFM '06

Pages from

61

Pages to

68

Pages count

8

BibTex

@inproceedings{BUT25902,
  author="Jiří {Techet}",
  title="Bidirectional Contextual Grammars",
  booktitle="Proceedings of 1st International Workshop WFM '06",
  year="2006",
  pages="61--68",
  publisher="Marq software s.r.o.",
  address="Přerov",
  isbn="80-86840-20-4"
}