The Linear Time Hierarchy Theorems for Abstract State Machines and RAMs

Andreas Blass (Partially supported by NSF grant DMS--9505118. Mathematics Department, University of Michigan)

Yuri Gurevich (Partially supported by NSF grant DMS--9505118. Mathematics Department, University of Michigan)

Abstract: 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.