{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:31:33Z","timestamp":1750307493672,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["DMS-0653696"],"award-info":[{"award-number":["DMS-0653696"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>We propose an extension of the behavioral theory of interactive sequential algorithms to deal with the following situation. A query is issued during a certain step, but the step ends before any reply is received. Later, a reply arrives, and later yet the algorithm makes use of this reply. By a persistent query, we mean a query for which a late reply might be used. Our proposal involves issuing, along with a persistent query, a location where a late reply is to be stored. After presenting our proposal in general terms, we discuss the modifications that it requires in the existing axiomatics of interactive sequential algorithms and in the existing syntax and semantics of abstract state machines. To make that discussion self-contained, we include a summary of this material before the modifications. Fortunately, only rather minor modifications are needed.<\/jats:p>","DOI":"10.1145\/1877714.1877722","type":"journal-article","created":{"date-parts":[[2011,1,25]],"date-time":"2011-01-25T19:12:52Z","timestamp":1295982772000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Persistent queries in the behavioral theory of algorithms"],"prefix":"10.1145","volume":"12","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","published-online":{"date-parts":[[2011,1,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/800228.806932"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2005.03.003"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/937555.937561"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1352582.1352587"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1131313.1131320"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1243996.1243999"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1131313.1131320"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1243996.1243998"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2005.09.017"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Boker U.\n     and \n      Dershowitz N\n  . \n  2008\n  . The Church-Turing thesis over arbitrary domains. In Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday A. Avron N. Dershowitz and A. Rabinovich Eds. Springer-Verlag Lecture Notes in Computer Science vol. \n  4800 199--229.   Boker U. and Dershowitz N. 2008. The Church-Turing thesis over arbitrary domains. In Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday A. Avron N. Dershowitz and A. Rabinovich Eds. Springer-Verlag Lecture Notes in Computer Science vol. 4800 199--229.","DOI":"10.1007\/978-3-540-78127-1_12"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133373.1133410"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1231081370"},{"key":"e_1_2_1_13_1","unstructured":"EasyChair. 2009. http:\/\/easychair.org\/.  EasyChair. 2009. http:\/\/easychair.org\/."},{"key":"e_1_2_1_14_1","unstructured":"Friedman D. and Wise D. 1976. CONS should not evaluate its arguments. In Automata Languages and Programming S. Michaelson and R. Milner Eds. Edinburgh University Press 257--284.  Friedman D. and Wise D. 1976. CONS should not evaluate its arguments. In Automata Languages and Programming S. Michaelson and R. Milner Eds. Edinburgh University Press 257--284."},{"key":"e_1_2_1_15_1","first-page":"46","article-title":"A semantic characterization of unbounded-nondeterministic ASMs. In Rigorous Methods for Software Construction and Analysis: Essays Dedicated to Egon B\u00f6rger on the Occasion of His 60th Birthday","volume":"4624","author":"Glausch A.","year":"2008","journal-title":"Lecture Notes in Computer Science"},{"volume":"5115","volume-title":"Proceedings of the Dagstuhl Seminar on Rigorous Methods in Software Construction and Analysis. Lecture Notes in Computer Science","author":"Glausch A.","key":"e_1_2_1_16_1"},{"volume-title":"Evolving algebras: Lipari guide","author":"Gurevich Y.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/343369.343384"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Gurevich Y.\n     and \n      Huggins J\n  . \n  1996\n  . The railroad crossing problem: an experiment with instantaneous actions and immediate reactions. In Computer Science Logic Selected Papers from CSL'95 H. Kleine-B\u00fcning Ed\n  . Lecture Notes in Computer Science vol. \n  1092 266--290.   Gurevich Y. and Huggins J. 1996. The railroad crossing problem: an experiment with instantaneous actions and immediate reactions. In Computer Science Logic Selected Papers from CSL'95 H. Kleine-B\u00fcning Ed. Lecture Notes in Computer Science vol. 1092 266--290.","DOI":"10.1007\/3-540-61377-3_43"},{"key":"e_1_2_1_20_1","unstructured":"Gurevich Y. and Yavorskaya T. 2006. On bounded exploration and bounded nondeterminism. Microsoft Research Tech. rep. MSR-TR-2006-07.  Gurevich Y. and Yavorskaya T. 2006. On bounded exploration and bounded nondeterminism. Microsoft Research Tech. rep. MSR-TR-2006-07."},{"key":"e_1_2_1_21_1","unstructured":"Millar J. 2006. Finite work. Microsoft Research Tech rep. MSR-TR-2006-06.  Millar J. 2006. Finite work. Microsoft Research Tech rep. MSR-TR-2006-06."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.08.041"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Rosenzweig D. Runje D. and \n      Slani N\n  . \n  2003\n  . Privacy abstract encryption and protocols: an ASM model\u2014Part I. In Proceedings of Abstract State Machines\u2014Advances in Theory and Applications: 10th International Workshop. E. B\u00f6rger A. Gargantini and E. Riccobene Eds\n  . Lecture Notes in Computer Science vol. \n  2589 372--390.   Rosenzweig D. Runje D. and Slani N. 2003. Privacy abstract encryption and protocols: an ASM model\u2014Part I. In Proceedings of Abstract State Machines\u2014Advances in Theory and Applications: 10th International Workshop. E. B\u00f6rger A. Gargantini and E. Riccobene Eds. Lecture Notes in Computer Science vol. 2589 372--390.","DOI":"10.1007\/3-540-36498-6_22"},{"key":"e_1_2_1_24_1","unstructured":"Rosenzweig D. and Runje D. 2005. Some things algorithms cannot do. Microsoft Research Tech. rep. MSR-TR-2005052.  Rosenzweig D. and Runje D. 2005. Some things algorithms cannot do. Microsoft Research Tech. rep. MSR-TR-2005052."},{"key":"e_1_2_1_25_1","unstructured":"Wikipedia 2008. Futures and promises.  Wikipedia 2008. Futures and promises."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1877714.1877722","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1877714.1877722","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:17:37Z","timestamp":1750249057000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1877714.1877722"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1145\/1877714.1877722"],"URL":"https:\/\/doi.org\/10.1145\/1877714.1877722","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2011,1]]},"assertion":[{"value":"2008-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-01-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}