Multivalued logics have a long tradition in the philosophy and logic literature that originates from the work by Lukaszewicz in the 1920s. More recently, many Al researchers have been interested in this topic for both semantic and computational reasons. Multivalued logics have indeed been frequently used both for their semantic properties and as tools for designing tractable reasoning systems. We focus here on the computational aspects of multivalued logics. The main result of this paper is a detailed picture of the impact that the semantic definition, the syntactic form and the assumptions on the relative sizes of the inputs have on the complexity of entailment checking. In particular we show new polynomial cases and generalize polynomial cases already known in the literature for various popular multivalued logics. Such polynomial cases are obtained by means of two simple algorithms, sharing a common method.

On the complexity of entailment in propositional multivalued logics / Cadoli, Marco; Schaerf, Marco. - In: ANNALS OF MATHEMATICS AND OF ARTIFICIAL INTELLIGENCE. - ISSN 1012-2443. - 18:1(1996), pp. 29-50. [10.1007/bf02136173]

On the complexity of entailment in propositional multivalued logics

CADOLI, Marco;SCHAERF, Marco
1996

Abstract

Multivalued logics have a long tradition in the philosophy and logic literature that originates from the work by Lukaszewicz in the 1920s. More recently, many Al researchers have been interested in this topic for both semantic and computational reasons. Multivalued logics have indeed been frequently used both for their semantic properties and as tools for designing tractable reasoning systems. We focus here on the computational aspects of multivalued logics. The main result of this paper is a detailed picture of the impact that the semantic definition, the syntactic form and the assumptions on the relative sizes of the inputs have on the complexity of entailment checking. In particular we show new polynomial cases and generalize polynomial cases already known in the literature for various popular multivalued logics. Such polynomial cases are obtained by means of two simple algorithms, sharing a common method.
1996
01 Pubblicazione su rivista::01a Articolo in rivista
On the complexity of entailment in propositional multivalued logics / Cadoli, Marco; Schaerf, Marco. - In: ANNALS OF MATHEMATICS AND OF ARTIFICIAL INTELLIGENCE. - ISSN 1012-2443. - 18:1(1996), pp. 29-50. [10.1007/bf02136173]
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/245214
 Attenzione

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

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