Finite state automata: A geometric approach

Steinberg, Benjamin

doi:10.1090/S0002-9947-01-02774-X

Finite state automata: A geometric approach
HTML articles powered by AMS MathViewer

by Benjamin Steinberg PDF

Trans. Amer. Math. Soc. 353 (2001), 3409-3464 Request permission

Abstract:

Recently, finite state automata, via the advent of hyperbolic and automatic groups, have become a powerful tool in geometric group theory. This paper develops a geometric approach to automata theory, analogous to various techniques used in combinatorial group theory, to solve various problems on the overlap between group theory and monoid theory. For instance, we give a geometric algorithm for computing the closure of a rational language in the profinite topology of a free group. We introduce some geometric notions for automata and show that certain important classes of monoids can be described in terms of the geometry of their Cayley graphs. A long standing open question, to which the answer was only known in the simplest of cases (and even then was non-trivial), is whether it is true, for a pseudovariety of groups $\mathbf {H}$, that a ${\mathcal J}$-trivial co-extension of a group in $\mathbf {H}$ must divide a semidirect product of a ${\mathcal J}$-trivial monoid and a group in $\mathbf {H}$. We show the answer is affirmative if $\mathbf {H}$ is closed under extension, and may be negative otherwise.

References

Douglas Albert, Robert Baldinger, and John Rhodes, Undecidability of the identity problem for finite semigroups, J. Symbolic Logic 57 (1992), no. 1, 179–192. MR 1150933, DOI 10.2307/2275184
Jorge Almeida, Finite semigroups and universal algebra, Series in Algebra, vol. 3, World Scientific Publishing Co., Inc., River Edge, NJ, 1994. Translated from the 1992 Portuguese original and revised by the author. MR 1331143
Jorge Almeida, Hyperdecidable pseudovarieties and the calculation of semidirect products, Internat. J. Algebra Comput. 9 (1999), no. 3-4, 241–261. Dedicated to the memory of Marcel-Paul Schützenberger. MR 1722629, DOI 10.1142/S0218196799000163
J. Almeida and A. Escada, On the equation $\mathbf V*\mathbf G = {\mathcal E}\mathbf V$, Tech. Rep. CMUP 98-6, Univ. of Porto, 1998
Jorge Almeida and Benjamin Steinberg, On the decidability of iterated semidirect products with applications to complexity, Proc. London Math. Soc. (3) 80 (2000), no. 1, 50–74. MR 1719180, DOI 10.1112/S0024611500012144
J. Almeida and M. V. Volkov, The gap between partial and full, Internat. J. Algebra Comput. 8 (1998), no. 3, 399–430. MR 1627844, DOI 10.1142/S0218196798000193
J. Almeida and P. Weil, Relatively free profinite monoids: an introduction and examples, Semigroups, formal languages and groups (York, 1993) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 466, Kluwer Acad. Publ., Dordrecht, 1995, pp. 73–117. MR 1630619
J. Almeida and P. Weil, Profinite categories and semidirect products, J. Pure Appl. Algebra 123 (1998), no. 1-3, 1–50. MR 1492894, DOI 10.1016/S0022-4049(96)00083-7
G. P. Monro, A category-theoretic approach to Boolean-valued models of set theory, J. Pure Appl. Algebra 42 (1986), no. 3, 245–274. MR 857894, DOI 10.1016/0022-4049(86)90010-1
C. J. Ash, Inevitable graphs: a proof of the type $\textrm {II}$ conjecture and some related decision procedures, Internat. J. Algebra Comput. 1 (1991), no. 1, 127–146. MR 1112302, DOI 10.1142/S0218196791000079
Michèle Benois, Parties rationnelles du groupe libre, C. R. Acad. Sci. Paris Sér. A-B 269 (1969), A1188–A1190. MR 265496
A. Gloden, Sur la résolution en nombres entiers du système $A^{kx}+B^{kx}+C^{kx}+D^{kx}=E^x+F^x+G^x+H^x$ ($x=1$, $2$ et $3$), Bol. Mat. 12 (1939), 118–122 (French). MR 24
M. Delgado, On the hyperdecidability of pseudovarieties of groups, Internat. J. Algebra and Comput. (to appear).
Samuel Eilenberg, Automata, languages, and machines. Vol. A, Pure and Applied Mathematics, Vol. 58, Academic Press [Harcourt Brace Jovanovich, Publishers], New York, 1974. MR 0530382
David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Michael S. Paterson, and William P. Thurston, Word processing in groups, Jones and Bartlett Publishers, Boston, MA, 1992. MR 1161694
Robert Knast, Some theorems on graph congruences, RAIRO Inform. Théor. 17 (1983), no. 4, 331–342 (English, with French summary). MR 743893, DOI 10.1051/ita/1983170403311
Kenneth Krohn and John Rhodes, Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines, Trans. Amer. Math. Soc. 116 (1965), 450–464. MR 188316, DOI 10.1090/S0002-9947-1965-0188316-1
Kenneth Krohn and John Rhodes, Complexity of finite semigroups, Ann. of Math. (2) 88 (1968), 128–160. MR 236294, DOI 10.2307/1970558
Robert H. Gilman, Groups with a rational cross-section, Combinatorial group theory and topology (Alta, Utah, 1984) Ann. of Math. Stud., vol. 111, Princeton Univ. Press, Princeton, NJ, 1987, pp. 175–183. MR 895616
Rita Gitik and Eliyahu Rips, On separability properties of groups, Internat. J. Algebra Comput. 5 (1995), no. 6, 703–717. MR 1365198, DOI 10.1142/S0218196795000288
Dion Gildenhuys and Luis Ribes, Profinite groups and Boolean graphs, J. Pure Appl. Algebra 12 (1978), no. 1, 21–47. MR 488811, DOI 10.1016/0022-4049(78)90019-1
Morgan Ward and R. P. Dilworth, The lattice theory of ova, Ann. of Math. (2) 40 (1939), 600–608. MR 11, DOI 10.2307/1968944
Charles Hopkins, Rings with minimal condition for left ideals, Ann. of Math. (2) 40 (1939), 712–730. MR 12, DOI 10.2307/1968951
Karsten Henckell, Stuart W. Margolis, Jean-Eric Pin, and John Rhodes, Ash’s type $\textrm {II}$ theorem, profinite topology and Mal′cev products. I, Internat. J. Algebra Comput. 1 (1991), no. 4, 411–436. MR 1154442, DOI 10.1142/S0218196791000298
Saunders MacLane, Categories for the working mathematician, Graduate Texts in Mathematics, Vol. 5, Springer-Verlag, New York-Berlin, 1971. MR 0354798
S. W. Margolis, private communication.
S. W. Margolis and J.-E. Pin, Inverse semigroups and extensions of groups by semilattices, J. Algebra 110 (1987), no. 2, 277–297. MR 910384, DOI 10.1016/0021-8693(87)90046-9
Stuart W. Margolis and John C. Meakin, Free inverse monoids and graph immersions, Internat. J. Algebra Comput. 3 (1993), no. 1, 79–99. MR 1214007, DOI 10.1142/S021819679300007X
S. Margolis, J. Meakin, and M. Sapir, Algorithmic problems in groups, semigroups and inverse semigroups, Semigroups, formal languages and groups (York, 1993) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 466, Kluwer Acad. Publ., Dordrecht, 1995, pp. 147–214. MR 1630621
S. W. Margolis, M. Sapir, and P. Weil, Closed subgroups in pro-$\mathbf V$ topologies and the extension problem for inverse automata, Internat. J. Algebra and Comput. (to appear).
O. Matz, A. Miller, A. Pothoff, W. Thomas, and E. Valkema, Report on the program AMoRE, Tech. Rep. 9507, Christian Albrechts Universitat, Kiel, 1994.
W. D. Munn, Free inverse semigroups, Semigroup Forum 5 (1972/73), 262–269. MR 322083, DOI 10.1007/BF02572897
G. A. Niblo, Separability properties of free groups and surface groups, J. Pure Appl. Algebra 78 (1992), no. 1, 77–84. MR 1154898, DOI 10.1016/0022-4049(92)90019-C
Jean-Eric Pin and Christophe Reutenauer, A conjecture on the Hall topology for the free group, Bull. London Math. Soc. 23 (1991), no. 4, 356–362. MR 1125861, DOI 10.1112/blms/23.4.356
Ion Armeanu, The structure of the groups all whose characters are rational valued on the odd order elements, Ital. J. Pure Appl. Math. 5 (1999), 149–156. MR 1736009
John Rhode and Benjamin Steinberg, Pointlike sets, hyperdecidability and the identity problem for finite semigroups, Internat. J. Algebra Comput. 9 (1999), no. 3-4, 475–481. Dedicated to the memory of Marcel-Paul Schützenberger. MR 1723478, DOI 10.1142/S021819679900028X
Luis Ribes and Pavel A. Zalesskii, On the profinite topology on a free group, Bull. London Math. Soc. 25 (1993), no. 1, 37–43. MR 1190361, DOI 10.1112/blms/25.1.37
Luis Ribes and Pavel A. Zalesskii, The pro-$p$ topology of a free group and algorithmic problems in semigroups, Internat. J. Algebra Comput. 4 (1994), no. 3, 359–374. MR 1297146, DOI 10.1142/S021819679400004X
Jean-Pierre Serre, Trees, Springer-Verlag, Berlin-New York, 1980. Translated from the French by John Stillwell. MR 607504
John R. Stallings, Topology of finite graphs, Invent. Math. 71 (1983), no. 3, 551–565. MR 695906, DOI 10.1007/BF02095993
Benjamin Steinberg, On pointlike sets and joins of pseudovarieties, Internat. J. Algebra Comput. 8 (1998), no. 2, 203–234. With an addendum by the author. MR 1620343, DOI 10.1142/S0218196798000119
Benjamin Steinberg, Monoid kernels and profinite topologies on the free abelian group, Bull. Austral. Math. Soc. 60 (1999), no. 3, 391–402. MR 1727475, DOI 10.1017/S0004972700036571
B. Steinberg, On algorithmic problems for joins of pseudovarieties, Semigroup Forum 62 (2001), 1-40.
B. Steinberg, Inevitable Graphs and Profinite Topologies: Some solutions to algorithmic problems in monoid and automata theory stemming from group theory, Internat. J. Algebra and Comput. 11 (2001), 25-71.
B. Steinberg, A note on the equation $\mathbf {PH} = \mathbf J*\mathbf H$, Semigroup Forum (to appear)
B. Steinberg, Polynomial closure and topology, Internat. J. Algebra and Comput. 10 (2000), 603–624.
B. Steinberg, Inverse automata and profinite topologies on a free group, J. Pure and Appl. Algebra (to appear).
Bret Tilson, Type $\textrm {II}$ redux, Semigroups and their applications (Chico, Calif., 1986) Reidel, Dordrecht, 1987, pp. 201–205. MR 900660
Bret Tilson, Categories as algebra: an essential ingredient in the theory of monoids, J. Pure Appl. Algebra 48 (1987), no. 1-2, 83–198. MR 915990, DOI 10.1016/0022-4049(87)90108-3
Pascal Weil, Some results on the dot-depth hierarchy, Semigroup Forum 46 (1993), no. 3, 352–370 (English, with English and French summaries). MR 1206213, DOI 10.1007/BF02573578
E. Zel′manov, More on Burnside’s problem, Combinatorial and geometric group theory (Edinburgh, 1993) London Math. Soc. Lecture Note Ser., vol. 204, Cambridge Univ. Press, Cambridge, 1995, pp. 314–321. MR 1320294