Статья
2014
Computational power of one-way turing machines with sublogarithmic memory restrictions
A. N. Leshchev
Русская математика
https://doi.org/10.3103/S1066369X14090096
Abstract / Full Text
This paper considers the well-known Turing machine model, the nondeterministic real-time Turing machine. The author proves the existence of nonregular complexity classes of languages that can be recognized by nondeterministic one-way Turing machines with sublogarithmic memory restrictions. And these complexity classes form a strict hierarchy. The author defines a special language family and shows its properties to prove that hierarchy.
Author information
- Kazan (Volga Region) Federal University, ul. Kremlyovskaya 18, Kazan, 420008, RussiaA. N. Leshchev
References
- Sanjeev, A., Boaz, B. Computational Complexity: A Modern Approach (Princeton University, 2006).
- Rosenberg, A. L. “Real-Time Definable Languages,” J. Assoc. Comp. Mach. 14, No. 4, 645–662 (1967).
- Book, R. V., Greibach, S. A. “Quasi-Realtime Languages,” Math. Systems Theory 4, No. 2, 97–111 (1970).
- Patrick, C. F., Chandra, M. R. K. “Real-Time Computations with Restricted Nondeterminism,” Math. Systems Theory 12, 219–231 (1979).
- Bruda, S. D., Akl, S. G. “On the Necessity of Formal Models for Real-Time Parallel Computations,” Parallel Process. Lett. 11, No. 2/3, 353–361 (2001).
- Kutrib, M. “Refining Nondeterminism Below Linear Time,” J. Automata, Languages and Combinatorics, 7, No. 4, 533–547 (2002).
- Bruda, S. D., Akl, S. G. “Real-Time Computation: A Formal Definition and its Applications,” Internat. J. Computers and Appl. 25, No. 2, 1–11 (2003).
- Bruda, S. D. “Sublinear Space Real-Time Turing Machines Cannot Count,” in Proceedings of Eighth International Conference on Information Technology: ‘New Generations’, 976–978 (2011).
- Hartmanis, J., Lewis, P. L. II, Stearns, R. E. “Hierarchies of Memory-Limited Computations,” in Proceedings of the 6th Annual IEEE Symposium on Switching Circuit Theory and Logic Design, 179–190 (1965).