Detail publikace

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. In Proceedings of 8th International Conference ISIM'05 Information Systems Implementation and Modelling. 1st edition. Ostrava: 2005. p. 67-72. ISBN: 80-86840-09-3.
Název česky
Gramatiky s náhodným kontextem a programované gramatiky konečného indexu mají stejnou mocnost
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Klíčová slova

gramatiky s náhodným kontextem, povolující gramatiky, programované gramatiky, konečný index, generativní síla

Abstrakt

Otázka, zda pro každou programovanou gramatiku indexu k existuje ekvivalentní gramatika s náhodným kontextem s pravidly bez zakazujícího kontextu, reprezentuje otevřený problém teorie formálních jazyků. Tento článek řeší tento problém dokázáním takovéto ekvivalence.

Anotace

Otázka, zda pro každou programovanou gramatiku indexu k existuje ekvivalentní gramatika s náhodným kontextem s pravidly bez zakazujícího kontextu, reprezentuje otevřený problém teorie formálních jazyků. Tento článek řeší tento problém dokázáním takovéto ekvivalence.

Rok
2005
Strany
67–72
Sborník
Proceedings of 8th International Conference ISIM'05 Information Systems Implementation and Modelling
Řada
1st edition
ISBN
80-86840-09-3
Místo
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"
}
Nahoru