Informace o publikaci
Descriptional Complexity of Multi-Parallel Grammars
| Název česky | Popisná složitost multi-paralelních gramatik |
|---|---|
| Autoři | |
| Rok publikování | 2008 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Information Processing Letters |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://dx.doi.org/10.1016/j.ipl.2008.04.002 |
| Klíčová slova | formal languages, multi-parallel grammars, descriptional complexity |
| Popis | Č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. |