Geodesic
On permutations generated by infinite binary words
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 3 (2006), pp. 304-311.

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

Let $w=w(1)w(2)\ldots w(n)\ldots$ be an arbitrary non-periodic infinite word on $\{0,1\}$. For every $i\in\mathbb{N}$ we may consider the binary real number $R_w(i)=0,w(i)w(i+1)\dots$. For all $n\in\mathbb{N}$ the numbers $R_w(1),\ldots,R_w(n)$ generate some permutation $\pi_w^n$ of length $n$ such that for all $i,j\in\{1,\ldots,n\}$ the inequalities $\pi_w^n(i)\pi_w^n(j)$ and $R_w(i)$ are equivalent. A permutation is said to be { it valid} if it is generated by some word. In this paper we investigate some properties of valid permutations. In particular, we prove a precise formula for the number of valid permutations of a given length. Also we consider a problem of continuability of valid permutations to the left. 
@article{SEMR_2006_3_a20,
     author = {M. A. Makarov},
     title = {On permutations generated by infinite binary words},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {304--311},
     publisher = {mathdoc},
     volume = {3},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2006_3_a20/}
}
TY  - JOUR
AU  - M. A. Makarov
TI  - On permutations generated by infinite binary words
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2006
SP  - 304
EP  - 311
VL  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2006_3_a20/
LA  - ru
ID  - SEMR_2006_3_a20
ER  - 
%0 Journal Article
%A M. A. Makarov
%T On permutations generated by infinite binary words
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2006
%P 304-311
%V 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2006_3_a20/
%G ru
%F SEMR_2006_3_a20
M. A. Makarov. On permutations generated by infinite binary words. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 3 (2006), pp. 304-311. http://geodesic.mathdoc.fr/item/SEMR_2006_3_a20/

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

[2] M. Domaratzki, D. Kisman, J. Shallit, “On the number of distinct languages accepted by finite automata with $n$ states”, J. Autom. Lang. Comb., 7 (2002), 469–486 | MR | Zbl

[3] D. G. Fon-Der-Flaass and A. E. Frid, “On periodicity and low complexity of infinite permutations”, Discrete Mathematics and Theoretical Computer Science proc. AE, 2005, 267–272 | Zbl

[4] R. Grossi and J. S. Vitter, Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, , 2000, 397–406 http://www.cs.duke.edu/~jsv/ Papers/GrV00.text_indexing.ps.gz. | MR

[5] M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics and Its Applications, 17, Addison-Wesley, 1983 | MR | Zbl

[6] M. He, J. I. Munro, S. S. Rao, Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (January 2005) (to appear) | MR

[7] C. Nicaud, “Average state complexity of operations on unary automata”, Mathematical Foundations of Computer Science 1999, Proc. 24th Symposium, Lecture Notes in Computer Science, 1672, eds. M. Kutylowski, L. Pacholski, and T. Wierzbicki, Springer-Verlag, 1999, 231–240 | MR | Zbl