no. 1
On automatic infinite permutations
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 1, pp. 77-85.

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.

DOI : 10.1051/ita/2011129
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},
     mrnumber = {2904962},
     zbl = {1247.05007},
     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
SP  - 77
EP  - 85
VL  - 46
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2011129/
DO  - 10.1051/ita/2011129
LA  - en
ID  - ITA_2012__46_1_77_0
ER  - 
%0 Journal Article
%A Frid, Anna
%A Zamboni, Luca
%T On automatic infinite permutations
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2012
%P 77-85
%V 46
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2011129/
%R 10.1051/ita/2011129
%G en
%F ITA_2012__46_1_77_0
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] J.-P. Allouche and J. Shallit, Automatic sequences - theory, applications, generalizations. Cambridge University Press (2003). | MR | Zbl

[2] J.-P. Allouche, N. Rampersad and J. Shallit, Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci. 410 (2009) 2795-2803. | MR | Zbl

[3] S. Avgustinovich, A. Frid, T. Kamae and P. Salimov, Infinite permutations of lowest maximal pattern complexity. Theoret. Comput. Sci. 412 (2011) 2911-2921. | MR | Zbl

[4] É. Charlier, N. Rampersad and J. Shallit, Enumeration and Decidable Properties of Automatic Sequences, Lect. Notes Comput. Sci. 6795 (2011) 165-179. | MR | Zbl

[5] G. Christol, T. Kamae, M.M. France and G. Rauzy, Suites algébriques, automates et substitutions. Bull. Soc. Math. France 108 (1980) 401-419. | EuDML | Numdam | MR | Zbl

[6] A. Cobham, Uniform tag sequences. Math. Syst. Theor. 6 (1972) 164-192. | MR | Zbl

[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. | EuDML | MR | Zbl

[8] S. Eilenberg, Automata, Languages, and Machines A. Academic Press (1974). | Zbl

[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. | MR | Zbl

[10] M. Makarov, On permutations generated by infinite binary words. Sib. Èlectron. Mat. Izv. 3 (2006) 304-311 (in Russian, English abstract). | EuDML | MR | Zbl

[11] M. Makarov, On an infinite permutation similar to the Thue-Morse word. Discrete Math. 309 (2009) 6641-6643. | MR | Zbl

[12] M. Makarov, On the permutations generated by Sturmian words. Sib. Math. J. 50 (2009) 674-680. | EuDML | MR | Zbl

[13] M. Makarov, On the infinite permutation generated by the period doubling word. Eur. J. Comb. 31 (2010) 368-378. | MR | Zbl

[14] S. Widmer, Permutation complexity of the Thue-Morse word. Adv. Appl. Math. 47 (2011) 309-329. | MR | Zbl

Cité par Sources :