Theory and Practice of Logic Programming



Propositional defeasible logic has linear complexity


MICHAEL J. MAHER a1a2
a1 Department of Mathematical and Computer Sciences, Loyola University Chicago, Chicago, IL, USA; (e-mail: mjm@cs.luc.edu)
a2 School of Computing & Information Technology, Griffith University

Abstract

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.


Key Words: defeasible reasoning; non-monotonic logic; computational complexity.