Random Context and Programmed Grammars of Finite Index Have The Same Generative Power

Czech title

Gramatiky s náhodným kontextem a programované gramatiky konečného indexu mají stejnou mocnost

Type

conference paper

Language

english

Authors

Křivka Zbyněk, Ing., Ph.D. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)

Keywords

random context grammars, permitting grammars, programmed grammars, finite index, generative power

Abstract

The question of whether for every programmed grammar of index k, there is an equivalent a random context grammar in which every production has no forbidding context represents an open problem in the formal language theory. This paper solves this problem by establishing this equivalence.

Annotation

The question of whether for every programmed grammar of index k, there is an equivalent a random context grammar in which every production has no forbidding context represents an open problem in the formal language theory. This paper solves this problem by establishing this equivalence.

Published

2005

Pages

67-72

Proceedings

Proceedings of 8th International Conference ISIM'05 Information Systems Implementation and Modelling

Series

1st edition

Conference

8th International Conference on Information Systems Implementation and Modelling, Hradec nad Moravicí, CZ

ISBN

80-86840-09-3

Place

Ostrava, CZ

BibTeX

@INPROCEEDINGS{FITPUB7727,
   author = "Zbyn\v{e}k K\v{r}ivka and Alexander Meduna",
   title = "Random Context and Programmed Grammars of Finite Index Have The Same Generative Power",
   pages = "67--72",
   booktitle = "Proceedings of 8th International Conference ISIM'05 Information Systems Implementation and Modelling",
   series = "1st edition",
   year = 2005,
   location = "Ostrava, CZ",
   ISBN = "80-86840-09-3",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7727"
}