Online citations, reference lists, and bibliographies.

Combinatorics On Words

J. Karhumäki, A. Lepistö, L. Zamboni
Published 2013 · Computer Science

Cite This
Download PDF
Analyze on Scholarcy
Arnoux-Rauzy words are one possible generalization of Sturmian words. They are infinite words with exactly one left special factor and one right special factor of each length, those special factors being extendable with any letter in the alphabet. Sturmian words are exactly binary Arnoux-Rauzy words. We are interested here in the language of an Arnoux-Rauzy word, not in the word itself. Just as the language of a Sturmian word depends only on the associated slope, or equivalently on its continued fraction expansion, the language of an Arnoux-Rauzy word is defined by the associated directive sequence. A classical property of Sturmian words is that they are 1-balanced: any two factors u and v of the same length of a given Sturmian word contain almost the same number of occurrences of any given letter, the difference being at most 1. Actually, this turns out to be a characterization of Sturmian words: an aperiodic infinite binary word is Sturmian if and only if it is balanced. For Arnoux-Rauzy words, the situation is quite different. It was expected however that they would be C-balanced for some constant C (the maximum allowed difference in the number of occurrences), but we proved [1] that it is not the case, constructing an Arnoux-Rauzy word which is not C-balanced for any C. This was further improved in [2], where a large class of such words is given. On the other hand, it is easy to construct 2-balanced infinite words that are not Arnoux-Rauzy. The question of characterizing Arnoux-Rauzy words with a given balance arises then naturally. We restrict here to 2-balance and a ternary alphabet, but even so it does not seem an easy problem. In [3] we obtained a sufficient condition, as well as a necessary condition, both of the type: the set of prefixes of the directive sequence is in a certain rational language. We were able to obtain a characterization [4], at the expense of replacing C-balance with a stronger notion, strong C-balance. Also, we proved that the set of prefixes of directive sequences of 2-balanced ternary Arnoux-Rauzy words does not form a rational language. Therefore, a characterization of 2-balanced ternary Arnoux-Rauzy in terms of rational languages only is not possible.
This paper references
Generation and recognition of digital planes using multi-dimensional continued fractions
Thomas Fernique (2009)
Atomic surfaces, tilings and coincidences II. Reducible case
H. Rao (2007)
Substitutions in dynamics, arithmetics, and combinatorics
V. Berthé (2002)
Tilings associated with beta-numeration and substitutions.
V. Berthé (2005)
Pisot property for the Brun and fully subtractive algorithms (preprint
A. Avila (2013)
Nombres algébriques et substitutions
G. Rauzy (1982)
Substitutive Arnoux-Rauzy sequences have pure discrete spectrum
V. Berthé (2011)
Multidimensional Continued Fractions
F. Schweiger (2000)
Pisot substitutions and Rauzy fractals
P. Arnoux (2001)
Critical Connectedness of Thin Arithmetical Discrete Planes
V. Berthé (2013)
Finite beta-expansions
C. Frougny (1992)
The condition for the generation of the stepped surfaces in terms of the modified Jacobi-Perron algorithm (preprint
M. Furukado (2013)
Une application des nombres de Pisot à l'algorithme de Jacobi-Perron
R. P. Roux (1984)
Tilings with S-adic Rauzy fractals (preprint
V. Berthé (2013)
Connectedness of fractals associated with Arnoux-Rauzy substitutions
Valérie Berthé (2014)
Parallelogram Tilings and Jacobi-Perron Algorithm
S. Ito (1994)
Algorithmes euclidiens pour trois et quatre nombres
V. Brun (1957)
F. Thomas (2006)

Semantic Scholar Logo Some data provided by SemanticScholar