D 2006

Closure Properties of Linear Languages under Operations of Linear Deletion

MASOPUST, Tomáš

Základní údaje

Originální název

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í

Název anglicky

Closure Properties of Linear Languages under Operations of Linear Deletion

Autoři

Vydání

Přerov, Proceedings of 1st International Workshop WFM'06, od s. 45-52, 8 s. 2006

Nakladatel

MARQ

Další údaje

Typ výsledku

Stať ve sborníku

Utajení

není předmětem státního či obchodního tajemství

Organizační jednotka

Fakulta informatiky

ISBN

80-86840-20-4

Klíčová slova anglicky

formal languages; regular languages; linear languages; regular deletion; linear deletion

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 18. 12. 2008 21:42, doc. RNDr. Tomáš Masopust, Ph.D., DSc.

Anotace

ORIG CZ

V originále

In this paper, we give constructive proofs that linear languages are closed under operations of regular deletion and that they are not closed under operations of linear deletion. The operations are called random parallel, parallel, sequential, scattered sequential, and multiple scattered sequential deletion. In addition, we prove that every recursively enumerable language can be obtained from a linear language by linear random parallel, parallel, or sequential deletion. In the conclusion, we formulate two open problems.

Česky

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.