# zbMATH — the first resource for mathematics

Some combinatorial properties of Sturmian words. (English) Zbl 0874.68245
Summary: 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\in {a, b}$$ and $$x\neq 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|\geq 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$$.

##### MSC:
 68R15 Combinatorics on words 05A15 Exact enumeration problems, generating functions
Full Text:
##### References:
  Berstel, J.; Pocchiola, M., A geometric proof of the enumeration formula for Sturmian words, Internat. J. algebra comput., 3, 349-355, (1993) · Zbl 0802.68099  de Luca, A., A combinatorial property of the Fibonacci word, Inform. process. lett., 12, 193-195, (1981)  Dulucq, S.; Gouyou-Beauchamps, D., Sur LES facteurs des suites de Sturm, Theoret. comput. sci., 71, 381-400, (1990) · Zbl 0694.68048  Fine, N.J.; Wilf, H.S., Uniqueness theorems for periodic functions, Proc. amer. math. soc., 16, 109-114, (1965) · Zbl 0131.30203  Hedlund, G.A., Sturmian minimal sets, Amer. J. math., 66, 605-620, (1944) · Zbl 0063.01982  Knuth, D.E.; Morris, J.H.; Pratt, V.R., Fast pattern matching in strings, SIAM J. comput., 6, 323-350, (1977) · Zbl 0372.68005  Lothaire, M., Combinatorics on words, (1983), Addison-Wesley Reading, MA · Zbl 0514.20045  Mignosi, F., Infinite words with linear subword complexity, Theoret. comput. sci., 65, 221-242, (1989) · Zbl 0682.68083  Mignosi, F., On the number of factors of Sturmian words, Theoret. comput. sci., 82, 71-84, (1991) · Zbl 0728.68093  Pedersen, A., Solution of problem E 3156, Amer. math. monthly, 95, 954-955, (1988)  Rauzy, G., Mots infinis en arithmétique, (), 165-171, Lecture Notes in Computer Science · Zbl 0613.10044  Robinson, R.M., Problem E 3156, Amer. math. monthly, 93, 482, (1986)  Venkov, B.A., Elementary number theory, (1970), Wolters-Noordhoff Groningen · Zbl 0204.37101
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.