On the structure of bispecial Sturmian words
From MaRDI portal
Publication:2637643
Abstract: A balanced word is one in which any two factors of the same length contain the same number of each letter of the alphabet up to one. Finite binary balanced words are called Sturmian words. A Sturmian word is bispecial if it can be extended to the left and to the right with both letters remaining a Sturmian word. There is a deep relation between bispecial Sturmian words and Christoffel words, that are the digital approximations of Euclidean segments in the plane. In 1997, J. Berstel and A. de Luca proved that emph{palindromic} bispecial Sturmian words are precisely the maximal internal factors of emph{primitive} Christoffel words. We extend this result by showing that bispecial Sturmian words are precisely the maximal internal factors of emph{all} Christoffel words. Our characterization allows us to give an enumerative formula for bispecial Sturmian words. We also investigate the minimal forbidden words for the language of Sturmian words.
Recommendations
- A Characterization of Bispecial Sturmian Words
- Sturmian words: structure, combinatorics, and their arithmetics
- Studies on finite Sturmian words
- On a combinatorial property of Sturmian words
- On the Lie complexity of Sturmian words
- On the arithmetical complexity of Sturmian words
- Some characterizations of finite Sturmian words.
- Some combinatorial properties of Sturmian words
- On minimal Sturmian partial words
- On minimal Sturmian partial words
Cites work
- scientific article; zbMATH DE number 3885787 (Why is no real title available?)
- scientific article; zbMATH DE number 3657869 (Why is no real title available?)
- scientific article; zbMATH DE number 1222602 (Why is no real title available?)
- scientific article; zbMATH DE number 1737190 (Why is no real title available?)
- A Characterization of Bispecial Sturmian Words
- A characterization of balanced episturmian sequences
- An arithmetic and combinatorial approach to three-dimensional discrete lines
- Balanced sequences and optimal routing
- Balanced words
- Burrows-Wheeler transform and Sturmian words
- Complementing and exactly covering sequences
- Complexity of sequences defined by billiard in the cube
- Developments in Language Theory
- Enumeration and structure of trapezoidal words
- Episturmian words: a survey
- Forbidden words in symbolic dynamics
- Minimal forbidden words and symbolic dynamics
- On the number of factors of Sturmian words
- Partitioning the positive integers to seven Beatty sequences
- Some combinatorial properties of Sturmian words
- Special factors and the combinatorics of suffix and factor automata
- Sturmian words, Lyndon words and trees
- Sturmian words: structure, combinatorics, and their arithmetics
- Suffix Automata and Standard Sturmian Words
- Uniformly balanced words with linear complexity and prescribed letter frequencies
- Using minimal absent words to build phylogeny
- Words and forbidden factors
Cited in
(9)- Studies on finite Sturmian words
- On braid words and irreflexivity
- The sequence of open and closed prefixes of a Sturmian word
- Sturmian numeration systems and decompositions to palindromes
- scientific article; zbMATH DE number 17555 (Why is no real title available?)
- Some results on digital segments and balanced words
- On bispecial factors of the Thue-Morse word
- Extremal values of semi‐regular continuants and codings of interval exchange transformations
- A Characterization of Bispecial Sturmian Words
This page was built for publication: On the structure of bispecial Sturmian words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2637643)
