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. Lecture Notes in Computer Science. Loughborough: Springer Verlag, 2025. no. 7, p. 123-136. ISBN: 978-3-031-97099-3. ISSN: 0302-9743.
Typ
článek ve sborníku konference
Jazyk
anglicky
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 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
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
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, řešení
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru