Sturmian words and the Stern sequence

Central, standard, and Christoffel words are three strongly interrelated classes of binary finite words which represent a finite counterpart to characteristic Sturmian words. A natural arithmetization of the theory is obtained by representing central and Christoffel words by irreducible fractions la...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2015-05, Vol.581, p.26-44
Main Authors: de Luca, Aldo, De Luca, Alessandro
Format: Article
Language:English
Subjects:
Central word
Christoffel word
Combinatorial analysis
Computer simulation
Inequalities
Marking
Mathematical analysis
Mathematical models
Raney tree
Standard word
Stern sequence
Sturmian word
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Central, standard, and Christoffel words are three strongly interrelated classes of binary finite words which represent a finite counterpart to characteristic Sturmian words. A natural arithmetization of the theory is obtained by representing central and Christoffel words by irreducible fractions labeling, respectively, two binary trees, the Raney (or Calkin–Wilf) tree and the Stern–Brocot tree. The sequence of denominators of the fractions in the Raney tree is the famous Stern diatomic numerical sequence. An interpretation of the terms s(n) of Stern's sequence as lengths of Christoffel words when n is odd, and as minimal periods of central words when n is even, allows one to interpret several results on Christoffel and central words in terms of Stern's sequence and, conversely, to obtain new insight into the combinatorics of Christoffel and central words. One of our main results is a non-commutative version of the “alternating bit sets theorem” by Calkin and Wilf. We also study the length distribution of Christoffel words corresponding to nodes of equal height in the tree, obtaining some interesting bounds and inequalities.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2015.02.043