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

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F26%3A0198282" target="_blank" >RIV/00216305:26230/26:0198282 - isvavai.cz</a>
Výsledek na webu
<a href="https://link.springer.com/book/10.1007/978-3-031-97100-6" target="_blank" >https://link.springer.com/book/10.1007/978-3-031-97100-6</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-031-97100-6_9" target="_blank" >10.1007/978-3-031-97100-6_9</a>

Jazyk výsledku
angličtina
Název v původním jazyce
Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Scattered Context Grammars with One Non-Context-Free Production and Six Nonterminals Are Computationally Complete
Popis výsledku anglicky
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.

Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Rok uplatnění
2025
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)