Some Results on Tape-Bounded Turing Machines
From MaRDI portal
Publication:5582355
DOI10.1145/321495.321508zbMath0188.33501MaRDI QIDQ5582355
Jeffrey D. Ullman, John E. Hopcrofts
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
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, The recursion-theoretic structure of complexity classes, Some observations concerning alternating Turing machines using small space, Three-dimensional alternating Turing machines with only universal states, Halting space-bounded computations, Multiple equality sets and Post machines, Complexity of algorithms and computations, A survey of space complexity, A hierarchy result for 2-dimensional TM's operating in small space, Diagonalization, uniformity, and fixed-point theorems, Minimum-complexity pairing functions, 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, Computing with graph rewriting systems with priorities, Bridging across the \(\log(n)\) space frontier, An optimal lower bound for nonregular languages, A remark on middle space bounded alternating Turing machines, Space hierarchy theorem revised., Amplification of slight probabilistic advantage at absolutely no cost in space, For completeness, sublogarithmic space is no space., Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds., Tight lower bounds for query processing on streaming and external memory data, 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 Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines, TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
