Propositional defeasible logic has linear complexity
Top Cited Papers
- 1 January 2001
- journal article
- research article
- Published by Cambridge University Press (CUP) in Theory and Practice of Logic Programming
- Vol. 1 (6) , 691-711
- https://doi.org/10.1017/s1471068401001168
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.Keywords
All Related Versions
This publication has 0 references indexed in Scilit: