DOI

An infinite permutation can be defined as a linear ordering of the set of natural numbers. In particular, an infinite permutation can be constructed with an aperiodic infinite word over {0, . . . , q −1} as the lexicographic order of the shifts of the word. In this paper, we discuss the question if an infinite permutation defined this way admits a canonical representative, that is, can be defined by a sequence of numbers from [0, 1], such that the frequency of its elements in any interval is equal to the length of that interval. We show that a canonical representative exists if and only if the word is uniquely ergodic, and that is why we use the term ergodic permutations. We also discuss ways to construct the canonical representative of a permutation defined by a morphic word and generalize the construction of Makarov, 2009, for the Thue-Morse permutation to a wider class of infinite words.

Язык оригиналаанглийский
Название основной публикацииCombinatorics on Words - 10th International Conference, WORDS 2015, Proceedings
РедакторыDirk Nowotka, Florin Manea
ИздательSpringer Nature
Страницы59-72
Число страниц14
ISBN (печатное издание)9783319236599
DOI
СостояниеОпубликовано - 1 янв 2015
Событие10th International Conference on Words, WORDS 2015 - Kiel, Германия
Продолжительность: 14 сен 201517 сен 2015

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том9304
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция10th International Conference on Words, WORDS 2015
Страна/TерриторияГермания
ГородKiel
Период14/09/1517/09/15

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 35285011