A Ramsey Theorem for Finite Monoids

Author Ismaël Jecker



PDF
Thumbnail PDF

File

LIPIcs.STACS.2021.44.pdf
  • Filesize: 0.68 MB
  • 13 pages

Document Identifiers

Author Details

Ismaël Jecker
  • Institute of Science and Technology, Klosterneuburg, Austria

Acknowledgements

I wish to thank Michaël Cadilhac, Emmanuel Filiot and Charles Paperman for their valuable insights concerning Green’s relations.

Cite AsGet BibTex

Ismaël Jecker. A Ramsey Theorem for Finite Monoids. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 44:1-44:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.STACS.2021.44

Abstract

Repeated idempotent elements are commonly used to characterise iterable behaviours in abstract models of computation. Therefore, given a monoid M, it is natural to ask how long a sequence of elements of M needs to be to ensure the presence of consecutive idempotent factors. This question is formalised through the notion of the Ramsey function R_M associated to M, obtained by mapping every k ∈ ℕ to the minimal integer R_M(k) such that every word u ∈ M^* of length R_M(k) contains k consecutive non-empty factors that correspond to the same idempotent element of M. In this work, we study the behaviour of the Ramsey function R_M by investigating the regular 𝒟-length of M, defined as the largest size L(M) of a submonoid of M isomorphic to the set of natural numbers {1,2, …, L(M)} equipped with the max operation. We show that the regular 𝒟-length of M determines the degree of R_M, by proving that k^L(M) ≤ R_M(k) ≤ (k|M|⁴)^L(M). To allow applications of this result, we provide the value of the regular 𝒟-length of diverse monoids. In particular, we prove that the full monoid of n × n Boolean matrices, which is used to express transition monoids of non-deterministic automata, has a regular 𝒟-length of (n²+n+2)/2.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic language theory
Keywords
  • Semigroup
  • monoid
  • idempotent
  • automaton

Metrics

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

References

  1. Félix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis. One-way definability of two-way word transducers. Logical Methods in Computer Science, 14, 2018. URL: https://doi.org/10.23638/LMCS-14(4:22)2018.
  2. Michael Breen. A maximal chain of principal ideals in the semigroup of binary relations on a finite set. In Semigroup Forum, volume 43, pages 63-76. Springer, 1991. Google Scholar
  3. Olexandr Ganyushkin and Volodymyr Mazorchuk. Classical finite transformation semigroups: an introduction, volume 9. Springer Science & Business Media, 2008. Google Scholar
  4. T. E. Hall and Mark V. Sapir. Idempotents, regular elements and sequences from finite semigroups. Discrete Mathematics, 161:151-160, 1996. URL: https://doi.org/10.1016/0012-365X(95)00223-J.
  5. Shaofang Hong. Distribution of cardinalities of row spaces of boolean matrices of order n. Southeast Asian Bulletin of Mathematics, 24:51-64, 2000. Google Scholar
  6. Janusz Konieczny. On cardinalities of row spaces of boolean matrices. In Semigroup Forum, volume 44, pages 393-402. Springer, 1992. Google Scholar
  7. Wen Li and Mou-Cheng Zhang. On konieczny’s conjecture of boolean matrices. In Semigroup Forum, volume 50, pages 37-58. Springer, 1995. Google Scholar
  8. Filip Mazowiecki and Cristian Riveros. Pumping lemmas for weighted automata. In Rolf Niedermeier and Brigitte Vallée, editors, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, volume 96 of LIPIcs, pages 50:1-50:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.50.
  9. A. Mukherjea and R. Chaudhuri. Idempotent boolean matrices. Semigroup forum, 21:273-282, 1980. URL: http://eudml.org/doc/134452.
  10. Anca Muscholl and Gabriele Puppis. The many facets of string transducers (invited talk). In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, volume 126 of LIPIcs, pages 2:1-2:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.2.
  11. Jean-Éric Pin. Mathematical foundations of automata theory. Lecture notes LIAFA, Université Paris, 7, 2010. Google Scholar
  12. Michael O. Rabin and Dana S. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3:114-125, 1959. URL: https://doi.org/10.1147/rd.32.0114.
  13. F. P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society, s2-30(1):264-286, 1930. URL: https://doi.org/10.1112/plms/s2-30.1.264.
  14. Marcel-Paul Schützenberger. Une théorie algébrique du codage. Séminaire Dubreil. Algebre et théorie des nombres, 9:1-24, 1955. Google Scholar
  15. Marcel Paul Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8:190-194, 1965. URL: https://doi.org/10.1016/S0019-9958(65)90108-7.
  16. Imre Simon. Factorization forests of finite height. Theor. Comput. Sci., 72:65-94, 1990. URL: https://doi.org/10.1016/0304-3975(90)90047-L.
  17. M-C Zhang, S-F Hong, and H-B Kan. On the cardinalities of the row spaces of non-full rank boolean matrices. In Semigroup Forum, volume 59, pages 152-154. Springer, 1999. 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