Detail výsledku

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. Loughborough: Springer Verlag, 2025. no. 7, p. 123-136. ISBN: 978-3-031-97099-3.
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Havel Martin, Ing., UIFS (FIT)
Křivka Zbyněk, Ing., Ph.D., UIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Abstrakt

The present paper explains how to reduce the size of scattered context grammars
with respect to the number of both non-contextfree productions and nonterminals.
It proves that every recursively enumerable language is generated by
a six-nonterminal scattered context grammar with a single non-context-free
production. Open problems are proposed.

Klíčová slova

Scattered context grammars, Size reduction, The number of non-context-free
productions, The number of nonterminal symbols, Computational completeness,
Descriptional complexity

URL
Rok
2025
Strany
123–136
Časopis
Lecture Notes in Computer Science, roč. 15759, č. 7, ISSN
Sborník
Descriptional Complexity of Formal Systems
Konference
26th International Conference on Descriptional Complexity of Formal Systems
ISBN
978-3-031-97099-3
Vydavatel
Springer Verlag
Místo
Loughborough
DOI
10.1007/978-3-031-97100-6_9
UT WoS
001552192300013
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",
  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
Projekty
Chytré informační technologie pro odolnou společnost, VUT, Vnitřní projekty VUT, FIT-S-23-8209, zahájení: 2023-03-01, ukončení: 2026-02-28, ukončen
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru