Finite state automata: a geometric approach (Q2716145)

As the author says, this paper contains an elementary and more general version of the recent results by \textit{S.~Margolis, M.~Sapir} and \textit{P.~Weil} [Closed subgroups in pro-\(\mathbf V\) topologies, and the extension problem for inverse automata. Int. J. Algebra Comput. 11, No. 4, 405-445 (2001)] that link finite automata theory with the study of profinite topologies on a free group. For example, the author gives a method that, for each extension-closed pseudovariety \(\mathbf H\) of groups, allows to rebuild any given finite automaton into a finite automaton which can be used to recognize the pro-\(\mathbf H\) closure of every language recognized by the original automaton (Theorem~6.27). This method becomes an algorithmically efficient procedure whenever there exists an algorithm to test membership in the pro-\(\mathbf H\) closure of a finitely generated subgroup of a free group, and the procedure is only polynomially slower than the membership algorithm (Theorem~6.28). In particular, the pro-\(\mathbf G\) closure of a rational language (where \(\mathbf G\) stands for the pseudovariety of all finite groups) can be computed by the author's method in rapid polynomial time.NEWLINENEWLINENEWLINEAs an application to language theory, the author shows that if \(\mathbf H\) is a group pseudovariety such that all free groups are residually in \(\mathbf H\) and \(L\) is a rational language which is open or closed in the pro-\(\mathbf H\) topology, then the syntactic monoid of \(L\) belongs to the Mal'cev product \({\mathbf J}\circm{\mathbf H}\) where \(\mathbf J\) is the pseudovariety of all finite \(\mathcal J\)-trivial semigroups (Theorem~7.19).NEWLINENEWLINENEWLINEThe main semigroup application of the author's techniques is the proof that, for each extension-closed pseudovariety \(\mathbf H\) of groups, the Mal'cev product \({\mathbf J}\circm{\mathbf H}\) is equal to the semidirect product \({\mathbf J}*{\mathbf H}\) (Theorem~7.24). This proof is independent of the previously known equality \({\mathbf J}\circm{\mathbf G}={\mathbf J}*{\mathbf G}\) due to \textit{K.~Henckell} and \textit{J.~Rhodes} [Monoids and semigroups with applications. Proc. Berkeley workshop on monoids, World Scientific, 453-463 (1991; Zbl 0826.20054)]; moreover, when restricted to the case \({\mathbf H}={\mathbf G}\) it gives the shortest and least technical proof of Henckell-Rhodes's theorem to date. The author also shows that if a non-trivial group pseudovariety \(\mathbf H\) satisfies either of the identities \(xy=yx\) or \(x^n=1\), then \({\mathbf J}\circm{\mathbf H}\neq{\mathbf J}*{\mathbf H}\) (Theorems 7.31 and 7.32).NEWLINENEWLINENEWLINEReviewer's remarks. 1. Theorem~7.40 states the equality \(({\mathbf V}*{\mathbf H})\cap({\mathbf R}*{\mathbf H})=({\mathbf V}*{\mathbf G})\cap({\mathbf R}*{\mathbf H})\) where \(\mathbf V\) is an arbitrary monoid pseudovariety, \(\mathbf H\) is an extension-closed pseudovariety of groups, and \(\mathbf R\) is the pseudovariety of all finite \(\mathcal R\)-trivial semigroups. It relies on a result by \textit{J.~Almeida} and \textit{P.~Weil} [J. Pure Appl. Algebra 123, No. 1-3, 1-50 (1998; Zbl 0891.20037)] the proof of which has been recently discovered to be insufficient. Therefore at the moment Theorem~7.40 may be considered as being proved only for the case when the pseudovariety \(\mathbf V\) has finite vertex rank.NEWLINENEWLINENEWLINE2. Recently \textit{K.~Auinger} and the author [The geometry of profinite graphs with applications to free groups and finite monoids (preprint)] have found a complete description (in terms of the geometry of the Cayley graphs of the relatively free profinite groups) of group pseudovarieties \(\mathbf H\) such that \({\mathbf J}\circm{\mathbf H}={\mathbf J}*{\mathbf H}\).