On the Sequential Nature of Unification.

Abstract

The problem of unification of terms is log-space 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 log-space 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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1984
Accession Number
ADA139939

Entities

People

  • C. Dwork
  • J. C. Mitchell
  • P. C. Kanellakis

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Weapons Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Automata
  • Computational Complexity
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Construction
  • Information Processing
  • Information Systems
  • Language
  • Machines
  • Military Research
  • Parallel Computing
  • Security
  • Technical Information Centers

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Calculus or Mathematical Analysis
  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Space