TY - JOUR
T1 - On commutativity based edge lean search
AU - Bosnacki, D.
AU - Elkind, E.
AU - Genest, B.
AU - Peled, D.
PY - 2010
Y1 - 2010
N2 - Exploring a graph through search is one of the most basic building blocks of various applications. In a setting with a huge state space, such as in testing and verification, optimizing the search may be crucial. We consider the problem of visiting all states in a graph where edges are generated by actions and the (reachable) states are not known in advance. Some of the actions may commute, i.e., they result in the same state for every order in which they are taken (this is the case when the actions are performed independently by different processes). We show how to use commutativity to achieve full coverage of the states traversing considerably fewer edges.
AB - Exploring a graph through search is one of the most basic building blocks of various applications. In a setting with a huge state space, such as in testing and verification, optimizing the search may be crucial. We consider the problem of visiting all states in a graph where edges are generated by actions and the (reachable) states are not known in advance. Some of the actions may commute, i.e., they result in the same state for every order in which they are taken (this is the case when the actions are performed independently by different processes). We show how to use commutativity to achieve full coverage of the states traversing considerably fewer edges.
U2 - 10.1007/s10472-009-9167-0
DO - 10.1007/s10472-009-9167-0
M3 - Article
SN - 1012-2443
VL - 56
SP - 187
EP - 210
JO - Annals of Mathematics and Artificial Intelligence
JF - Annals of Mathematics and Artificial Intelligence
IS - 2
ER -