Efficient Propositional Constraint Propagation

Problem Solving

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 10

Problem Solving: Constraint Satisfaction

We present an efficient method for inferring facts from a propositional knowledge base, which is not required to be in conjunctive normal form. This logically-incomplete method, called propositional fact propagation, is more powerful and efficient than some forms of boolean constraint propagation. Hence, it can be used for tractable deductive reasoning in many AI applications, including various truth maintenance systems. We also use propositional fact propagation to define a weak logical entailment relation that is more powerful and efficient than some others presented in the literature. Among other applications, this new entailment relation can be used for efficiently answering queries posed to a knowledge base, and for modeling beliefs held by a resource-limited agent.