Relating refined space complexity classes

DOI10.1016/S0022-0000(77)80042-1zbMath0352.68063MaRDI QIDQ1235980

Joel I. Seiferas

Publication date: 1977

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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

Related Items

NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES, Multihead two-way probabilistic finite automata, Remarks on multihead pushdown automata and multihead stack automata, A space-hierarchy result on two-dimensional alternating Turing machines with only universal states, Complexity lower bounds for machine computing models, On the structure of one-tape nondeterministic Turing machine time hierarchy, Finite automata and unary languages, Hierarchies of one-way multihead automata languages, Cyclic automata, Simultaneous (poly-time, log-space) lower bounds, k\(+1\) heads are better than k for PDAs, Alternating multihead finite automata, Hierarchy of complexity of computation of partial functions with values 0 and 1, A survey of space complexity, Techniques for separating space complexity classes, Amplification of slight probabilistic advantage at absolutely no cost in space, On the descriptional power of heads, counters, and pebbles, Domino-tiling games, Characterization of realizable space complexities, Context-free languages can be accepted with absolutely no space overhead, Gradually intractable problems and nondeterministic log-space lower bounds, Unnamed Item, On two-way weak counter machines, Classifying the computational complexity of problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space bounds for processing contentless inputs
• Hierarchies of Turing machines with restricted tape alphabet size
• Techniques for separating space complexity classes
• Nonerasing stack automata
• Relationships between nondeterministic and deterministic tape complexities
• On non-determinacy in simple computing devices
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• 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
• Infinite exponent partition relations and well-ordered choice
• Stack automata and compiling
• Some Results on Tape-Bounded Turing Machines
• The Operator Gap
• A Note Concerning Nondeterministic Tape Complexities
• Computational Complexity and the Existence of Complexity Gaps