The parallel complexity of single rule logic programs

AbstractWe consider logic programs without function symbols, called Datalog programs, and study their parallel complexity. We survey the tools developed for proving that there is a PRAM algorithm which computes the minimum model of a Datalog program in polylogarithmic parallel time using a polynomial number of processors (that is, for proving membership in NC). We extend certain of these tools to be applied to a wider class of programs; as they were, they were applied to chain rule programs (i.e., the relations on the right-hand side of the rule are binary and form a chain). We examine the parallel complexity of weak-chain rule programs (i.e., the relations on the right-hand side of the rule form a weak chain), and prove certain subclasses to belong to NC. Finally we prove a wide class of programs to be log space complete for P, by giving sufficient conditions for a single rule program to be P-complet