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

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2025

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Descriptional Complexity of Formal Systems

ISBN

978-3-031-97099-3

ISSN

0302-9743

e-ISSN

—

Number of pages

13

Pages from-to

123-136

Publisher name

Springer Verlag

Place of publication

Loughborough

Event location

Loughborough University, UK

Event date

Jul 22, 2025

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

001552192300013