Rigidity and Substitutive Dendric Words
| Autor: | Fabien Durand, Dominique Perrin, Francesco Dolce, Julien Leroy, Valérie Berthé |
|---|---|
| Přispěvatelé: | 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) |
| Rok vydání: | 2018 |
| Předmět: |
Left and right
[MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS] 010102 general mathematics Substitution (logic) Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Rigidity (psychology) 0102 computer and information sciences Extension (predicate logic) S-adic word 01 natural sciences Combinatorics 010201 computation theory & mathematics Rigidity Computer Science (miscellaneous) Bipartite graph Topological eigenvalue Dendric word 0101 mathematics Substitution Computer Science::Formal Languages and Automata Theory Mathematics |
| Zdroj: | 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⟩ |
| ISSN: | 1793-6373 0129-0541 |
| DOI: | 10.1142/s0129054118420017 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|