[{"quality_controlled":"1","year":"2021","date_created":"2021-09-27T14:33:15Z","date_updated":"2023-08-14T07:03:23Z","project":[{"call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"volume":187,"file":[{"content_type":"application/pdf","date_created":"2021-10-01T09:55:00Z","file_id":"10063","success":1,"access_level":"open_access","date_updated":"2021-10-01T09:55:00Z","file_name":"2021_LIPIcs_Jecker.pdf","file_size":720250,"creator":"cchlebak","relation":"main_file","checksum":"17432a05733f408de300e17e390a90e4"}],"isi":1,"article_processing_charge":"No","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"publication_identifier":{"isbn":["978-3-9597-7180-1"],"issn":["1868-8969"]},"scopus_import":"1","doi":"10.4230/LIPIcs.STACS.2021.44","publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","language":[{"iso":"eng"}],"file_date_updated":"2021-10-01T09:55:00Z","type":"conference","license":"https://creativecommons.org/licenses/by/4.0/","conference":{"start_date":"2021-03-16","name":"STACS: Symposium on Theoretical Aspects of Computer Science","end_date":"2021-03-19","location":"Saarbrücken, Germany"},"external_id":{"isi":["000635691700044"]},"oa_version":"Published Version","date_published":"2021-03-10T00:00:00Z","publication":"38th International Symposium on Theoretical Aspects of Computer Science","ddc":["000"],"author":[{"id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","full_name":"Jecker, Ismael R","first_name":"Ismael R","last_name":"Jecker"}],"ec_funded":1,"article_number":"44","status":"public","abstract":[{"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.","lang":"eng"}],"day":"10","has_accepted_license":"1","citation":{"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>.","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>","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.","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>.","short":"I.R. Jecker, in:, 38th International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.","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>"},"intvolume":"       187","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"10055","month":"03","oa":1,"title":"A Ramsey theorem for finite monoids","publication_status":"published","department":[{"_id":"KrCh"}],"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.","alternative_title":["LIPIcs"]}]