On the complexity of parallel implementation of logic programs.

We study several data-structures and operations that commonly arise in parallel implementations of logic programming languages. The main problems that arise in implementing such parallel systems are abstracted out and precisely stated. Upper and lower bounds are derived for several of these problems. We prove a lower bound of Ω(log n) on the overhead incurred in implementing even a simplified version of or-parallelism. We prove that the aliasing problem in parallel logic programming is at least as hard as the union-find problem. We prove that an and-parallel implementation can be realized on an extended pointer machine with an O(1) overhead. [ABSTRACT FROM AUTHOR]