ON THE PARALLEL COMPLEXITY OF ACYCLIC LOGIC PROGRAMS
Shiva Chaudhuri, Yannis Dimopoulos, Christos Zaroliagis · Parallel Processing Letters · 1996
In this paper we investigate the parallel complexity of computing the stable model of acyclic general logic programs. Within this class of logic programs, we consider the cases of negative and definite logic programs. Both cases are proved to be [Formula: see text]-complete. We prove the same for a related problem, namely that of computing the kernel of a directed acyclic graph.