Skip to main content
SpringerLink
Log in

Pro-aperiodic monoids via saturated models

  • Published:
Israel Journal of Mathematics Aims and scope Submit manuscript

Abstract

We apply Stone duality and model theory to study the structure theory of free pro-aperiodic monoids. Stone duality implies that elements of the free pro-aperiodic monoid may be viewed as elementary equivalence classes of pseudofinite words. Model theory provides us with saturated words in each such class, i.e., words in which all possible factorizations are realized. We give several applications of this new approach, including a solution to the word problem for ω-terms that avoids using McCammond’s normal forms, as well as new proofs and extensions of other structural results concerning free pro-aperiodic monoids.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J. Almeida, Finite Semigroups and Universal Algebra, Series in Algebra, Vol. 3, World Scientific Publishing, River Edge, NJ, 1994.

    Google Scholar 

  2. J. Almeida, On hyperdecidable pseudovarieties of simple semigroups, International Journal of Algebra and Computation 10 (2000), 261–284.

    MathSciNet  MATH  Google Scholar 

  3. J. Almeida, Profinite groups associated with weakly primitive substitutions, Fundamentalnaya i Prikladnaya Matematika 11 (2005), 13–48.

    MATH  Google Scholar 

  4. J. Almeida and A. Costa, Infinite-vertex free profinite semigroupoids and symbolic dynamics, Journal of Pure and Applied Algebra 213 (2009), 605–631.

    MathSciNet  MATH  Google Scholar 

  5. J. Almeida, A. Costa, J. C. Costa and M. Zeitoun, The linear nature of pseudowords, Publications Matématiques 63 (2019), 361–422.

    MathSciNet  MATH  Google Scholar 

  6. J. Almeida, J. C. Costa and M. Zeitoun, Some structural properties of the free profinite aperiodic semigroup, in Automatha Plenary Conference, Liège, 2009, https://hal.archives-ouvertes.fr/hal-00948998.

    Google Scholar 

  7. J. Almeida, J. C. Costa and M. Zeitoun, Iterated periodicity over finite aperiodic semigroups, European Journal of Combinatorics 37 (2014), 115–149.

    MathSciNet  MATH  Google Scholar 

  8. J. Almeida, J. C. Costa and M. Zeitoun, McCammond’s normal forms for free aperiodic semigroups revisited, LMS Journal of Computation and Mathematics 18 (2015), 130–147.

    MathSciNet  MATH  Google Scholar 

  9. J. Almeida, O. Klima and M. Kunc, The ω-inequality problem for concatenation hierarchies of star-free languages, Forum Mathematicum 30 (2018), 663–679.

    MathSciNet  MATH  Google Scholar 

  10. J. Almeida and M. V. Volkov, Subword complexity of profinite words and subgroups of free profinite semigroups, International Journal of Algebra and Computation 16 (2006), 221–258.

    MathSciNet  MATH  Google Scholar 

  11. S. L. Bloom and Z. Ésik, The equational theory of regular words, Information and Computation 197 (2005), 55–89.

    MathSciNet  MATH  Google Scholar 

  12. M. Bojańczyk, Recognisable languages over monads, in Developments in Language Theory. DLT 2015, Lecture Notes in Computer Science, Vol. 9168, Springer, Cham, 2015, pp. 1–13.

    Google Scholar 

  13. J. A. Brzozowski, Hierarchies of aperiodic languages, Revue Francaise d’Automatique Informatique Recherche Opérationnelle Série Rouge Informatique Théorique 10 (1976), 33–49.

    MathSciNet  Google Scholar 

  14. J. R. Büchi, Weak second-order arithmetic and finite automata, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 6 (1960), 66–92.

    MathSciNet  MATH  Google Scholar 

  15. O. Carton, T. Colcombet and G. Puppis, Regular languages of words over countable linear orderings, in Automata, Languages and Programming. Part II, Lecture Notes in Computer Science, Vol. 6756, Springer, Heidelberg, 2011, pp. 125–136.

    Google Scholar 

  16. O. Carton, T. Colcombet and G. Puppis, An algebraic approach to mso-definability on countable linear orderings, Journal of Symbolic Logic 83 (2018), 1147–1189.

    MathSciNet  MATH  Google Scholar 

  17. C.-C. Chang and J. H. Keisler, Model Theory, Studies in Logic and the Foundations of Mathematics, Vol. 73, North-Holland, Amsterdam, 1990.

    Google Scholar 

  18. H. C. Doets, Completeness and Definability: Applications of the Ehrenfeucht game in second-order and intensional logic, Ph.D. thesis, Universiteit van Amsterdam, May 1987.

    Google Scholar 

  19. S. Eilenberg, Automata, Languages, and Machines. Vol. B, Pure and Applied Mathematics, Vol. 59, Academic Press, New York London, 1976.

    Google Scholar 

  20. M. Gehrke, Stone duality, topological algebra, and recognition, Journal of Pure and Applied Algebra 220 (2016), 2711–2747.

    MathSciNet  MATH  Google Scholar 

  21. M. Gehrke, S. Grigorieff and J.-É. Pin, Duality and equational theory of regular languages, in Automata, Languages and Programming. Part II, Lecture Notes in Computer Science, Vol. 5126, Springer, Berlin, 2008, pp. 246–257.

    Google Scholar 

  22. M. Gehrke, A. Krebs and J.-É. Pin, Ultrafilters on words for a fragment of logic, Theoretical Computer Science 610 (2016), 37–58.

    MathSciNet  MATH  Google Scholar 

  23. M. Gehrke, D. Petrisan and L. Reggio, The Schützenberger product for syntactic spaces, in 43rd International Colloquium on Automata, Languages and Programming, Leibniz International Proceedings in Informatics, Vol. 55, Schloss Dagstuhl Leibniz-Zentrum für Informatik, Dagstuhl, 2016, pp. 112:1112:14.

    Google Scholar 

  24. S. J. van Gool and B. Steinberg, Pro-aperiodic monoids via saturated models, in 34th Symposium on Theoretical Aspects of Computer Science, Leibniz International Proceedings in Informatics, Vol. 66, Schloss Dagstuhl Leibniz-Zentrum für Informatik, Dagstuhl, 2017, pp. 39:139:14.

    Google Scholar 

  25. K. Henckell, Idempotent pointlike sets, International Journal of Algebra and Computation 14 (2004), 703–717.

    MathSciNet  MATH  Google Scholar 

  26. K. Henckell, Stable pairs, International Journal of Algebra and Computation 20 (2010), 241–267.

    MathSciNet  MATH  Google Scholar 

  27. K. Henckell, J. Rhodes and B. Steinberg, A profinite approach to stable pairs, International Journal of Algebra and Computation 20 (2010), 269–285.

    MathSciNet  MATH  Google Scholar 

  28. K. Henckell, J. Rhodes and B. Steinberg, An effective lower bound for group complexity of finite semigroups and automata, Transactions of the American Mathematical Society 364 (2012), 1815–1857.

    MathSciNet  MATH  Google Scholar 

  29. W. Hodges, Model Theory, Encyclopedia of Mathematics and its Applications, Vol. 42, Cambridge University Press, Cambridge, 1993.

    Google Scholar 

  30. M. Huschenbett and M. Kufleitner, Ehrenfeucht Fraïssé games on omega-terms, in 31st International Symposium on Theoretical Aspects of Computer Science, Leibniz International Proceedings in Informatics, Vol. 25, Schloss Dagstuhl Leibniz-Zentrum für Informatik, Dagstuhl, 2014, pp. 374–385.

    Google Scholar 

  31. K. Krohn and J. Rhodes, Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines, Transactions of the American Mathematical Society 116 (1965), 450–464.

    MathSciNet  MATH  Google Scholar 

  32. K. Krohn and J. Rhodes, Complexity of finite semigroups, Annals of Mathematics 88 (1968), 128–160.

    MathSciNet  MATH  Google Scholar 

  33. M. Lohrey and C. Mathissen, Isomorphism of regular trees and words, Information and Computation 224 (2013), 71–105.

    MathSciNet  MATH  Google Scholar 

  34. D. Marker, Model Theory: An Introduction, Graduate Texts in Mathematics, Vol. 217, Springer, New York, 2002.

    Google Scholar 

  35. J. P. McCammond, The solution to the word problem for the relatively free semigroups satisfying Ta = Ta+b with a = 6, International Journal of Algebra and Computation 1 (1991), 1–32.

    MathSciNet  MATH  Google Scholar 

  36. J. P. McCammond, Normal forms for free aperiodic semigroups, International Journal of Algebra and Computation 11 (2001), 581–625.

    MathSciNet  MATH  Google Scholar 

  37. R. McNaughton and S. Papert, Counter-free Automata, M.I.T. Research Monograph, no. 65, MIT Press, Cambridge, MA, 1971.

    Google Scholar 

  38. J.-É. Pin, The dot-depth hierarchy, 45 years later, in The Role of Theory in Computer Science, World Scientific, Hackensack, NJ, 2017, pp. 177–202.

    MATH  Google Scholar 

  39. T. Place and M. Zeitoun, Going higher in the first-order quantifier alternation hierarchy on words, in Automata, languages, and programming. Part II, Lecture Notes in Computer Science, Vol. 8573, Springer, Heidelberg, 2014, pp. 342–353.

    MATH  Google Scholar 

  40. J. Rhodes and B. Steinberg, Profinite semigroups, varieties, expansions and the structure of relatively free profinite semigroups, International Journal of Algebra and Computation 11 (2001), 627–672.

    MathSciNet  MATH  Google Scholar 

  41. J. Rhodes and B. Steinberg, The q-theory of Finite Semigroups, Springer Monographs in Mathematics, Springer, New York, 2009.

    MATH  Google Scholar 

  42. J. G. Rosenstein, Linear Orderings, Pure and Applied Mathematics, Vol. 98, Academic Press, New York London, 1982.

    Google Scholar 

  43. M.-P. Schützenberger, On finite monoids having only trivial subgroups, Information and Control 8 (1965), 190–194.

    MathSciNet  MATH  Google Scholar 

  44. S. Shelah, The monadic theory of order, Annals of Mathematics 102 (1975), 379–419.

    MathSciNet  MATH  Google Scholar 

  45. B. Steinberg, A combinatorial property of ideals in free profinite monoids, Journal of Pure and Applied Algebra 214 (2010), 1693–1695.

    MathSciNet  MATH  Google Scholar 

  46. M. H. Stone, The theory of representation for Boolean algebras, Transactions of the American Mathematical Society 74 (1936), 37–111.

    MathSciNet  MATH  Google Scholar 

  47. H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity, Progress in Theoretical Computer Science, Birkhäuser Boston, Boston, MA, 1994.

    MATH  Google Scholar 

  48. J. Väänänen, Pseudo-finite model theory, Matemática Contemporânea 24 (2003), 169–183.

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut de Recherche en Informatique Fondamentale, Université de Paris Bâtiment Sophie Germain, Case courier 7014, 8 Place Aurélie Nemours, 75205, Paris Cedex 13, France

    Samuel J. van Gool

  2. Department of mathematics, City College of New york NAC 8/133, Covent Ave. at 138th St., New York, NY, 11031, USA

    Benjamin Steinberg

Authors
  1. Samuel J. van Gool
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Benjamin Steinberg
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Benjamin Steinberg.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

van Gool, S.J., Steinberg, B. Pro-aperiodic monoids via saturated models. Isr. J. Math. 234, 451–498 (2019). https://doi.org/10.1007/s11856-019-1947-6

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11856-019-1947-6

Search

Navigation