In this paper we introduce the well distributed occurrences (WDO) combinatorial property for infinite words, which guarantees good behavior (no lattice structure) in some related pseudorandom number generators. An infinite word u on a d-ary alphabet has the WDO property if, for each factor w of u, positive integer m, and vector v ∈ℤ_d^m , there is an occurrence of w such that the Parikh vector of the prefix of u preceding such occurrence is congruent to v modulo m. We prove that Sturmian words, and more generally Arnoux-Rauzy words and some morphic images of them, have the WDO property.
Infinite Words with Well Distributed Occurrences / Ľubomíra, Balková; Michelangelo, Bucci; DE LUCA, Alessandro; Svetlana, Puzynina. - 8079:(2013), pp. 46-57. (Intervento presentato al convegno WORDS 2013 tenutosi a Turku, Finland nel 16–20 settembre 2013) [10.1007/978-3-642-40579-2_8].
Infinite Words with Well Distributed Occurrences
DE LUCA, ALESSANDRO;
2013
Abstract
In this paper we introduce the well distributed occurrences (WDO) combinatorial property for infinite words, which guarantees good behavior (no lattice structure) in some related pseudorandom number generators. An infinite word u on a d-ary alphabet has the WDO property if, for each factor w of u, positive integer m, and vector v ∈ℤ_d^m , there is an occurrence of w such that the Parikh vector of the prefix of u preceding such occurrence is congruent to v modulo m. We prove that Sturmian words, and more generally Arnoux-Rauzy words and some morphic images of them, have the WDO property.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
