Commutative, integral and bounded GBL-algebras form a subvariety of residuated lattices which provides the algebraic semantics of an interesting common fragment of intuitionistic logic and of several fuzzy logics. It is known that both the equational theory and the quasiequational theory of commutative GBL-algebras are decidable (in contrast to the noncommutative case), but their complexity has not been studied yet. In this paper, we prove that both theories are in PSPACE, and that the quasiequational theory is PSPACE-hard.
Bova, S., Montagna, F. (2009). The Consequence Relation in the Logic of Commutative GBL-Algebras is PSPACE-complete. THEORETICAL COMPUTER SCIENCE, 410, 1143-1158 [10.1016/j.tcs.2008.10.024].
The Consequence Relation in the Logic of Commutative GBL-Algebras is PSPACE-complete.
MONTAGNA, FRANCO
2009-01-01
Abstract
Commutative, integral and bounded GBL-algebras form a subvariety of residuated lattices which provides the algebraic semantics of an interesting common fragment of intuitionistic logic and of several fuzzy logics. It is known that both the equational theory and the quasiequational theory of commutative GBL-algebras are decidable (in contrast to the noncommutative case), but their complexity has not been studied yet. In this paper, we prove that both theories are in PSPACE, and that the quasiequational theory is PSPACE-hard.
| File | Dimensione | Formato | |
|---|---|---|---|
|
tcs-2009.pdf
non disponibili
Tipologia:
Post-print
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
977.89 kB
Formato
Adobe PDF
|
977.89 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/17186
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo