| |
VOLUME 3, ISSUE 4, PAPER 4
Interactive Small-Step Algorithms II: Abstract State Machines and the
Characterization Theorem
|
©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. In Part I (Interactive Small-Step Algorithms I:
Axiomatization), the axiomatization was extended 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. In order to prove the
thesis for algorithms of this generality, we extend here the definition of
abstract state machines to incorporate explicit attention to the relative
timing of replies and to the possible absence of replies. We prove the
characterization theorem for extended abstract state machines with respect to
general algorithms as axiomatized in Part I.
|
Publication date: November 5, 2007
Full Text: PDF | PostScript
DOI: 10.2168/LMCS-3(4:4)2007
Hit Counts: 932 |
 Creative Commons | |
