×

On automatic infinite permutations. (English) Zbl 1247.05007

Summary: An infinite permutation \(\alpha \) is a linear ordering of \(\mathbb N\). We study properties of infinite permutations analogous to those of infinite words, and show some resemblances and some differences between permutations and words. In this paper, we try to extend to permutations the notion of automaticity. As we show, the standard definitions which are equivalent in the case of words are not equivalent in the context of permutations. We investigate the relationships between these definitions and prove that they constitute a chain of inclusions. We also construct and study an automaton generating the Thue-Morse permutation.

MSC:

05A05 Permutations, words, matrices
68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI arXiv EuDML

References:

[1] J.-P. Allouche and J. Shallit, Automatic sequences - theory, applications, generalizations. Cambridge University Press (2003). · Zbl 1086.11015
[2] J.-P. Allouche, N. Rampersad and J. Shallit, Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci.410 (2009) 2795-2803. Zbl1173.68044 · Zbl 1173.68044 · doi:10.1016/j.tcs.2009.02.006
[3] S. Avgustinovich, A. Frid, T. Kamae and P. Salimov, Infinite permutations of lowest maximal pattern complexity. Theoret. Comput. Sci.412 (2011) 2911-2921. · Zbl 1232.68095 · doi:10.1016/j.tcs.2010.12.062
[4] É. Charlier, N. Rampersad and J. Shallit, Enumeration and Decidable Properties of Automatic Sequences, Lect. Notes Comput. Sci.6795 (2011) 165-179. · Zbl 1221.68122 · doi:10.1007/978-3-642-22321-1_15
[5] G. Christol, T. Kamae, M.M. France and G. Rauzy, Suites algébriques, automates et substitutions. Bull. Soc. Math. France108 (1980) 401-419. · Zbl 0472.10035
[6] A. Cobham, Uniform tag sequences. Math. Syst. Theor.6 (1972) 164-192. · Zbl 0253.02029 · doi:10.1007/BF01706087
[7] J.A. Davis, R.C. Entringer, R.L. Graham and G.J. Simmons, On permutations containing no long arithmetic progressions. Acta Arith.34 (1977) 81-90. · Zbl 0326.10045
[8] S. Eilenberg, Automata, Languages, and MachinesA. Academic Press (1974).
[9] D.G. Fon-Der-Flaass and A.E. Frid, On periodicity and low complexity of infinite permutations. Eur. J. Comb.28 (2007) 2106-2114. · Zbl 1126.05004 · doi:10.1016/j.ejc.2007.04.017
[10] M. Makarov, On permutations generated by infinite binary words. Sib. Èlectron. Mat. Izv.3 (2006) 304-311 (in Russian, English abstract). · Zbl 1150.68389
[11] M. Makarov, On an infinite permutation similar to the Thue-Morse word. Discrete Math.309 (2009) 6641-6643. · Zbl 1194.05002 · doi:10.1016/j.disc.2009.06.030
[12] M. Makarov, On the permutations generated by Sturmian words. Sib. Math. J.50 (2009) 674-680. · Zbl 1224.68068
[13] M. Makarov, On the infinite permutation generated by the period doubling word. Eur. J. Comb.31 (2010) 368-378. · Zbl 1192.05003 · doi:10.1016/j.ejc.2009.03.038
[14] S. Widmer, Permutation complexity of the Thue-Morse word. Adv. Appl. Math.47 (2011) 309-329. · Zbl 1234.05012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.