Geodesic
On the complexity of recurring sequences
Diskretnaya Matematika, Tome 15 (2003) no. 2, pp. 52-62 
S. S. Marchenkov. On the complexity of recurring sequences. Diskretnaya Matematika, Tome 15 (2003) no. 2, pp. 52-62. http://geodesic.mathdoc.fr/item/DM_2003_15_2_a3/
@article{DM_2003_15_2_a3,
     author = {S. S. Marchenkov},
     title = {On the complexity of recurring sequences},
     journal = {Diskretnaya Matematika},
     pages = {52--62},
     year = {2003},
     volume = {15},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2003_15_2_a3/}
}
TY  - JOUR
AU  - S. S. Marchenkov
TI  - On the complexity of recurring sequences
JO  - Diskretnaya Matematika
PY  - 2003
SP  - 52
EP  - 62
VL  - 15
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2003_15_2_a3/
LA  - ru
ID  - DM_2003_15_2_a3
ER  - 
%0 Journal Article
%A S. S. Marchenkov
%T On the complexity of recurring sequences
%J Diskretnaya Matematika
%D 2003
%P 52-62
%V 15
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2003_15_2_a3/
%G ru
%F DM_2003_15_2_a3

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

We study recurring sequences over finite fields sets and the set $\mathbf N=\{0,1,2,\ldots\}$. The complexity of recurring sequences over finite sets is estimated as the complexity of computing on determinate linearly bounded automata. We introduce the notion of a branching recurring sequence. The complexity of branching recurring sequences over finite sets is estimated as the complexity of computing on non-determinate linearly bounded automata. Recurring sequences over the set $\mathbf N$ simulate computations on multi-tape Minsky machines. We ascertain undecidability of some problems concerning this type of recurring sequences. This research was supported by the Russian Foundation for Basic Research, grant 00–01–00351.

[1] Kholl M., Kombinatorika, Mir, Moskva, 1970 | MR

[2] Nechaev V. I., Elementy kriptografii. Osnovy teorii zaschity informatsii, Vysshaya shkola, Moskva, 1999 | MR

[3] Kuroda S. I., “Klassy yazykov i lineino ogranichennye avtomaty”, Kibern. sb., 9 (1972), 36–51 | Zbl

[4] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, Moskva, 1982 | MR

[5] Ullian J. S., “Splinters of recursive functions”, J. Symb. Logic, 25:1 (1960), 33–38 | DOI | MR | Zbl

[6] Degtev A. N., Rekursivno perechislimye mnozhestva i svodimosti tablichnogo tipa, Nauka, Moskva, 1998 | Zbl

[7] Minskii M., Vychisleniya i avtomaty, Mir, Moskva, 1971 | MR | Zbl

[8] Maltsev A. I., Algoritmy i rekursivnye funktsii, Nauka, Moskva, 1986 | MR

[9] Marchenkov S. S., “Bazisy po superpozitsii v klassakh rekursivnykh funktsii”, Matem. voprosy kibernetiki, 3 (1991) | MR