{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T17:42:53Z","timestamp":1648921373055},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1997,3]]},"abstract":"<jats:p> Two operations commute if they generate the same result regardless of the order in which they execute. Commutativity is an important property \u2014 commuting operations enable significant optimizations in the fields of parallel computing, optimizing compilers, parallelizing compilers and database concurrency control. Algorithms that statically decide if operations commute can be an important component of systems in these fields because they enable the automatic application of these optimizations. In this paper we define the commutativity decision problem and establish its complexity for a variety of basic instructions and control constructs. Although deciding commutativity is, in general, undecidable or computationally intractable, we believe that efficient algorithms exist that can solve many of the cases that arise in practice. <\/jats:p>","DOI":"10.1142\/s0129054197000069","type":"journal-article","created":{"date-parts":[[2003,10,15]],"date-time":"2003-10-15T20:35:19Z","timestamp":1066250119000},"page":"81-94","source":"Crossref","is-referenced-by-count":1,"title":["On the Complexity of Commutativity Analysis"],"prefix":"10.1142","volume":"08","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[{"name":"University of California, Santa Barbara, California 93106-5110, U.S.A"}]},{"given":"Pedro C.","family":"Diniz","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, California 93106-5110, U.S.A"}]},{"given":"Martin C.","family":"Rinard","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, California 93106-5110, U.S.A"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054197000069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:45:50Z","timestamp":1565124350000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054197000069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":0,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1997,3]]}},"alternative-id":["10.1142\/S0129054197000069"],"URL":"https:\/\/doi.org\/10.1142\/s0129054197000069","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,3]]}}}