On language inequalities XK ⊆ LX

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

KUNC Michal

Year of publication 2005
Type Article in Proceedings
Conference Developments in Language Theory: 9th International Conference, DLT 2005, Palermo, Italy, July 4-8, 2005. Proceedings
MU Faculty or unit

Faculty of Science

Citation
Web http://www.springerlink.com/link.asp?id=qdg18xkthkj0rn0g
Field General mathematics
Keywords Language inequality; Regular language; Recursively enumerable language; Minsky machine
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.