Live Webcast 15th Annual Charm++ Workshop

A tree-representation for problem-solving suited for parallel processing is proposed. We give a formal definition of REDUCE-OR trees and illustrate it with a detailed example. Each node of the proposed tree denotes a completely described subproblem. When literals share variables, it permits solutions from one literal to prune the search space for the other literals. Attempts to get such pruning with AND-OR trees lose a significant form of "OR parallelism." An alternative strategy for searching AND-OR trees leads to the SLD trees, which miss the "AND-parallelism." The REDUCE-OR trees are especially useful for problems with a generate-and-test flavor.