摘要
This paper presents the design of a special-purpose cellular tree architecture for the unification algorithm. The unification algorithm either finds the most general substitution which makes a set of terms identical, or elsereturns failure. The resulting substitution is permitted to contain loops. Manyof the more recent pure logic programs make use of such recursive substitutions to store data structures which are accessed in a lazy fashion. So lackof such an occurs check is intentional. The algorithm involves only integercomparison and shifting operations between adjacent cells in a data-drivencomputation mode. The physical design of a VLSI chip, therefore, shouldbe quite easy. Each unification problem runs on the cellular tree in worst-case timeO(n• logn), wherenis the number of input symbols. Many unification problems can be run simultaneously on the same chip with no slowdown. © 1994 Taylor & Francis Group, LLC.