2010/12/07 by Laurent Bartholdi, Bartholdi, Laurent, Pedro V. Silva +1
Computer Science · Mathematics · #20E08 #20F10 #20F65 #20F67 #68Q45 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Finite Group Theory Research #Formal Languages and Automata Theory (cs.FL) #Geometric and Algebraic Topology #Group Theory (math.GR) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1012.1531
openalex publication_date 2010/12/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This is Chapter 24 in the "AutoMathA" handbook. Finite automata have been used effectively in recent years to define infinite groups. The two main lines of research have as their most representative objects the class of automatic groups (including word-hyperbolic groups as a particular case) and automata groups (singled out among the more general self-similar groups). The first approach implements in the language of automata some tight constraints on the geometry of the group's Cayley graph, building strange, beautiful bridges between far-off domains. Automata are used to define a normal form for group elements, and to monitor the fundamental group operations. The second approach features groups acting in a finitely constrained manner on a regular rooted tree. Automata define sequential permutations of the tree, and represent the group elements themselves. The choice of particular classes of automata has often provided groups with exotic behaviour which have revolutioned our perception of infinite finitely generated groups.