The freeness conjecture for two-state reversible Mealy automata
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 -state reversible Mealy automaton generates a semigroup which is either finite or free of rank . This is a structural conjecture about infinite automaton semigroups. The source reports that it was tested and appeared correct for reversible -state Mealy automata with up to 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.