Publication Details

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

KŘIVKA, Z.; MEDUNA, A. Random Context and Programmed Grammars of Finite Index Have The Same Generative Power. Proceedings of 8th International Conference ISIM'05 Information Systems Implementation and Modelling. 1st edition. Ostrava: 2005. p. 67-72. ISBN: 80-86840-09-3.
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)
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
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
ISBN
80-86840-09-3
Place
Ostrava
BibTeX 
@inproceedings{BUT21455,
  author="Zbyněk {Křivka} and Alexandr {Meduna}",
  title="Random Context and Programmed Grammars of Finite Index Have The Same Generative Power",
  booktitle="Proceedings of 8th International Conference ISIM'05 Information Systems Implementation and Modelling",
  year="2005",
  series="1st edition",
  pages="67--72",
  address="Ostrava",
  isbn="80-86840-09-3"
}
Back to top