J 2010

Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals

MASOPUST, Tomáš

Základní údaje

Originální název

Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals

Autoři

Vydání

Fundamenta Informaticae, Poland, IOS Press, The Netherlands, 2010, 0169-2968

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Impakt faktor

Impact factor: 0.522

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

UT WoS

Klíčová slova anglicky

Scattered context grammars, parallel productions, descriptional complexity, generative power

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 20. 8. 2010 11:41, doc. RNDr. Tomáš Masopust, Ph.D., DSc.

Anotace

V originále

Scattered context grammars with three nonterminals are known to be computationally complete. So far, however, it was an open problem whether the number of parallel productions can be bounded along with three nonterminals. In this paper, we prove that every recursively enumerable language is generated by a scattered context grammar with three nonterminals and five parallel productions, each of which simultaneously rewrites no more than nine nonterminals.