A Ramsey Theorem for semigroups

ABSTRACT. In automata theory, it is useful to expose patterns that can be iterated. Depending on the model considered, having a loop (repetition of the same state) along a computation might not be sufficient to ensure good properties once the loop is iterated. This is sometimes solved by requiring an idempotent structure of either the corresponding element of the transition monoid of the automaton, or, in the case of transducers, of the output produced along the loop. In this talk, we will consider the following problem. Given a semigroup S and an integer λ, we would like to expose a bound B such that every sequence of elements of S that has a length greater than B admits λ consecutive factors corresponding to the same idempotent element of S. This question can be answered by applying Ramsey’s theorem, or Simon’s factorisation forest theorem. However, this yields bounds that are exponential with respect to the size of S. We improve this result by exposing a new bound that is exponential with respect to the size of the maximal J-chain of S. For some semigroups, this matches the previous bounds, but we will see that there exist semigroups where the new bound is exponentially better (groups, transformation monoids, substitution monoids). Finally, we show how this result can be used to obtain pumping Lemmas for regular relations, i. e. , relations definable by non-deterministic streaming string transducers.

Authors

• Ismaël Jecker

Keywords

No keywords are indexed for this paper.