Publication details
The power of commuting with finite sets of words
| Authors | |
|---|---|
| Year of publication | 2007 |
| Type | Article in Periodical |
| Magazine / Source | Theory of Computing Systems |
| MU Faculty or unit | |
| 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: |