Naslov
Interactive Small-Step Algorithms I: Axiomatization

Autori
Blass, Andreas ; Gurevich, Yuri ; Rosenzweig, Dean ; Rossman, Benjamin

Izvornik
Logical Methods in Computer Science (1860-5974) 3 (2007), 4; 1-29

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
behavioral theory of algorithms ; ASM thesis ; interactive algorithms

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA