Informace o publikaci
Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars
| Název česky | Dvě omezení snižující sílu zobecněných gramatik s rozptýleným kontextem |
|---|---|
| Autoři | |
| Rok publikování | 2008 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Acta Cybernetica |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://www.inf.u-szeged.hu/actacybernetica/edb/Author/MASOPUST-TOMAS.xml |
| Klíčová slova | scattered context grammar, grammatical generalization, derivation restriction, generative power |
| Popis | Článek zavádí a diskutuje zobecněné gramatiky s rozptýleným kontextem založené na sekvencích pravidel, jejichž levé strany jsou tvořeny řetězci neterminálů místo standardního jednoho neterminálu. Studovány jsou dvě omezení v těchto gramatikách. První omezení vyžaduje, aby se všechny přepisované symboly jakéhokoliv derivačního kroku vyskytovaly v prvních k symbolech prvního souvislého bloku neterminálů. Druhé pak definuje derivace, jejichž jednotlivé větné formy nemají více než k neterminálů. Hlavním výsledkem článku je, že obě omezení vedou ke snížení síly těchto gramatik na sílu bezkontextových gramatik. |