Detail publikace

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

KŘIVKA Zbyněk a MEDUNA Alexander. 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: MARQ, 2005, s. 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
angličtina
Autoři
Křivka Zbyněk, Ing., Ph.D. (UIFS FIT VUT)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
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
Konference
8th International Conference on Information Systems Implementation and Modelling, Hradec nad Moravicí, CZ
ISBN
80-86840-09-3
Vydavatel
MARQ
Místo
Ostrava, CZ
BibTeX 
@INPROCEEDINGS{FITPUB7727,
   author = "Zbyn\v{e}k K\v{r}ivka and Alexander Meduna",
   title = "Random Context and Programmed Grammars of Finite Index Have The Same Generative Power",
   pages = "67--72",
   booktitle = "Proceedings of 8th International Conference ISIM'05 Information Systems Implementation and Modelling",
   series = "1st edition",
   year = 2005,
   location = "Ostrava, CZ",
   ISBN = "80-86840-09-3",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7727"
}
Nahoru