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

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 in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11365/17186
 Attenzione

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