Coloring factors of substitutive infinite words

DOI10.1016/J.DISC.2016.09.013MaRDI QIDQ729779zbMATH OpenOpenAlexFDO

Authors André Bernardino, Rui Pacheco, Manuel Silva

Publication date 22 December 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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$.

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

Cites work

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

Cited in

(3)

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

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)