MASOPUST, Tomáš. Descriptional Complexity of Multi-Parallel Grammars. Information Processing Letters. Elsevier, 2008, roč. 108, č. 2, s. 68-70. ISSN 0020-0190.
Další formáty:   BibTeX LaTeX RIS
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 MASOPUST, Tomáš.
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í
WWW URL
Impakt faktor Impact factor: 0.706
Organizační jednotka Fakulta informatiky
UT WoS 000259435800005
Klíčová slova anglicky formal languages, multi-parallel grammars, descriptional complexity
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: doc. RNDr. Tomáš Masopust, Ph.D., DSc., učo 4030. Změněno: 29. 6. 2009 15:20.
Anotace
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.
Anotace č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.
VytisknoutZobrazeno: 12. 6. 2024 06:23