Renaming a Set of Non-Horn Clauses  

作　　者：聂旭民 郭青 

机构地区：[1]DepartmentofComputerSciencs,WichitaStateUniversity,Wichits,Kansas67260,USA [2]DepartmentofComputerScience,StateUniversityofNewYorkatAlbanyAlbany,NewYork12222,USA

出　　处：《Journal of Computer Science & Technology》2000年第5期409-415,共7页计算机科学技术学报（英文版）

摘　　要：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.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.

关 键 词：logic for artificial intelligence (AI) automated theorem proving logic programming Horn and non-Horn sets predicate renaming NP-COMPLETENESS 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]