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, 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.

Original languageEnglish
Title of host publicationCombinatorics on Words - 9th International Conference, WORDS 2013, Proceedings
Pages46-57
Number of pages12
DOIs
StatePublished - 28 Oct 2013
Event9th International Conference on Combinatorics on Words, WORDS 2013 - Turku, Finland
Duration: 16 Sep 201320 Sep 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8079 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Conference on Combinatorics on Words, WORDS 2013
Country/TerritoryFinland
CityTurku
Period16/09/1320/09/13

    Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

ID: 41130364