{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T20:07:38Z","timestamp":1762459658648,"version":"3.37.3"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319961415"},{"type":"electronic","value":"9783319961422"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-96142-2_23","type":"book-chapter","created":{"date-parts":[[2018,7,20]],"date-time":"2018-07-20T15:55:08Z","timestamp":1532102108000},"page":"372-391","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["On the Completeness of Verifying Message Passing Programs Under Bounded Asynchrony"],"prefix":"10.1007","author":[{"given":"Ahmed","family":"Bouajjani","sequence":"first","affiliation":[]},{"given":"Constantin","family":"Enea","sequence":"additional","affiliation":[]},{"given":"Kailiang","family":"Ji","sequence":"additional","affiliation":[]},{"given":"Shaz","family":"Qadeer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,7,18]]},"reference":[{"key":"23_CR1","doi-asserted-by":"publisher","unstructured":"Abdulla, P.A., Aronis, S., Jonsson, B., Sagonas, K.F.: Optimal dynamic partial order reduction. In: Jagannathan, S., Sewell, P. (eds.) The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2014, San Diego, CA, USA, 20-21 January 2014, pp. 373\u2013384. ACM (2014). \nhttps:\/\/doi.org\/10.1145\/2535838.2535845","DOI":"10.1145\/2535838.2535845"},{"issue":"2","key":"23_CR2","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1006\/inco.1996.0053","volume":"127","author":"PA Abdulla","year":"1996","unstructured":"Abdulla, P.A., Jonsson, B.: Verifying programs with unreliable channels. Inf. Comput. 127(2), 91\u2013101 (1996). \nhttps:\/\/doi.org\/10.1006\/inco.1996.0053","journal-title":"Inf. Comput."},{"key":"23_CR3","doi-asserted-by":"publisher","unstructured":"Bakst, A., von Gleissenthall, K., Kici, R.G., Jhala, R.: Verifying distributed programs via canonical sequentialization. PACMPL 1(OOPSLA), 110:1\u2013110:27 (2017). \nhttps:\/\/doi.org\/10.1145\/3133934","DOI":"10.1145\/3133934"},{"key":"23_CR4","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.tcs.2016.09.023","volume":"656","author":"S Basu","year":"2016","unstructured":"Basu, S., Bultan, T.: On deciding synchronizability for asynchronously communicating systems. Theor. Comput. Sci. 656, 60\u201375 (2016). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2016.09.023","journal-title":"Theor. Comput. Sci."},{"key":"23_CR5","unstructured":"Bouajjani, A., Derevenetc, E., Meyer, R.: Robustness against relaxed memory models. In: Hasselbring, W., Ehmke, N.C. (eds.) Software Engineering 2014, Kiel, Deutschland. LNI, vol. 227, pp. 85\u201386. GI (2014). \nhttp:\/\/eprints.uni-kiel.de\/23752\/"},{"key":"23_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/978-3-642-28756-5_31","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"A Bouajjani","year":"2012","unstructured":"Bouajjani, A., Emmi, M.: Bounded phase analysis of message-passing programs. In: Flanagan, C., K\u00f6nig, B. (eds.) TACAS 2012. LNCS, vol. 7214, pp. 451\u2013465. Springer, Heidelberg (2012). \nhttps:\/\/doi.org\/10.1007\/978-3-642-28756-5_31"},{"key":"23_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/978-3-662-54434-1_7","volume-title":"Programming Languages and Systems","author":"A Bouajjani","year":"2017","unstructured":"Bouajjani, A., Emmi, M., Enea, C., Ozkan, B.K., Tasiran, S.: Verifying robustness of event-driven asynchronous programs against concurrency. In: Yang, H. (ed.) ESOP 2017. LNCS, vol. 10201, pp. 170\u2013200. Springer, Heidelberg (2017). \nhttps:\/\/doi.org\/10.1007\/978-3-662-54434-1_7"},{"key":"23_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-642-23702-7_13","volume-title":"Static Analysis","author":"A Bouajjani","year":"2011","unstructured":"Bouajjani, A., Emmi, M., Parlato, G.: On sequentializing concurrent programs. In: Yahav, E. (ed.) SAS 2011. LNCS, vol. 6887, pp. 129\u2013145. Springer, Heidelberg (2011). \nhttps:\/\/doi.org\/10.1007\/978-3-642-23702-7_13"},{"key":"23_CR9","unstructured":"Bouajjani, A., Enea, C., Ji, K., Qadeer, S.: On the completeness of verifying message passing programs under bounded asynchrony. \narXiv:1804.06612\n\n [cs.PL]"},{"issue":"2","key":"23_CR10","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1145\/322374.322380","volume":"30","author":"D Brand","year":"1983","unstructured":"Brand, D., Zafiropulo, P.: On communicating finite-state machines. J. ACM 30(2), 323\u2013342 (1983). \nhttps:\/\/doi.org\/10.1145\/322374.322380","journal-title":"J. ACM"},{"issue":"2","key":"23_CR11","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.ic.2005.05.006","volume":"202","author":"G C\u00e9c\u00e9","year":"2005","unstructured":"C\u00e9c\u00e9, G., Finkel, A.: Verification of programs with half-duplex communication. Inf. Comput. 202(2), 166\u2013190 (2005). \nhttps:\/\/doi.org\/10.1016\/j.ic.2005.05.006","journal-title":"Inf. Comput."},{"key":"23_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-642-28869-2_10","volume-title":"Programming Languages and Systems","author":"P-M Deni\u00e9lou","year":"2012","unstructured":"Deni\u00e9lou, P.-M., Yoshida, N.: Multiparty session types meet communicating automata. In: Seidl, H. (ed.) ESOP 2012. LNCS, vol. 7211, pp. 194\u2013213. Springer, Heidelberg (2012). \nhttps:\/\/doi.org\/10.1007\/978-3-642-28869-2_10"},{"key":"23_CR13","doi-asserted-by":"publisher","unstructured":"Desai, A., Garg, P., Madhusudan, P.: Natural proofs for asynchronous programs using almost-synchronous reductions. In: Black, A.P., Millstein, T.D. (eds.) Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA 2014, part of SPLASH 2014, Portland, OR, USA, 20\u201324 October 2014, pp. 709\u2013725. ACM (2014). \nhttps:\/\/doi.org\/10.1145\/2660193.2660211","DOI":"10.1145\/2660193.2660211"},{"key":"23_CR14","doi-asserted-by":"publisher","unstructured":"Desai, A., Gupta, V., Jackson, E.K., Qadeer, S., Rajamani, S.K., Zufferey, D.: P: safe asynchronous event-driven programming. In: Boehm, H., Flanagan, C. (eds.) ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2013, Seattle, WA, USA, 16\u201319 June 2013, pp. 321\u2013332. ACM (2013). \nhttps:\/\/doi.org\/10.1145\/2462156.2462184","DOI":"10.1145\/2462156.2462184"},{"key":"23_CR15","doi-asserted-by":"publisher","unstructured":"Emmi, M., Qadeer, S., Rakamaric, Z.: Delay-bounded scheduling. In: Ball, T., Sagiv, M. (eds.) Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, Austin, TX, USA, 26\u201328 January 2011, pp. 411\u2013422. ACM (2011). \nhttps:\/\/doi.org\/10.1145\/1926385.1926432","DOI":"10.1145\/1926385.1926432"},{"key":"23_CR16","doi-asserted-by":"publisher","unstructured":"Flanagan, C., Godefroid, P.: Dynamic partial-order reduction for model checking software. In: Palsberg, J., Abadi, M. (eds.) Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2005, Long Beach, California, USA, 12\u201314 January 2005, pp. 110\u2013121. ACM (2005). \nhttps:\/\/doi.org\/10.1145\/1040305.1040315","DOI":"10.1145\/1040305.1040315"},{"issue":"1\u20133","key":"23_CR17","first-page":"147","volume":"80","author":"B Genest","year":"2007","unstructured":"Genest, B., Kuske, D., Muscholl, A.: On communicating automata with bounded channels. Fundam. Inform. 80(1\u20133), 147\u2013167 (2007). \nhttp:\/\/content.iospress.com\/articles\/fundamenta-informaticae\/fi80-1-3-09","journal-title":"Fundam. Inform."},{"key":"23_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70545-1","volume-title":"Computer Aided Verification","year":"2008","unstructured":"Gupta, A., Malik, S. (eds.): CAV 2008. LNCS, vol. 5123. Springer, Heidelberg (2008). \nhttps:\/\/doi.org\/10.1007\/978-3-540-70545-1"},{"key":"23_CR19","doi-asserted-by":"publisher","unstructured":"Heu\u00dfner, A., Leroux, J., Muscholl, A., Sutre, G.: Reachability analysis of communicating pushdown systems. Logical Methods Comput. Sci. 8(3) (2012). \nhttps:\/\/doi.org\/10.2168\/LMCS-8(3:23)2012","DOI":"10.2168\/LMCS-8(3:23)2012"},{"key":"23_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/BFb0053567","volume-title":"Programming Languages and Systems","author":"K Honda","year":"1998","unstructured":"Honda, K., Vasconcelos, V.T., Kubo, M.: Language primitives and type discipline for structured communication-based programming. In: Hankin, C. (ed.) ESOP 1998. LNCS, vol. 1381, pp. 122\u2013138. Springer, Heidelberg (1998). \nhttps:\/\/doi.org\/10.1007\/BFb0053567"},{"issue":"1","key":"23_CR21","doi-asserted-by":"publisher","first-page":"9:1","DOI":"10.1145\/2827695","volume":"63","author":"K Honda","year":"2016","unstructured":"Honda, K., Yoshida, N., Carbone, M.: Multiparty asynchronous session types. J. ACM 63(1), 9:1\u20139:67 (2016). \nhttps:\/\/doi.org\/10.1145\/2827695","journal-title":"J. ACM"},{"key":"23_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/978-3-642-16164-3_18","volume-title":"Model Checking Software","author":"N Kidd","year":"2010","unstructured":"Kidd, N., Jagannathan, S., Vitek, J.: One stack to run them all. In: van de Pol, J., Weber, M. (eds.) SPIN 2010. LNCS, vol. 6349, pp. 245\u2013261. Springer, Heidelberg (2010). \nhttps:\/\/doi.org\/10.1007\/978-3-642-16164-3_18"},{"key":"23_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-540-78800-3_21","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"S Torre La","year":"2008","unstructured":"La Torre, S., Madhusudan, P., Parlato, G.: Context-bounded analysis of concurrent queue systems. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 299\u2013314. Springer, Heidelberg (2008). \nhttps:\/\/doi.org\/10.1007\/978-3-540-78800-3_21"},{"key":"23_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/978-3-642-14295-6_54","volume-title":"Computer Aided Verification","author":"S La Torre","year":"2010","unstructured":"La Torre, S., Madhusudan, P., Parlato, G.: Model-checking parameterized concurrent programs using linear interfaces. In: Touili, T., Cook, B., Jackson, P. (eds.) CAV 2010. LNCS, vol. 6174, pp. 629\u2013644. Springer, Heidelberg (2010). \nhttps:\/\/doi.org\/10.1007\/978-3-642-14295-6_54"},{"key":"23_CR25","doi-asserted-by":"publisher","unstructured":"Lal, A., Reps, T.W.: Reducing concurrent analysis under a context bound to sequential analysis. In: Gupta and Malik [18], pp. 37\u201351. \nhttps:\/\/doi.org\/10.1007\/978-3-540-70545-1_7","DOI":"10.1007\/978-3-540-70545-1_7"},{"key":"23_CR26","doi-asserted-by":"publisher","unstructured":"Lange, J., Tuosto, E., Yoshida, N.: From communicating machines to graphical choreographies. In: Rajamani, S.K., Walker, D. (eds.) Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015, Mumbai, India, 15\u201317 January 2015, pp. 221\u2013232. ACM (2015). \nhttps:\/\/doi.org\/10.1145\/2676726.2676964","DOI":"10.1145\/2676726.2676964"},{"issue":"4","key":"23_CR27","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1145\/322154.322158","volume":"26","author":"CH Papadimitriou","year":"1979","unstructured":"Papadimitriou, C.H.: The serializability of concurrent database updates. J. ACM 26(4), 631\u2013653 (1979)","journal-title":"J. ACM"},{"key":"23_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-540-31980-1_7","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"S Qadeer","year":"2005","unstructured":"Qadeer, S., Rehof, J.: Context-bounded model checking of concurrent software. In: Halbwachs, N., Zuck, L.D. (eds.) TACAS 2005. LNCS, vol. 3440, pp. 93\u2013107. Springer, Heidelberg (2005). \nhttps:\/\/doi.org\/10.1007\/978-3-540-31980-1_7"},{"key":"23_CR29","doi-asserted-by":"publisher","unstructured":"Qadeer, S., Wu, D.: KISS: keep it simple and sequential. In: Pugh, W., Chambers, C. (eds.) Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation 2004, Washington, DC, USA, 9\u201311 June 2004, pp. 14\u201324. ACM (2004). \nhttps:\/\/doi.org\/10.1145\/996841.996845","DOI":"10.1145\/996841.996845"}],"container-title":["Lecture Notes in Computer Science","Computer Aided Verification"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-96142-2_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,7,20]],"date-time":"2018-07-20T16:05:01Z","timestamp":1532102701000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-96142-2_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319961415","9783319961422"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-96142-2_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}