Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Finite state automata: A geometric approach


Author: Benjamin Steinberg
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
Published electronically: May 4, 2001
MathSciNet review: 1837243
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. D. Albert, R. Baldinger, J. Rhodes, Undecidability of the identity problem for finite semigroups, The Journal of Symb. Logic 57 (1992), 179-192.MR 93f:03030
  • 2. J. Almeida, Finite Semigroups and Universal Algebra, World Scientific, 1994.MR 96b:20069
  • 3. J. Almeida, Hyperdecidable pseudovarieties and the calculation of semidirect products, Internat. J. Algebra and Comput. 9 (1999), 241-261. MR 2001a:20102
  • 4. 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
  • 5. J. Almeida and B. Steinberg, On the decidability of iterated semidirect products with applications to complexity, Proc. London Math. Soc. 80 (2000), 50-74.MR 2000j:20109
  • 6. J. Almeida and M. V. Volkov, The gap between partial and full, Internat. J. Algebra and Comput. 8 (1998), 399-430. MR 99g:20102
  • 7. J. Almeida and P. Weil, Relatively free profinite monoids: An introduction and examples, Semigroups, Formal Languages and Groups, J. B. Fountain, ed., vol. 466, Dordrecht, 1995, Kluwer Publ., 73-117. MR 2000f:20095
  • 8. J. Almeida and P. Weil, Profinite categories and semidirect products, J. Pure and Appl. Algebra (1998) 123, 1-50. MR 99c:20080
  • 9. C. J. Ash, Finite semigroups with commuting idempotents, J. Austral. Math. Soc. Ser. A 43 (1987), 81-90. MR 88f:03045
  • 10. C. J. Ash, Inevitable graphs: A proof of the type II conjecture and some related decision procedures, Internat. J. Algebra and Comput. 1 (1991), 127-146. MR 92k:20114
  • 11. M. Benois, Parties rationnelles du groupe libre, C. R. Acad. Sci. Paris, Sér. A, 269 (1969), 1188-1190. MR 42:405
  • 12. A. H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups, Mathematical Surveys No. 7, AMS, Providence, RI, Vol. 1, 1961; Vol. 2, 1967. MR 24:A2627; MR 36:1558
  • 13. M. Delgado, On the hyperdecidability of pseudovarieties of groups, Internat. J. Algebra and Comput. (to appear).
  • 14. S. Eilenberg, Automata, Languages and Machines, Academic Press, New York, Vol A, 1974; Vol B, 1976. MR 58:26604a
  • 15. D. B. A. Epstein with J. W. Cannon, D. F. Holt, S. V. F Levy, M. S. Paterson, W. P. Thurston, Word Processing in Groups, Jones and Bartlett, Boston-London, 1992. MR 93i:20036
  • 16. R. Knast, Some theorems on graph congruences, RAIRO Inform. Théor. 17 (1983), 331-342. MR 86a:68055
  • 17. K. Krohn and J. Rhodes, Algebraic theory of machines, I, Trans. Amer. Math. Soc. 116 (1965), 450-464. MR 32:5755
  • 18. K. Krohn and J. Rhodes, Complexity of finite semigroups, Ann. of Math. 88 (1968), 128-160. MR 38:4591
  • 19. R. H. Gilman, Groups with rational cross-sections, in ``Essays in group theory", edited by S. M. Gersten and J. R. Stallings, P. U. P. Annals of Math series #111, 1987, 175-183. MR 88g:20065
  • 20. R. Gitik and E. Rips, On separability properties of groups, Internat. J. Algebra and Comput. 5 (1995), 703-717. MR 97e:20059
  • 21. D. Gildenhuys and L. Ribes, Profinite groups and Boolean graphs, J. Pure Appl. Algebra 12 (1978), 21-47. MR 81g:20059
  • 22. M. Hall, Jr. Coset representation in free groups, Trans. Amer. Math. Soc. 67 (1949), 421-432. MR 11:322e
  • 23. M. Hall, Jr. A topology for free groups and related groups, Annals of Mathematics 52 (1950), 127-139. MR 12:158b
  • 24. K. Henckell, S. Margolis, J.-E. Pin, and J. Rhodes, Ash's type II theorem, profinite topology and Malcev products. Part I, Internat. J. Algebra and Comput. 1 (1991), 411-436. MR 93h:20064
  • 25. S. MacLane, Categories for the Working Mathematician, Springer-Verlag, New York, 1971. MR 50:7275
  • 26. S. W. Margolis, private communication.
  • 27. S. W. Margolis and J.-E. Pin, Inverse semigroups and varieties of finite semigroups, J. Algebra 110 (1987), 306-323. MR 89j:20066b
  • 28. S. W. Margolis and J. C. Meakin, Free inverse monoids and graph immersions, Internat. J. Algebra and Comput. 3 (1993), 79-99. MR 94c:20105
  • 29. S. W. Margolis, J. C. Meakin, and M. Sapir, Algorithmic problems, Semigroups, Formal Languages and Groups, J. B. Fountain, ed., vol. 466, Dordrecht, 1995, Kluwer Publ. MR 99e:20043
  • 30. 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).
  • 31. O. Matz, A. Miller, A. Pothoff, W. Thomas, and E. Valkema, Report on the program AMoRE, Tech. Rep. 9507, Christian Albrechts Universitat, Kiel, 1994.
  • 32. W. D. Munn, Free inverse semigroups, Proc. London Math. Soc. 30 (1974), 385-404. MR 48:447
  • 33. G. Niblo, Separability properties of free groups and surface groups, J. Pure Appl. Algebra 78 (1992), 77-84. MR 92m:20019
  • 34. J.-E. Pin and C. Reutenauer, A conjecture on the Hall topology for the free group, Bull. London Mat. Soc. 23 (1991), 356-362. MR 92g:20035
  • 35. J. Rhodes, Undecidability, automata and pseudovarieties of finite semigroups, Internat. J. Algebra and Comput. 9 (1999), 455-473. MR 2000j:20012
  • 36. J. Rhodes and B. Steinberg, Pointlike sets, hyperdecidability, and the identity problem for finite semigroups, Internat. J. Algebra and Comput. 9 (1999), 475-481. MR 2000k:20075
  • 37. L. Ribes and P. A. Zalesski{\u{\i}}\kern.15em, On the profinite topology on a free group, Bull. London Math. Soc. 25 (1993), 37-43. MR 93j:20062
  • 38. L. Ribes and P. A. Zalesski{\u{\i}}\kern.15em, The pro-$p$ topology of a free group and algorithmic problems in semigroups, Internat. J. Algebra and Comput. 4 (1994), 359-374. MR 96e:20046
  • 39. J.-P. Serre, Trees, Springer-Verlag, Heidelberg, 1980. MR 82c:20083
  • 40. J. Stallings, Topology of finite graphs, Inv. Math. 71 (1983), 551-565. MR 85m:05037a
  • 41. B. Steinberg, On pointlike sets and joins of pseudovarieties, Internat. J. Algebra and Comput. 8 (1998), 203-231. MR 99g:20104
  • 42. B. Steinberg, Monoid kernels and profinite topologies on the free Abelian group, Bull. of the Austral. Math. Soc. 60 (1999), 391-402. MR 2000h:20120
  • 43. B. Steinberg, On algorithmic problems for joins of pseudovarieties, Semigroup Forum 62 (2001), 1-40.
  • 44. 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.
  • 45. B. Steinberg, A note on the equation $\mathbf{PH} = \mathbf J*\mathbf H$, Semigroup Forum (to appear)
  • 46. B. Steinberg, Polynomial closure and topology, Internat. J. Algebra and Comput. 10 (2000), 603-624. CMP 2001:01
  • 47. B. Steinberg, Inverse automata and profinite topologies on a free group, J. Pure and Appl. Algebra (to appear).
  • 48. B. Tilson, Type II redux, Semigroups and Their Applications, ed. S. M. Goberstein and P. M. Higgins, Reidel, Dordecht, 1987, 201-205.MR 88k:20086
  • 49. B. Tilson, Categories as algebra: An essential ingredient in the theory of monoids, J. Pure and Appl. Algebra 48 (1987), 83-198. MR 90e:20061
  • 50. P. Weil, Some results on the dot-depth hierarchy, Semigroup Forum 46 (1993), 352-370. MR 93m:20089
  • 51. E. Zel'manov, More on Burnside's Problem, Combinatorial and geometric group theory. Proceedings of a workshop held at Heriot-Watt University, Edinborough GB Spring of 93, ed. A. Duncan et al., London Math. Soc. Lec. Note Ser. 204, Cambridge, 1995, 314-321. MR 96k:20080

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 20M35, 20F10

Retrieve articles in all journals with MSC (1991): 20M35, 20F10


Additional Information

Benjamin Steinberg
Affiliation: Faculdade de Ciências, da Universidade do Porto, 4099-002 Porto, Portugal
Email: bsteinbg@agc0.fc.up.pt

DOI: https://doi.org/10.1090/S0002-9947-01-02774-X
Keywords: Immersions, coverings, fundamental groups, profinite topologies, rational languages, automata, graphs, monoids, block groups, semidirect products, pseudovarieties, Mal$'$cev products
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
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society