Computational complexity for bounded distributive lattices with negation

Annals of Pure and Applied Logic 172 (7):102962 (2021)
  Copy   BIBTEX

Abstract

We study the computational complexity of the universal and quasi-equational theories of classes of bounded distributive lattices with a negation operation, i.e., a unary operation satisfying a subset of the properties of the Boolean negation. The upper bounds are obtained through the use of partial algebras. The lower bounds are either inherited from the equational theory of bounded distributive lattices or obtained through a reduction of a global satisfiability problem for a suitable system of propositional modal logic.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,931

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Infinite substructure lattices of models of Peano Arithmetic.James H. Schmerl - 2010 - Journal of Symbolic Logic 75 (4):1366-1382.
Free modal lattices via Priestley duality.Claudia B. Wegener - 2002 - Studia Logica 70 (3):339 - 352.
Distributive Lattices with a Negation Operator.Sergio Arturo Celani - 1999 - Mathematical Logic Quarterly 45 (2):207-218.
Distributive lattices with an operator.Alejandro Petrovich - 1996 - Studia Logica 56 (1-2):205 - 224.
Decision problem for separated distributive lattices.Yuri Gurevich - 1983 - Journal of Symbolic Logic 48 (1):193-196.
On the representation of n4-lattices.Sergei P. Odintsov - 2004 - Studia Logica 76 (3):385 - 405.
Ockham Algebras with Additional Operators.Aldo Figallo, Paolo Landini & Alicia Zillani - 2004 - Logic Journal of the IGPL 12 (6):447-459.

Analytics

Added to PP
2021-03-02

Downloads
26 (#629,867)

6 months
9 (#356,042)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Complexity of the Universal Theory of Residuated Ordered Groupoids.Dmitry Shkatov & C. J. Van Alten - 2023 - Journal of Logic, Language and Information 32 (3):489-510.

Add more citations

References found in this work

Modal Logic.Patrick Blackburn, Maarten de Rijke & Yde Venema - 2001 - Studia Logica 76 (1):142-148.
Modal Logic.Yde Venema, Alexander Chagrov & Michael Zakharyaschev - 2000 - Philosophical Review 109 (2):286.
Semantic analysis of orthologic.R. I. Goldblatt - 1974 - Journal of Philosophical Logic 3 (1/2):19 - 35.
Star and perp: Two treatments of negation.J. Michael Dunn - 1993 - Philosophical Perspectives 7:331-357.
Algebraic Methods in Philosophical Logic.J. Michael Dunn & Gary M. Hardegree - 2003 - Bulletin of Symbolic Logic 9 (2):231-234.

View all 13 references / Add more references