All promiment examples of first-order predicate fuzzy logics are undecidable. This leads to the problem of the arithmetical complexity of their sets of tautologies and satisfiable sentences. This article is a contribution to the general study of this problem. We propose the classes of first-order core and Delta-core fuzzy logics as a good framework to address these arithmetical complexity issues. We obtain general results providing lower bounds for the complexities associated with arbitrary semantics, and we compute upper bounds and exact positions in the arithmetical hierarchy for distinguished semantics: general semantics given by all chains, finite-chain semantics, standard semantics and rational semantics.

Noguera, C., Montagna, F. (2010). Arithmetical Complexity of First-Order Predicate Logics over Distinguished Semantics. JOURNAL OF LOGIC AND COMPUTATION, 20(2), 399-424 [10.1093/logcom/exp052].

Arithmetical Complexity of First-Order Predicate Logics over Distinguished Semantics

NOGUERA C;MONTAGNA, FRANCO
2010-01-01

Abstract

All promiment examples of first-order predicate fuzzy logics are undecidable. This leads to the problem of the arithmetical complexity of their sets of tautologies and satisfiable sentences. This article is a contribution to the general study of this problem. We propose the classes of first-order core and Delta-core fuzzy logics as a good framework to address these arithmetical complexity issues. We obtain general results providing lower bounds for the complexities associated with arbitrary semantics, and we compute upper bounds and exact positions in the arithmetical hierarchy for distinguished semantics: general semantics given by all chains, finite-chain semantics, standard semantics and rational semantics.
2010
Noguera, C., Montagna, F. (2010). Arithmetical Complexity of First-Order Predicate Logics over Distinguished Semantics. JOURNAL OF LOGIC AND COMPUTATION, 20(2), 399-424 [10.1093/logcom/exp052].
File in 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/11365/7138
 Attenzione

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