JUCS - Journal of Universal Computer Science 3(4): 247-278, doi: 10.3217/jucs-003-04-0247
The Linear Time Hierarchy Theorems for Abstract State Machines and RAMs
expand article infoAndreas Blass‡, Yuri Gurevich§
‡ Partially supported by NSF grant DMS--9505118. Mathematics Department, University of Michigan§ University of Michigan, United States of America

Corresponding author: Andreas Blass ( ablass@umich.edu )

© Andreas Blass, Yuri Gurevich.
This article is freely available under the J.UCS Open Content License.
Citation: Blass A, Gurevich Y (1997) The Linear Time Hierarchy Theorems for Abstract State Machines and RAMs. JUCS - Journal of Universal Computer Science 3(4): 247-278. https://doi.org/10.3217/jucs-003-04-0247
Open Access
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.