Computational complexity for bounded distributive lattices with negation |
| |
Authors: | Dmitry Shkatov C.J. Van Alten |
| |
Affiliation: | School of Computer Science and Applied Mathematics, University of the Witwatersrand, Johannesburg, Private Bag 3, Wits 2050, South Africa |
| |
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. |
| |
Keywords: | Universal theory Computational complexity Distributive lattice with negation Partial algebra |
本文献已被 ScienceDirect 等数据库收录! |