Publication result detail
Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete
HAVEL, M.; KŘIVKA, Z.; MEDUNA, A.
Original Title
Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete
English Title
Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete
Type
Paper in proceedings (conference paper)
Original 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.
English 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
Key words in English
Scattered context grammars, Size reduction, The number of non-context-free productions, The number of nonterminal symbols, Computational completeness, Descriptional complexity
Authors
HAVEL, M.; KŘIVKA, Z.; MEDUNA, A.
Released
22.07.2025
Publisher
Springer Verlag
Location
Loughborough
ISBN
978-3-031-97099-3
Book
Descriptional Complexity of Formal Systems
Edition
Lecture Notes in Computer Science
ISBN
0302-9743
Periodical
Lecture Notes in Computer Science
Volume
15759
Number
7
State
Federal Republic of Germany
Pages from
123
Pages to
136
Pages count
13
URL
Full text in the Digital Library
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"
}Documents
Responsibility: Ing. Marek Strakoš