Examples



mdbootstrap.com



 
Статья
2014

Computational power of one-way turing machines with sublogarithmic memory restrictions


A. N. LeshchevA. 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
  1. Sanjeev, A., Boaz, B. Computational Complexity: A Modern Approach (Princeton University, 2006).
  2. Rosenberg, A. L. “Real-Time Definable Languages,” J. Assoc. Comp. Mach. 14, No. 4, 645–662 (1967).
  3. Book, R. V., Greibach, S. A. “Quasi-Realtime Languages,” Math. Systems Theory 4, No. 2, 97–111 (1970).
  4. Patrick, C. F., Chandra, M. R. K. “Real-Time Computations with Restricted Nondeterminism,” Math. Systems Theory 12, 219–231 (1979).
  5. 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).
  6. Kutrib, M. “Refining Nondeterminism Below Linear Time,” J. Automata, Languages and Combinatorics, 7, No. 4, 533–547 (2002).
  7. 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).
  8. 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).
  9. 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).