文章基本信息
- 标题：The Linear Time Hierarchy Theorems for Abstract State Machines and RAMs
- 本地全文：下载
- 作者：Andreas Blass ; Yuri Gurevich
- 期刊名称：Journal of Universal Computer Science
- 印刷版ISSN：0948-6968
- 出版年度：1997
- 卷号：3
- 期号：4
- 页码：247-278
- 出版社：Graz University of Technology and Know-Center
- 摘要：We prove the Linear Time Hierarchy Theorems for random access machines and Gurevich abstract state machines. One long-term goal of this line or research is to prove lower bounds for natural linear time problems.
