TY - GEN

T1 - Ergodic infinite permutations of minimal complexity

AU - Avgustinovich, Sergey V.

AU - Frid, Anna E.

AU - Puzynina, Svetlana

PY - 2015/1/1

Y1 - 2015/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=84947069982&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-21500-6_5

DO - 10.1007/978-3-319-21500-6_5

M3 - Conference contribution

AN - SCOPUS:84947069982

SN - 9783319214993

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 71

EP - 84

BT - Developments in Language Theory - 19th International Conference, DLT 2015, Proceedings

A2 - Potapov, Igor

PB - Springer Nature

T2 - 19th International Conference on Developments in Language Theory, DLT 2015

Y2 - 27 July 2015 through 30 July 2015

ER -