2009/10/29 by S. V. Avgustinovich, Anna E. Frid, Avgustinovich, S. V. +5
Computer Science · Engineering · #05A05 #68R15 #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0910.5696
openalex publication_date 2009/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An infinite permutation is a linear ordering of the set of non-negative integers. Generally, the properties of infinite permutations analogous to those of infinite words show some resemblances and some differences between permutations and words. In this paper, we define maximal pattern complexity for infinite permutations and show that this complexity function is ultimately constant if and only if the permutation is ultimately periodic. Then we characterize the non-periodic permutations of minimal complexity (equal to n) and find that they all are constructed with the use of Sturmian words.