Stronger Reduction Criteria for Local First Search
Stronger Reduction Criteria for Local First Search
复制标题
本地优先搜索的更强的减少标准
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
W. Vogler
中科院分区：
文献类型：
--
作者：
M. E. Kurbán;P. Niebert;Hongyang Qu;W. Vogler
局部优先搜索（LFS）是一种偏序技术，用于在并行系统中确定局部（组件）属性的可达性时减少需要探索的状态数；它是基于对这类系统中部分执行顺序结构的分析。直观地说，LFS基于一个标准，该标准允许通过限制组件的“并发进程”来指导对此类局部属性的搜索。
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 question 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 providing an improvement of high potential, as is illustrated by experimental results.