Geodesic
Almost periodicity, finite automata mappings, and related effectiveness issues
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 1 (2010), pp. 74-87 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We introduce a class of eventually almost periodic sequences where some suffix is almost periodic (i.e., uniformly recurrent). The class of generalized almost periodic sequences includes the class of eventually almost periodic sequences, and we prove this inclusion to be strict. We also prove that the class of eventually almost periodic sequences is closed under finite automata mappings and finite transductions. Moreover, we obtain an effective form of this result. In conclusion we consider some algorithmic questions related to the almost periodicity.
Keywords: almost periodic sequences, finite automata, effectiveness. 
@article{IVM_2010_1_a7,
     author = {Yu. L. Pritykin},
     title = {Almost periodicity, finite automata mappings, and related effectiveness issues},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {74--87},
     year = {2010},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2010_1_a7/}
}
TY  - JOUR
AU  - Yu. L. Pritykin
TI  - Almost periodicity, finite automata mappings, and related effectiveness issues
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2010
SP  - 74
EP  - 87
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/IVM_2010_1_a7/
LA  - ru
ID  - IVM_2010_1_a7
ER  - 
%0 Journal Article
%A Yu. L. Pritykin
%T Almost periodicity, finite automata mappings, and related effectiveness issues
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2010
%P 74-87
%N 1
%U http://geodesic.mathdoc.fr/item/IVM_2010_1_a7/
%G ru
%F IVM_2010_1_a7
Yu. L. Pritykin. Almost periodicity, finite automata mappings, and related effectiveness issues. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 1 (2010), pp. 74-87. http://geodesic.mathdoc.fr/item/IVM_2010_1_a7/

[1] Morse M., Hedlund G. A., “Symbolic dynamics”, Amer. J. Math., 60:4 (1938), 815–866 | DOI | MR | Zbl

[2] Morse M., Hedlund G. A., “Symbolic dynamics II: Sturmian trajectories”, Amer. J. Math., 62:1 (1940), 1–42 | DOI | MR | Zbl

[3] Cassaigne J., “Recurrence in infinite words”, 18th symposium on theoretical aspects of computer science, STACS 2001, Berlin, 2001, 1–11 | MR | Zbl

[4] Muchnik An., Semenov A., Ushakov M., “Almost periodic sequences”, Theor. Comp. Sci., 304:1–3 (2003), 1–33 | DOI | MR | Zbl

[5] Semenov A. L., “O nekotorykh rasshireniyakh arifmetiki slozheniya naturalnykh chisel”, Izv. AN SSSR. Ser. matem., 43:5 (1979), 1175–1195 | MR | Zbl

[6] Semenov A. L., “Logicheskie teorii odnomestnykh funktsii na naturalnom ryade”, Izv. AN SSSR. Ser. matem., 47:3 (1983), 623–658 | MR | Zbl

[7] Thue A., “Über unendliche Zeichenreihen”, Norske vid. Selsk. Skr. Mat. Nat. Kl., 7 (1906), 1–22

[8] Allouche J.-P., Shallit J., “The ubiquitous Prouhet–Thue–Morse sequence”, Sequences and their applications, Proc. of SETA' 98, Berlin, 1999, 1–16 | MR | Zbl

[9] Jacobs K., “Maschinenerzeugte 0-1-Folgen”, Selecta Mathematica, II, Springer, Berlin, 1970, 141–167 | MR

[10] Pritykin Yu. L., “Konechno-avtomatnye preobrazovaniya strogo pochti periodicheskikh posledovatelnostei”, Matem. zametki, 80:5 (2006), 751–756 | MR | Zbl

[11] Pritykin Yu. L., “Konechno-avtomatnye preobrazovaniya pochti periodicheskikh posledovatelnostei i algoritmicheskaya nerazreshimost”, Tr. XXVIII konf. molodykh uchenykh, mekh.-matem. f-t MGU im. Lomonosova, M., 2006, 177–181

[12] Raskin M. A., “Ob otsenke regulyatora avtomatnogo obraza pochti periodicheskoi posledovatelnosti”, Tr. XXVIII konf. molodykh uchenykh, mekh.-matem. f-t MGU im. Lomonosova, M., 2006, 181–185

[13] Weber A., “On the valuedness of finite transducers”, Acta Informatica, 27:9 (1989), 749–780 | MR

[14] Keane M., “Generalized Morse sequences”, Z. Wahrscheinlichkeitstheorie verw. Geb., 10:4 (1968), 335–353 | DOI | MR | Zbl