Verification of non-monotonic knowledge bases

摘要

Non-monotonic Knowledge-Based Systems (KBSs) must undergo quality assurance procedures for the following two reasons: (i) belief revision (if such is provided) cannot always guarantee the structural correctness of the knowledge base, and in certain cases may introduce new semantic errors in the revised theory; (ii) non-monotonic theories may have multiple extensions, and some types of functional errors which do not violate structural properties of a given extension are hard to detect without testing the overall performance of the KBS. This paper presents an extension of the distributed verification method, which is meant to reveal structural and functional anomalies in non-monotonic KBSs. Two classes of anomalies are considered: (i) structural anomalies which manifest themselves within a given extension (such as logical inconsistencies, structural incompleteness, and intractabilities caused by circular rule chains), and (ii) functional anomalies related to the overall performance of the KBS (such as the existence of complementary rules and some types of rule subsumptions). The corresponding verification tests are presented and illustrated on an extended example.