Logo image
Test-words for Sturmian morphisms
Article de revue scientifique

Test-words for Sturmian morphisms

Gwenaël Richomme
Bulletin of the Belgian Mathematical Society, Simon Stevin, Vol.6(4), p.481-489
1999

Résumé

Computer Science Discrete Mathematics
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.

Indicateurs

1 Consultations de la notice

Détails

Logo image