Detail publikace

Bidirectional Contextual Grammars

TECHET, J.

Originální název

Bidirectional Contextual Grammars

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

angličtina

Originální abstrakt

The present paper introduces and discusses bidirectional contextual grammars as a straightforward generalization of externally generating contextual grammars without choice. In essence, besides ordinary derivation steps, the bidirectional contextual grammars can also make reduction steps, which shorten the rewritten strings. This paper demonstrates that these grammars characterize the family of recursively enumerable languages. In fact, this characterization holds even in terms of one-turn bidirectional contextual grammars, which can change derivations steps to reduction steps during the generation process no more than once.

Klíčová slova

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

Autoři

TECHET, J.

Rok RIV

2006

Vydáno

26. 4. 2006

Místo

Přerov

ISBN

80-86840-20-4

Kniha

Proceedings of 1st International Workshop WFM '06

Strany od

61

Strany do

68

Strany počet

8

BibTex

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