Renaming a Set of Non-Horn Clauses

摘要

Several extensions of the logic programming language Prolog to non-Horn clauses use case analysis to handle non-Horn clauses. In this paper, analytical and empirical evidences are presented to show that, by making a set of clauses less "non-Horn" using predicate renaming, the performance of these case-analysis based procedures can be improved significantly. In addition, the paper also investigated the problem of efficiently constructing a predicate renaming that reduces the degree of "non-Hornness" of a clause set maximally. It is shown that this problem of finding a predicate renaming to achieve minimal "non-Hornness" is NP-complete.