Publication Details

Bidirectional Contextual Grammars

TECHET Jiří. Bidirectional Contextual Grammars. In: Proceedings of 1st International Workshop WFM '06. Přerov, 2006, pp. 61-68. ISBN 80-86840-20-4.
Czech title
Obousměrné kontextuální gramatiky
Type
conference paper
Language
english
Authors
Keywords

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

Abstract

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.

Published
2006
Pages
61-68
Proceedings
Proceedings of 1st International Workshop WFM '06
Conference
1st International Workshop on Formal Models (WFM'06), Přerov, CZ
ISBN
80-86840-20-4
Place
Přerov, CZ
BibTeX
@INPROCEEDINGS{FITPUB8044,
   author = "Ji\v{r}\'{i} Techet",
   title = "Bidirectional Contextual Grammars",
   pages = "61--68",
   booktitle = "Proceedings of 1st International Workshop WFM '06",
   year = 2006,
   location = "P\v{r}erov, CZ",
   ISBN = "80-86840-20-4",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8044"
}
Back to top