Non-Horn clause logic programming

摘要

There has been active work to extend the Prolog style Horn clause logic programming to non-Horn clauses. In this paper, we analyze and compare several such extensions using an analytical approach. All the extensions discussed behave exactly like Prolog when only Horn clauses are involved. The purpose is to understand the computational complexity of these inference systems when non-Horn clauses are present. The analyses do not necessarily prove that any one system is better than the others all the time. But they do suggest when one system may be better than the others for some particular kind of problems. They also help to discover some interesting properties of some extensions and suggest a possible syntactic transformation on problems to improve the performance of some extensions.