On time versus space. II

DOI10.1016/0022-0000(81)90035-0MaRDI QIDQ1152954zbMATH OpenOpenAlexFDO

Authors Wolfgang J. Paul, Rüdiger Reischuk

Publication date 1981

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

Full work available at URL https://doi.org/10.1016/0022-0000(81)90035-0

zbMATH Keywords

Turing machinerandom access machinestorage structuresmultidimensional tapes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• scientific article; zbMATH DE number 3692650 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Boolean Memories
• On Time Versus Space
• On the Computational Complexity of Algorithms
• Relations Among Complexity Measures
• Relations Between Time and Tape Complexities
• Tape bounds for time-bounded Turing machines
• Two fast simulations which imply some fast string matching and palindrome-recognition algorithms

Cited in

(7)

• Linear speed-up does not hold on Turing machines with tree storages
• Minimizing access pointers into trees and arrays
• An information-theoretic approach to time bounds for on-line computation
• Improved simulation of nondeterministic Turing machines
• On time versus space III
• On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
• Parallelizing time with polynomial circuits

This page was built for publication: On time versus space. II

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