Deciding Consistency of Databases Containing Defeasible and Strict
  Information
  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.
