{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,10,12]],"date-time":"2022-10-12T18:09:42Z","timestamp":1665598182468},"reference-count":5,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["DMS-0070723"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2008,6]]},"abstract":"We consider parallel algorithms working in sequential global time, for example, circuits or parallel random access machines (PRAMs). Parallel abstract state machines (parallel ASMs) are such parallel algorithms, and the parallel ASM thesis asserts that every parallel algorithm is behaviorally equivalent to a parallel ASM. In an earlier article, we axiomatized parallel algorithms, proved the ASM thesis, and proved that every parallel ASM satisfies the axioms. It turned out that we were too timid in formulating the axioms; they did not allow a parallel algorithm to create components on the fly. This restriction did not hinder us from proving that the usual parallel models, like circuits or PRAMs or even alternating Turing machines, satisfy the postulates. But it resulted in an error in our attempt to prove that parallel ASMs always satisfy the postulates. To correct the error, we liberalize our axioms and allow on-the-fly creation of new parallel components. We believe that the improved axioms accurately express what parallel algorithms ought to be. We prove the parallel thesis for the new, corrected notion of parallel algorithms, and we check that parallel ASMs satisfy the new axioms.<\/jats:p>","DOI":"10.1145\/1352582.1352587","type":"journal-article","created":{"date-parts":[[2008,6,10]],"date-time":"2008-06-10T13:30:05Z","timestamp":1213104605000},"page":"1-32","source":"Crossref","is-referenced-by-count":14,"title":["Abstract state machines capture parallel algorithms"],"prefix":"10.1145","volume":"9","author":[{"given":"Andreas","family":"Blass","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}]},{"given":"Yuri","family":"Gurevich","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/937555.937561"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1131313.1131320"},{"key":"e_1_2_1_3_1","volume-title":"I: Axiomatization, and II: Abstract state machines and the characterization theorem. Microsoft Research Tech. Rep. MSR-TR-2006-170 and MSR-TR-2006-171. Microsoft Research","author":"Blass A.","year":"2006"},{"key":"e_1_2_1_4_1","volume-title":"Oxford","author":"Gurevich Y."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/343369.343384"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1352582.1352587","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,20]],"date-time":"2021-02-20T03:39:22Z","timestamp":1613792362000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1352582.1352587"}},"subtitle":["Correction and extension"],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":5,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1145\/1352582.1352587"],"URL":"http:\/\/dx.doi.org\/10.1145\/1352582.1352587","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":["Computational Mathematics","Logic","General Computer Science","Theoretical Computer Science"],"published":{"date-parts":[[2008,6]]}}}