Publication detail

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

KŘIVKA, Z., MEDUNA, A.

Original Title

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

Type

conference paper

Language

English

Original 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.

Keywords

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

Authors

KŘIVKA, Z., MEDUNA, A.

RIV year

2005

Released

10. 3. 2005

Location

Ostrava

ISBN

80-86840-09-3

Book

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

Edition

1st edition

Pages from

67

Pages to

72

Pages count

6

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"
}