On efficient deterministic simulation of Turing machine computations below logspace

From MaRDI portal





It is shown that a bounded language accepted by a nondeterministic Turing machine in space S(n)\(\in o(\log n)\) can be accepted by a deterministic Turing machine in space \(Max\{(s(n)^ 2,\log n\}\). This can be interpretd as extending Savitch's algorithm [\textit{W. Savitch}, J. Comput. Syst. Sci. 4, 177-192 (1970; Zbl 0188.335)] below logspace. Results of \textit{H. Alt} [Acta Inf. 12, 33-61 (1979; Zbl 0389.68043)] can be used to show that in the general case the indicated space bound cannot be improved. The result can also be interpreted as a sharpening in the special case of bounded languages of the results of \textit{B. Monien} and \textit{I. H. Sudborough} [Theor. Comput. Sci. 21, 237-253 (1982; Zbl 0493.68046)].











This page was built for publication: On efficient deterministic simulation of Turing machine computations below logspace

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3742717)