J 2008

On Descriptional Complexity of Partially Parallel Grammars

MASOPUST, Tomáš a Alexander MEDUNA

Základní údaje

Originální název

On Descriptional Complexity of Partially Parallel Grammars

Název česky

O popisné složitosti částečně paralelních gramatik

Autoři

MASOPUST, Tomáš a Alexander MEDUNA

Vydání

Fundamenta Informaticae, Polsko, IOS Press, Nizozemí, 2008, 0169-2968

Další údaje

Typ výsledku

Článek v odborném periodiku

Utajení

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

Odkazy

Impakt faktor

Impact factor: 0.715

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

UT WoS

Klíčová slova anglicky

formal languages, scattered context grammars, multisequential grammars, multicontinuous grammars, descriptional complexity

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 29. 6. 2009 15:20, doc. RNDr. Tomáš Masopust, Ph.D., DSc.

Anotace

ORIG CZ

V originále

In this paper, we improve some well-known results concerning descriptional complexity of partially parallel grammars. Specifically, we prove that every recursively enumerable language is generated by a four-nonterminal scattered context grammar with no more than four non-context-free productions, by a two-nonterminal multisequential grammar with no more than two selectors, or by a three-nonterminal multicontinuous grammar with no more than two selectors.

Česky

Článek upravuje některé výsledky týkající se popisné složitosti částečně paralelních gramatik. Ukazuje, že každý rekurzívně spočetný jazyk je generovaný gramatikou s rozptýleným kontextem se čtyřmi neterminály a ne více jak čtyřmi pravidly, která nejsou bezkontextová, multisekvenční gramatikou mající dva neterminály a dva selektory a multicontinuous gramatikou mající tři neterminály a dva selektory.