Infinite automaton semigroups and groups have infinite orbits

JOURNAL OF ALGEBRA

卷:553

Article

D'Angeli, Daniele¹  Francoeur, Dominik²  Rodaro, Emanuele³  Waechter, Jan Philipp⁴ 

[1] Univ Niccolo Cusano, Via Don Gnocchi 3, I-00166 Rome, Italy

[2] Univ Geneva, Sect Math, 2-4 Rue Lievre, CH-1211 Geneva 4, Switzerland

[3] Politecn Milan, Dept Math, Pzza Leonardo 32, I-20133 Milan, Italy

[4] Univ Stuttgart, Inst Formale Methoden Informat FMI, Univ Str 38, D-70569 Stuttgart, Germany

关键词: Automaton groups;    Automaton semigroups;    Orbits;    Schreier graphs;    Orbital graphs;    Self-similar;   

DOI  :  10.1016/j.jalgebra.2020.02.014

来源: Elsevier

【 摘 要 】

We show that an automaton group or semigroup is infinite if and only if it admits an omega-word (i.e. a right-infinite word) with an infinite orbit, which solves an open problem communicated to us by I. V. Bondarenko. In fact, we prove a generalization of this result, which can be applied to show that finitely generated subgroups and subsemigroups as well as principal left ideals of automaton semigroups are infinite if and only if there is an omega-word with an infinite orbit under their action. The proof also shows some interesting connections between the automaton semigroup and its dual. Finally, our result is interesting from an algorithmic perspective as it allows for a re-formulation of the finiteness problem for automaton groups and semigroups. (C) 2020 Elsevier Inc. All rights reserved.

【 授权许可】

Free