Ergodic infinite permutations of minimal complexity

Sergey V. Avgustinovich, Anna E. Frid, Svetlana Puzynina

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

2 Цитирования (Scopus)

Аннотация

An infinite permutation can be defined as a linear ordering of the set of natural numbers. Similarly to infinite words, a complexity p(n) of an infinite permutation is defined as a function counting the number of its factors of length n. For infinite words, a classical result of Morse and Hedlund, 1940, states that if the complexity of an infinite word satisfies p(n) ≤ n for some n, then the word is ultimately periodic. Hence minimal complexity of aperiodic words is equal to n + 1, and words with such complexity are called Sturmian. For infinite permutations this does not hold: There exist aperiodic permutations with complexity functions of arbitrarily slow growth, and hence there are no permutations of minimal complexity. In the paper we introduce a new notion of ergodic permutation, i.e., a permutation which 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 the minimal complexity of an ergodic permutation is p(n) = n, and that the class of ergodic permutations of minimal complexity coincides with the class of so-called Sturmian permutations, directly related to Sturmian words.

Язык оригиналаанглийский
Название основной публикацииDevelopments in Language Theory - 19th International Conference, DLT 2015, Proceedings
РедакторыIgor Potapov
ИздательSpringer Nature
Страницы71-84
Число страниц14
ISBN (печатное издание)9783319214993
DOI
СостояниеОпубликовано - 1 янв 2015
Событие19th International Conference on Developments in Language Theory, DLT 2015 - Liverpool, Великобритания
Продолжительность: 27 июл 201530 июл 2015

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

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

конференция

конференция19th International Conference on Developments in Language Theory, DLT 2015
СтранаВеликобритания
ГородLiverpool
Период27/07/1530/07/15

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

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

Fingerprint

Подробные сведения о темах исследования «Ergodic infinite permutations of minimal complexity». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать