On groups generated by bi-reversible automata: the two-state case over a changing alphabet

Abstract

The notion of an automaton over a changing alphabet $X=(X_i{)}_{i\ge 1}$ is used to define and study automorphism groups of the tree $X^{\ast }$ of finite words over $X$. The concept of bi-reversibility for Mealy-type automata is extended to automata over a changing alphabet. It is proved that a non-abelian free group can be generated by a two-state bi-reversible automaton over a changing alphabet $X=(X_i{)}_{i\ge 1}$ if and only if $X$ is unbounded. The characterization of groups generated by a two-state bi-reversible automaton over the sequence of binary alphabets is established.

References in corpus (3)

• The concept of duality for automata over a changing alphabet and generation of a free group by such automata
• The concept of self-similar automata over a changing alphabet and lamplighter groups generated by such automata
• The classification of abelian groups generated by time-varying automata and by Mealy automata over the binary alphabet