Computational complexity for bounded distributive lattices with negation

DOI10.1016/J.APAL.2021.102962MaRDI QIDQ2032990zbMATH OpenOpenAlexFDO

Authors Dmitry Shkatov, C. J. van Alten

Publication date 14 June 2021

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2021.102962

zbMATH Keywords

computational complexitydistributive lattice with negationpartial algebrauniversal theory

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Pseudocomplemented lattices (06D15) De Morgan algebras, ?ukasiewicz algebras (lattice-theoretic aspects) (06D30) Generalizations of Boolean algebras (06E75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• STACS 2004
• Partial algebras and complexity of satisfiability and universal theory for distributive lattices, Boolean algebras and Heyting algebras
• On the Computational Complexity of Algebra on Lattices
• Complexity of the universal theory of bounded residuated distributive lattice-ordered groupoids
• Complexity of the universal theory of modal algebras

Cites work

• Algebraic methods in philosophical logic
• Boolean Algebras with Operators
• Boolean Algebras with Operators. Part I
• Canonical rules
• Complexity of finite-variable fragments of propositional modal logics of symmetric frames
• Complexity of the universal theory of bounded residuated distributive lattice-ordered groupoids
• Complexity of the universal theory of modal algebras
• Consequence relations and admissible rules
• Distributive lattices with an additional unary operation
• Equational Classes of Distributive Pseudo-Complemented Lattices
• Generalized ortho negation
• scientific article; zbMATH DE number 4016857 (Why is no real title available?)
• scientific article; zbMATH DE number 1003731 (Why is no real title available?)
• scientific article; zbMATH DE number 549966 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1499085 (Why is no real title available?)
• scientific article; zbMATH DE number 1748069 (Why is no real title available?)
• scientific article; zbMATH DE number 3995647 (Why is no real title available?)
• Intuitionistic propositional logic is polynomial-space complete
• Lattices With Involution
• Mathematical Foundations of Computer Science 2003
• Modal logic
• Negation in the context of gaggle theory
• Negation in the light of modal logic
• On rules
• On the polynomial-space completeness of intuitionistic propositional logic
• Partial algebras and complexity of satisfiability and universal theory for distributive lattices, Boolean algebras and Heyting algebras
• Propositional dynamic logic of regular programs
• Semantic analysis of orthologic
• Stable canonical rules
• The Computational Complexity of Provability in Systems of Modal Propositional Logic

Cited in

(1)

• Complexity of the universal theory of residuated ordered groupoids

This page was built for publication: Computational complexity for bounded distributive lattices with negation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2032990)