Consistency in Valuation-Based Systems
ORSA Journal on Computing · 1994 · Volume 6 · Issue 3
Abstract
This paper has three main results. First, we present a new computational technique for checking for inconsistencies in valuation-based systems. This technique is different from the implicit enumeration method of Davis-Putnam and its variants. Our technique uses the divide-and-conquer method of dynamic programming. The computational complexity of this technique depends on the sizes of the valuations and on the graphical structure of the valuation-based system. Second, if a valuation-based system is consistent, we describe a method for generating a model for the system, i.e., an assignment of values for each variable that is consistent with each valuation in the system. Third, if a valuation-based system is inconsistent, we describe a method for isolating a minimal inconsistent set of valuations. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Keywords
computers/computer science, artificial intelligence, information systems, expert systems, valuation-based systems, consistency in rule-based systems, satisfiability problem, propositional logic, theorem proving, knowledge representation
Enable JavaScript for citation tools and additional paper interactions.