Rational subsets of groups (Q2244818)

The paper under review constitutes Chapter 23 of the [\textit{J.-É. Pin} (ed.), Handbook of automata theory. Volume I. Theoretical foundations. Berlin: European Mathematical Society (EMS) (2021; Zbl 1470.68001); Handbook of automata theory. Volume II. Automata in mathematics and selected applications. Berlin: European Mathematical Society (EMS) (2021; Zbl 1470.68002)], it is a survey on the representation of rational subsets of infinite groups by automata. The first part (``Finitely generated groups'') is dedicated to essential definitions, terminology, and notation. This includes some standard group-theoretical notions along with classical algorithmic problems for groups, with special emphasis on the free group. Furthermore, the main problems of the algorithmic theory of finitely generated groups are listed: word problem, conjugacy problem, membership problem, generalized word problem, order problem, isomorphism problem for a class of groups. In the second part (``Inverse automata and Stallings' construction''), the authors focus on the representation of finitely generated subgroups of the free group as automata: the so-called theory of Stallings automata. The approach to this theory is automata-theoretic, and the relevant graphical definitions are given before proving Stallings' results. After that, some standard applications of Stallings' machinery are given, both algorithmic (membership problem, subgroup conjugacy problem, and finite index problem), algebraic (Nielsen-Schreier, Howson, and Takahasi theorems), topological (M. Hall theorem), and dynamical (subgroup orbit problem and Goldstein-Turner theorem on fixed points). Over the years, Stallings automata became the standard representation for finitely generated subgroups of free groups and are involved in many of the algorithmic results presently obtained. Several of these algorithms are implemented in computer software, such as \textsf{CRAG} and the packages \textsc{Automata} and \textsc{FGA} in \textsf{GAP}. The last part (``Rational and recognizable subsets'') is devoted to more general rational subsets of groups. One of the results discussed is Benois' Theorem, the cornerstone of the whole theory of rational subsets of free groups. Next, the authors move to language-theoretic theorems about the word problem submonoid of a general group, including Anisimov's theorem and Muller and Schupp's theorem. The paper ends with a characterization of the solvability of the rational subset membership problem, and a discussion on rational solutions and rational constraints in groups. For the entire collection see [Zbl 1470.68002].