The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable

Ines Klimann (1)

1 Automates et Applications

We prove that a semigroup generated by a reversible two-state Mealy automaton is either finite or free of rank 2. This fact leads to the decidability of finiteness for groups generated by two-state or two-letter invertible-reversible Mealy automata and to the decidability of freeness for semigroups generated by two-state invertible-reversible Mealy automata.

Mots clés: Mealy automata; automaton semigroups; decidability of finiteness; decidability of freeness; Nerode equivalence

Domaines: Théorie et langage formel [cs.FL]; Théorie des groupes [math.GR]

Ines Klimann. The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable. 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Feb 2013, Kiel, Germany. pp.502--513, ⟨10.4230/LIPIcs.STACS.2013.502⟩. ⟨hal-00875177⟩