On quasi-inconsistency and its complexity

摘要

We address the issue of analyzing potential inconsistencies in knowledge bases. This refers to knowledge bases that contain rules which will always be activated together, and the knowledge base will become inconsistent, should these rules be activated. We investigate this problem in the context of the industrial use-case of business rule management, where it is often required that sets of (only) rules are analyzed for potential inconsistencies, e.g., during business rule modelling. To this aim, we introduce the notion of quasi-inconsistency, which is a formalization of the above-mentioned problem of potential inconsistencies. We put a specific focus on the analysis of computational complexity of some involved problems and show that many of them are intractable.