Monochromatic arithmetic progressions in binary Thue–Morse-like words
Journal article
Authors | Aedo, I., Grimm, U., Nagai, Y. and Staynova, P. |
---|---|
Abstract | We study the length of monochromatic arithmetic progressions in the Thue–Morse word and in a class of generalised Thue–Morse words. In particular, we give exact values or upper bounds for the lengths of monochromatic arithmetic progressions of given fixed differences inside these words. Some arguments for these are inspired by van der Waerden's proof for the existence of arbitrary long monochromatic arithmetic progressions in any finite colouring of the (positive) integers. We also establish upper bounds for the length of monochromatic arithmetic progressions of certain differences in any fixed point of a primitive binary bijective substitution. |
Keywords | Combinatorics on words; Binary language; Infinite word; Thue–Morse sequence; Arithmetic progression; Bijective substitution; Bijective automata |
Year | 2022 |
Journal | Theoretical Computer Science |
Journal citation | 943, pp. 65-80 |
Publisher | Elseiver |
ISSN | 0304-3975 |
Digital Object Identifier (DOI) | https://doi.org/10.1016/j.tcs.2022.08.013 |
Web address (URL) | https://www.sciencedirect.com/science/article/pii/S0304397522004868 |
Accepted author manuscript | File Access Level Open |
Publisher's version | License File Access Level Open |
Output status | Published |
Publication dates | |
Online | 19 Aug 2022 |
Publication process dates | |
Accepted | 12 Aug 2022 |
Deposited | 07 Jul 2023 |
https://repository.derby.ac.uk/item/9y455/monochromatic-arithmetic-progressions-in-binary-thue-morse-like-words
Download files
31
total views26
total downloads0
views this month0
downloads this month