Detail publikace

Closure Properties of Linear Languages under Operations of Linear Deletion

MASOPUST Tomáš. Closure Properties of Linear Languages under Operations of Linear Deletion. In: Proceedings of 1st International Workshop WFM'06. Přerov: MARQ, 2006, s. 45-52. ISBN 80-86840-20-4.
Název česky
Uzávěrová vlastnosti lineárních jazyků na operace lineárního vymazávání
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Masopust Tomáš, RNDr., Ph.D. (UIFS FIT VUT)
Klíčová slova

formální jazyky, regulární jazyky, lineární jazyky, regulární vymazávání, lineární vymazávání

Abstrakt

V práci jsou podány konstruktivní důkazy toho, že lineární jazyky jsou uzavřeny na operace náhodného paralelního, paralelního, sekvenčního, rozptýleného sekvenčního a násobného rozptýleného sekvenčního regulárního vymazávání. Naproti tomu je zde dokázáno, že lineární jazyky nejsou uzavřeny na operace lineárního vymazávání. Přesněji, je ukázáno, že libovolný rekurzívně spočetný jazyk L lze získat pomocí operace náhodného paralelního vymazávání, paralelního vymazávání, či sekvenčního vymazávání aplikované na vhodné dva lineární jazyky.

Rok
2006
Strany
45-52
Sborník
Proceedings of 1st International Workshop WFM'06
Konference
1st International Workshop on Formal Models (WFM'06), Přerov, CZ
ISBN
80-86840-20-4
Vydavatel
MARQ
Místo
Přerov, CZ
BibTeX 
@INPROCEEDINGS{FITPUB8047,
   author = "Tom\'{a}\v{s} Masopust",
   title = "Closure Properties of Linear Languages under Operations of Linear Deletion",
   pages = "45--52",
   booktitle = "Proceedings of 1st International Workshop WFM'06",
   year = 2006,
   location = "P\v{r}erov, CZ",
   ISBN = "80-86840-20-4",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8047"
}
Nahoru