Deciding Consistency of Databases Containing Defeasible and Strict Information
Moises Goldszmidt, Judea Pearl
We propose a norm of consistency for a mixed set of defeasible and strict sentences, based on a probabilistic semantics. This norm establishes a clear distinction between knowledge bases depicting exceptions and those containing outright contradictions. We then define a notion of entailment based also on probabilistic considerations and provide a characterization of the relation between consistency and entailment. We derive necessary and sufficient conditions for consistency, and provide a simple decision procedure for testing consistency and deciding whether a sentence is entailed by a database. Finally, it is shown that if al1 sentences are Horn clauses, consistency and entailment can be tested in polynomial time.
PDF Link: /papers/89/p134-goldszmidt.pdf
AUTHOR = "Moises Goldszmidt
and Judea Pearl",
TITLE = "Deciding Consistency of Databases Containing Defeasible and Strict Information",
BOOKTITLE = "Proceedings of the Fifth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-89)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "1989",
PAGES = "134--141"