Optimal expression evaluation and term matching on the Boolean hypercube and on hypercubic networks

An optimal tree contraction algorithm for the Boolean hypercube and constant degree hypercubic networks, such as the shuffle exchange or the butterfly network, is presented. The algorithm is based on a recursive approach, uses novel routing techniques, and, for certain small subtrees, simulates optimal PRAM algorithms. For trees of size n, stored in-order on a p processor hypercube, the running time of the algorithm is O/spl lsqb/(n/p)log p/spl rsqb/, which can be shown to be optimal on the hypercube by a corresponding lower bound. Tree contraction can be used to evaluate algebraic expressions consisting of operators +,/spl minus/,/spl middot/,/ and rational operands, as well as for the membership problem for certain subclasses of languages in DCFL. The same algorithmic ingredients can also be used to solve the term matching problem, one of the fundamental problems in logic programming.<>