Default logic is one of the most widely used formalisms to formalize commonsense reasoning. In this paper we analyze the complexity of deciding whether a propositional interpretation is a model of a default theory for some of the variants of default logic presented in the literature. We prove that all the analyzed variants have the same complexity and that this problem is in general Sigma(2)(p) complete, while it is coNP complete under some restrictions on the form of the defaults.

The complexity of model checking for propositional default logics / Liberatore, Paolo; Schaerf, Marco. - (1998), pp. 18-22. (Intervento presentato al convegno 13TH European Conference on Artificial Intelligence (ECAI 98) tenutosi a BRIGHTON, ENGLAND nel AUG 23-28, 1998).

The complexity of model checking for propositional default logics

LIBERATORE, Paolo;SCHAERF, Marco
1998

Abstract

Default logic is one of the most widely used formalisms to formalize commonsense reasoning. In this paper we analyze the complexity of deciding whether a propositional interpretation is a model of a default theory for some of the variants of default logic presented in the literature. We prove that all the analyzed variants have the same complexity and that this problem is in general Sigma(2)(p) complete, while it is coNP complete under some restrictions on the form of the defaults.
1998
9780471984313
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/243792
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 6
social impact