Blass, Andreas and Gurevich, Yuri and Rosenzweig, Dean and Rossman, Benjamin - Interactive Small-Step Algorithms I: Axiomatization

lmcs:1200 - Logical Methods in Computer Science, November 5, 2007, Volume 3, Issue 4
Interactive Small-Step Algorithms I: Axiomatization

Authors: Blass, Andreas and Gurevich, Yuri and Rosenzweig, Dean and Rossman, Benjamin

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.


Source : oai:arXiv.org:0707.3782
DOI : 10.2168/LMCS-3(4:3)2007
Volume: Volume 3, Issue 4
Published on: November 5, 2007
Submitted on: June 11, 2007
Keywords: Computer Science - Logic in Computer Science,F.1.1,F.1.2,F.3.1


Share

Consultation statistics

This page has been seen 45 times.
This article's PDF has been downloaded 11 times.