A Tree Representation for Parallel Problem Solving

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.

@INPROCEEDINGS{TreeRepAAAI88,
        author = "L. V. Kal{\'e}",
        title = "A Tree Representation for Parallel Problem
Solving",
        booktitle = "Proceedings of AAAI", 
        month = "August", 
        year = "1988", 
        pages = "677-681",
        annote = "88-6",
        group = Y,
}