Detail publikace

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: 2006. p. 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
anglicky
Autoři
Masopust Tomáš, doc. RNDr., Ph.D. (CK-SZZ)
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 jsouuzavřeny na operace náhodného paralelního, paralelního, sekvenčního,rozptýlenéhosekvenčního a násobného rozptýleného sekvenčního regulárníhovymazávání. Naproti tomu je zde dokázáno, želineá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 lzezískatpomocí operace náhodného paralelního vymazávání, paralelníhovymazávání, či sekvenčního vymazávání aplikované na vhodné dvalineární jazyky.

Rok
2006
Strany
45–52
Sborník
Proceedings of 1st International Workshop WFM'06
Konference
1. mezinárodní sympozium o formálních modelech (WFM'06), Přerov, CZ
ISBN
80-86840-20-4
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",
  address="Přerov",
  isbn="80-86840-20-4"
}
Nahoru