Propositional Defeasible Logic has Linear Complexity
  Defeasible logic is a rule-based nonmonotonic logic, with both strict and
defeasible rules, and a priority relation on rules. We show that inference in
the propositional form of the logic can be performed in linear time. This
contrasts markedly with most other propositional nonmonotonic logics, in which
inference is intractable.
