We show that an automaton group or semigroup is infinite if and only if it admits an ω-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 ω-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.

Infinite automaton semigroups and groups have infinite orbits

D'Angeli D.;Rodaro E.;
2020

Abstract

We show that an automaton group or semigroup is infinite if and only if it admits an ω-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 ω-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.
File in questo prodotto:
File Dimensione Formato  
Infinite orbit infinite (semi)group.pdf

Accesso riservato

: Publisher’s version
Dimensione 400.71 kB
Formato Adobe PDF
400.71 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11311/1141861
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact