Random generation of finite Sturmian words

✍ Scribed by Jean Berstel; Michel Pocchiola

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 521 KB
• Volume: 153
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00125-g

✦ Synopsis

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.