
Accession Number : ADA139939
Title : On the Sequential Nature of Unification.
Descriptive Note : Interim research rept.,
Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
Personal Author(s) : Dwork,C ; Kanellakis,P C ; Mitchell,J C
PDF Url : ADA139939
Report Date : Mar 1984
Pagination or Media Count : 24
Abstract : The problem of unification of terms is logspace complete for P. in deriving this lower bound no use is made of the potentially concise representation of terms by directed acyclic graphs. In addition, the problem remains complete even if infinite substitutions are allowed. A consequence of this result is that parallelism cannot significantly improve on the best sequential solutions for unification. The dual problem of computing the congruence closure of an equivalence relation is also logspace complete for P. However, it is shown that for the problem of term matching, an important subcase of unification, there is a good parallel algorithm using O(log 2 n) time and nO(1) processors on a PRAM. For the O(log2 n) parallel time upper bound it is assumed that the terms are represented by directed acyclic graphs; if the longer string representation is used an O(log n) parallel time bound is obtained. (Author)
Descriptors : *Algorithms, *Sequences(Mathematics), *Parallel processing, *Computations, Problem solving, Variables, Graphs, Theorems
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE