Geodesic
Antimonotone permutations
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 9 (2012), pp. 346-359.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper is devoted to a class of infinite permutations. One of the properties of these permutations is their avoiding monotone subsequences of elements with numbers forming an arithmetical progression of length 3. We find the complexity of these permutations, their Rauzy graphs, their maximal pattern complexity, their arithmetical complexity with odd differences, and also we find the lower and upper bounds for their arithmetical complexity and show that these bounds are attained.
Mots-clés : infinite permutations
Keywords: combinatorics on words, Rauzy graphs, maximal pattern complexity, arithmetical complexity. 
@article{SEMR_2012_9_a20,
     author = {M. A. Makarov},
     title = {Antimonotone permutations},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {346--359},
     publisher = {mathdoc},
     volume = {9},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2012_9_a20/}
}
TY  - JOUR
AU  - M. A. Makarov
TI  - Antimonotone permutations
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2012
SP  - 346
EP  - 359
VL  - 9
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2012_9_a20/
LA  - ru
ID  - SEMR_2012_9_a20
ER  - 
%0 Journal Article
%A M. A. Makarov
%T Antimonotone permutations
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2012
%P 346-359
%V 9
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2012_9_a20/
%G ru
%F SEMR_2012_9_a20
M. A. Makarov. Antimonotone permutations. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 9 (2012), pp. 346-359. http://geodesic.mathdoc.fr/item/SEMR_2012_9_a20/

[1] S. Avgustinovich, J. Cassaigne, A. Frid, “Sequences of low arithmetical complexity”, Theoretical Informatics and Applications, 40 (2006), 569–582 | DOI | MR | Zbl

[2] S. Avgustinovich, D. Fon-Der-Flaass, A. Frid, “Arithmetical complexity of infinite words”, Words, Languages Combinatorics III, World Scientific Publishing, 2003, 51–62 | DOI | MR

[3] S. Avgustinovich, A. Frid, T. Kamae, P. Salimov, “Infinite permutations of lowest maximal pattern complexity”, Theoretical Computer Science, 412 (2011), 2911–2921 | DOI | MR | Zbl

[4] J. Cassaigne, “On a conjecture of J. Shallit”, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, 1256, Springer, Bologna, 1997, 693–784 | DOI | MR

[5] J. Cassaigne, A. Frid, “On arithmetical complexity of Sturmian words”, Theoretical Computer Science, 380 (2007), 304–316 | DOI | MR | Zbl

[6] J. Davis, R. Entringer, R. Graham, G. Simmons, “On permutations containing no long arithmetic progressions”, Acta Arithmetica, 34 (1977), 81–90 | MR | Zbl

[7] D. Fon-Der-Flaass, A. Frid, “On periodicity and low complexity of infinite permutations”, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb'05), Discrete Mathematics and Theoretical Computer Science Proceedings volume AE, 267–272 | Zbl

[8] D. Fon-Der-Flaass, A. Frid, “On periodicity and low complexity of infinite permutations”, European Journal of Combinatorics, 28 (2007), 2106–2114 | DOI | MR | Zbl

[9] A. Frid, “Arithmetical complexity of symmetric D0L words”, Theoretical Computer Science, 306 (2003), 535–542 | DOI | MR | Zbl

[10] A. Frid, “Infinite permutations vs. infinite words”, Electronic Proceedings in Theoretical Computer Science, 63 (2011), 13–19 | DOI

[11] A. Frid, “On possible growths of arithmetical complexity”, Theoretical Informatics and Applications, 40 (2006), 443–458 | DOI | MR | Zbl

[12] A. Frid, “Sequences of linear arithmetical complexity”, Theoretical Computer Science, 339 (2005), 68–87 | DOI | MR | Zbl

[13] A. Frid, L. Zamboni, “On automatic infinite permutations”, RAIRO Theoretical Informatics and Applications, 46 (2012), 77–85 | DOI | MR | Zbl

[14] N. Gjini, T. Kamae, Bo Tan, Yu-Mei Xue, “Maximal pattern complexity for Toeplitz words”, Ergodic Theory and Dynamical Systems, 26 (2006), 1073–1086 | DOI | MR | Zbl

[15] T. LeSaulnier, S. Vijay, “On permutations avoiding arithmetic progressions”, Discrete Mathematics, 311 (2011), 205–207 | DOI | MR | Zbl

[16] M. Makarov, “On an infinite permutation similar to the Thue-Morse word”, Discrete Mathematics, 309 (2009), 6641–6643 | DOI | MR | Zbl

[17] M. Makarov, “On the infinite permutation generated by the period doubling word”, European Journal of Combinatorics, 31 (2010), 368–378 | DOI | MR | Zbl

[18] T. Kamae, “Behavior of various complexity functions”, Theoretical Computer Science, 420 (2012), 36–47 | DOI | MR | Zbl

[19] T. Kamae, H. Rao, “Maximal pattern complexity of words over $\ell$ letters”, European Journal of Combinatorics, 27 (2006), 125–137 | DOI | MR | Zbl

[20] T. Kamae, H. Rao, Bo Tan, Yu-Mei Xue, “Language structure of pattern Sturmian word”, Discrete Mathematics, 306 (2006), 1651–1668 | DOI | MR | Zbl

[21] T. Kamae, H. Rao, Yu-Mei Xue, “Maximal pattern complexity of two-dimensional words”, Theoretical Computer Science, 359 (2006), 15–27 | DOI | MR | Zbl

[22] T. Kamae, P. Salimov, “On maximal pattern complexity of some automatic words”, Ergodic Theory and Dynamical Systems, 31 (2011), 1463–1470 | DOI | MR | Zbl

[23] T. Kamae, L. Zamboni, “Maximal pattern complexity for discrete systems”, Ergodic Theory and Dynamical Systems, 22 (2002), 1201–1214 | MR | Zbl

[24] T. Kamae, L. Zamboni, “Sequence entropy and the maximal pattern complexity of infinite words”, Ergodic Theory and Dynamical Systems, 22 (2002)), 1191–1199 | MR | Zbl

[25] G. Rauzy, “Suites à termes dans un alphabet fini”, Séminaire de Théorie des nombres de Bordeaux, exposé 25, 1983, 2501–2516 | MR

[26] M. Makarov, “O perestanovkakh, porozhdennykh beskonechnymi binarnymi slovami”, Sibirskie elektronnye matematicheskie izvestiya, 3 (2006), 304–311 | MR

[27] M. Makarov, “O perestanovkakh, porozhdennykh slovami Shturma”, Sibirskii matematicheskii zhurnal, 50 (2009), 850–857 | Zbl

[28] A. Frid, “Nizhnyaya otsenka na arifmeticheskuyu slozhnost slov Shturma”, Sibirskie elektronnye matematicheskie izvestiya, 2 (2005), 14–22