Paper Info
Title
Exact exploration and hanging algorithms
Abstract
Recent analysis of sequential algorithms resulted in their axiomatization and in a representation theorem stating that, for any sequential algorithm, there is an abstract state machine (ASM) with the same states, initial states and state transitions. That analysis, however, abstracted from details of intra-step computation, and the ASM, produced in the proof of the representation theorem, may and often does explore parts of the state unexplored by the algorithm. We refine the analysis, the axiomatization and the representation theorem. Emulating a step of the given algorithm, the ASM, produced in the proof of the new representation theorem, explores exactly the part of the state explored by the algorithm. That frugality pays off when state exploration is costly. The algorithm may be a high-level specification, and a simple function call on the abstraction level of the algorithm may hide expensive interaction with the environment. Furthermore, the original analysis presumed that state functions are total. Now we allow state functions, including equality, to be partial so that a function call may cause the algorithm as well as the ASM to hang. Since the emulating ASM does not make any superfluous function calls, it hangs only if the algorithm does.
Year
DOI
Venue
2010
10.1007/978-3-642-15205-4_14
CSL
Keywords
Field
DocType
exact exploration,original analysis,state function,new representation theorem,initial state,state transition,sequential algorithm,recent analysis,state exploration,abstract state machine,representation theorem
Subroutine,Computer science,Representation theorem,State function,Abstract state machines,Algorithm,Hang,Abstraction layer,Sequential algorithm,Computation
Conference
Volume
ISSN
ISBN
6247
0302-9743
3-642-15204-X
Citations 
PageRank 
References 
7
0.58
13
Authors
3
Name
Order
Citations
PageRank
Andreas Blass170.58
Nachum Dershowitz22818473.00
Yuri Gurevich33258505.49