Paper Info
Title
Some combinatorial properties of Sturmian words
Abstract
In this paper we give a characterization of finite Sturmian words, by palindrome words, which generalizes a property of the Fibonacci words. We prove that the set St of finite Sturmian words coincides with the set of the factors of all the words w such that w = AB = Cxy with A, B, C palindromes, x , y ϵ{ a,b } and x ≠ y . Moreover, using this result we prove that St is equal to the set of the factors of all words w having two periods p and q which are coprimes and such that | w | ⩾ p + q − 2. Several other combinatorial properties concerning special and bispecial elements of St are shown. As a consequence we give a new, and purely combinatorial, proof of the enumeration formula of St .
Year
DOI
Venue
1994
10.1016/0304-3975(94)00035-H
Theor. Comput. Sci.
Keywords
DocType
Volume
combinatorial property,Sturmian word
Journal
136
Issue
ISSN
Citations 
2
Theoretical Computer Science
92
PageRank 
References 
Authors
17.46
3
2
Name
Order
Citations
PageRank
Aldo De Luca11390557.58
Filippo Mignosi256999.71