Publication details
The power of commuting with finite sets of words
Authors | |
---|---|
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 | |
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: |