Coloring factors of substitutive infinite words

DOI10.1016/J.DISC.2016.09.013zbMATH Open1351.05220arXiv1605.09343OpenAlexW2963640332MaRDI QIDQ729779FDOQ729779

Authors: André Bernardino, Rui Pacheco, Manuel Silva 

Publication date: 22 December 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: In this paper, we consider infinite words that arise as fixed points of primitive substitutions on a finite alphabet and finite colorings of their factors. Any such infinite word exhibits a "hierarchal structure" that will allow us to define, under the additional condition of strong recognizability, certain remarkable finite colorings of its factors. In particular, we generalize two combinatorial results by Justin and Pirillo concerning arbitrarily large monochromatic $k$-powers occurring in infinite words, in view of a recent paper by de Luca, Pribavkina and Zamboni, we will give new examples of classes of infinite words $mathbfu$ and finite colorings that do not allow infinite monochromatic factorizations $mathbfu=mathbf{u}_{1}mathbf{u}_{2}mathbf{u}_{3}ldots$.

Full work available at URL: https://arxiv.org/abs/1605.09343

Recommendations

• On some variations of coloring problems of infinite words
• A coloring problem for infinite words
• Coloring problems for infinite words
• On subwords of infinite words
• On colorings of variable words
• scientific article; zbMATH DE number 3850488
• On sets of indefinitely desubstitutable words
• On the subword equivalence problem for infinite words
• scientific article; zbMATH DE number 1943973
• On a class of infinite words with affine factor complexity

zbMATH Keywords

combinatorics on wordsRamsey theoryrecognizabilitysubstitutive words

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorics on words (68R15) Ramsey theory (05D10)

Cites Work

• Substitution dynamical systems - spectral analysis
• Valeurs propres des systèmes dynamiques définis par des substitutions de longueur variable
• Strongly non-repetitive sequences and progression-free sets
• Reconnaissabilité des substitutions et complexité des suites automatiques
• Characterization of the repetitive commutative semigroups
• On prefixal factorizations of words
• Two combinatorial properties of partitions of the free semigroup into finitely many parts
• A coloring problem for infinite words
• Minimal flows arising from substitutions of non-constant length

Cited In (3)

• On prefixal factorizations of words
• Coloring problems for infinite words
• Monochromatic factorizations of words and periodicity

This page was built for publication: Coloring factors of substitutive infinite words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q729779)