[{"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"month":"03","article_processing_charge":"No","title":"A Ramsey theorem for finite monoids","type":"conference","abstract":[{"lang":"eng","text":"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."}],"citation":{"ista":"Jecker IR. 2021. A Ramsey theorem for finite monoids. 38th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 187, 44.","ama":"Jecker IR. A Ramsey theorem for finite monoids. In: <i>38th International Symposium on Theoretical Aspects of Computer Science</i>. Vol 187. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.44\">10.4230/LIPIcs.STACS.2021.44</a>","ieee":"I. R. Jecker, “A Ramsey theorem for finite monoids,” in <i>38th International Symposium on Theoretical Aspects of Computer Science</i>, Saarbrücken, Germany, 2021, vol. 187.","mla":"Jecker, Ismael R. “A Ramsey Theorem for Finite Monoids.” <i>38th International Symposium on Theoretical Aspects of Computer Science</i>, vol. 187, 44, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.44\">10.4230/LIPIcs.STACS.2021.44</a>.","apa":"Jecker, I. R. (2021). A Ramsey theorem for finite monoids. In <i>38th International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 187). Saarbrücken, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.44\">https://doi.org/10.4230/LIPIcs.STACS.2021.44</a>","chicago":"Jecker, Ismael R. “A Ramsey Theorem for Finite Monoids.” In <i>38th International Symposium on Theoretical Aspects of Computer Science</i>, Vol. 187. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.44\">https://doi.org/10.4230/LIPIcs.STACS.2021.44</a>.","short":"I.R. Jecker, in:, 38th International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021."},"article_number":"44","oa_version":"Published Version","department":[{"_id":"KrCh"}],"publication":"38th International Symposium on Theoretical Aspects of Computer Science","has_accepted_license":"1","doi":"10.4230/LIPIcs.STACS.2021.44","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","file_date_updated":"2021-10-01T09:55:00Z","scopus_import":"1","acknowledgement":"This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411. I wish to thank Michaël Cadilhac, Emmanuel Filiot and Charles Paperman for their valuable insights concerning Green’s relations.","conference":{"end_date":"2021-03-19","name":"STACS: Symposium on Theoretical Aspects of Computer Science","start_date":"2021-03-16","location":"Saarbrücken, Germany"},"day":"10","_id":"10055","ddc":["000"],"oa":1,"status":"public","language":[{"iso":"eng"}],"external_id":{"isi":["000635691700044"]},"date_published":"2021-03-10T00:00:00Z","date_created":"2021-09-27T14:33:15Z","author":[{"first_name":"Ismael R","last_name":"Jecker","id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","full_name":"Jecker, Ismael R"}],"date_updated":"2025-05-14T10:55:11Z","year":"2021","publication_status":"published","volume":187,"ec_funded":1,"alternative_title":["LIPIcs"],"file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","success":1,"file_size":720250,"checksum":"17432a05733f408de300e17e390a90e4","file_name":"2021_LIPIcs_Jecker.pdf","date_created":"2021-10-01T09:55:00Z","creator":"cchlebak","date_updated":"2021-10-01T09:55:00Z","file_id":"10063"}],"publication_identifier":{"isbn":["978-3-9597-7180-1"],"issn":["1868-8969"]},"license":"https://creativecommons.org/licenses/by/4.0/","intvolume":"       187","isi":1}]