An infinite permutation α is a linear ordering of 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 shall 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.
Classification : 05A05, 68R15
Mots clés : permutation, infinite permutation, ordering, infinite word, automatic word, automatic permutation, Thue-Morse word, Thue-Morse permutation
@article{ITA_2012__46_1_77_0, author = {Frid, Anna and Zamboni, Luca}, title = {On automatic infinite permutations}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {77--85}, publisher = {EDP-Sciences}, volume = {46}, number = {1}, year = {2012}, doi = {10.1051/ita/2011129}, zbl = {1247.05007}, mrnumber = {2904962}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ita/2011129/} }
TY - JOUR AU - Frid, Anna AU - Zamboni, Luca TI - On automatic infinite permutations JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2012 DA - 2012/// SP - 77 EP - 85 VL - 46 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2011129/ UR - https://zbmath.org/?q=an%3A1247.05007 UR - https://www.ams.org/mathscinet-getitem?mr=2904962 UR - https://doi.org/10.1051/ita/2011129 DO - 10.1051/ita/2011129 LA - en ID - ITA_2012__46_1_77_0 ER -
Frid, Anna; Zamboni, Luca. On automatic infinite permutations. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 1, pp. 77-85. doi : 10.1051/ita/2011129. http://www.numdam.org/articles/10.1051/ita/2011129/
[1] Automatic sequences - theory, applications, generalizations. Cambridge University Press (2003). | MR 1997038 | Zbl 1086.11015
and ,[2] Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci. 410 (2009) 2795-2803. | MR 2543333 | Zbl 1173.68044
, and ,[3] Infinite permutations of lowest maximal pattern complexity. Theoret. Comput. Sci. 412 (2011) 2911-2921. | MR 2830255 | Zbl 1232.68095
, , and ,[4] Enumeration and Decidable Properties of Automatic Sequences, Lect. Notes Comput. Sci. 6795 (2011) 165-179. | MR 2862724 | Zbl 1221.68122
, and ,[5] Suites algébriques, automates et substitutions. Bull. Soc. Math. France 108 (1980) 401-419. | EuDML 87381 | Numdam | MR 614317 | Zbl 0472.10035
, , and ,[6] Uniform tag sequences. Math. Syst. Theor. 6 (1972) 164-192. | MR 457011 | Zbl 0253.02029
,[7] On permutations containing no long arithmetic progressions. Acta Arith. 34 (1977) 81-90. | EuDML 205594 | MR 491459 | Zbl 0326.10045
, , and ,[8] Automata, Languages, and Machines A. Academic Press (1974). | Zbl 0359.94067
,[9] Flaass and A.E. Frid, On periodicity and low complexity of infinite permutations. Eur. J. Comb. 28 (2007) 2106-2114. | MR 2351513 | Zbl 1126.05004
-[10] On permutations generated by infinite binary words. Sib. Èlectron. Mat. Izv. 3 (2006) 304-311 (in Russian, English abstract). | EuDML 54783 | MR 2276028 | Zbl 1150.68389
,[11] On an infinite permutation similar to the Thue-Morse word. Discrete Math. 309 (2009) 6641-6643. | MR 2558629 | Zbl 1194.05002
,[12] On the permutations generated by Sturmian words. Sib. Math. J. 50 (2009) 674-680. | EuDML 225880 | MR 2583623 | Zbl 1224.68068
,[13] On the infinite permutation generated by the period doubling word. Eur. J. Comb. 31 (2010) 368-378. | MR 2552616 | Zbl 1192.05003
,[14] Permutation complexity of the Thue-Morse word. Adv. Appl. Math. 47 (2011) 309-329. | MR 2803805 | Zbl 1234.05012
,Cité par Sources :