Publication Details

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

HAVEL Martin, KřIVKA Zbyněk and MEDUNA Alexander. 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, vol. 15759. Loughborough: Springer Verlag, 2025, pp. 123-136. ISSN 0302-9743. Available from: https://link.springer.com/book/10.1007/978-3-031-97100-6

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 FIT BUT)
Křivka Zbyněk, Ing., Ph.D. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)

URL

https://link.springer.com/book/10.1007/978-3-031-97100-6

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

Publisher

Springer Verlag

Place

Loughborough, GB

DOI

10.1007/978-3-031-97100-6

BibTeX

@INPROCEEDINGS{FITPUB13540,
   author = "Martin Havel and Zbyn\v{e}k K\v{r}ivka and Alexander Meduna",
   title = "Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete",
   pages = "123--136",
   booktitle = "Descriptional Complexity of Formal Systems",
   series = "Lecture Notes in Computer Science",
   journal = "Lecture Notes in Computer Science",
   volume = 15759,
   number = 7,
   year = 2025,
   location = "Loughborough, GB",
   publisher = "Springer Verlag",
   ISSN = "0302-9743",
   doi = "10.1007/978-3-031-97100-6",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/13540"
}