Informace o publikaci
On Descriptional Complexity of Partially Parallel Grammars
| Název česky | O popisné složitosti částečně paralelních gramatik |
|---|---|
| Autoři | |
| Rok publikování | 2008 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Fundamenta Informaticae |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://fi.mimuw.edu.pl/vol87.html |
| Klíčová slova | formal languages, scattered context grammars, multisequential grammars, multicontinuous grammars, descriptional complexity |
| Popis | Č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. |