Tape bounds for time-bounded Turing machines

DOI10.1016/S0022-0000(72)80017-5MaRDI QIDQ2552124zbMATH OpenOpenAlexFDO

Authors Michael S. Paterson

Publication date 1972

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0022-0000(72)80017-5

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Analysis of algorithms and problem complexity (68Q25)

Cites work

• scientific article; zbMATH DE number 3453571 (Why is no real title available?)
• Relations Between Time and Tape Complexities
• Relationships between nondeterministic and deterministic tape complexities

Cited in

(20)

• Complexity lower bounds for machine computing models
• Speedups of deterministic machines by synchronous parallel machines
• On the structure of one-tape nondeterministic Turing machine time hierarchy
• Relating the power of cellular arrays to their closure properties
• Parallel computation with threshold functions
• On alternation
• A space bound for one-tape multidimensional Turing machines
• On time versus space. II
• Complexity of algorithms and computations
• Time complexity of multidimensional Turing machines
• Log space machines with multiple oracle tapes
• On minimal-node-cost planar embeddings
• On time versus space III
• Space-bounded simulation of multitape turing machines
• scientific article; zbMATH DE number 3507976 (Why is no real title available?)
• Space bounds for a game on graphs
• Complexity and polynomially solvable special cases of QUBO
• Complexity of nondeterministic multitape computations based on crossing sequences
• On some open problems concerning the complexity of cellular arrays
• Simulating time with square-root space

This page was built for publication: Tape bounds for time-bounded Turing machines

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