On the structure of bispecial Sturmian words
From MaRDI portal
Publication:2637643
DOI10.1016/J.JCSS.2013.11.001zbMATH Open1285.68132arXiv1311.4904OpenAlexW2056235565MaRDI QIDQ2637643FDOQ2637643
Authors: Gabriele Fici 
Publication date: 13 February 2014
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1311.4904
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
- Balanced words
- Title not available (Why is that?)
- Sturmian words: structure, combinatorics, and their arithmetics
- Sturmian words, Lyndon words and trees
- Title not available (Why is that?)
- Enumeration and structure of trapezoidal words
- Some combinatorial properties of Sturmian words
- Words and forbidden factors
- Title not available (Why is that?)
- Minimal forbidden words and symbolic dynamics
- Forbidden words in symbolic dynamics
- On the number of factors of Sturmian words
- Complexity of sequences defined by billiard in the cube
- Episturmian words: a survey
- An arithmetic and combinatorial approach to three-dimensional discrete lines
- Burrows-Wheeler transform and Sturmian words
- Title not available (Why is that?)
- Using minimal absent words to build phylogeny
- Complementing and exactly covering sequences
- Uniformly balanced words with linear complexity and prescribed letter frequencies
- Suffix Automata and Standard Sturmian Words
- A characterization of balanced episturmian sequences
- A Characterization of Bispecial Sturmian Words
- Balanced sequences and optimal routing
- Special factors and the combinatorics of suffix and factor automata
- Partitioning the positive integers to seven Beatty sequences
- Developments in Language Theory
Cited In (10)
- Title not available (Why is that?)
- The sequence of open and closed prefixes of a Sturmian word
- On bispecial factors of the Thue-Morse word
- Ergodic infinite permutations of minimal complexity
- Some results on digital segments and balanced words
- On braid words and irreflexivity
- A Characterization of Bispecial Sturmian Words
- Studies on finite Sturmian words
- Sturmian numeration systems and decompositions to palindromes
- Extremal values of semi‐regular continuants and codings of interval exchange transformations
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)
