MASOPUST, Tomáš a Alexander MEDUNA. On Descriptional Complexity of Partially Parallel Grammars. Fundamenta Informaticae. Polsko: IOS Press, Nizozemí, 2008, roč. 87, č. 3, s. 407-415. ISSN 0169-2968.
Další formáty:   BibTeX LaTeX RIS
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í
WWW URL
Impakt faktor Impact factor: 0.715
Organizační jednotka Fakulta informatiky
UT WoS 000262368900006
Klíčová slova anglicky formal languages, scattered context grammars, multisequential grammars, multicontinuous 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
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.
Anotace č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.
VytisknoutZobrazeno: 12. 6. 2024 01:56