| |
VOLUME 3, ISSUE 4, PAPER 3
|
Interactive Small-Step Algorithms I: Axiomatization
|
©Andreas Blass, Mathematics Dept., University of Michigan, U.S.A.
©Yuri Gurevich, Microsoft Research, Redmond, U.S.A.
©Dean Rosenzweig, University of Zagreb, Croatia
©Benjamin Rossman, Computer Science Dept., M.I.T., Cambridge, U.S.A.
|
Abstract
In earlier work, the Abstract State Machine Thesis -- that arbitrary
algorithms are behaviorally equivalent to abstract state machines -- was
established for several classes of algorithms, including ordinary, interactive,
small-step algorithms. This was accomplished on the basis of axiomatizations of
these classes of algorithms. Here we extend the axiomatization and, in a
companion paper, the proof, to cover interactive small-step algorithms that are
not necessarily ordinary. This means that the algorithms (1) can complete a
step without necessarily waiting for replies to all queries from that step and
(2) can use not only the environment's replies but also the order in which the
replies were received.
|
Publication date: November 5, 2007
Full Text: PDF | PostScript
DOI: 10.2168/LMCS-3(4:3)2007
Hit Counts: 1971 |
 Creative Commons | |
