On language inequalities XK ⊆ LX

KUNC, Michal. On language inequalities XK ⊆ LX. In Developments in Language Theory: 9th International Conference, DLT 2005, Palermo, Italy, July 4-8, 2005. Proceedings. Berlin: Springer-Verlag, 2005, s. 327-337. ISBN 3-540-26546-5.

Základní údaje

Originální název

On language inequalities XK ⊆ LX

Název česky

O jazykových nerovnicích XK ⊆ LX

Autoři

KUNC, Michal

Vydání

Berlin, Developments in Language Theory: 9th International Conference, DLT 2005, Palermo, Italy, July 4-8, 2005. Proceedings, s. 327-337, 2005

Nakladatel

Springer-Verlag

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10101 Pure mathematics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Kód RIV

RIV/00216224:14310/05:00025512

Organizační jednotka

Přírodovědecká fakulta

ISBN

3-540-26546-5

Klíčová slova anglicky

Language inequality; Regular language; Recursively enumerable language; Minsky machine

Štítky

Language inequality, Minsky machine, Recursively enumerable language, Regular language

---

Anotace

V originále

It is known that for a regular language L and an arbitrary language K the largest solution of the inequality XK subset LX is regular. Here we show that there exist finite languages K and P and star-free languages L, M and R such that the largest solutions of the systems {XK subset LX, X subset M} and {XK subset LX, XP subset RX} are not recursively enumerable.

Česky

Je známo, že pro regulární jazyk L a libovolný jazyk K je největší řešení nerovnice XK subset LX regulární. V práci ukazujeme, že existují konečné jazyky K a P a star-free jazyky L, M a R takové, že největší řešení systémů {XK subset LX, X subset M} a {XK subset LX, XP subset RX} nejsou rekurzívně vyčíslitelná.

---

Návaznosti

MSM0021622409, záměr

Název: Matematické struktury a jejich fyzikální aplikace Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Matematické struktury a jejich fyzikální aplikace