The finiteness problem for groups generated by reset automata

DOI10.4171/GGD/838MaRDI QIDQ7303104zbMATH OpenFDO

Authors Feyishayo Olukoya

Publication date 23 July 2026

Published in Groups, Geometry, and Dynamics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4171/GGD/838

Mathematics Subject Classification ID

Groups acting on trees (20E08) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Review text

The finiteness problem is investigated for groups generated by invertible, strongly synchronizing Mealy automata that coincide with their core. Here an automaton is strongly synchronizing if, for some integer \(k\), every input word of length \(k\) determines the resulting state independently of the initial state; the core consists of the states reached in this way. The main result shows that the group generated by such an automaton is either finite or contains a free subsemigroup of rank at least two. Consequently, every infinite group in this class has exponential growth.\N\NFor an automaton \(A\) in this class, synchronizing at level \(k\), finite directed graphs \(G_r(A)\) of bad pairs are defined for \(r\geq k\). If one of these graphs contains a directed circuit, the induced action of \(A\) on the two-sided shift has an eventually periodic point with\ infinite orbit, and the automaton group is infinite. The paper also proves that, for a finite group \(G\) and every \(n\geq 1\), the \(n\)th power of its Cayley machine is strongly connected and has \(|G|^n\) states inducing pairwise distinct homeomorphisms of \(G^{\mathbb{N}}\).

Cites work

• A connected 3-state reversible Mealy automaton cannot generate an infinite Burnside group
• A Property of Groups of Nonexponential Growth
• An automaton group with undecidable order and Engel problems
• Automata, dynamical systems, and groups
• Automorphisms of one-sided subshifts of finite type
• Automorphisms of shift spaces and the Higman-Thompson groups: the one-sided case
• Combinatorial algebra: syntax and semantics. With contributions by Victor S. Guba and Mikhail V. Volkov
• Elementary amenable groups
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
• On the finiteness problem for automaton (semi)groups.
• Synchronizing Automata and the Černý Conjecture
• The further chameleon groups of Richard Thompson and Graham Higman: Automorphisms via dynamics for the Higman-Thompson groups~\(G_{n,r}\)
• The road coloring problem
• The word and order problems for self-similar and automata groups
• To infinity and beyond

This page was built for publication: The finiteness problem for groups generated by reset automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7303104)