Informace o publikaci
On the Descriptional Complexity of Scattered Context Grammars
| Název česky | O popisné složitosti gramatik s rozptýleným kontextem |
|---|---|
| Autoři | |
| Rok publikování | 2009 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Theoretical Computer Science |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://dx.doi.org/10.1016/j.tcs.2008.10.017 |
| Klíčová slova | scattered context grammar; descriptional complexity |
| Popis | V článku je dokázáno, že každý rekurzívně spočetný jazyk je generovaný gramatikou s rozptýleným kontextem s nejvýše čtyřmi neterminály a třemi pravidly, která nejsou bezkontextová. V závěru je rovněž podán přehled výsledků a otevřených problémů z této problematiky. |