A Ramsey Characterisation of Eventually Periodic Words
| Autor: | Maria‐Romina Ivan, Imre Leader, Luca Q. Zamboni |
|---|---|
| Přispěvatelé: | Ivan, Maria [0000-0003-0817-3777], Apollo - University of Cambridge Repository |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: | |
| Popis: | A factorisation $x = u_1 u_2 \cdots$ of an infinite word $x$ on alphabet $X$ is called `monochromatic', for a given colouring of the finite words $X^*$ on alphabet $X$, if each $u_i$ is the same colour. Wojcik and Zamboni proved that the word $x$ is periodic if and only if for every finite colouring of $X^*$ there is a monochromatic factorisation of $x$. On the other hand, it follows from Ramsey's theorem that, for \textit{any} word $x$, for every finite colouring of $X^*$ there is a suffix of $x$ having a monochromatic factorisation. A factorisation $x = u_1 u_2 \cdots$ is called `super-monochromatic' if each word $u_{k_1} u_{k_2} \cdots u_{k_n}$, where $k_1 < \cdots < k_n$, is the same colour. Our aim in this paper is to show that a word $x$ is eventually periodic if and only if for every finite colouring of $X^*$ there is a suffix of $x$ having a super-monochromatic factorisation. Our main tool is a Ramsey result about alternating sums that may be of independent interest. 19 pages, 4 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|