On time versus space II |
| |
Authors: | W Paul R Reischuk |
| |
Affiliation: | Fakultät für Mathematik, Universität Bielefeld, 4800 Bielefeld 1, Germany |
| |
Abstract: | Every t(n)-time bounded RAM (assuming the logarithmic cost measure) can be simulated by a t(n)/log t(n)-space bounded Turing machine and every t(n)-time bounded Turing machine with d-dimensional tapes by a bounded machine, where n is the length of the input. A class of storage structures which generalizes multidimensional tapes is defined. Every t(n)-time bounded Turing machine whose storage structures are in can be simulated by a t(n) loglog t(n)/log t(n)-space bounded Turing machine. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|