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
Additional Information
- Benjamin Steinberg
- Affiliation: Faculdade de Ciências, da Universidade do Porto, 4099-002 Porto, Portugal
- MR Author ID: 633258
- Email: bsteinbg@agc0.fc.up.pt
- Received by editor(s): February 12, 1999
- Received by editor(s) in revised form: August 24, 2000
- Published electronically: May 4, 2001
- Additional Notes: The author was supported in part by Praxis XXI scholarship BPD 16306 98
- © Copyright 2001 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 353 (2001), 3409-3464
- MSC (1991): Primary 20M35, 20F10
- DOI: https://doi.org/10.1090/S0002-9947-01-02774-X
- MathSciNet review: 1837243