Detail výsledku

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. Proceedings of 8th International Conference ISIM'05 Information Systems Implementation and Modelling. 1st edition. Ostrava: Marq software s.r.o., 2005. p. 67-72. ISBN: 80-86840-09-3.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Křivka Zbyněk, Ing., Ph.D., UIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
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

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
ISBN
80-86840-09-3
Vydavatel
Marq software s.r.o.
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",
  publisher="Marq software s.r.o.",
  address="Ostrava",
  isbn="80-86840-09-3"
}
Projekty
Optimally Integrated Models of Modern Information Technologies, GAČR, Standardní projekty, GA201/04/0441, zahájení: 2004-01-01, ukončení: 2006-12-31, ukončen
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru