Publication Details

Closure Properties of Linear Languages under Operations of Linear Deletion

MASOPUST, T. Closure Properties of Linear Languages under Operations of Linear Deletion. Proceedings of the 12th Conference and Competition STUDENT EEICT 2006 Volume 4. Brno: Faculty of Information Technology BUT, 2006. p. 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
Keywords

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

Abstract

In this paper, we give constructive proofs that linear languagesare closed under operations of regular deletion and that they are notclosed under operations of linear deletion. The operations are calledrandom parallel, parallel, sequential, scattered sequential, andmultiple scattered sequential deletion.
In addition, we prove that every recursively enumerable languagecan be obtained from a linear language by linear random parallel,parallel, or sequential deletion. In the conclusion, we formulate twoopen 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
BibTeX
@inproceedings{BUT192596,
  author="Tomáš {Masopust}",
  title="Closure Properties of Linear Languages under Operations of Linear Deletion",
  booktitle="Proceedings of the 12th Conference and Competition STUDENT EEICT 2006 Volume 4",
  year="2006",
  pages="390--394",
  publisher="Faculty of Information Technology BUT",
  address="Brno",
  isbn="80-214-3163-6"
}
Back to top