Result 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: Marq software s.r.o., 2006. p. 45-52. ISBN: 80-86840-20-4.
Type
conference paper
Language
English
Authors
Masopust Tomáš, doc. RNDr., Ph.D., DIFS (FIT)
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.
Keywords
formal languages, regular languages, linear languages, regular deletion, linear deletion
Published
2006
Pages
45–52
Proceedings
Proceedings of 1st International Workshop WFM'06
Conference
1st International Workshop on Formal Models (WFM'06)
ISBN
80-86840-20-4
Publisher
Marq software s.r.o.
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",
publisher="Marq software s.r.o.",
address="Přerov",
isbn="80-86840-20-4"
}
Research groups
Formal Model Research Group (RG FM)
Departments