The recurrence function of a random Sturmian word

DOI10.1137/1.9781611974775.10MaRDI QIDQ5195041zbMATH OpenOpenAlexFDO

Authors Pablo Rotondo, Brigitte Vallée

Publication date 17 September 2019

Published in 2017 Proceedings of the Fourteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.01479

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05) Combinatorics on words (68R15)

Abstract: This paper describes the probabilistic behaviour of a random Sturmian word. It performs the probabilistic analysis of the recurrence function which can be viewed as a waiting time to discover all the factors of length $n$ of the Sturmian word. This parameter is central to combinatorics of words. Having fixed a possible length $n$ for the factors, we let $alpha$ to be drawn uniformly from the unit interval $[0,1]$, thus defining a random Sturmian word of slope $alpha$. Thus the waiting time for these factors becomes a random variable, for which we study the limit distribution and the limit density.

Recommendations

• Recurrence function on Sturmian words: a probabilistic study
• Random generation of finite Sturmian words
• Relation between powers of factors and the recurrence function characterizing Sturmian words
• Periods and borders of random words
• On the number of factors of Sturmian words

Cited in

(3)

• The Brun gcd algorithm in high dimensions is almost always subtractive
• Recurrence function on Sturmian words: a probabilistic study
• Recurrence and Frequencies

This page was built for publication: The recurrence function of a random Sturmian word

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5195041)