Highlights Conference 2013 Conference Abstract
Automaton semigroups: the two-state case
- Inès Klimann
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.