Low maximal pattern complexity of innite permutations
S. V. Avgustinovich, Anna E. Frid, Teturo Kamae · 2009
An innite permutation is a linear ordering of N. We study properties of innite permutations analogous to those of innite words and showing some resemblance and some dierence between permutations and words. In this paper, we dene maximal pattern complexity p (n) for innite permutations and show that this complexity function is ultimately constant if and only if the permutation is ultimately periodic; otherwise its maximal pattern complexity is at least n, and the value p (n) n is reached on a large family of permutations constructed with the use of Sturmian words. We also conjecture that there are no other innite permutations of maximal pattern complexity equal to n.