Publication result 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

English Title

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

Type

Paper in proceedings outside WoS and Scopus

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.

English 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

Key words in English

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

Authors

KŘIVKA, Z.; MEDUNA, A.

Released

10.03.2005

Publisher

Marq software s.r.o.

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",
  publisher="Marq software s.r.o.",
  address="Ostrava",
  isbn="80-86840-09-3"
}