Реферат: An infinite permutation is a linear ordering of the set of natural numbers. An infinite permutation can be defined by a sequence of real numbers where only the order of elements is taken into account; such sequence of reals is called a representative of a permutation. In this paper we consider infinite permutations which possess an equidistributed representative on [0,1] (i.e., such that the prefix frequency of elements from each interval exists and is equal to the length of this interval), and we call such permutations equidistributed. Similarly to infinite words, a complexity p(n) of an infinite permutation is defined as a function counting the number of its subpermutations of length n. We show that, unlike for permutations in general, the minimal complexity of an equidistributed permutation α is pα(n)=n, establishing an analog of Morse and Hedlund theorem. The class of equidistributed permutations of minimal complexity coincides with the class of so-called Sturmian permutations, directly related to Sturmian words.

Библиографическая ссылка: Avgustinovich S.V. , Frid A.E. , Puzynina S.
Minimal complexity of equidistributed infinite permutations
European Journal of Combinatorics. 2017. V.65. P.24-36. DOI: 10.1016/j.ejc.2017.05.003 WOS Scopus РИНЦ OpenAlex

Даты:

Поступила в редакцию:	20 дек. 2016 г.
Принята к публикации:	11 мая 2017 г.

Идентификаторы БД:

Web of science:	WOS:000408301100003
Scopus:	2-s2.0-85020262101
РИНЦ:	31002012
OpenAlex:	W2962952252

Цитирование в БД:

БД	Цитирований
Web of science	2
Scopus	2
РИНЦ	2
OpenAlex	2

Альметрики: