Tape bounds for time-bounded Turing machines

DOI10.1016/S0022-0000(72)80017-5zbMATH Open0236.02031OpenAlexW1980572240MaRDI QIDQ2552124FDOQ2552124

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

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

Cites Work

• Relationships between nondeterministic and deterministic tape complexities
• Relations Between Time and Tape Complexities
• Title not available (Why is that?)

Cited In (19)

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

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)