{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:38:14Z","timestamp":1753889894654,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T00:00:00Z","timestamp":1434672000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>An algorithm for unification modulo one-sided distributivity is an early\nresult by Tid\\'en and Arnborg. More recently this theory has been of interest\nin cryptographic protocol analysis due to the fact that many cryptographic\noperators satisfy this property. Unfortunately the algorithm presented in the\npaper, although correct, has recently been shown not to be polynomial time\nbounded as claimed. In addition, for some instances, there exist most general\nunifiers that are exponentially large with respect to the input size. In this\npaper we first present a new polynomial time algorithm that solves the decision\nproblem for a non-trivial subcase, based on a typed theory, of unification\nmodulo one-sided distributivity. Next we present a new polynomial algorithm\nthat solves the decision problem for unification modulo one-sided\ndistributivity. A construction, employing string compression, is used to\nachieve the polynomial bound. Lastly, we examine the one-sided distributivity\nproblem in the new asymmetric unification paradigm. We give the first\nasymmetric unification algorithm for one-sided distributivity.<\/jats:p>","DOI":"10.2168\/lmcs-11(2:11)2015","type":"journal-article","created":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T13:13:12Z","timestamp":1479733992000},"source":"Crossref","is-referenced-by-count":2,"title":["On Unification Modulo One-Sided Distributivity: Algorithms, Variants and Asymmetry"],"prefix":"10.46298","volume":"Volume 11, Issue 2","author":[{"given":"Andrew M","family":"Marshall","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Catherine","family":"Meadows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paliath","family":"Narendran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2015,6,19]]},"reference":[{"key":"1020:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1571\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1571\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:06:38Z","timestamp":1681243598000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1571"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,19]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-11(2:11)2015","relation":{"is-same-as":[{"id-type":"arxiv","id":"1503.06687","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1503.06687","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2015,6,19]]},"article-number":"1571"}}