Hostname: page-component-7c8c6479df-995ml Total loading time: 0 Render date: 2024-03-27T03:55:46.567Z Has data issue: false hasContentIssue false

Propositional defeasible logic has linear complexity

Published online by Cambridge University Press:  09 June 2004

MICHAEL J. MAHER
Affiliation:
Department of Mathematical and Computer Sciences, Loyola University Chicago, Chicago, IL, USA; (e-mail: mjm@cs.luc.edu) 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.

Type
Research Article
Copyright
© 2001 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)