×

zbMATH — the first resource for mathematics

The power of commuting with finite sets of words. (English) Zbl 1121.68065
Summary: 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.

MSC:
68Q45 Formal languages and automata
68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: DOI