Detail publikace

Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete

HAVEL Martin, KřIVKA Zbyněk a MEDUNA Alexander. Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete. In: Descriptional Complexity of Formal Systems. Lecture Notes in Computer Science, roč. 15759. Loughborough: Springer Verlag, 2025, s. 123-136. ISSN 0302-9743. Dostupné z: https://link.springer.com/book/10.1007/978-3-031-97100-6
Název česky
Gramatiky s rozptýleným kontextem a jedním nekontextovým pravidel a šesti neterminály jsou výpočetně úplné
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Havel Martin, Ing. (UIFS FIT VUT)
Křivka Zbyněk, Ing., Ph.D. (UIFS FIT VUT)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
URL
Klíčová slova

Gramatiky s rozptýleným kontextem, Zmenšení velikosti, Počet nekontextových pravidel, Počet neterminálních symbolů, Výpočetní úplnost, Popisná složitost

Abstrakt

Tento článek vysvětluje, jak redukovat gramatiky s rozptýleným kontextem z hlediska počtu jak nekontextových pravidel, tak i neterminálů. Dokazuje, že každý rekurzivně spočetný jazyk je generován gramatikou s rozptýleným kontextem se šesti neterminály a jediným nekontextovým pravidlem. Jsou navrženy otevřené problémy.

Rok
2025
Strany
123-136
Časopis
Lecture Notes in Computer Science, roč. 15759, č. 7, ISSN 0302-9743
Sborník
Descriptional Complexity of Formal Systems
Řada
Lecture Notes in Computer Science
Konference
26th International Conference on Descriptional Complexity of Formal Systems, Loughborough University, UK, GB
Vydavatel
Springer Verlag
Místo
Loughborough, GB
DOI
10.1007/978-3-031-97100-6
BibTeX 
@INPROCEEDINGS{FITPUB13540,
   author = "Martin Havel and Zbyn\v{e}k K\v{r}ivka and Alexander Meduna",
   title = "Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete",
   pages = "123--136",
   booktitle = "Descriptional Complexity of Formal Systems",
   series = "Lecture Notes in Computer Science",
   journal = "Lecture Notes in Computer Science",
   volume = 15759,
   number = 7,
   year = 2025,
   location = "Loughborough, GB",
   publisher = "Springer Verlag",
   ISSN = "0302-9743",
   doi = "10.1007/978-3-031-97100-6",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/13540"
}
Nahoru