The freeness conjecture for two-state reversible Mealy automata

Let a reversible Mealy automaton be a Mealy automaton whose transition maps are permutations, and let the semigroup generated by an automaton be the semigroup generated by its states under composition. Two-state freeness conjecture. Every 22-state reversible Mealy automaton generates a semigroup which is either finite or free of rank 22. This is a structural conjecture about infinite automaton semigroups. The source reports that it was tested and appeared correct for reversible 22-state Mealy automata with up to 66 letters.

Sources & referencesView supporting material

Primary source

Ines Klimann, Jean Mairesse and Matthieu Picantin, “Implementing Computations in Automaton (Semi)groups”, arXiv:1310.4856 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.