Detail publikace

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

HAVEL, M.; KŘIVKA, Z.; MEDUNA, A. 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. Lecture Notes in Computer Science. Loughborough: Springer Verlag, 2025. p. 123-136. ISBN: 978-3-031-97099-3. ISSN: 0302-9743.
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
anglicky
Autoři
Havel Martin, Ing. (UIFS)
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
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
Popisná složitost formálních systémů, Loughborough University, UK, GB
ISBN
978-3-031-97099-3
Vydavatel
Springer Verlag
Místo
Loughborough
DOI
10.1007/978-3-031-97100-6_9
EID Scopus
2-s2.0-105010821461
BibTeX 
@inproceedings{BUT198282,
  author="Martin {Havel} and Zbyněk {Křivka} and Alexandr {Meduna}",
  title="Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete",
  booktitle="Descriptional Complexity of Formal Systems",
  year="2025",
  series="Lecture Notes in Computer Science",
  journal="Lecture Notes in Computer Science",
  volume="15759",
  number="7",
  pages="123--136",
  publisher="Springer Verlag",
  address="Loughborough",
  doi="10.1007/978-3-031-97100-6\{_}9",
  isbn="978-3-031-97099-3",
  issn="0302-9743",
  url="https://link.springer.com/book/10.1007/978-3-031-97100-6"
}
Soubory
Nahoru