Modal nonmonotonic logics: Ranges, characterization, computation

V. Wiktor Marek, Grigori F. Schwarz, Miroslaw Truszczynski

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

Abstract

Many nonmonotonic formalisms, including default logic, logic programming with stable models, and autoepistemic logic, can be represented faithfully by means of modal nonmonotonic logics in the family proposed by McDermott and Doyle. In this paper properties of logics in this family are thoroughly investigated. We present several results on characterization of expansions. These results are applicable to a wide class of nonmonotonic modal logics. Using these characterization results, algorithms for computing expansions for finite theories are developed. Perhaps the most important finding of this paper is that the structure of the family of modal nonmonotonic logics is much simpler than that of the family of underlying modal (monotonic) logics. Namely, it is often the case that different monotonic modal logics collapse to the same nonmonotonic system. We exhibit four families of logics whose nonmonotonic variants coincide: 5-KD45, TW5-SW5, N-WK, and W5-D4W5. These nonmonotonic logics naturally represent logics related to commonsense reasoning and knowledge representation such as autoepistemic logic, reflexive autoepistemic logic, default logic, and truth maintenance with negation.

Original languageEnglish
Pages (from-to)963-990
Number of pages28
JournalJournal of the ACM (JACM)
Volume40
Issue number4
StatePublished - Sep 1993

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Modal nonmonotonic logics: Ranges, characterization, computation'. Together they form a unique fingerprint.

Cite this