On efficient deterministic simulation of turing machine computations below logaspace

DOI10.1007/BF01699458zbMath0605.68036OpenAlexW2022693656MaRDI QIDQ3742717

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 languagespace boundnondeterministic Turing machine

Mathematics Subject Classification ID

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

Related Items (2)

Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties ⋮ A survey of space complexity

Cites Work

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

This page was built for publication: On efficient deterministic simulation of turing machine computations below logaspace