Result Details

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.
Type
conference paper
Language
English
Authors
Havel Martin, Ing., DIFS (FIT)
Křivka Zbyněk, Ing., Ph.D., DIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Abstract

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.

Keywords

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

URL
Published
2025
Pages
123–136
Journal
Lecture Notes in Computer Science, vol. 15759, no. 7, ISSN 0302-9743
Proceedings
Descriptional Complexity of Formal Systems
Series
Lecture Notes in Computer Science
Conference
26th International Conference on Descriptional Complexity of Formal Systems
ISBN
978-3-031-97099-3
Publisher
Springer Verlag
Place
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"
}
Files
Projects
Chytré informační technologie pro odolnou společnost, BUT, Vnitřní projekty VUT, FIT-S-23-8209, start: 2023-03-01, end: 2026-02-28, running
Research groups
Formal Model Research Group (RG FM)
Departments
Department of Information Systems (DIFS)
Back to top