Abstract
An infinite permutation can be defined as a linear ordering of the set of natural numbers. In particular, an infinite permutation can be constructed with an aperiodic infinite word over \(\{0,\ldots ,q-1\}\) as the lexicographic order of the shifts of the word. In this paper, we discuss the question if an infinite permutation defined this way admits a canonical representative, that is, 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 a canonical representative exists if and only if the word is uniquely ergodic, and that is why we use the term ergodic permutations. We also discuss ways to construct the canonical representative of a permutation defined by a morphic word and generalize the construction of Makarov, 2009, for the Thue-Morse permutation to a wider class of infinite words.
S. Puzynina—Supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Allouche, J.-P., Shallit, J.: Automatic Sequences – Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003)
Allouche, J.-P., Shallit, J.: The ubiquitous Prouhet-Thue-Morse sequence. In: Ding, C., Helleseth, T., Niederreiter, H. (eds.) Sequences and Their Applications. Discrete Mathematics and Theoretical Computer Science, pp. 1–16. Springer, London (1999)
Amigó, J.: Permutation Complexity in Dynamical Systems - Ordinal Patterns, Permutation Entropy and All That. Springer Series in Synergetics. Springer, Heidelberg (2010)
Avgustinovich, S.V., Frid, A., Kamae, T., Salimov, P.: Infinite permutations of lowest maximal pattern complexity. Theort. Comput. Sci. 412, 2911–2921 (2011)
Avgustinovich, S.V., Frid, A.E., Puzynina, S.: Ergodic infinite permutations of minimal complexity. In: Potapov, I. (ed.) DLT 2015. LNCS, vol. 9168, pp. 71–84. Springer, Heidelberg (2015)
Bandt, C., Keller, G., Pompe, B.: Entropy of interval maps via permutations. Nonlinearity 15, 1595–1602 (2002)
Elizalde, S.: The number of permutations realized by a shift. SIAM J. Discrete Math. 23, 765–786 (2009)
Ferenczi, S., Monteil, T.: Infinite words with uniform frequencies, and invariant measures. Combinatorics, automata and number theory. Encyclopedia Math. Appl. 135, 373–409 (2010). Cambridge University Press
Dumont, J.-M., Thomas, A.: Systèmes de numération et fonctions fractales relatifs aux substitutions. Theoret. Comput. Sci. 65(2), 153–169 (1989)
Fon-Der-Flaass, D.G., Frid, A.E.: On periodicity and low complexity of infinite permutations. Eur. J. Combin. 28, 2106–2114 (2007)
Frid, A.: Fine and Wilf’s theorem for permutations. Sib. Elektron. Mat. Izv. 9, 377–381 (2012)
Lothaire, M.: Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002)
Makarov, M.: On permutations generated by infinite binary words. Sib. Elektron. Mat. Izv. 3, 304–311 (2006)
Makarov, M.: On an infinite permutation similar to the Thue-Morse word. Discrete Math. 309, 6641–6643 (2009)
Makarov, M.: On the permutations generated by Sturmian words. Sib. Math. J. 50, 674–680 (2009)
Morse, M., Hedlund, G.: Symbolic dynamics II: Sturmian sequences. Amer. J. Math. 62, 1–42 (1940)
Valyuzhenich, A.: On permutation complexity of fixed points of uniform binary morphisms. Discr. Math. Theoret. Comput. Sci. 16, 95–128 (2014)
Widmer, S.: Permutation complexity of the Thue-Morse word. Adv. Appl. Math. 47, 309–329 (2011)
Widmer, S.: Permutation complexity related to the letter doubling map. In: WORDS 2011 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Avgustinovich, S.V., Frid, A.E., Puzynina, S. (2015). Canonical Representatives of Morphic Permutations. In: Manea, F., Nowotka, D. (eds) Combinatorics on Words. WORDS 2015. Lecture Notes in Computer Science(), vol 9304. Springer, Cham. https://doi.org/10.1007/978-3-319-23660-5_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-23660-5_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23659-9
Online ISBN: 978-3-319-23660-5
eBook Packages: Computer ScienceComputer Science (R0)