On language inequalities XK ⊆ LX
| Authors | |
|---|---|
| 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 | |
| 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: |