Publication 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. p. 123-136. ISBN: 978-3-031-97099-3. ISSN: 0302-9743.
Czech title
Gramatiky s rozptýleným kontextem a jedním nekontextovým pravidel a šesti neterminály jsou výpočetně úplné
Type
conference paper
Language
English
Authors
Havel Martin, Ing. (DIFS)
Křivka Zbyněk, Ing., Ph.D. (DIFS)
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
URL
Keywords

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

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.

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, Loughborough University, UK, GB
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
Back to top