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 1st International Workshop WFM'06. Přerov: 2006. p. 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

Masopust Tomáš, doc. RNDr., Ph.D. (CM-SFE)

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

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

BibTeX

@inproceedings{BUT192593,
  author="Tomáš {Masopust}",
  title="Closure Properties of Linear Languages under Operations of Linear Deletion",
  booktitle="Proceedings of 1st International Workshop WFM'06",
  year="2006",
  pages="45--52",
  address="Přerov",
  isbn="80-86840-20-4"
}