KUNC, Michal. On language inequalities XK ⊆ LX. In Developments in Language Theory: 9th International Conference, DLT 2005, Palermo, Italy, July 4-8, 2005. Proceedings. Berlin: Springer-Verlag, 2005, p. 327-337. ISBN 3-540-26546-5. |
Other formats:
BibTeX
LaTeX
RIS
@inproceedings{573394, author = {Kunc, Michal}, address = {Berlin}, booktitle = {Developments in Language Theory: 9th International Conference, DLT 2005, Palermo, Italy, July 4-8, 2005. Proceedings}, keywords = {Language inequality; Regular language; Recursively enumerable language; Minsky machine}, language = {eng}, location = {Berlin}, isbn = {3-540-26546-5}, pages = {327-337}, publisher = {Springer-Verlag}, title = {On language inequalities XK ⊆ LX}, url = {http://www.springerlink.com/link.asp?id=qdg18xkthkj0rn0g}, year = {2005} }
TY - JOUR ID - 573394 AU - Kunc, Michal PY - 2005 TI - On language inequalities XK ⊆ LX PB - Springer-Verlag CY - Berlin SN - 3540265465 KW - Language inequality KW - Regular language KW - Recursively enumerable language KW - Minsky machine UR - http://www.springerlink.com/link.asp?id=qdg18xkthkj0rn0g N2 - 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. ER -
KUNC, Michal. On language inequalities XK \&{}sube; LX. In \textit{Developments in Language Theory: 9th International Conference, DLT 2005, Palermo, Italy, July 4-8, 2005. Proceedings}. Berlin: Springer-Verlag, 2005, p.~327-337. ISBN~3-540-26546-5.
|