A Tree Representation for Parallel Problem Solving

Abstract

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.