{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T13:02:11Z","timestamp":1726232531555},"publisher-location":"Cham","reference-count":20,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031452857"},{"type":"electronic","value":"9783031452864"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-45286-4_3","type":"book-chapter","created":{"date-parts":[[2023,10,4]],"date-time":"2023-10-04T09:02:28Z","timestamp":1696410148000},"page":"28-41","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Weakly Synchronous Systems with\u00a0Three Machines Are Turing Powerful"],"prefix":"10.1007","author":[{"ORCID":"http:\/\/orcid.org\/0000-0003-1563-6581","authenticated-orcid":false,"given":"Cinzia","family":"Di Giusto","sequence":"first","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-6578-6804","authenticated-orcid":false,"given":"Davide","family":"Ferre\u2019","sequence":"additional","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0001-8505-585X","authenticated-orcid":false,"given":"Etienne","family":"Lozes","sequence":"additional","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0003-4500-5078","authenticated-orcid":false,"given":"Nicolas","family":"Nisse","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,5]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","unstructured":"Akroun, L., Sala\u00fcn, G.: Automated verification of automata communicating via FIFO and bag buffers. Formal Methods Syst. Des. 52(3), 260\u2013276 (2018). https:\/\/doi.org\/10.1007\/s10703-017-0285-8","DOI":"10.1007\/s10703-017-0285-8"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Basu, S., Bultan, T.: Choreography conformance via synchronizability. In: Srinivasan, S., Ramamritham, K., Kumar, A., Ravindra, M.P., Bertino, E., Kumar, R. (eds.) Proceedings of the 20th International Conference on World Wide Web, WWW 2011, Hyderabad, India, March 28\u2013April 1, 2011, pp. 795\u2013804. ACM (2011)","DOI":"10.1145\/1963405.1963516"},{"key":"3_CR3","doi-asserted-by":"publisher","unstructured":"Basu, S., Bultan, T.: On deciding synchronizability for asynchronously communicating systems. Theor. Comput. Sci. 656, 60\u201375 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2016.09.023","DOI":"10.1016\/j.tcs.2016.09.023"},{"key":"3_CR4","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1\u20132), 1\u201345 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(97)00228-4","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"3_CR5","doi-asserted-by":"publisher","unstructured":"Bollig, B., Di Giusto, C., Finkel, A., Laversa, L., Lozes, \u00c9., Suresh, A.: A unifying framework for deciding synchronizability. In: Haddad, S., Varacca, D. (eds.) 32nd International Conference on Concurrency Theory, CONCUR 2021, August 24\u201327, 2021. LIPIcs, vol. 203, pp. 14:1\u201314:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Virtual Conference (2021). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2021.14","DOI":"10.4230\/LIPIcs.CONCUR.2021.14"},{"key":"3_CR6","unstructured":"Bollig, B., Di Giusto, C., Finkel, A., Laversa, L., Lozes, \u00c9., Suresh, A.: A unifying framework for deciding synchronizability (extended version). Technical report (2021). https:\/\/hal.archives-ouvertes.fr\/hal-03278370\/document"},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/978-3-319-96142-2_23","volume-title":"Computer Aided Verification","author":"A Bouajjani","year":"2018","unstructured":"Bouajjani, A., Enea, C., Ji, K., Qadeer, S.: On the completeness of verifying message passing programs under bounded asynchrony. In: Chockler, H., Weissenbacher, G. (eds.) CAV 2018. LNCS, vol. 10982, pp. 372\u2013391. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96142-2_23"},{"key":"3_CR8","doi-asserted-by":"publisher","unstructured":"Brand, D., Zafiropulo, P.: On communicating finite-state machines. J. ACM 30(2), 323\u2013342 (1983). https:\/\/doi.org\/10.1145\/322374.322380","DOI":"10.1145\/322374.322380"},{"key":"3_CR9","doi-asserted-by":"publisher","unstructured":"Charron-Bost, B., Mattern, F., Tel, G.: Synchronous, asynchronous, and causally ordered communication. Distributed Comput. 9(4), 173\u2013191 (1996). https:\/\/doi.org\/10.1007\/s004460050018","DOI":"10.1007\/s004460050018"},{"key":"3_CR10","doi-asserted-by":"publisher","unstructured":"Di Giusto, C., Ferr\u00e9, D., Laversa, L., Lozes, \u00c9.: A partial order view of message-passing communication models. Proc. ACM Program. Lang. 7(POPL), 1601\u20131627 (2023). https:\/\/doi.org\/10.1145\/3571248","DOI":"10.1145\/3571248"},{"key":"3_CR11","unstructured":"Di\u00a0Giusto, C., Ferr\u00e9, D., Lozes, E., Nisse, N.: Weakly synchronous systems with three machines are Turing powerful. Technical report, Universit\u00e9 C\u00f4te d\u2019Azur, CNRS, I3S, France; Universit\u00e9 C\u00f4te d\u2019Azur, Inria, CNRS, I3S, France (2023). https:\/\/hal.science\/hal-04182953"},{"key":"3_CR12","unstructured":"Finkel, A., Lozes, \u00c9.: Synchronizability of communicating finite state machines is not decidable. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10\u201314, 2017, Warsaw, Poland. LIPIcs, vol. 80, pp. 122:1\u2013122:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"key":"3_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/978-3-540-85238-4_26","volume-title":"Mathematical Foundations of Computer Science 2008","author":"A Finkel","year":"2008","unstructured":"Finkel, A., Sangnier, A.: Reversal-bounded counter machines revisited. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 323\u2013334. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-85238-4_26"},{"key":"3_CR14","unstructured":"Genest, B., Kuske, D., Muscholl, A.: On communicating automata with bounded channels. Fundam. Informaticae 80(1-3), 147\u2013167 (2007). http:\/\/content.iospress.com\/articles\/fundamenta-informaticae\/fi80-1-3-09"},{"key":"3_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-642-12032-9_19","volume-title":"Foundations of Software Science and Computational Structures","author":"A Heu\u00dfner","year":"2010","unstructured":"Heu\u00dfner, A., Leroux, J., Muscholl, A., Sutre, G.: Reachability analysis of communicating pushdown systems. In: Ong, L. (ed.) FoSSaCS 2010. LNCS, vol. 6014, pp. 267\u2013281. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-12032-9_19"},{"issue":"1","key":"3_CR16","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/322047.322058","volume":"25","author":"OH Ibarra","year":"1978","unstructured":"Ibarra, O.H.: Reversal-bounded multicounter machines and their decision problems. J. ACM (JACM) 25(1), 116\u2013133 (1978)","journal-title":"J. ACM (JACM)"},{"key":"3_CR17","unstructured":"ITU-T: Recommendation ITU-T Z.120: Message sequence chart (MSC). Technical report, International Telecommunication Union, Geneva (2011)"},{"key":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/3-540-45931-6_21","volume-title":"Foundations of Software Science and Computation Structures","author":"M Lohrey","year":"2002","unstructured":"Lohrey, M., Muscholl, A.: Bounded MSC communication. In: Nielsen, M., Engberg, U. (eds.) FoSSaCS 2002. LNCS, vol. 2303, pp. 295\u2013309. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45931-6_21"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Mayr, E.W.: An algorithm for the general petri net reachability problem. In: Symposium on the Theory of Computing (1981)","DOI":"10.1145\/800076.802477"},{"key":"3_CR20","doi-asserted-by":"publisher","unstructured":"Torre, S.L., Madhusudan, P., Parlato, G.: Context-bounded analysis of concurrent queue systems. In: Tools and Algorithms for the Construction and Analysis of Systems, 14th International Conference, TACAS 2008, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2008, Budapest, Hungary, March 29\u2013April 6, 2008. Proceedings, pp. 299\u2013314 (2008). https:\/\/doi.org\/10.1007\/978-3-540-78800-3_21","DOI":"10.1007\/978-3-540-78800-3_21"}],"container-title":["Lecture Notes in Computer Science","Reachability Problems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-45286-4_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,4]],"date-time":"2023-10-04T12:03:12Z","timestamp":1696420992000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-45286-4_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031452857","9783031452864"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-45286-4_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"5 October 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Reachability Problems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Nice","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 October 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 October 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"rp2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.lix.polytechnique.fr\/Labo\/Olivier.Bournez\/RP2023\/i.php?n=Main.Home","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Open","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair.org","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"19","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"13","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"68% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}