Switch to: References

Add citations

You must login to add citations.
  1. Computational complexity for bounded distributive lattices with negation.Dmitry Shkatov & C. J. Van Alten - 2021 - Annals of Pure and Applied Logic 172 (7):102962.
    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.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • 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.
    We study the computational complexity of the universal theory of residuated ordered groupoids, which are algebraic structures corresponding to Nonassociative Lambek Calculus. We prove that the universal theory is co $$\textsf {NP}$$ -complete which, as we observe, is the lowest possible complexity for a universal theory of a non-trivial class of structures. The universal theories of the classes of unital and integral residuated ordered groupoids are also shown to be co $$\textsf {NP}$$ -complete. We also prove the co $$\textsf {NP}$$ (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
    		•