Test-words for Sturmian morphisms
Gwénaël Richomme · Bulletin of the Belgian Mathematical Society - Simon Stevin · 1999
J. Berstel and P. Séébold have proved that an acyclic morphism f is Sturmian iff the word f (baabaababaabab) is balanced.More precisely, they have given a set Ω of test-words for Sturmian morphisms.Here, we characterize all such test-words.In particular, we show the optimality of the previous result: there is no test-word of length less or equal to 13, and any test-word has a subword in Ω.To do this, we describe an efficient algorithm to determine if a finite word is balanced, and we give a short proof of the fact that any finite balanced word is a prefix of an infinite Sturmian word.Finally, we show that the test-words for Sturmian morphisms are exactly the test-words for morphisms preserving finite balanced words.