|Publications & Technical Reports|
The Impact of AND/OR Search Spaces on Constraint Satisfaction and CountingRina Dechter and Robert Mateescu
The contribution of this paper is in demonstrating the impact of AND/OR search spaces view on solutions counting. In contrast to the traditional (OR) search space view, the AND/OR search space displays independencies present in the graphical model explicitly and may sometimes reduce the search space exponentially. Empirical evaluation focusing on counting demonstrates the spectrum of search and inference within the AND/OR search spaces.