On Language Inequalities XK is contained in LX

摘要

It is known that for a regular language L and an arbitrary language K the largest solution of the inequality XK is contained in 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 is contained in LX, X is contained in M} and {XK is contained in LX, XP is contained in RX} are not recursively enumerable.