On the structure of bispecial Sturmian words |
| |
Authors: | Gabriele Fici |
| |
Affiliation: | Dipartimento di Matematica e Informatica, Università di Palermo, Via Archirafi 34, 90123 Palermo, Italy |
| |
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 palindromic bispecial Sturmian words are precisely the maximal internal factors of primitive Christoffel words. We extend this result by showing that bispecial Sturmian words are precisely the maximal internal factors of 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. |
| |
Keywords: | Sturmian words Christoffel words Special factors Minimal forbidden words Enumerative formula |
本文献已被 ScienceDirect 等数据库收录! |
|