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 the 12th Conference and Competition STUDENT EEICT 2006 Volume 4. Brno: Faculty of Information Technology BUT, 2006, pp. 390-394. ISBN 80-214-3163-6.

Czech title

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

Type

conference paper

Language

english

Authors

Masopust Tomáš, RNDr., Ph.D. (DIFS FIT BUT)

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

390-394

Proceedings

Proceedings of the 12th Conference and Competition STUDENT EEICT 2006 Volume 4

Conference

Student EEICT 2006, Brno, CZ

ISBN

80-214-3163-6

Publisher

Faculty of Information Technology BUT

Place

Brno, CZ

BibTeX

@INPROCEEDINGS{FITPUB8052,
   author = "Tom\'{a}\v{s} Masopust",
   title = "Closure Properties of Linear Languages under Operations of Linear Deletion",
   pages = "390--394",
   booktitle = "Proceedings of the 12th Conference and Competition STUDENT EEICT 2006 Volume 4",
   year = 2006,
   location = "Brno, CZ",
   publisher = "Faculty of Information Technology BUT",
   ISBN = "80-214-3163-6",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8052"
}