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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2014},
     number = {9},
     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
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
%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/

[1] Sanjeev A., Boaz B., Computational complexity: a modern approach, Princeton University, 2006 | MR

[2] Rosenberg A. L., “Real-time definable languages”, J. Assoc. Comp. Mach., 14:4 (1967), 645–662 | DOI | MR | Zbl

[3] Book R. V., Greibach S. A., “Quasi-realtime languages”, Math. Systems Theory, 4:2 (1970), 97–111 | DOI | MR | Zbl

[4] Patrick C. F., Chandra M. R. K., “Real-time computations with restricted nondeterminism”, Math. Systems Theory, 12 (1979), 219–231 | MR | Zbl

[5] Bruda S. D., Akl S. G., “On the necessity of formal models for real-time parallel computations”, Parallel Process. Lett., 11:2/3 (2001), 353–361 | DOI

[6] Kutrib M., “Refining nondeterminism below linear time”, J. Automata, Languages and Combinatorics, 7:4 (2002), 533–547 | MR | Zbl

[7] Bruda S. D., Akl S. G., “Real-time computation: a formal definition and its applications”, Internat. J. Computers and Appl., 25:2 (2003), 1–11

[8] Bruda S. D., “Sublinear space real-time Turing machines cannot count”, Eighth Internat. Conference on Information Technology: New Generations, 2011, 976–978 | DOI

[9] Hartmanis J., Lewis P. L. II, Stearns R. E., “Hierarchies of memory-limited computations”, Proc. of the 6th Annual IEEE Symposium on switching circuit theory and logic design, 1965, 179–190