On the complexities of non-Horn Clause logic programming
On the Complexities of Non-Horn Clause Logic Programming

There have been active work to extend the Prolog style Horn Clause logic programming to non-Horn clauses. In this paper, we will analyze the complexities of several such extensions. The purpose is to understand the computational complexity of these inference systems. The analyses do not prove that any one system is better than the others all the time. But they do suggest that one system may be better than the others for some particular problems. We also discuss the effect of caching. A preliminary version of the paper appeared in the Proceedings of the Fifth International Symposium on Methodologies for Intelligent Systems held October 25–27, 1990 in Knoxville, Tennessee, USA.