The Linear Time Hierarchy Theorems for Abstract State Machines and RAMs
Дата
Авторы
Blass,Andreas
Gurevich,Yuri
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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.