Sturmian words and the Stern sequence

DOI10.1016/J.TCS.2015.02.043zbMATH Open1321.68395arXiv1410.4085OpenAlexW2004319476MaRDI QIDQ2345447FDOQ2345447

Authors: Aldo De Luca, Alessandro De Luca 

Publication date: 22 May 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Central, standard, and Christoffel words are three strongly interrelated classes of binary finite words which represent a finite counterpart of 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 Raney's 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 a new insight in the combinatorics of Christoffel and central words by using properties of Stern's sequence. 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.

Full work available at URL: https://arxiv.org/abs/1410.4085

Recommendations

• Sturmian sequences and the lexicographic world
• Sturmian words: structure, combinatorics, and their arithmetics
• Some combinatorial properties of Sturmian words
• scientific article; zbMATH DE number 1254095
• On the permutations generated by Sturmian words
• Sturmian words and words with a critical exponent
• scientific article; zbMATH DE number 1086496
• On a combinatorial property of Sturmian words
• scientific article; zbMATH DE number 1783022
• Studies on finite Sturmian words

zbMATH Keywords

Stern-Brocot treecentral wordChristoffel wordstandard Sturmian wordCalkin-Wilf theoremRaney treeStern's sequence

Mathematics Subject Classification ID

Special sequences and polynomials (11B83) Combinatorics on words (68R15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Certain words on the real projective line
• Sturmian words: structure, combinatorics, and their arithmetics
• Sturmian words, Lyndon words and trees
• On continued fractions and finite automata
• Episturmian words and some constructions of de Luca and Rauzy
• Combinatorics on Words
• Sturmian and Episturmian Words
• Some combinatorial properties of Sturmian words
• On an involution of Christoffel words and Sturmian morphisms
• Pseudopalindrome closure operators in free monoids
• Stern's diatomic sequence \(0, 1, 1, 2, 1, 3, 2, 3, 1, 4, \dots \)
• A pattern sequence approach to Stern's sequence
• A palindromization map for the free group
• On graphs of central episturmian words
• A standard correspondence on epicentral words
• Episturmian morphisms and a Galois theorem on continued fractions
• Involutions of epicentral words
• Codes of central Sturmian words
• On a paper by Castelli, Mignosi, Restivo
• Recounting the Rationals
• Christoffel words and the Calkin-Wilf tree
• A generalized palindromization map in free monoids
• Title not available (Why is that?)
• Some extremal properties of the Fibonacci word

Cited In (11)

• Reversible Christoffel factorizations
• Codes of central Sturmian words
• A pattern sequence approach to Stern's sequence
• A First Investigation of Sturmian Trees
• A note on Sturmian words
• Three distance theorems and Sturmian sequences: length governing words
• On Christoffel and standard words and their derivatives
• Sturmian words and words with a critical exponent
• Studies on finite Sturmian words
• Christoffel words and the Calkin-Wilf tree
• Sturmian trees

Uses Software

• OEIS

This page was built for publication: Sturmian words and the Stern sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2345447)