Complexity of the Universal Theory of Residuated Ordered Groupoids

Journal of Logic, Language and Information 32 (3):489-510 (2023)
  Copy   BIBTEX

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 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}$$ -completeness of the universal theory of classes of residuated algebras, algebraic structures corresponding to Generalized Lambek Calculus.

Links

PhilArchive



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

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

Call for Papers.[author unknown] - 1999 - Journal of Logic, Language and Information 8 (3):399-400.
Instructions for Authors.[author unknown] - 2001 - Journal of Logic, Language and Information 10 (4):531-537.
Instructions for Authors.[author unknown] - 2004 - Journal of Logic, Language and Information 13 (1):111-116.
Instructions for Authors.[author unknown] - 2002 - Journal of Logic, Language and Information 11 (4):523-529.
Contents of Volume 8.[author unknown] - 1999 - Journal of Logic, Language and Information 8 (4):487-489.
Contents of Volume 10.[author unknown] - 2001 - Journal of Logic, Language and Information 10 (4):527-529.
Upcoming Themes.[author unknown] - 2004 - Journal of Logic, Language and Information 7 (1):115-115.
Contents of Volume 7.[author unknown] - 2004 - Journal of Logic, Language and Information 7 (4):509-511.
Contents of Volume 12.[author unknown] - 2003 - Journal of Logic, Language and Information 12 (4):533-535.
Note from the Editor.[author unknown] - 1999 - Journal of Logic, Language and Information 8 (2):3-3.
Instructions for Authors.[author unknown] - 2000 - Journal of Logic, Language and Information 9 (4):525-531.
Upcoming Themes.[author unknown] - 2004 - Journal of Logic, Language and Information 7 (3):393-393.
Contents of Volume 9.[author unknown] - 2004 - Journal of Logic, Language and Information 9 (4):521-523.
Call for Papers.[author unknown] - 1999 - Journal of Logic, Language and Information 8 (1):135-136.

Analytics

Added to PP
2023-01-14

Downloads
14 (#1,014,919)

6 months
8 (#411,508)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Model Theory.Michael Makkai, C. C. Chang & H. J. Keisler - 1991 - Journal of Symbolic Logic 56 (3):1096.
Consequence Relations and Admissible Rules.Rosalie Iemhoff - 2016 - Journal of Philosophical Logic 45 (3):327-348.
Stable canonical rules.Guram Bezhanishvili, Nick Bezhanishvili & Rosalie Iemhoff - 2016 - Journal of Symbolic Logic 81 (1):284-315.
Canonical Rules.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (4):1171 - 1205.

View all 16 references / Add more references