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 the 12th Conference and Competition STUDENT EEICT 2006 Volume 4. Brno: Fakulta informačních technologií VUT v Brně, 2006, s. 390-394. ISBN 80-214-3163-6.
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
390-394
Sborník
Proceedings of the 12th Conference and Competition STUDENT EEICT 2006 Volume 4
Konference
Student EEICT 2006, Brno, CZ
ISBN
80-214-3163-6
Vydavatel
Fakulta informačních technologií VUT v Brně
Místo
Brno, CZ
BibTeX 
@INPROCEEDINGS{FITPUB8052,
   author = "Tom\'{a}\v{s} Masopust",
   title = "Closure Properties of Linear Languages under Operations of Linear Deletion",
   pages = "390--394",
   booktitle = "Proceedings of the 12th Conference and Competition STUDENT EEICT 2006 Volume 4",
   year = 2006,
   location = "Brno, CZ",
   publisher = "Faculty of Information Technology BUT",
   ISBN = "80-214-3163-6",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8052"
}
Nahoru