Deterministic One-Way Turing Machines with Sublinear Space

• Autorzy: Kutrib M. , Provillard J. , Vaszil G. , Wendlandt M.

Identyfikatory

DOI

10.3233/FI-2015-1147

• Języki publikacji: EN

Abstrakty

EN

Deterministic one-way Turing machines with sublinear space bounds are systematically studied. We distinguish among the notions of strong, weak, and restricted space bounds. The latter is motivated by the study of P automata. The space available on the work tape depends on the number of input symbols read so far, instead of the entire input. The class of functions space constructible by such machines is investigated, and it is shown that every function f that is space constructible by a deterministic two-way Turing machine, is space constructible by a strongly f space-bounded deterministic one-way Turing machine as well. We prove that the restricted mode coincides with the strong mode for space constructible functions. The known infinite, dense, and strict hierarchy of strong space complexity classes is derived also for the weak mode by Kolmogorov complexity arguments. Finally, closure properties under AFL operations, Boolean operations and reversal are shown.

Słowa kluczowe

EN

machine theory; Kolmogorov complexity; electronic data processing; information theory; boolean matrices

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 136, nr 1/2
• Strony: 139--155
• Opis fizyczny: Bibliogr. 14 poz., tab.

Twórcy

autor

Kutrib M.

• Institut für Informatik Universität Giessen Arndtstr. 2, 35392 Giessen, Germany

autor

Provillard J.

• Laboratoire I3S Universite Nice Sophia Antipolis 06903 Sophia Antipolis Cedex, France

autor

Vaszil G.

• Department of Computer Science University of Debrecen 4028 Debrecen, Kassaiut 26, Hungary

autor

Wendlandt M.

• Institut für Informatik Universität Giessen Arndtstr. 2, 35392 Giessen, Germany

Bibliografia

• [1] Allender, E.: Isomorphisms and 1-L Reductions, J. Comput. System Sci., 36, 1988, 336–350.
• [2] Balcázar, J. L., D´ıaz, J., Gabarró, J.: Structural Complexity I, Springer, Berlin, 1988.
• [3] Burtschick, H.-J., Hoene, A.: The Degree Structure of 1-L Reductions, Mathematical Foundations of Computer Science (MFCS 1992) (I. M. Havel, V. Koubek, Eds.), 629, Springer, 1992.
• [4] Csuhaj-Varjú, E., Ibarra, O. H., Vaszil, G.: On the Computational Complexity of P Automata, Natural Computing, 5, 2006, 109–126.
• [5] Hartmanis, J., Immerman, N., Mahaney, S. R.: One-Way Log-Tape Reductions, Foundations of Computer Science (FOCS 1978), IEEE Computer Society, 1978.
• [6] Hartmanis, J., Mahaney, S. R.: Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata, SIAM J. Comput., 10, 1981, 383–390.
• [7] Hopcroft, J. E., Ullman, J. D.: Some Results on Tape-Bounded TuringMachines, J. ACM, 16, 1969, 168–177.
• [8] Lewis II, P. M., Stearns, R. E., Hartmanis, J.: Memory Bounds for Recognition of Context-Free and Context-Sensitive Languages, Symposium on Switching Circuit Theory and Logical Design, IEEE Computer Society, 1965.
• [9] Li, M., Vitányi, P. M. B.: An Introduction to Kolmogorov Complexity and Its Applications, Springer, 1993.
• [10] Mereghetti, C.: Testing the Descriptional Power of Small Turing Machines on Nonregular Language Acceptance, Int. J. Found. Comput. Sci., 19, 2008, 827–843.
• [11] Stearns, R. E., Hartmanis, J., Lewis II, P. M.: Hierarchies of memory limited computations, Symposium on Switching Circuit Theory and Logical Design, IEEE Computer Society, 1965.
• [12] Szepietowski, A.: Turing Machines with Sublogarithmic Space, vol. 843 of LNCS, Springer, 1994.
• [13] Szepietowski, A.: Weak and Strong One-Way Space Complexity Classes, Inform. Process. Lett., 68, 1998, 299–302.
• [14] Wagner, K., Wechsung, G.: Computational Complexity, Reidel, Dordrecht, 1986.