{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T02:45:44Z","timestamp":1763433944764,"version":"3.45.0"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T00:00:00Z","timestamp":1750464000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T00:00:00Z","timestamp":1750464000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of the Witwatersrand"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Order"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    The equational theory of the class of lattices with a pair of unary residuated operations is shown to be decidable in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(n^5)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>n<\/mml:mi>\n                              <mml:mn>5<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    time. The same complexity holds in the bounded case. The equational theory of the class of lattices, as well as the class of bounded lattices, with a unary operator is shown to be decidable in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(n^3)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>n<\/mml:mi>\n                              <mml:mn>3<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    time. Explicit algorithms are given for deciding the above equational theories. These algorithms use a dynamic programming approach and are based on a sequent calculus that extends Whitman\u2019s sequent calculus for lattices.\n                  <\/jats:p>","DOI":"10.1007\/s11083-025-09701-4","type":"journal-article","created":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T00:41:42Z","timestamp":1750466502000},"page":"645-662","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial-time Equational Theory for Lattices with Unary Operators"],"prefix":"10.1007","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7865-4886","authenticated-orcid":false,"given":"C.J.","family":"Van Alten","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,6,21]]},"reference":[{"issue":"2","key":"9701_CR1","doi-asserted-by":"publisher","first-page":"103374","DOI":"10.1016\/j.apal.2023.103374","volume":"175","author":"N Bezhanishvili","year":"2024","unstructured":"Bezhanishvili, N., Dmitrieva, A., De Groot, J., Moraschini, T.: Positive modal logic beyond distributivity. Ann. Pure Appl. Logic 175(2), 103374 (2024)","journal-title":"Ann. Pure Appl. Logic"},{"key":"9701_CR2","unstructured":"Birkhoff, G.: Lattice Theory (2nd edition). American Mathematical Society Colloquium Publications, vol. 25 (1948)"},{"key":"9701_CR3","unstructured":"Blyth, T.S., Janowitz, M.F.: Residuation Theory. Pergamon Press (1972)"},{"issue":"3","key":"9701_CR4","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1093\/jigpal\/jzp094","volume":"19","author":"W Buszkowski","year":"2011","unstructured":"Buszkowski, W.: Interpolation and FEP for logics of residuated algebras. Log. J. IGPL 19(3), 437\u2013454 (2011)","journal-title":"Log. J. IGPL"},{"issue":"9","key":"9701_CR5","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1016\/j.apal.2019.04.003","volume":"170","author":"W Conradie","year":"2019","unstructured":"Conradie, W., Palmigiano, A.: Algorithmic correspondence and canonicity for non-distributive logics. Ann. Pure Appl. Logic 170(9), 923\u2013974 (2019)","journal-title":"Ann. Pure Appl. Logic"},{"key":"9701_CR6","doi-asserted-by":"crossref","unstructured":"Dunn J.M.: Partial gaggles applied to logics with restricted structural rules. In: Schroeder-Heister, P., Do\u0161en, K. (eds.) Substructural logics, Studies in Logic and Computation, vol.\u00a02, Clarendon Press,\u00a0pp. 72\u2013108 (1993)","DOI":"10.1093\/oso\/9780198537779.003.0004"},{"key":"9701_CR7","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/BF00340775","volume":"3","author":"R Freese","year":"1987","unstructured":"Freese, R.: Free lattice algorithms. Order 3, 331\u2013344 (1987)","journal-title":"Order"},{"issue":"1","key":"9701_CR8","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1006\/jabr.2000.8622","volume":"238","author":"M Gehrke","year":"2001","unstructured":"Gehrke, M., Harding, J.: Bounded lattice expansions. J. Algebra 238(1), 345\u2013371 (2001)","journal-title":"J. Algebra"},{"issue":"2","key":"9701_CR9","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1090\/S0002-9947-05-03816-X","volume":"358","author":"M Gehrke","year":"2006","unstructured":"Gehrke, M., Harding, J., Venema, Y.: MacNeille completions and canonical extensions. Trans. Am. Math. Soc. 358(2), 573\u2013590 (2006)","journal-title":"Trans. Am. Math. Soc."},{"issue":"1","key":"9701_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3632526","volume":"25","author":"G Greco","year":"2024","unstructured":"Greco, G., Jipsen, P., Liang, F., Palmigiano, A., Tzimoulis, A.: Algebraic Proof Theory for LE-logics. ACM Trans. Comput. Log. 25(1), 1\u201337 (2024)","journal-title":"ACM Trans. Comput. Log."},{"issue":"1","key":"9701_CR11","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1093\/logcom\/exy030","volume":"29","author":"C Hartonas","year":"2019","unstructured":"Hartonas, C.: Discrete duality for lattices with modal operators. J. Log. Comput. 29(1), 71\u201389 (2019)","journal-title":"J. Log. Comput."},{"issue":"1","key":"9701_CR12","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1137\/0216011","volume":"16","author":"HB Hunt III","year":"1987","unstructured":"Hunt, H.B., III., Rosenkrantz, D.J., Bloniarz, P.A.: On the computational complexity of algebra on lattices. SIAM J. Comput. 16(1), 129\u2013148 (1987)","journal-title":"SIAM J. Comput."},{"key":"9701_CR13","doi-asserted-by":"crossref","unstructured":"Jipsen, P., Tsinakis, C.: A survey of residuated lattices. In: Martinez, J. (ed.) Ordered Algebraic Structures. Kluwer Academic Publishers, pp. 226\u2013237 (2002)","DOI":"10.1007\/978-1-4757-3627-4_3"},{"issue":"3","key":"9701_CR14","doi-asserted-by":"publisher","first-page":"493","DOI":"10.2307\/1990305","volume":"55","author":"O Ore","year":"1944","unstructured":"Ore, O.: Galois connexions. Trans. Am. Math. Soc. 55(3), 493\u2013513 (1944)","journal-title":"Trans. Am. Math. Soc."},{"key":"9701_CR15","unstructured":"Or\u0142owska, E., Radzikowska, A.M., Rewitzky, I.: Dualities for Structures of Applied Logics. College Publications (2015)"},{"key":"9701_CR16","unstructured":"Or\u0142owska, E., Vakarelov, D.: Lattice-based modal algebras and modal logics. In: Logic, Methodology and Philosophy of Science. Proceedings of the 12th International Congress, pp. 147\u2013170 (2005)"},{"key":"9701_CR17","doi-asserted-by":"crossref","unstructured":"Spaan, E.: The complexity of propositional tense logics. In: de Rijke, M. (ed.) Diamonds and Defaults: Studies in Pure and Applied Intensional Logic. Kluwer Academic Publishers, pp. 287\u2013308 (1993)","DOI":"10.1007\/978-94-015-8242-1_10"},{"issue":"2","key":"9701_CR18","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s00012-007-2033-1","volume":"57","author":"M Theunissen","year":"2007","unstructured":"Theunissen, M., Venema, Y.: MacNeille completions of lattice expansions. Algebra Univers. 57(2), 143\u2013193 (2007)","journal-title":"Algebra Univers."},{"issue":"1","key":"9701_CR19","doi-asserted-by":"publisher","first-page":"325","DOI":"10.2307\/1969001","volume":"42","author":"PM Whitman","year":"1941","unstructured":"Whitman, P.M.: Free lattices. Ann. Math. 42(1), 325\u2013330 (1941)","journal-title":"Ann. Math."}],"container-title":["Order"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-025-09701-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11083-025-09701-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-025-09701-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T02:41:29Z","timestamp":1763433689000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11083-025-09701-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,21]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["9701"],"URL":"https:\/\/doi.org\/10.1007\/s11083-025-09701-4","relation":{},"ISSN":["0167-8094","1572-9273"],"issn-type":[{"type":"print","value":"0167-8094"},{"type":"electronic","value":"1572-9273"}],"subject":[],"published":{"date-parts":[[2025,6,21]]},"assertion":[{"value":"12 December 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 June 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics Approval and Consent to Participate"}},{"value":"I agree to the submission of the manuscript to the journal\n                      Order\n                      . If accepted for publication, I agree to publish the paper via the subscription publishing route and will therefore agree to the journal\u2019s licensing terms and Springer Nature\u2019s self-archiving policies.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for Publication"}}]}}