Back to Search Start Over

Rigidity and Substitutive Dendric Words

Authors :
Fabien Durand
Dominique Perrin
Francesco Dolce
Julien Leroy
Valérie Berthé
Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243))
Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)
Laboratoire de combinatoire et d'informatique mathématique [Montréal] (LaCIM)
Université du Québec à Montréal = University of Québec in Montréal (UQAM)-Centre de Recherches Mathématiques [Montréal] (CRM)
Université de Montréal (UdeM)-Université de Montréal (UdeM)
Laboratoire Amiénois de Mathématique Fondamentale et Appliquée - UMR CNRS 7352 (LAMFA)
Université de Picardie Jules Verne (UPJV)-Centre National de la Recherche Scientifique (CNRS)
Université de Liège
Laboratoire d'Informatique Gaspard-Monge (LIGM)
Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM)
Université du Québec à Montréal (UQAM)
Laboratoire d'Informatique Gaspard-Monge (ligm)
Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)
Laboratoire Amiénois de Mathématique Fondamentale et Appliquée (LAMFA)
Centre de Recherches Mathématiques [Montréal] (CRM)
Université de Montréal (UdeM)-Université de Montréal (UdeM)-Université du Québec à Montréal = University of Québec in Montréal (UQAM)
Source :
International Journal of Foundations of Computer Science, International Journal of Foundations of Computer Science, World Scientific Publishing, 2018, 29 (05), pp.705-720. ⟨10.1142/S0129054118420017⟩
Publication Year :
2018
Publisher :
World Scientific Pub Co Pte Lt, 2018.

Abstract

International audience; Received (Day Month Year) Accepted (Day Month Year) Communicated by (xxxxxxxxxx) Dendric words are infinite words that are defined in terms of extension graphs. These are bipartite graphs that describe the left and right extensions of factors. Dendric words are such that all their extension graphs are trees. They are also called tree words. This class of words includes classical families of words such as Sturmian words, codings of interval exchanges, or else, Arnoux-Rauzy words. We investigate here the properties of substitutive dendric words and prove some rigidity properties, that is, algebraic properties on the set of substitutions that fix a dendric word. We also prove that aperiodic minimal dendric subshifts (generated by dendric words) cannot have rational topological eigenvalues, and thus, cannot be generated by constant length substitutions.

Details

ISSN :
17936373 and 01290541
Volume :
29
Database :
OpenAIRE
Journal :
International Journal of Foundations of Computer Science
Accession number :
edsair.doi.dedup.....6e881ea6a47866cc15f3d8fa4a9e7ba1
Full Text :
https://doi.org/10.1142/s0129054118420017