Back to Search
Start Over
Rigidity and Substitutive Dendric Words
- 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.
- Subjects :
- 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
Subjects
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