Some Results on Tape-Bounded Turing Machines
From MaRDI portal
Publication:5582355
DOI10.1145/321495.321508zbMath0188.33501OpenAlexW2089690927MaRDI QIDQ5582355
John E. Hopcrofts, Jeffrey D. Ullman
Publication date: 1969
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321495.321508
Related Items
Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds. ⋮ An optimal lower bound for nonregular languages ⋮ Two-way non-uniform finite automata ⋮ Tight lower bounds for query processing on streaming and external memory data ⋮ Some observations concerning alternating Turing machines using small space ⋮ A remark on middle space bounded alternating Turing machines ⋮ Three-dimensional alternating Turing machines with only universal states ⋮ On languages accepted with simultaneous complexity bounds and their ranking problem ⋮ Halting space-bounded computations ⋮ Space hierarchy theorem revised. ⋮ Multiple equality sets and Post machines ⋮ Two-Way Non-Uniform Finite Automata ⋮ Complexity of algorithms and computations ⋮ TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE ⋮ Reversibility of computations in graph-walking automata ⋮ A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines ⋮ Two-Way Automata versus Logarithmic Space ⋮ A survey of space complexity ⋮ A hierarchy result for 2-dimensional TM's operating in small space ⋮ Minimal Size of Counters for (Real-Time) Multicounter Automata ⋮ Diagonalization, uniformity, and fixed-point theorems ⋮ Minimum-complexity pairing functions ⋮ Infinite games with finite knowledge gaps ⋮ Two-way automata versus logarithmic space ⋮ A very hard log-space counting class ⋮ Space bounds for processing contentless inputs ⋮ Remarks on the complexity of nondeterministic counter languages ⋮ Nonexistence of program optimizers in several abstract settings ⋮ On tape bounds for single letter alphabet language processing ⋮ Techniques for separating space complexity classes ⋮ Relating refined space complexity classes ⋮ On store languages of language acceptors ⋮ Computing with graph rewriting systems with priorities ⋮ A combinatorial characterization of smooth LTCs and applications ⋮ Bridging across the \(\log(n)\) space frontier ⋮ Time- and tape-bounded Turing acceptors and AFLs ⋮ On the computational power of pushdown automata ⋮ Some properties of one-pebble Turing machines with sublogarithmic space ⋮ A note on alternating on-line Turing machines ⋮ Bandwidth constraints on problems complete for polynomial time ⋮ A space-hierarchy result on two-dimensional alternating Turing machines with only universal states ⋮ For completeness, sublogarithmic space is no space. ⋮ The recursion-theoretic structure of complexity classes ⋮ Amplification of slight probabilistic advantage at absolutely no cost in space
