Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F21%3APU135484" target="_blank" >RIV/00216305:26230/21:PU135484 - isvavai.cz</a>

Result on the web

<a href="https://www.fit.vut.cz/research/publication/11559/" target="_blank" >https://www.fit.vut.cz/research/publication/11559/</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3233/FI-2021-2028" target="_blank" >10.3233/FI-2021-2028</a>

Result language

angličtina

Original language name

Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete

Original language description

This paper investigates the reduction of scattered context grammars with respect to the number of non-context-free productions.  It proves that every recursively enumerable language is generated by a scattered context grammar that has no more than one non-context-free production. An open problem is formulated.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

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

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2021

Confidentiality

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

Name of the periodical

Fundamenta Informaticae

ISSN

0169-2968

e-ISSN

1875-8681

Volume of the periodical

179

Issue of the periodical within the volume

4

Country of publishing house

PL - POLAND

Number of pages

24

Pages from-to

361-384

UT code for WoS article

000651794800003

EID of the result in the Scopus database

2-s2.0-85106764278