A Tree Representation for Parallel Problem Solving
National Conference on Artificial Intelligence (AAAI) 1988
Publication Type: Paper
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.
L. V. Kale, "A Tree Representation for Parallel Problem Solving", Proceedings of AAAI, August 1988, pp. 677-681.