Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{799989,
author = {Masopust, Tomáš},
address = {Přerov},
booktitle = {Proceedings of 1st International Workshop WFM'06},
keywords = {formal languages; regular languages; linear languages; regular deletion; linear deletion},
location = {Přerov},
isbn = {80-86840-20-4},
pages = {45-52},
publisher = {MARQ},
title = {Closure Properties of Linear Languages under Operations of Linear Deletion},
year = {2006}
}
TY - JOUR
ID - 799989
AU - Masopust, Tomáš
PY - 2006
TI - Closure Properties of Linear Languages under Operations of Linear Deletion
PB - MARQ
CY - Přerov
SN - 8086840204
KW - formal languages
KW - regular languages
KW - linear languages
KW - regular deletion
KW - linear deletion
N2 - 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.
ER -
MASOPUST, Tomáš. Closure Properties of Linear Languages under Operations of Linear Deletion. In \textit{Proceedings of 1st International Workshop WFM'06}. Přerov: MARQ, 2006, s.~45-52. ISBN~80-86840-20-4.
|
