Informace o publikaci
Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof
| Název česky | Nejlevější derivace nevymazávacích gramatik s rozptýleným kontextem: nový důkaz |
|---|---|
| Autoři | |
| Rok publikování | 2008 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Discrete Mathematics & Theoretical Computer Science |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/issue/view/93 |
| Klíčová slova | formal languages, propagating scattered context grammars, leftmost derivations, generative power |
| Popis | V roce 1973 V. Virkkunen dokázal, že nevymazávací gramatiky s rozptýleným kontextem, které používají nejlevější derivace, jsou stejně silné jako kontextové gramatiky. Tento článek přináší významně zjednodušený důkaz tohoto výsledku. |