On the structure of bispecial Sturmian words

详细信息    查看全文

• 作者：Gabriele Fici
• 关键词：Sturmian words ; Christoffel words ; Special factors ; Minimal forbidden words ; Enumerative formula
• 刊名：Journal of Computer and System Sciences
• 出版年：June, 2014
• 年：2014
• 卷：80
• 期：4
• 页码：711-719
• 全文大小：314 K

文摘

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.