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.)

[an error occurred while processing this directive]

Abstract State Machines