Informace o publikaci
Closure Properties of Linear Languages under Operations of Linear Deletion
| Název česky | Uzávěrová vlastnosti lineárních jazyků na operace lineárního vymazávání |
|---|---|
| Autoři | |
| Rok publikování | 2006 |
| Druh | Článek ve sborníku |
| Konference | Proceedings of 1st International Workshop WFM'06 |
| Fakulta / Pracoviště MU | |
| Citace | |
| Klíčová slova | formal languages; regular languages; linear languages; regular deletion; linear deletion |
| Popis | V práci jsou podány konstruktivní důkazy toho, že lineární jazyky jsou uzavřeny na operace náhodného paralelního, paralelního, sekvenčního, rozptýleného sekvenčního a násobného rozptýleného sekvenčního regulárního vymazávání. Naproti tomu je zde dokázáno, že lineární jazyky nejsou uzavřeny na operace lineárního vymazávání. Přesněji, je ukázáno, že libovolný rekurzívně spočetný jazyk L lze získat pomocí operace náhodného paralelního vymazávání, paralelního vymazávání, či sekvenčního vymazávání aplikované na vhodné dva lineární jazyky. |