Automaton semigroups: the two-state case

A Mealy automaton is a deterministic, complete, letter-by-letter transducer, with same input and output alphabet. We can consider the semigroup generated by the functions on words induced by its states. We prove that semigroups generated by reversible two-state Mealy automata have remarkable growth properties: they are either finite or free. We give an effective procedure to decide finiteness or freeness of such semigroups when the generating automaton is also invertible.

Authors

• Inès Klimann

Keywords

No keywords are indexed for this paper.