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/p87-goldszmidt.pdf
AUTHOR = "Moises Goldszmidt
and Judea Pearl",
TITLE = "Deciding Consistency of Databases Containing Defeasible and Strict Information",
BOOKTITLE = "Uncertainty in Artificial Intelligence 5 Annual Conference on Uncertainty in Artificial Intelligence (UAI-89)",
PUBLISHER = "Elsevier Science",
ADDRESS = "Amsterdam, NL",
YEAR = "1989",
PAGES = "87--97"