Complexity of the universal theory of residuated ordered groupoids

Abstract

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 coNP-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 coNP-complete. We also prove the coNP-completeness of the universal theory of classes of residuated algebras, algebraic structures corresponding to Generalized Lambek Calculus.