Deterministic One-Way Turing Machines with Sublinear Space
Martin Kutrib, Julien Provillard, György Vaszil, Matthias Wendlandt · Fundamenta Informaticae · 2015
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 th