Two-Tape Simulation of Multitape Turing Machines

Cited in

(70)

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
Local reduction
Domino-tiling games
Linear-time simulation of multihead Turing machines
Time bounded random access machines
A linear time two tape merge
PAC-learning gains of Turing machines over circuits and neural networks
Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts
Modeling multitape Minsky and Turing machines by three-tape Minsky machines
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
Relativized depth
Turing machines for dummies. Why representations do matter
Local reductions
Amplifying circuit lower bounds against polynomial time, with applications
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
An application of the translational method
On uniformity and circuit lower bounds
A tight lower bound for on-line monotonic list labeling
Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
New time hierarchy results for deterministic TMS
The undecidability of the domino problem
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
Effective guessing has unlikely consequences
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
Structure in average case complexity
Complexity barriers as independence
On quasilinear-time complexity theory
On the power of several queues
Good things come to those who wait. Dishonest-majority coin-flipping requires delay functions
Lower bounds for Levin-Kolmogorov complexity
Characterizations of pushdown machines in terms of time-bounded computers
Differentially oblivious Turing machines
Oblivious complexity classes revisited: lower bounds and hierarchies
Simulating time with square-root space
A formalization of multi-tape Turing machines
A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
Improved simulation of nondeterministic Turing machines
Data structures for distributed counting
Minimizing access pointers into trees and arrays
Time hierarchies for cryptographic function inversion with advice
Milking the Aanderaa argument

This page was built for publication: Two-Tape Simulation of Multitape Turing Machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5526975)