Informace o publikaci
On context-free rewriting with a simple restriction and its computational completeness
| Název česky | O bezkontextovém přepisování s jednoduchým omezením a jeho výpočetní úplnost |
|---|---|
| Autoři | |
| Rok publikování | 2009 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | RAIRO - Theoretical Informatics and Applications |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://dx.doi.org/10.1051/ita/2009002 |
| Klíčová slova | formal languages, context-free grammar, context-free rewriting system, derivation restriction, generative power |
| Popis | Článek diskutuje bezkontextové přepisovací systémy, v nichž existují dvě konečné disjunktní množiny pravidel, a symbol, označovaný jako podmínka aplikovatelnosti, je přiřazen ke každému pravidlu v obou množinách. V jedné množině jsou pravidla, která jsou aplikovatelná pouze tehdy, pokud se k ním přiřazené symboly vyskytuje ve větné formě, zatímco ve druhé množině jsou pravidla, která jsou aplikovatelná pouze tehdy, pokud se k ním přiřazené symboly nevyskytují ve větné formě. Článek demonstruje, že takovéto přepisující systémy jsou výpočetně úplné. V závěru je pak odvozeno několik důsledků. |