Informace o publikaci
Cooperating Distributed Grammar Systems with Permitting Grammars as Components
| Autoři | |
|---|---|
| Rok publikování | 2009 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Romanian Journal of Information Science and Technology |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://www.imt.ro/romjist/ |
| Obor | Informatika |
| Klíčová slova | Cooperating distributed grammar system; permitting grammars; left-permitting grammars; generative power. |
| Popis | Článek studuje kooperující distribuované gramatické systémy pracující v terminálním módu, kde komponenty jsou varianty povolujících gramatik. Ukazuje, že ačkoliv je třída povolujících jazyků ostře vnořena do třídy random context jazyků, jsou třídy random context jazyků a jazyků generovaných povolujícími kooperujícími distribuovanými gramatickými systémy shodné. Navíc, pokud jsou komponenty tzv. levě-povolující gramatiky, pak kooperující distribuované gramatické systémy s terminálním módem charakterizují třídu kontextových jazyků, či jazyků typu 0, pokud připustíme vymazávací pravidla. Článek dále uvádí výsledky z popisné složitosti, zejména to, že počet komponent může být ohraničen a v případě levě-povolujících gramatik s vymazávacími pravidly dokonce společně s počtem neterminálů. |