Local First Search (LFS) is a partial order technique for
reducing the number of states to be explored when trying to decide
reachability of a local (component) property in a parallel system; it is
based on an analysis of the structure of the partial orders of executions
in such systems. Intuitively, LFS is based on a criterion that allows to
guide the search for such local properties by limiting the “concurrent
progress��? of components.
In this paper, we elaborate the analysis of the partial orders in ques-
tion and obtain related but significantly stronger criteria for reductions,
show their relation to the previously established criterion, and discuss
the algorithmics of the proposed improvement. Our contribution is both
fundamental in providing better insights into LFS and practical in pro-
viding an improvement of high potential.
|Name||Lecture Notes in Computer Science|
|Conference||Third International Colloquium on Theoretical Aspects of Computing, Tunis, Tunisia|
|Period||26/10/06 → …|