On simultaneous resource bounds
- 1 October 1979
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 307-311
- https://doi.org/10.1109/sfcs.1979.29
Abstract
It is well known that time bounds for machines correspond closely to size bounds for networks, and that space bounds correspond to depth bounds. It is not known whether simultaneous time and space bounds correspond to simultaneous size and depth bounds. It is shown here that simultaneous time and "reversal" bounds correspond to simultaneous size and depth bounds, and that simultaneous time and space bounds correspond to simultaneous size and "width" bounds.Keywords
This publication has 9 references indexed in Scilit:
- Tree-size bounded alternationJournal of Computer and System Sciences, 1980
- Parallel Prefix ComputationJournal of the ACM, 1980
- On uniform circuit complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Relations Among Complexity MeasuresJournal of the ACM, 1979
- Deterministic CFL's are accepted simultaneously in polynomial time and log squared spacePublished by Association for Computing Machinery (ACM) ,1979
- On Relating Time and Space to Size and DepthSIAM Journal on Computing, 1977
- The network complexity and the Turing machine complexity of finite functionsActa Informatica, 1976
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971
- Two-Tape Simulation of Multitape Turing MachinesJournal of the ACM, 1966