On efficient deterministic simulation of turing machine computations below logaspace

DOI10.1007/BF01699458MaRDI QIDQ3742717zbMATH OpenOpenAlexFDO

Authors Bruce Litow

Publication date 1985

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01699458

zbMATH Keywords

bounded languagenondeterministic Turing machinespace bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• 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)

Cites work

• On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
• Relationships between nondeterministic and deterministic tape complexities

Cited in

(10)

• 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 logaspace

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