6533b836fe1ef96bd12a14c9
RESEARCH PRODUCT
On the Structure of Bispecial Sturmian Words
Gabriele Ficisubject
FOS: Computer and information sciencesGeneral Computer ScienceSpecial factorDiscrete Mathematics (cs.DM)Computer Networks and CommunicationsApproximations of πFormal Languages and Automata Theory (cs.FL)Computer Science - Formal Languages and Automata TheoryEnumerative formula68R15Characterization (mathematics)Minimal forbidden wordTheoretical Computer ScienceCombinatoricsComputer Science::Discrete MathematicsEuclidean geometryPhysics::Atomic PhysicsMathematicsChristoffel symbolsApplied MathematicsPalindromeSturmian wordSturmian wordComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Combinatorics on wordsComputational Theory and MathematicsWord (group theory)Computer Science::Formal Languages and Automata TheoryChristoffel wordComputer Science - Discrete Mathematicsdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2013-11-19 |