Conference paper

Deterministic One-Way Turing Machines with Sublinear Space


Authors listKutrib, Martin; Provillard, Julien; Vaszil, Gyoergy; Wendlandt, Matthias

Publication year2015

Pages139-155

JournalFundamenta Informaticae

Volume number136

Issue number1-2

ISSN0169-2968

eISSN1875-8681

DOI Linkhttps://doi.org/10.3233/FI-2015-1147

Conference5th Workshop on Non-Classical Models of Automata and Applications (NCMA)

PublisherSAGE Publications


Abstract
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.



Citation Styles

Harvard Citation styleKutrib, M., Provillard, J., Vaszil, G. and Wendlandt, M. (2015) Deterministic One-Way Turing Machines with Sublinear Space, Fundamenta Informaticae, 136(1-2), pp. 139-155. https://doi.org/10.3233/FI-2015-1147

APA Citation styleKutrib, M., Provillard, J., Vaszil, G., & Wendlandt, M. (2015). Deterministic One-Way Turing Machines with Sublinear Space. Fundamenta Informaticae. 136(1-2), 139-155. https://doi.org/10.3233/FI-2015-1147



Keywords


Complexity

Last updated on 2025-02-04 at 02:05