Logspace Reducibility

Citation: Erich Grädel and Marc Spielmann, "Logspace Reducibility via Abstract State Machines". In J. Wing, J. Woodcock, and J. Davies (eds.), Proceedings of FM'99, Volume II, Springer LNCS 1709, 1999, 1738--1757.
Summary: ASMs are used to investigate logspace reducibility among structures, capturing the choiceless fragment of logspace.
Subjects: Logic & Computability
Download: PostScript, PDF, Compressed PostScript
Notes: Based on the choiceless polynomial time paper. (Courtesy of Springer-Verlag.)