D 2006

Closure Properties of Linear Languages under Operations of Linear Deletion

MASOPUST, Tomáš

Basic information

Original name

Closure Properties of Linear Languages under Operations of Linear Deletion

Name in Czech

Uzávěrová vlastnosti lineárních jazyků na operace lineárního vymazávání

Name (in English)

Closure Properties of Linear Languages under Operations of Linear Deletion

Authors

Edition

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

Publisher

MARQ

Other information

Type of outcome

Stať ve sborníku

Confidentiality degree

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

Organization unit

Faculty of Informatics

ISBN

80-86840-20-4

Keywords in English

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

Tags

Tags

International impact, Reviewed
Změněno: 18/12/2008 21:42, doc. RNDr. Tomáš Masopust, Ph.D., DSc.

Abstract

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.

In Czech

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.