The power of commuting with finite sets of words

Warning

This publication doesn't include Institute of Computer Science. 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	STACS 2005: 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005. Proceedings
MU Faculty or unit	Faculty of Science
Citation
Web	http://www.springerlink.com/link.asp?id=72ul1qvmpr3utqyp
Field	General mathematics
Keywords	Commutation of languages; Language equation; Regular language; Recursively enumerable language; Minsky machine
Description	We show that one can construct a finite language L such that the largest language commuting with L is not recursively enumerable. This gives a negative answer to the question raised by Conway in 1971 and also strongly disproves Conway's conjecture on context-freeness of maximal solutions of systems of semi-linear inequalities.
Related projects:	Mathematical structures of algebra and geometry