2005
On language inequalities XK ⊆ LX
KUNC, MichalZákladní údaje
Originální název
On language inequalities XK ⊆ LX
Název česky
O jazykových nerovnicích XK ⊆ LX
Autoři
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
Označené pro přenos do RIV
Ano
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
Změněno: 24. 6. 2009 14:50, doc. Mgr. Michal Kunc, Ph.D.
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 |
|