Informace o publikaci
Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement
| Autoři | |
|---|---|
| Rok publikování | 2009 |
| Druh | Článek ve sborníku |
| Konference | Proceedings of 11th International Workshop on Descriptional Complexity of Formal Systems |
| Fakulta / Pracoviště MU | |
| Citace | |
| Obor | Informatika |
| Klíčová slova | Scattered context grammars, descriptional complexity, generative power |
| Popis | Nedávno bylo ukázáno, že každý rekurzívně spočetný jazyk lze generovat gramatikou s rozptýleným kontextem s nejvýše třemi neterminály. V této konstrukci však počet současně přepisovaných neterminálů zavisí na mnoha faktorech, jako je kardinalita abecedy generovaného jazyka a struktura daného jazyka vůbec. Tento článek vylepšuje původní konstrukci tak, že v každém kroku derivace se přepíše nejvýše fixní počet symbolů bez ohledu na generovaný jazyk. |