{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T06:46:31Z","timestamp":1743144391817,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031308284"},{"type":"electronic","value":"9783031308291"}],"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:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,21]],"date-time":"2023-04-21T00:00:00Z","timestamp":1682035200000},"content-version":"vor","delay-in-days":110,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the open map approach to bisimilarity, the paths and their runs in a given state-based system are the first-class citizens, and bisimilarity becomes a derived notion. While open maps were successfully used to model bisimilarity in non-deterministic systems, the approach fails to describe quantitative system equivalences such as probabilistic bisimilarity. In the present work, we see that this is indeed impossible and we thus generalize the notion of open maps to also accommodate weighted and probabilistic bisimilarity. Also, extending the notions of strong path and path bisimulations into this new framework, we show that branching bisimilarity can be captured by this extended theory and that it can be viewed as the history preserving restriction of weak bisimilarity.<\/jats:p>","DOI":"10.1007\/978-3-031-30829-1_15","type":"book-chapter","created":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T19:56:19Z","timestamp":1682020579000},"page":"308-327","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Weighted and Branching Bisimilarities from Generalized Open Maps"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2640-3065","authenticated-orcid":false,"given":"J\u00e9r\u00e9my","family":"Dubut","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8993-6486","authenticated-orcid":false,"given":"Thorsten","family":"Wi\u00dfmann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,21]]},"reference":[{"key":"15_CR1","doi-asserted-by":"publisher","unstructured":"Beohar, H., Cuijpers, P.J.L.: Open Maps in Concrete Categories and Branching Bisimulation for Prefix Orders. Electronic Notes in Theoretical Computer Science 319, 51\u201366 (2015). https:\/\/doi.org\/10.1016\/j.entcs.2015.12.005","DOI":"10.1016\/j.entcs.2015.12.005"},{"key":"15_CR2","doi-asserted-by":"publisher","unstructured":"Beohar, H., K\u00fcpper, S.: Bisimulation Maps in Presheaf Categories. Electronic Notes in Theoretical Computer Science 347, 5\u201324 (2019). https:\/\/doi.org\/10.1016\/j.entcs.2019.09.002","DOI":"10.1016\/j.entcs.2019.09.002"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Cheng, A., Nielsen, M.: Open Maps (at) Work. B R I C S Report Series (RS-95-23) (1995)","DOI":"10.7146\/brics.v2i23.19925"},{"key":"15_CR4","doi-asserted-by":"publisher","unstructured":"Danos, V., Desharnais, J., Laviolette, F., Panangaden, P.: Bisimulation and cocongruence for probabilistic systems. Information and Computation 204(4), 503\u2013523 (2006). https:\/\/doi.org\/10.1016\/j.ic.2005.02.004","DOI":"10.1016\/j.ic.2005.02.004"},{"key":"15_CR5","doi-asserted-by":"publisher","unstructured":"Desharnais, J., Edalat, A., Panangaden, P.: Bisimulation for Labelled Markov Processes. Information and Computation 179(2), 163\u2013193 (2003). https:\/\/doi.org\/10.1006\/inco.2001.2962","DOI":"10.1006\/inco.2001.2962"},{"key":"15_CR6","doi-asserted-by":"publisher","unstructured":"Dubut, J., Goubault, E., Goubault-Larrecq, J.: Bisimulations and unfolding in P-accessible categorical models. In: Desharnais, J., Jagadeesan, R. (eds.) 27th International Conference on Concurrency Theory, CONCUR 2016. LIPIcs, vol.\u00a059, pp. 25:1\u201325:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2016.25","DOI":"10.4230\/LIPIcs.CONCUR.2016.25"},{"key":"15_CR7","unstructured":"Dubut, J., Hasuo, I., Katsumata, S., Sprunger, D.: Quantitative bisimulations using coreflections and open morphisms (2018), arXiv:1809.09278"},{"key":"15_CR8","doi-asserted-by":"publisher","unstructured":"Fahrenberg, U., Legay, A.: History-Preserving Bisimilarity for Higher-Dimensional Automata via Open Maps. Electronic Notes in Theoretical Computer Science 298, 165\u2013178 (2013). https:\/\/doi.org\/10.1016\/j.entcs.2013.09.012","DOI":"10.1016\/j.entcs.2013.09.012"},{"key":"15_CR9","doi-asserted-by":"publisher","unstructured":"Fiore, M., Cattani, G.L., Winskel, G.: Weak bisimulation and open maps. In: Proceedings. 14th Symposium on Logic in Computer Science. pp. 67\u201376 (1999). https:\/\/doi.org\/10.1109\/LICS.1999.782590","DOI":"10.1109\/LICS.1999.782590"},{"key":"15_CR10","unstructured":"Freyd, P., Scedrov, A.: Categories, Allegories, Mathematical Library, vol.\u00a039. North-Holland (1990)"},{"key":"15_CR11","doi-asserted-by":"publisher","unstructured":"Hughes, J., Jacobs, B.: Simulations in coalgebra. Theor. Comput. Sci. 327(1-2), 71\u2013108 (2004). https:\/\/doi.org\/10.1016\/j.tcs.2004.07.022","DOI":"10.1016\/j.tcs.2004.07.022"},{"key":"15_CR12","doi-asserted-by":"publisher","unstructured":"Hune, T., Nielsen, M.: Timed bisimulations and open maps. In: Brim, L., Gruska, J., Zlatu\u0161ka, J. (eds) Mathematical Foundations of Computer Science 1998. MFCS 1998. Lecture Notes in Computer Science, vol.\u00a01450. Springer, Berlin, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0055787","DOI":"10.1007\/BFb0055787"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Jacobs, B.: Introduction to Coalgebra: Towards Mathematics of States and Observation, Cambridge Tracts in Theoretical Computer Science, vol.\u00a059. Cambridge University Press (2016)","DOI":"10.1017\/CBO9781316823187"},{"key":"15_CR14","doi-asserted-by":"publisher","unstructured":"Johnstone, P., Power, J., Tsujishita, T., Watanabe, H., Worrell, J.: On the structure of categories of coalgebras. Theoretical Computer Science 260, 87\u2013117 (2001). https:\/\/doi.org\/10.1016\/S0304-3975(00)00124-9","DOI":"10.1016\/S0304-3975(00)00124-9"},{"key":"15_CR15","doi-asserted-by":"publisher","unstructured":"Joyal, A., Moerdijk, I.: A completeness theorem for open maps. Annals of Pure and Applied Logic 70, 51\u201386 (1994). https:\/\/doi.org\/10.1016\/0168-0072(94)90069-8","DOI":"10.1016\/0168-0072(94)90069-8"},{"key":"15_CR16","doi-asserted-by":"publisher","unstructured":"Joyal, A., Nielsen, M., Winskel, G.: Bisimulation from Open Maps. Information and Computation 127, 164\u2013185 (1996). https:\/\/doi.org\/10.1006\/inco.1996.0057","DOI":"10.1006\/inco.1996.0057"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Klin, B.: Semantics and Algebraic Specification, Lecture Notes in Computer Science, vol.\u00a05700, chap. Structural Operational Semantics for Weighted Transition Systems, pp. 121\u2013139. Springer, Berlin, Heidelberg (2009)","DOI":"10.1007\/978-3-642-04164-8_7"},{"key":"15_CR18","doi-asserted-by":"publisher","unstructured":"Larsen, K.G., Skou, A.: Bisimulations through Probabilistic Testing. Information and Computation 94, 1\u201328 (1991). https:\/\/doi.org\/10.1016\/0890-5401(91)90030-6","DOI":"10.1016\/0890-5401(91)90030-6"},{"key":"15_CR19","doi-asserted-by":"publisher","unstructured":"Lasota, S.: Coalgebra morphisms subsume open maps. Theoretical Computer Science 280(1), 123 \u2013 135 (2002). https:\/\/doi.org\/10.1016\/S0304-3975(01)00023-8","DOI":"10.1016\/S0304-3975(01)00023-8"},{"key":"15_CR20","doi-asserted-by":"publisher","unstructured":"Park, D.: Concurrency and automata on infinite sequences. In: Proceedings of the 5th GI-Conference on Theoretical Computer Science. Lecture Notes in Computer Science, vol.\u00a0104, pp. 167\u2013183. Springer (1981). https:\/\/doi.org\/10.1007\/BFb0017309","DOI":"10.1007\/BFb0017309"},{"key":"15_CR21","doi-asserted-by":"publisher","unstructured":"Pratt, V.: Higher dimensional automata revisited. Mathenatical Structures in Computer Science 10(4), 525\u2013548 (2000). https:\/\/doi.org\/10.1017\/S0960129500003169","DOI":"10.1017\/S0960129500003169"},{"key":"15_CR22","doi-asserted-by":"publisher","unstructured":"Rutten, J.: Universal coalgebra: a theory of systems. Theoretical Computer Science 249(1), 3 \u2013 80 (2000). https:\/\/doi.org\/10.1016\/S0304-3975(00)00056-6","DOI":"10.1016\/S0304-3975(00)00056-6"},{"key":"15_CR23","doi-asserted-by":"publisher","unstructured":"van Glabbeek, R.J., Weijland, W.P.: Branching Time and Abstraction in Bisimulation Semantics. Journal of the ACM 43(3), 555\u2013600 (1996). https:\/\/doi.org\/10.1145\/233551.233556","DOI":"10.1145\/233551.233556"},{"key":"15_CR24","doi-asserted-by":"publisher","unstructured":"Winskel, G.: Distributed probabilistic and quantum strategies. Electronic Notes in Theoretical Computer Science 298, 403\u2013425 (2013). https:\/\/doi.org\/10.1016\/j.entcs.2013.09.024","DOI":"10.1016\/j.entcs.2013.09.024"},{"key":"15_CR25","doi-asserted-by":"publisher","unstructured":"Wi\u00dfmann, T., Dubut, J., Katsumata, S., Hasuo, I.: Path category for free. In: Boja\u0144czyk, M., Simpson, A. (eds.) Foundations of Software Science and Computation Structures (FoSSaCS 2019). pp. 523\u2013540. Springer International Publishing, Cham (04 2019). https:\/\/doi.org\/10.1007\/978-3-030-17127-8_30","DOI":"10.1007\/978-3-030-17127-8_30"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-30829-1_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T20:00:22Z","timestamp":1682020822000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30829-1_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031308284","9783031308291"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30829-1_15","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":"21 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paris","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":"22 April 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 April 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2023\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"85","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":"26","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":"31% - 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.1","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":"10","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)"}}]}}