Some combinatorial properties of Sturmian words

DOI10.1016/0304-3975(94)00035-HzbMath0874.68245OpenAlexW2006661113MaRDI QIDQ1349698

Publication date: 27 February 1997

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

Full work available at URL: https://doi.org/10.1016/0304-3975(94)00035-h

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorics on words (68R15)

Related Items

Bit catastrophes for the Burrows-Wheeler transform ⋮ Words and special factors ⋮ Minimal forbidden factors of circular words ⋮ COMBINATORIAL PROPERTIES OF STURMIAN PALINDROMES ⋮ MULTIPSEUDOPERIODIC WORDS ⋮ Occurrences of palindromes in characteristic Sturmian words ⋮ Exponents of Diophantine approximation in dimension 2 for a general class of numbers ⋮ RECENT RESULTS ON EXTENSIONS OF STURMIAN WORDS ⋮ The sequence of open and closed prefixes of a Sturmian word ⋮ Novel results on the number of runs of the Burrows-Wheeler-transform ⋮ Characterisations of balanced words via orderings ⋮ Moments of conjugacy classes of binary words ⋮ Automata and forbidden words ⋮ On a generalization of Christoffel words: epichristoffel words ⋮ Words that almost commute ⋮ A note on the Markov condition and central words ⋮ Generalized Hausdorff dimensions of sets of real numbers with zero entropy expansion ⋮ Palindromes in the Fibonacci word ⋮ On the structure of bispecial Sturmian words ⋮ Farey codes and languages ⋮ Palindromic prefixes and episturmian words ⋮ Minimal complexity of equidistributed infinite permutations ⋮ Counting Lyndon factors ⋮ A periodicity result of partial words with one hole ⋮ Random generation of finite Sturmian words ⋮ The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words ⋮ \(\alpha\)-words and factors of characteristic sequences ⋮ On Sturmian graphs ⋮ On the conjugation of standard morphisms ⋮ Sturmian words: structure, combinatorics, and their arithmetics ⋮ Words with many palindrome pair factors ⋮ Sturmian words, Lyndon words and trees ⋮ Standard Sturmian morphisms ⋮ A representation theorem of the suffixes of characteristic sequences ⋮ Reprint of: ``Palindromization and construction of Markoff triples ⋮ Euclidean strings ⋮ Sturmian graphs and integer representations over numeration systems ⋮ Weak repetitions in Sturmian strings. ⋮ A new geometric approach to Sturmian words ⋮ Sturmian and Episturmian Words ⋮ Locating factors of a characteristic word via the generalized Zeckendorf representation of numbers ⋮ A standard correspondence on epicentral words ⋮ Palindromes and Sturmian words ⋮ Sturmian morphisms and \(\alpha\)-words ⋮ A combinatorial view on string attractors ⋮ Graph connectivity, partial words, and a theorem of Fine and Wilf ⋮ On generating binary words palindromically ⋮ Fine and Wilf words for any periods ⋮ Decimations and sturmian words ⋮ A remark on morphic sturmian words ⋮ Two-variable word equations ⋮ Standard Sturmian words and automata minimization algorithms ⋮ Combinatorial properties of sequences defined by the billiard in the tesselation triangles ⋮ Frequencies of factors of Sturmian sequences ⋮ A division property of the Fibonacci word ⋮ Cyclic complexity of words ⋮ Generalized Sturmian languages ⋮ On an involution of Christoffel words and Sturmian morphisms ⋮ Sturmian numeration systems and decompositions to palindromes ⋮ Discrete segments of \(\mathbb{Z}^3\) constructed by synchronization of words ⋮ Codes of central Sturmian words ⋮ Minimal non-convex words ⋮ Some characterizations of finite Sturmian words. ⋮ On the number of episturmian palindromes ⋮ Factors of characteristic words of irrational numbers ⋮ Languages under substitutions and balanced words ⋮ Factors of characteristic words: location and decompositions ⋮ Characteristic Sturmian words are extremal for the critical factorization theorem ⋮ On factorially balanced sets of words ⋮ Pseudopalindrome closure operators in free monoids ⋮ 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 ⋮ On \(\theta\)-episturmian words ⋮ Palindromization and construction of Markoff triples ⋮ On Lazy Representations and Sturmian Graphs ⋮ A Challenging Family of Automata for Classical Minimization Algorithms ⋮ Burrows-Wheeler transform and Sturmian words ⋮ On Christoffel classes ⋮ Unbordered factors of the characteristic sequences of irrational numbers ⋮ On Sturmian and episturmian words, and related topics ⋮ Two linear-time algorithms for computing the minimum length polygon of a digital contour ⋮ Harmonic and gold Sturmian words ⋮ Well-balanced sequences ⋮ SOME EXTREMAL PROPERTIES OF THE FIBONACCI WORD ⋮ A NEW COMPLEXITY FUNCTION FOR WORDS BASED ON PERIODICITY ⋮ On graphs of central episturmian words ⋮ On the combinatorics of finite 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 ⋮ Repetitions in Sturmian strings ⋮ Repetitive perhaps, but certainly not boring ⋮ Forbidden words in symbolic dynamics ⋮ Obituary: Aldo de Luca 1941--2018 ⋮ Semiperiodic words and root-conjugacy. ⋮ Second Order Balance Property on Christoffel Words ⋮ Sturmian words and the Stern sequence ⋮ On bispecial factors of the Thue-Morse word ⋮ Words and forbidden factors ⋮ Combinatorial, ergodic and arithmetic properties of the Tribonacci substitution ⋮ On low-complexity bi-infinite words and their factors ⋮ On a group theoretic generalization of the Morse-Hedlund theorem ⋮ Studies on finite Sturmian words ⋮ Asymptotic formula for balanced words

Cites Work