Detail výsledku

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.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Masopust Tomáš, doc. RNDr., Ph.D., UIFS (FIT)
Abstrakt

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.

Klíčová slova

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

Rok
2006
Strany
45–52
Sborník
Proceedings of 1st International Workshop WFM'06
Konference
1st International Workshop on Formal Models (WFM'06)
ISBN
80-86840-20-4
Vydavatel
Marq software s.r.o.
Místo
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"
}
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru