Publication details

The power of commuting with finite sets of words

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.

More info