Random generation of finite sturmian words

J. Berstel, M. POCCHIOLA

IBP-Litp 1994/44: Rapport de Recherche Litp / Litp research reports
11 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Random generation of finite sturmian words

Résumé : Nous présentons une bijection entre l'ensemble des facteurs des mots de Sturm de longueur donnée et un ensemble de triplets d'entiers. Cette bijection et son inverse sont calculables en temps linéaire. Ses applications sont : une preuve bijective de la formule de Mignosi dénombrant les facteurs finis des mots de Sturm, un algorithme probabiliste linéaire de génération aléatoire des facteurs finis des mots de Sturm et un algorithme linéaire en ligne pour calculer le plus long préfixe sturmien d'un mot donné. La construction de la bijection s'appuie sur des concepts de géométrie combinatoire.

Abstract : We present a bijection between the set of factors of given length of sturmian words and some set of triples of nonnegative integers. This bijection and its inverse are both computable in linear time. Its applications are : a bijective proof of Mignosi's formula for counting Sturmian words, a linear probabilistic algorithm for generating finite Sturmian word at random, and, using similar techniques, a linear on-line algorithm for computing the longest Sturmian prefix of a given word. The construction of the bijection relies on concepts from combinatorial geometry.

Publications internes Litp 1994 / Litp research reports 1994