An extension of Savitch's theorem to small space bounds

DOI10.1016/0020-0190(81)90013-2zbMath0457.68040OpenAlexW2061157732MaRDI QIDQ1151259

Martin Tompa

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90013-2

zbMATH Keywords

alternating time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Alternating on-line Turing machines with only universal states and small space bounds ⋮ On the parallel complexity of loops ⋮ On eliminating nondeterminism from Turing machines which use less than logarithm worktape space ⋮ A survey of space complexity ⋮ Some classes of languages in \(NC^ 1\) ⋮ Bandwidth constraints on problems complete for polynomial time

Cites Work

• Relationships between nondeterministic and deterministic tape complexities
• Alternation
• Unnamed Item