FDE, LP and are closely related to each other and admit of an intuitive informational interpretation. However, all these logics are co-NP complete, and so idealized models of how an agent can think. We address this issue by shifting to signed formulae, where the signs express imprecise values associated with two bipartitions of the corresponding set of standard values. We present proof systems whose operational rules are all linear and have only two structural branching rules that express a generalized Principle of Bivalence. Each of these systems leads to defining an infinite hierarchy of tractable approximations to the respective logic, in terms of the maximum number of allowed nested applications of the two branching rules. Further, each resulting hierarchy admits of an intuitive 5-valued non-deterministic semantics.
Tractable depth-bounded approximations to FDE and its satellites / M. D’Agostino, A. Solares-Rojas. - In: JOURNAL OF LOGIC AND COMPUTATION. - ISSN 0955-792X. - (2023), pp. 1-41. [Epub ahead of print] [10.1093/logcom/exad040]
Tractable depth-bounded approximations to FDE and its satellites
M. D’AgostinoPrimo
;A. Solares-Rojas
Secondo
2023
Abstract
FDE, LP and are closely related to each other and admit of an intuitive informational interpretation. However, all these logics are co-NP complete, and so idealized models of how an agent can think. We address this issue by shifting to signed formulae, where the signs express imprecise values associated with two bipartitions of the corresponding set of standard values. We present proof systems whose operational rules are all linear and have only two structural branching rules that express a generalized Principle of Bivalence. Each of these systems leads to defining an infinite hierarchy of tractable approximations to the respective logic, in terms of the maximum number of allowed nested applications of the two branching rules. Further, each resulting hierarchy admits of an intuitive 5-valued non-deterministic semantics.File | Dimensione | Formato | |
---|---|---|---|
exad040.pdf
accesso aperto
Descrizione: Journal Article
Tipologia:
Publisher's version/PDF
Dimensione
1.44 MB
Formato
Adobe PDF
|
1.44 MB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.