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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.