The power of commuting with finite sets of words

Warning

This publication doesn't include Faculty of Arts. 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:

You are running an old browser version. We recommend updating your browser to its latest version.