Geodesic
On permutation complexity of fixed points of some nonuniform binary morphisms
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 12 (2015), pp. 64-79 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We study properties of infinite permutations generated by fixed points of morphism $\varphi(0)=01^{k},\varphi(1)=0$ for $k\geq{2}$, and find the formula for their factor complexity.
Keywords: permutation complexity
Mots-clés : infinite permutation, morphism. 
@article{SEMR_2015_12_a52,
     author = {A. A. Valuzhenich},
     title = {On permutation complexity of fixed points of some nonuniform binary morphisms},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {64--79},
     year = {2015},
     volume = {12},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2015_12_a52/}
}
TY  - JOUR
AU  - A. A. Valuzhenich
TI  - On permutation complexity of fixed points of some nonuniform binary morphisms
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2015
SP  - 64
EP  - 79
VL  - 12
UR  - http://geodesic.mathdoc.fr/item/SEMR_2015_12_a52/
LA  - ru
ID  - SEMR_2015_12_a52
ER  - 
%0 Journal Article
%A A. A. Valuzhenich
%T On permutation complexity of fixed points of some nonuniform binary morphisms
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2015
%P 64-79
%V 12
%U http://geodesic.mathdoc.fr/item/SEMR_2015_12_a52/
%G ru
%F SEMR_2015_12_a52
A. A. Valuzhenich. On permutation complexity of fixed points of some nonuniform binary morphisms. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 12 (2015), pp. 64-79. http://geodesic.mathdoc.fr/item/SEMR_2015_12_a52/

[1] S. V. Avgustinovich, “The number of distinct subwords of fixed length in the Morse–Hedlund sequence”, Sibirsk. zhurnal issledovaniya operatsii, 1:2 (1994), 3–7 | MR | Zbl

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

[3] S. V. Avgustinovich, S. Kitaev, A. Pyatkin, A. Valyuzhenich, “On squarefree permutations”, Journal of Automata, Languages and Combinatorics, 16:1 (2011), 3–10 | MR

[4] J. Cassaigne, “Complexité et facteurs spéciaux”, Bull. Belg. Math. Soc., 4 (1997), 67–88 | MR | Zbl

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

[6] M. A. Makarov, “On permutations generated by infinite binary words”, Sib. Elektron. Mat. Izv., 3 (2006), 304–311 (in Russian) | MR | Zbl

[7] M. A. Makarov, “On the permutations generated by the Sturmian words”, Sib. Math. J., 50:3 (2009), 674–680 | DOI | MR | Zbl

[8] A. Valyuzhenich, “Permutation complexity of the fixed points of some uniform binary morphisms”, EPTCS, 63 (2011), 257–264 | DOI

[9] S. Widmer, “Permutation complexity of the Thue-Morse word”, Adv. in Appl. Math., 47:2 (2011), 309–329 | DOI | MR | Zbl