Publication Details

Closure Properties of Linear Languages under Operations of Linear Deletion

MASOPUST Tomáš. Closure Properties of Linear Languages under Operations of Linear Deletion. In: Proceedings of 1st International Workshop WFM'06. Přerov, 2006, pp. 45-52. ISBN 80-86840-20-4.
Czech title
Uzávěrová vlastnosti lineárních jazyků na operace lineárního vymazávání
Type
conference paper
Language
english
Authors
Keywords

formal languages, regular languages, linear languages, regular deletion, linear deletion

Abstract

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.

Published
2006
Pages
45-52
Proceedings
Proceedings of 1st International Workshop WFM'06
Conference
1st International Workshop on Formal Models (WFM'06), Přerov, CZ
ISBN
80-86840-20-4
Place
Přerov, CZ
BibTeX
@INPROCEEDINGS{FITPUB8047,
   author = "Tom\'{a}\v{s} Masopust",
   title = "Closure Properties of Linear Languages under Operations of Linear Deletion",
   pages = "45--52",
   booktitle = "Proceedings of 1st International Workshop WFM'06",
   year = 2006,
   location = "P\v{r}erov, CZ",
   ISBN = "80-86840-20-4",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8047"
}
Back to top