Complexity  of the universal theory of residuated ordered groupoids

Simple item page
dc.article.end-page510
dc.article.start-page489
dc.contributor.authorShkatov, Dmitry
dc.contributor.authorVan Alten, C. J.
dc.date.accessioned2026-07-28T06:15:16Z
dc.date.issued2023-01
dc.description.abstractWe 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.
dc.description.submitterPM2026
dc.facultyFaculty of Science
dc.identifier0000-0002-0559-1503
dc.identifier0000-0002-7865-4886
dc.identifier.citationShkatov, D., Van Alten, C.J. Complexity of the Universal Theory of Residuated Ordered Groupoids. J of Log Lang and Inf 32, 489–510 (2023). https://doi.org/10.1007/s10849-022-09392-9
dc.identifier.issn0925-8531 (print)
dc.identifier.issn1572-9583 (online)
dc.identifier.other10.1007/s10849-022-09392-9
dc.identifier.urihttps://hdl.handle.net/10539/49658
dc.journal.titleJournal of Logic, Language and Information
dc.language.isoen
dc.publisherSpringer
dc.relation.ispartofseriesVol. 32
dc.rights© The Author(s), under exclusive licence to Springer Nature B.V. 2023
dc.schoolSchool of Computer Science and Applied Mathematics
dc.subjectResiduated ordered groupoid
dc.subjectUniversal theory
dc.subjectPartial algebra
dc.subjectResiduated algebra
dc.subject.primarysdgN/A
dc.titleComplexity  of the universal theory of residuated ordered groupoids
dc.typeArticle

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
Shkatov_Complexity_2023.pdf
Size:
417.45 KB
Format:
Adobe Portable Document Format
Description:
Main article
Download

License bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.43 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

School of Computer Science and Applied Mathematics (Journal Articles)