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: |