Two-Tape Simulation of Multitape Turing Machines
From MaRDI portal
Publication:5526975
DOI10.1145/321356.321362zbMath0148.24801WikidataQ55923064 ScholiaQ55923064MaRDI QIDQ5526975
Richard E. Stearns, F. C. Hennie
Publication date: 1966
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321356.321362
Related Items
An application of the translational method, The theory of languages, The theory of languages, Computational complexity of random access stored program machines, On restricted turing computability, Subrecursiveness: Machine-independent notions of computability in restricted time and storage, Time-space tradeoffs for SAT on nonuniform machines, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, On quasilinear-time complexity theory, On the power of several queues, A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes, Data structures for distributed counting, Minimizing access pointers into trees and arrays, Time hierarchies for cryptographic function inversion with advice, Milking the Aanderaa argument, Complexity lower bounds for machine computing models, Tape versus queue and stacks: The lower bounds, Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time, On time hierarchies, Hierarchy of complexity of computation of partial functions with values 0 and 1, An improved simulation result for ink-bounded Turing machines, Complexity of algorithms and computations, An information-theoretic approach to time bounds for on-line computation, The network complexity and the Turing machine complexity of finite functions, Relations between diagonalization, proof systems, and complexity gaps, Almost-everywhere complexity hierarchies for nondeterministic time, On average time hierarchies, On the simulation of many storage heads by one, Deterministic multitape automata computations, A hierarchy for nondeterministic time complexity, Time-space tradeoffs for satisfiability, Domino-tiling games, Linear-time simulation of multihead Turing machines, Time bounded random access machines, A linear time two tape merge, Generality's price: Inescapable deficiencies in machine-learned programs, Time-restricted sequence generation, k-Band-Simulation von k-Kopf-Turing-Maschinen. (k-tape simulation of k- head Turing machines), Zwei-Band Simulation von Turingmaschinen. (Two-tape simulation of Turing machines), On non-determinacy in simple computing devices, Writing stack acceptors, Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata, On two-way multihead automata, Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines, On the complexity of finite, pushdown, and stack automata, Towards the Actual Relationship Between NP and Exponential Time
