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	2007
Type	Article in Periodical
Magazine / Source	Theory of Computing Systems
MU Faculty or unit	Faculty of Science
Citation
web	http://dx.doi.org/10.1007/s00224-006-1321-z
Field	General mathematics
Keywords	Commutation of languages; Language equation; Regular language; Recursively enumerable language; Minsky machine
Description	We 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 and their physical applications