Detail publikačního výsledku

Bidirectional Contextual Grammars

TECHET, J.

Originální název

Bidirectional Contextual Grammars

Anglický název

Bidirectional Contextual Grammars

Druh

Stať ve sborníku mimo WoS a Scopus

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

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

Klíčová slova v angličtině

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

Autoři

TECHET, J.

Vydáno

26.04.2006

Nakladatel

Marq software s.r.o.

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",
  publisher="Marq software s.r.o.",
  address="Přerov",
  isbn="80-86840-20-4"
}