Document Open Access Logo

Pro-Aperiodic Monoids via Saturated Models

Authors Samuel J. van Gool, Benjamin Steinberg

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.39.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Samuel J. van Gool
Benjamin Steinberg

Cite AsGet BibTex

Samuel J. van Gool and Benjamin Steinberg. Pro-Aperiodic Monoids via Saturated Models. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.STACS.2017.39

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 omega-terms that avoids using McCammond's normal forms, as well as new proofs and extensions of other structural results concerning free pro-aperiodic monoids.
Keywords
  • aperiodic monoids
  • profinite monoids
  • Stone duality
  • saturated models

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. J. Almeida. Finite semigroups and universal algebra, volume 3 of Series in Algebra. World Scientific Publishing Co. Inc., River Edge, NJ, 1994. Translated from the 1992 Portuguese original and revised by the author. Google Scholar
  2. J. Almeida. Profinite groups associated with weakly primitive substitutions. Fundam. Prikl. Mat., 11(3):13-48, 2005. URL: http://dx.doi.org/10.1007/s10958-007-0242-y.
  3. J. Almeida and A. Costa. Infinite-vertex free profinite semigroupoids and symbolic dynamics. J. Pure Appl. Algebra, 213(5):605-631, 2009. URL: http://dx.doi.org/10.1016/j.jpaa.2008.08.009.
  4. J. Almeida, J. C. Costa, and M. Zeitoun. Some structural properties of the free profinite aperiodic semigroup. In 2nd AutoMathA Conference, 2009. Google Scholar
  5. J. Almeida, J. C. Costa, and M. Zeitoun. Iterated periodicity over finite aperiodic semigroups. European J. Combin., 37:115-149, 2014. URL: http://dx.doi.org/10.1016/j.ejc.2013.07.011.
  6. J. Almeida, J. C. Costa, and M. Zeitoun. McCammond’s normal forms for free aperiodic semigroups revisited. LMS J. Comput. Math., 18(1):130-147, 2015. URL: http://dx.doi.org/10.1112/S1461157014000448.
  7. J. Almeida and M. V. Volkov. Subword complexity of profinite words and subgroups of free profinite semigroups. Internat. J. Algebra Comput., 16(2):221-258, 2006. URL: http://dx.doi.org/10.1142/S0218196706002883.
  8. S. L. Bloom and Z. Ésik. The equational theory of regular words. Information and Computation, 197:55-89, 2005. Google Scholar
  9. M. Bojańczyk. Recognisable Languages over Monads. arXiv:1502.04898v1, 2015. Google Scholar
  10. J. A. Brzozowski. Hierarchies of aperiodic languages. Theoret. Informatics Appl., 10(2):33-49, 1976. Google Scholar
  11. O. Carton, T. Colcombet, and G. Puppis. Regular languages of words over countable linear orderings. In Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), volume 6756 of LNCS, pages 125-136. Springer, 2011. Google Scholar
  12. C.-C. Chang and J. H. Keisler. Model Theory. North-Holland, Amsterdam-London, third edition, 1990. Google Scholar
  13. H. C. Doets. Completeness And Definability : Applications Of The Ehrenfeucht Game In Second-Order And Intensional Logic. PhD thesis, Universiteit van Amsterdam, May 1987. URL: http://oai.cwi.nl/oai/asset/22742/22742A.pdf.
  14. S. Eilenberg. Automata, languages, and machines. Vol. B. Academic Press, New York, 1976. With two chapters ("Depth decomposition theorem" and "Complexity of semigroups and morphisms") by Bret Tilson, Pure and Applied Mathematics, Vol. 59. Google Scholar
  15. M. Gehrke. Stone duality, topological algebra, and recognition. J. Pure Appl. Algebra, 220(7):2711-2747, 2016. Google Scholar
  16. M. Gehrke, S. Grigorieff, and J.-É. Pin. Duality and equational theory of regular languages. In L. Aceto et al., editor, ICALP 2008, Part II, number 5126 in Lect. Notes Comput. Sci., pages 246-257. Springer, 2008. Google Scholar
  17. M. Gehrke, A. Krebs, and J.-É. Pin. Ultrafilters on words for a fragment of logic. Theoretical Computer Science, 610 A:37-58, 2016. Google Scholar
  18. M. Gehrke, D. Petrisan, and L. Reggio. The Schützenberger product for syntactic spaces. In 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), 2016. Google Scholar
  19. S. J. v. Gool and B. Steinberg. Pro-aperiodic monoids and model theory. Technical report, 2016. URL: http://www.samvangool.net/papers/goolsteinberg2016TR.pdf.
  20. K. Henckell, J. Rhodes, and B. Steinberg. A profinite approach to stable pairs. Internat. J. Algebra Comput., 20(2):269-285, 2010. URL: http://dx.doi.org/10.1142/S0218196710005650.
  21. W. Hodges. Model theory, volume 42 of Encyclopedia of mathematics and its applications. Cambridge University Press, 1993. Google Scholar
  22. M. Huschenbett and M. Kufleitner. Ehrenfeucht-Fraisse Games on Omega-Terms. In STACS, pages 374-385, 2014. Google Scholar
  23. K. Krohn and J. Rhodes. Complexity of finite semigroups. Ann. of Math. (2), 88:128-160, 1968. Google Scholar
  24. M. Lohrey and C. Mathissen. Isomorphism of regular trees and words. Inform. and Comput., 224:71-105, 2013. URL: http://dx.doi.org/10.1016/j.ic.2013.01.002.
  25. J. P. McCammond. The solution to the word problem for the relatively free semigroups satisfying T^a = T^a+b with a ≥ 6. Internat. J. Algebra Comput., 1(1):1-32, 1991. URL: http://dx.doi.org/10.1142/S021819679100002X.
  26. J. P. McCammond. Normal forms for free aperiodic semigroups. Int. J. Algebra Comput., 11(5):581-625, 2001. Google Scholar
  27. R. McNaughton and S. Papert. Counter-free automata. Number 65 in M.I.T. Research Monograph. M.I.T. Press, 1971. Google Scholar
  28. J.-É. Pin. The dot-depth hierarchy, 45 years later. Preprint available from the author’s homepage. Google Scholar
  29. T. Place and M. Zeitoun. Going Higher in the First-Order Quantifier Alternation Hierarchy on Words. In Proceedings ICALP, 2014. Google Scholar
  30. J. Rhodes and B. Steinberg. The q-theory of Finite Semigroups. Springer, 2009. Google Scholar
  31. J. G. Rosenstein. Linear orderings. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], 1982. Google Scholar
  32. M.-P. Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8:190-194, 1965. Google Scholar
  33. S. Shelah. The monadic theory of order. Ann. of Math. (2), 102(3):379-419, 1975. Google Scholar
  34. M. H. Stone. The Theory of Representation for Boolean Algebras. Trans. Amer. Math. Soc., 74(1):37-111, 1936. Google Scholar
  35. H. Straubing. Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Birkhäuser Boston Inc., Boston, 1994. Google Scholar
  36. H. Straubing and P. Weil. Varieties. In J.-É. Pin, editor, Handbook of automata theory. European Mathematical Society Publishing House, to appear. ArXiv:1502.03951. Google Scholar
  37. J. Väänänen. Pseudo-finite model theory. Mat. Contemp, 24:169-183, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact