Detail publikace
Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete
HAVEL, M. KŘIVKA, Z. MEDUNA, A.
Originální název
Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete
Typ
článek ve sborníku ve WoS nebo Scopus
Jazyk
angličtina
Originální 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
Autoři
HAVEL, M.; KŘIVKA, Z.; MEDUNA, A.
Vydáno
22. 7. 2025
Nakladatel
Springer Verlag
Místo
Loughborough
ISBN
978-3-031-97099-3
Kniha
Descriptional Complexity of Formal Systems
Edice
Lecture Notes in Computer Science
ISSN
0302-9743
Periodikum
Lecture Notes in Computer Science
Ročník
15759
Číslo
7
Stát
Spolková republika Německo
Strany od
123
Strany do
136
Strany počet
13
URL
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"
}Dokumenty
Odpovědnost: Ing. Marek Strakoš