Detail publikace

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

KŘIVKA, Z., MEDUNA, A.

Originální název

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

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

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

Autoři

KŘIVKA, Z., MEDUNA, A.

Rok RIV

2005

Vydáno

10. 3. 2005

Místo

Ostrava

ISBN

80-86840-09-3

Kniha

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

Edice

1st edition

Strany od

67

Strany do

72

Strany počet

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