(joint work with C. J. Van Alten)

We consider the computational complexity of universal theories of residuated ordered groupoids, or rogs (algebraic models for Nonassociative Lambek Calculus) and residuated distributive lattice-ordered groupoids, or rdgs, (algebraic models for Full Distributive Nonassociative Lambek Calculus).  The universal theory or rogs is shown to be coNP-complete, and the universal theories of rdgs is shown to be EXPTIME-complete. Upper bounds are obtained using partial algebras. Lower bounds are obtained by reduction from a suitable propositional logic.