Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space

DOI10.1137/0222009zbMath0766.68039OpenAlexW2074574452MaRDI QIDQ4037687

Viliam Geffert

Publication date: 16 May 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0222009

zbMATH Keywords

tally setsnondeterministic Turing machinespace bounded computationnondeterministic space

Mathematics Subject Classification ID

Related Items (10)

Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds. ⋮ Weak and strong one-way space complexity classes ⋮ A remark on middle space bounded alternating Turing machines ⋮ Complementing two-way finite automata ⋮ Space hierarchy theorem revised. ⋮ TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE ⋮ A hierarchy that does not collapse : alternations in low level space ⋮ Bridging across the \(\log(n)\) space frontier ⋮ A variant of inductive counting ⋮ The alternation hierarchy for sublogarithmic space is infinite

This page was built for publication: Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space