Propositional Defeasible Logic has Linear Complexity

Preprint

24 May 2004

preprint
Published by arXiv in arXiv

https://doi.org/10.48550/arXiv.cs/0405090

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

PROPOSITIONAL DEFEASIBLE
COMPLEXITY DEFEASIBLE
NONMONOTONIC LOGIC
LINEAR COMPLEXITY
DEFEASIBLE LOGIC
PRIORITY

All Related Versions

Version 1, 2004-05-24, ArXiv

This publication has 0 references indexed in Scilit: