ON THE SEQUENTIAL NATURE OF UNIFICATION.

被引：70

作者：

Dwork, Cynthia ^{[1
]}

Kanellakis, Paris C. ^{[1
]}

Mitchell, John C. ^{[1
]}

机构：

[1] Brown Univ, Providence, RI, USA, Brown Univ, Providence, RI, USA

来源：

Journal of Logic Programming | 1984年 / 1卷 / 01期

基金：

美国国家科学基金会;

关键词：

COMPUTER PROGRAMMING LANGUAGES;

D O I：

10.1016/0743-1066(84)90022-0

中图分类号：

学科分类号：

摘要：

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. However, the authors show that for the problem of term matching, an important subcase of unification, there is a good parallel algorithm using O(log**2n) time and n**o**(**1**) processors on a PRAM.

引用

页码：35 / 50