Techniques for separating space complexity classes

DOI10.1016/S0022-0000(77)80041-XzbMath0352.68062MaRDI QIDQ1235979

Joel I. Seiferas

Publication date: 1977

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Gradually intractable problems and nondeterministic log-space lower bounds, On the structure of one-tape nondeterministic Turing machine time hierarchy, Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs, Finite automata and unary languages, Hierarchies of one-way multihead automata languages, Cyclic automata, On the complexity of deciding fair termination of probabilistic concurrent finite-state programs, Unnamed Item, P-RAM vs. RP-RAM, Unnamed Item, Hierarchy of complexity of computation of partial functions with values 0 and 1, On time-space classes and their relation to the theory of real addition, On eliminating nondeterminism from Turing machines which use less than logarithm worktape space, Multihead two-way probabilistic finite automata, A survey of space complexity, A multiparameter analysis of domino tiling with an application to concurrent systems, Communicating processes, scheduling, and the complexity of nontermination, Relating refined space complexity classes, Multihead two-way probabilistic finite automata, A space-hierarchy result on two-dimensional alternating Turing machines with only universal states

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space bounds for processing contentless inputs
• Hierarchies of Turing machines with restricted tape alphabet size
• Relating refined space complexity classes
• A hierarchy for nondeterministic time complexity
• Relationships between nondeterministic and deterministic tape complexities
• Tape-bounded Turing acceptors and principal AFLs
• On two-way multihead automata
• A class of universal linear bounded automata
• Classes of Predictably Computable Functions
• A Hierarchy Theorem for Polynomial-Space Recognition
• Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems
• Separating Nondeterministic Time Complexity Classes
• Infinite exponent partition relations and well-ordered choice
• Some Results on Tape-Bounded Turing Machines
• The Operator Gap
• A Note Concerning Nondeterministic Tape Complexities
• On Languages Accepted in Polynomial Time
• Computational Complexity and the Existence of Complexity Gaps