On efficient deterministic simulation of Turing machine computations below logspace
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)].
- scientific article; zbMATH DE number 17549
- Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
- Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
- Improved simulation of nondeterministic Turing machines
- Deterministic simulation of non-deterministic Turing machines (detailed abstract)
- An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits
- A survey of space complexity
- scientific article; zbMATH DE number 3883610 (Why is no real title available?)
- On efficient simulations of multicounter machines
- On space and time efficient TM simulations of some restricted classes of PDA's
- scientific article; zbMATH DE number 3986645 (Why is no real title available?)
- Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
- Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space
- Trading determinism for time in space bounded computations
- Deterministic simulation of non-deterministic Turing machines (detailed abstract)
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)