Geodesic
On the complexity of recurring sequences
Diskretnaya Matematika, Tome 15 (2003) no. 2, pp. 52-62

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. 
@article{DM_2003_15_2_a3,
     author = {S. S. Marchenkov},
     title = {On the complexity of recurring sequences},
     journal = {Diskretnaya Matematika},
     pages = {52--62},
     publisher = {mathdoc},
     volume = {15},
     number = {2},
     year = {2003},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2003_15_2_a3/
%G ru
%F DM_2003_15_2_a3
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/