Coloring factors of substitutive infinite words

André Bernardino; Rui Pacheco; Manuel Silva

doi:10.1016/j.disc.2016.09.013

Coloring factors of substitutive infinite words

André Bernardino, Rui Pacheco, Manuel Silva

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

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 u and finite colorings that do not allow infinite monochromatic factorizations u=u₁u₂u₃….

Original language	English
Pages (from-to)	443-451
Number of pages	9
Journal	Discrete Mathematics
Volume	340
Issue number	3
DOIs	https://doi.org/10.1016/j.disc.2016.09.013
Publication status	Published - Mar 2017

Keywords

Combinatorics on words
Ramsey theory
Recognizability
Substitutive words

Access to Document

10.1016/j.disc.2016.09.013Licence: CC BY-NC-ND

Cite this

@article{dc73c01752934821a1e00aeb9aab97d2,

title = "Coloring factors of substitutive infinite words",

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 u and finite colorings that do not allow infinite monochromatic factorizations u=u1u2u3….",

keywords = "Combinatorics on words, Ramsey theory, Recognizability, Substitutive words",

author = "Andr{\'e} Bernardino and Rui Pacheco and Manuel Silva",

note = "Sem PDF. Center of Mathematics and Applications of Universidade da Beira Interior (UID/MAT/00212/2013) Center of Mathematics and Applications of Universidade Nova de Lisboa (UID/MAT/00297/2013)",

year = "2017",

month = mar,

doi = "10.1016/j.disc.2016.09.013",

language = "English",

volume = "340",

pages = "443--451",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier Science B.V., Inc",

number = "3",

}

TY - JOUR

T1 - Coloring factors of substitutive infinite words

AU - Bernardino, André

AU - Pacheco, Rui

AU - Silva, Manuel

N1 - Sem PDF. Center of Mathematics and Applications of Universidade da Beira Interior (UID/MAT/00212/2013) Center of Mathematics and Applications of Universidade Nova de Lisboa (UID/MAT/00297/2013)

PY - 2017/3

Y1 - 2017/3

N2 - 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 u and finite colorings that do not allow infinite monochromatic factorizations u=u1u2u3….

AB - 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 u and finite colorings that do not allow infinite monochromatic factorizations u=u1u2u3….

KW - Combinatorics on words

KW - Ramsey theory

KW - Recognizability

KW - Substitutive words

UR - http://www.scopus.com/inward/record.url?scp=84995770406&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2016.09.013

DO - 10.1016/j.disc.2016.09.013

M3 - Article

AN - SCOPUS:84995770406

SN - 0012-365X

VL - 340

SP - 443

EP - 451

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 3

ER -

Coloring factors of substitutive infinite words

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this