Sturmian words, Lyndon words and trees

DOI10.1016/S0304-3975(96)00101-6zbMath0901.68155OpenAlexW1971237591WikidataQ59487320 ScholiaQ59487320MaRDI QIDQ1391533

Publication date: 22 July 1998

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00101-6

zbMATH Keywords

binary trees combinatorial properties

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (76)

An output-sensitive algorithm to compute the normal vector of a digital plane ⋮ The Characterization of Rational Numbers Belonging to a Minimal Path in the Stern-Brocot Tree According to a Second Order Balancedness ⋮ Novel results on the number of runs of the Burrows-Wheeler-transform ⋮ Lyndon + Christoffel = digitally convex ⋮ Moments of conjugacy classes of binary words ⋮ Two equivalence relations on digital lines with irrational slopes. A continued fraction approach to upper mechanical words ⋮ On a generalization of Christoffel words: epichristoffel words ⋮ Reversals and palindromes in continued fractions ⋮ A geometrical characterization of factors of multidimensional billiard words and some applications ⋮ Perfectly clustering words are primitive positive elements of the free group ⋮ Viennot factorization of infinite words ⋮ Markov word patterns and a relation on \(\alpha\)-words ⋮ On the structure of bispecial Sturmian words ⋮ Convex digital polygons, maximal digital straight segments and convergence of discrete geometric estimators ⋮ Plain and Twisted Adjoints of Well-Formed Words ⋮ Regions and Standard Modes ⋮ Farey codes and languages ⋮ Counting Lyndon factors ⋮ A periodicity result of partial words with one hole ⋮ Reversible Christoffel factorizations ⋮ Lyndon words and Fibonacci numbers ⋮ Standard Sturmian morphisms ⋮ Convexity preserving deformations of digital sets: characterization of removable and insertable pixels ⋮ On prefixal factorizations of words ⋮ Euclidean strings ⋮ Cluster duality between Calkin-Wilf tree and Stern-Brocot tree ⋮ \(\alpha\)-words and the radix order ⋮ Sturmian and Episturmian Words ⋮ A standard correspondence on epicentral words ⋮ Palindromes and Sturmian words ⋮ Sturmian morphisms and \(\alpha\)-words ⋮ A combinatorial view on string attractors ⋮ Lyndon factorization of the Prouhet words. ⋮ Graph connectivity, partial words, and a theorem of Fine and Wilf ⋮ On generating binary words palindromically ⋮ Substitutions on two letters, cutting segments and their projections ⋮ Multiplicative analogue of Markoff-Lagrange spectrum and Pisot numbers ⋮ On an involution of Christoffel words and Sturmian morphisms ⋮ MINIMAL DUVAL EXTENSIONS ⋮ A characterization of Sturmian words by return words ⋮ Periodic scheduling of marked graphs using balanced binary words ⋮ Discrete segments of \(\mathbb{Z}^3\) constructed by synchronization of words ⋮ Involutions of epicentral words ⋮ Codes of central Sturmian words ⋮ Palindromic factors of billiard words ⋮ Minimal non-convex words ⋮ Some characterizations of finite Sturmian words. ⋮ Factors of characteristic words of irrational numbers ⋮ Standard factors of Sturmian words ⋮ On Christoffel and standard words and their derivatives ⋮ A characterization of Sturmian sequences by indistinguishable asymptotic pairs ⋮ Sturmian morphisms, the braid group \(B_4\), Christoffel words and bases of \(F_2\) ⋮ A palindromization map on free monoids ⋮ Combinatorial View of Digital Convexity ⋮ On Christoffel classes ⋮ A conjecture on continued fractions ⋮ On Sturmian and episturmian words, and related topics ⋮ Two linear-time algorithms for computing the minimum length polygon of a digital contour ⋮ On a graph connecting hyperbinary expansions ⋮ Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour ⋮ Analytical description of digital intersections: minimal parameters and multiscale representation ⋮ Harmonic and gold Sturmian words ⋮ Ionian theorem ⋮ Christoffel Words and Markoff Triples: An Algebraic Approach ⋮ An alternative approach to generalized Pythagorean scales. Generation and properties derived in the frequency domain ⋮ SOME EXTREMAL PROPERTIES OF THE FIBONACCI WORD ⋮ On the combinatorics of finite words ⋮ Lyndon words and singular factors of sturmian words ⋮ Fine and Wilf's theorem for three periods and a generalization of Sturmian words ⋮ Further steps on the reconstruction of convex polyominoes from orthogonal projections ⋮ Second Order Balance Property on Christoffel Words ⋮ Sturmian words and the Stern sequence ⋮ A combinatorial problem on trapezoidal words. ⋮ On low-complexity bi-infinite words and their factors ⋮ On a group theoretic generalization of the Morse-Hedlund theorem ⋮ Studies on finite Sturmian words

Cites Work

This page was built for publication: Sturmian words, Lyndon words and trees