Linear Time Hierarchy

Citation: Andreas Blass and Yuri Gurevich, "The Linear Time Hierarchy Theorems for Abstract State Machines and RAMs", Journal of Universal Computer Science, vol. 3, no. 4 (1997), 247--278.
Summary: A proof of the Linear Time Hierarchy Theorems for random access machines and Gurevich ASMs. One long-term goal of this line of research is to prove lower bounds for natural linear-time problems.
Subjects: Logic & Computability
Download: PostScript, PDF, Compressed PostScript.
Notes: (Courtesy of Springer-Verlag.)