首页 | 本学科首页   官方微博 | 高级检索  
     


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 t(n)5log1t(n)/log t(n)-space bounded machine, where n is the length of the input. A class E of storage structures which generalizes multidimensional tapes is defined. Every t(n)-time bounded Turing machine whose storage structures are in E can be simulated by a t(n) loglog t(n)/log t(n)-space bounded Turing machine.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号