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
Keywords:
Conway’s conjecture
Full Text: