J 2008

Descriptional Complexity of Multi-Parallel Grammars

MASOPUST, Tomáš

Základní údaje

Originální název

Descriptional Complexity of Multi-Parallel Grammars

Název česky

Popisná složitost multi-paralelních gramatik

Autoři

Vydání

Information Processing Letters, Elsevier, 2008, 0020-0190

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

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

UT WoS

Klíčová slova anglicky

formal languages, multi-parallel 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

This paper studies the descriptional complexity of multi-parallel grammars with respect to the number of nonterminals and selectors, and the length of these selectors. As a result, it proves that every recursively enumerable language is generated by a multi-parallel grammar with no more than seven nonterminals and four selectors of length five.

Česky

Článek diskutuje popisnou složitost multi-paralelních gramatik s ohledem k počtu neterminálů, selektorů a délce selektorů. Dokazuje, že libovolný rekurzivně spočetný jazyk lze generovat multi-paralelní gramatikou s nejvýše sedmi neterminály a čtyřmi selektory délky pět.