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

An optimal tree contraction algorithm for the boolean hypercube and the 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 on a p processor hypercube in in-order, the running time of the algorithm is O([n/p] log p), 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 +, -, ·,/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.