2019/03/31 by Daniele D'Angeli, Daniele D’Angeli, Dominik Francoeur +2 · 5 citations
Computer Science · Mathematics · #Advanced Operator Algebra Research #Automaton #Computer science #Discrete mathematics #Generalization #Geometric and Algebraic Topology #Group (periodic table) #Mathematical analysis #Mathematics #Orbit (dynamics) #Pure mathematics #Semigroup #Word (group theory) #acm:20E99 #acm:20F10 #acm:20M30 #acm:20M35 #acm:68Q70 #cs.FL #math.GR #msc:20E99 #msc:20F10 #msc:20M30 #msc:20M35 #msc:68Q70 #semigroups and automata theory
paper · pdf · doi:10.1016/j.jalgebra.2020.02.014
published in Journal of Algebra 553, 119-137 (Elsevier BV) · This matches the published version. Compared to v1, the paper has mostly been re-written and some results have been removed. Almost all of them can be found in arXiv:2007.10273. There are no changes compared to v2
openalex publication_date 2020/02/27 · arxiv created 2020/08/21 · arxiv updated 2020/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
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 Ievgen 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 reformulation of the finiteness problem for automaton groups and semigroups.