Skip to main content

Interactive small-step algorithms II: Abstract state machines and the characterization theorem

Publication ,  Journal Article
Blass, A; Gurevich, Y; Rosenzweig, D; Rossman, B
Published in: Logical Methods in Computer Science
November 5, 2007

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 a companion paper [5] the axiomatisation 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 ASMs with respect to general algorithms as axiomatised in [5].

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Logical Methods in Computer Science

DOI

EISSN

1860-5974

Publication Date

November 5, 2007

Volume

3

Issue

4

Related Subject Headings

  • 0803 Computer Software
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Blass, A., Gurevich, Y., Rosenzweig, D., & Rossman, B. (2007). Interactive small-step algorithms II: Abstract state machines and the characterization theorem. Logical Methods in Computer Science, 3(4). https://doi.org/10.2168/LMCS-3(4:4)2007
Blass, A., Y. Gurevich, D. Rosenzweig, and B. Rossman. “Interactive small-step algorithms II: Abstract state machines and the characterization theorem.” Logical Methods in Computer Science 3, no. 4 (November 5, 2007). https://doi.org/10.2168/LMCS-3(4:4)2007.
Blass A, Gurevich Y, Rosenzweig D, Rossman B. Interactive small-step algorithms II: Abstract state machines and the characterization theorem. Logical Methods in Computer Science. 2007 Nov 5;3(4).
Blass, A., et al. “Interactive small-step algorithms II: Abstract state machines and the characterization theorem.” Logical Methods in Computer Science, vol. 3, no. 4, Nov. 2007. Scopus, doi:10.2168/LMCS-3(4:4)2007.
Blass A, Gurevich Y, Rosenzweig D, Rossman B. Interactive small-step algorithms II: Abstract state machines and the characterization theorem. Logical Methods in Computer Science. 2007 Nov 5;3(4).

Published In

Logical Methods in Computer Science

DOI

EISSN

1860-5974

Publication Date

November 5, 2007

Volume

3

Issue

4

Related Subject Headings

  • 0803 Computer Software
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics