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

Analysis of algorithms and problem complexity (68Q25)

Related Items (27)

Gradually intractable problems and nondeterministic log-space lower bounds ⋮ On the structure of one-tape nondeterministic Turing machine time hierarchy ⋮ On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection ⋮ Characterization of realizable space complexities ⋮ 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 ⋮ Unnamed Item ⋮ On two-way weak counter machines ⋮ Generalizations of Checking Stack Automata: Characterizations and Hierarchies ⋮ Hierarchy of complexity of computation of partial functions with values 0 and 1 ⋮ Classifying the computational complexity of problems ⋮ NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES ⋮ Multihead two-way probabilistic finite automata ⋮ A survey of space complexity ⋮ On the descriptional power of heads, counters, and pebbles ⋮ Techniques for separating space complexity classes ⋮ Multihead two-way probabilistic finite automata ⋮ Domino-tiling games ⋮ 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 ⋮ Context-free languages can be accepted with absolutely no space overhead ⋮ Amplification of slight probabilistic advantage at absolutely no cost in space

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

This page was built for publication: Relating refined space complexity classes