Geodesic
Computational power of real-time Turing machines with sublogarithmic memory restrictions
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 9 (2014), pp. 80-86

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

In this paper we consider the well-known Turing machine model – nondeterministic real-time Turing machine. We prove the existence of nonregular complexity classes of languages that can be recognized by nondeterministic real-time Turing machines with sublogarithmic memory restrictions. These complexity classes form a strict hierarchy. We define a special language family and show its properties to prove that hierarchy.
Keywords: real-time Turing machine, nondeterministic Turing machine, memory restrictions. 
@article{IVM_2014_9_a8,
     author = {A. N. Leshchev},
     title = {Computational power of real-time {Turing} machines with sublogarithmic memory restrictions},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {80--86},
     publisher = {mathdoc},
     number = {9},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2014_9_a8/}
}
TY  - JOUR
AU  - A. N. Leshchev
TI  - Computational power of real-time Turing machines with sublogarithmic memory restrictions
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2014
SP  - 80
EP  - 86
IS  - 9
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2014_9_a8/
LA  - ru
ID  - IVM_2014_9_a8
ER  - 
%0 Journal Article
%A A. N. Leshchev
%T Computational power of real-time Turing machines with sublogarithmic memory restrictions
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2014
%P 80-86
%N 9
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2014_9_a8/
%G ru
%F IVM_2014_9_a8
A. N. Leshchev. Computational power of real-time Turing machines with sublogarithmic memory restrictions. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 9 (2014), pp. 80-86. http://geodesic.mathdoc.fr/item/IVM_2014_9_a8/