Hostname: page-component-745bb68f8f-v2bm5 Total loading time: 0 Render date: 2025-02-11T17:45:39.310Z Has data issue: false hasContentIssue false
  • English
  • Français

Propositional defeasible logic has linear complexity

Published online by Cambridge University Press:  09 June 2004

MICHAEL J. MAHER
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
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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

defeasible reasoningnon-monotonic logiccomputational complexity
Type
Research Article
Information
Theory and Practice of Logic Programming , Volume 1 , Issue 6 , November 2001 , pp. 691 - 711
Copyright
© 2001 Cambridge University Press