On language inequalities XK ⊆ LX
| Název česky | O jazykových nerovnicích XK ⊆ LX |
|---|---|
| Autoři | |
| Rok publikování | 2005 |
| Druh | Článek ve sborníku |
| Konference | Developments in Language Theory: 9th International Conference, DLT 2005, Palermo, Italy, July 4-8, 2005. Proceedings |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://www.springerlink.com/link.asp?id=qdg18xkthkj0rn0g |
| Obor | Obecná matematika |
| Klíčová slova | Language inequality; Regular language; Recursively enumerable language; Minsky machine |
| Popis | 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á. |
| Související projekty: |