The consequence relation in the logic of commutative GBL-algebras is PSPACE-complete

DOI10.1016/j.tcs.2008.10.024zbMath1159.03045MaRDI QIDQ1006641

Franco Montagna, Simone Bova

Publication date: 25 March 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.10.024

zbMATH Keywords

computational complexity; fuzzy logic; substructural logics; intuitionistic logic; residuated lattices; commutative GBL-algebras

Mathematics Subject Classification ID

03B52: Fuzzy logic; logic of vagueness

03D15: Complexity of computation (including implicit computational complexity)

03G25: Other algebras related to logic

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

06F05: Ordered semigroups and monoids

Related Items

Soft Constraints Processing over Divisible Residuated Lattices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity issues in Basic Logic
• On the structure of generalized BL-algebras
• Residuated lattices. An algebraic glimpse at substructural logics
• Embedding theorems for classes of GBL-algebras
• Retracted: Ordered groups with a modality
• The complexity of the word problem for abelian l-groups
• Satisfiability in many-valued sentential logic is NP-complete
• An algebraic approach to non-classical logics
• Intuitionistic propositional logic is polynomial-space complete
• Metamathematics of fuzzy logic
• Generalized MV-algebras
• On the structure of hoops
• The Blok-Ferreirim theorem for normal GBL-algebras and its application
• Algebraizable logics
• A theorem about infinite-valued sentential logic
• Complexity of t-tautologies