{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:10:41Z","timestamp":1760080241113,"version":"3.44.0"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030171261"},{"type":"electronic","value":"9783030171278"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T00:00:00Z","timestamp":1554422400000},"content-version":"vor","delay-in-days":94,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>There are different categorical approaches to variations of transition systems and their bisimulations. One is coalgebra for a functor G, where a bisimulation is defined as a span of G-coalgebra homomorphism. Another one is in terms of path categories and open morphisms, where a bisimulation is defined as a span of open morphisms. This similarity is no coincidence: given a functor G, fulfilling certain conditions, we derive a path-category for pointed G-coalgebras and lax homomorphisms, such that the open morphisms turn out to be precisely the G-coalgebra homomorphisms. The above construction provides path-categories and trace semantics for free for different flavours of transition systems: (1) non-deterministic tree automata (2) regular nondeterministic nominal automata (RNNA), an expressive automata notion living in nominal sets (3) multisorted transition systems. This last instance relates to Lasota\u2019s construction, which is in the converse direction.<\/jats:p>","DOI":"10.1007\/978-3-030-17127-8_30","type":"book-chapter","created":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T11:11:46Z","timestamp":1554462706000},"page":"523-540","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Path Category for Free"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8993-6486","authenticated-orcid":false,"given":"Thorsten","family":"Wi\u00dfmann","sequence":"first","affiliation":[]},{"given":"J\u00e9r\u00e9my","family":"Dubut","sequence":"additional","affiliation":[]},{"given":"Shin-ya","family":"Katsumata","sequence":"additional","affiliation":[]},{"given":"Ichiro","family":"Hasuo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,4,5]]},"reference":[{"key":"30_CR1","unstructured":"Ad\u00e1mek, J., Herrlich, H., Strecker, G.E.: Abstract and concrete categories: the joy of cats. online and enhanced edition of the book published in 1990 by John Wiley and Sons (2004). http:\/\/katmat.math.uni-bremen.de\/acc\/acc.pdf"},{"issue":"3","key":"30_CR2","first-page":"1","volume":"9","author":"J Ad\u00e1mek","year":"2013","unstructured":"Ad\u00e1mek, J., Milius, S., Moss, L.S., Sousa, L.: Well-pointed coalgebras. Logical Methods Comput. Sci. 9(3), 1\u201351 (2013)","journal-title":"Logical Methods Comput. Sci."},{"key":"30_CR3","volume-title":"Category Theory","author":"S Awodey","year":"2010","unstructured":"Awodey, S.: Category Theory, 2nd edn. Oxford University Press, Inc., New York (2010)","edition":"2"},{"key":"30_CR4","doi-asserted-by":"publisher","unstructured":"Beohar, H., K\u00fcpper, S.: On path-based coalgebras and weak notions of bisimulation. In: 7th Conference on Algebra and Coalgebra in Computer Science, CALCO 2017, Ljubljana, Slovenia, 12\u201316 June 2017, pp. 6:1\u20136:17 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.CALCO.2017.6","DOI":"10.4230\/LIPIcs.CALCO.2017.6"},{"key":"30_CR5","doi-asserted-by":"publisher","unstructured":"Bonchi, F., Silva, A., Sokolova, A.: The power of convex algebras. In: Meyer, R., Nestmann, U. (eds.) 28th International Conference on Concurrency Theory (CONCUR 2017), Dagstuhl, Germany, vol. 85, pp. 23:1\u201323:18 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2017.23","DOI":"10.4230\/LIPIcs.CONCUR.2017.23"},{"key":"30_CR6","unstructured":"Comon, H., et al.: Tree Automata Techniques and Applications (2007). http:\/\/tata.gforge.inria.fr"},{"key":"30_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/978-3-662-47666-6_14","volume-title":"Automata, Languages, and Programming","author":"J Dubut","year":"2015","unstructured":"Dubut, J., Goubault, \u00c9., Goubault-Larrecq, J.: Natural homology. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015, Part II. LNCS, vol. 9135, pp. 171\u2013183. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47666-6_14"},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.entcs.2013.09.012","volume":"298","author":"U Fahrenberg","year":"2013","unstructured":"Fahrenberg, U., Legay, A.: History-preserving bisimilarity for higher-dimensional automata via open maps. Electron. Notes Theor. Comput. Sci. 298, 165\u2013178 (2013)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"Fiore, M.P., Cattani, G.L., Winskel, G.: Weak bisimulation and open maps. In: 14th Annual IEEE Symposium on Logic in Computer Science (LICS 1999), pp. 67\u201376 (1999)","DOI":"10.1109\/LICS.1999.782590"},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"Gabbay, M., Pitts, A.M.: A new approach to abstract syntax involving binders. In: Longo, G. (ed.) Proceedings of the Fourteenth Annual IEEE Symposium on Logic in Computer Science, LICS 1999, pp. 214\u2013224. IEEE Computer Society Press (1999)","DOI":"10.1109\/LICS.1999.782617"},{"issue":"1","key":"30_CR11","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1017\/S096012951000054X","volume":"21","author":"HH Hansen","year":"2011","unstructured":"Hansen, H.H., Klin, B.: Pointwise extensions of GSOS-defined operations. Math. Struct. Comput. Sci. 21(1), 321\u2013361 (2011)","journal-title":"Math. Struct. Comput. Sci."},{"issue":"4","key":"30_CR12","first-page":"1","volume":"3","author":"I Hasuo","year":"2007","unstructured":"Hasuo, I., Jacobs, B., Sokolova, A.: Generic trace semantics via coinduction. Logical Methods Comput. Sci. 3(4), 1\u201336 (2007)","journal-title":"Logical Methods Comput. Sci."},{"key":"30_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-642-03741-2_15","volume-title":"Algebra and Coalgebra in Computer Science","author":"B Jacobs","year":"2009","unstructured":"Jacobs, B., Sokolova, A.: Traces, executions and schedulers, coalgebraically. In: Kurz, A., Lenisa, M., Tarlecki, A. (eds.) CALCO 2009. LNCS, vol. 5728, pp. 206\u2013220. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03741-2_15"},{"issue":"1","key":"30_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0001-8708(81)90052-9","volume":"42","author":"A Joyal","year":"1981","unstructured":"Joyal, A.: Une th\u00e9orie combinatoire des s\u00e9ries formelles. Adv. Math. 42(1), 1\u201382 (1981)","journal-title":"Adv. Math."},{"key":"30_CR15","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/BFb0072514","volume-title":"Combinatoire \u00e9num\u00e9rative","author":"A Joyal","year":"1986","unstructured":"Joyal, A.: Foncteurs analytiques et esp\u00e8ces de structures. In: Labelle, G., Leroux, P. (eds.) Combinatoire \u00e9num\u00e9rative. LNM, vol. 1234, pp. 126\u2013159. Springer, Heidelberg (1986). https:\/\/doi.org\/10.1007\/BFb0072514"},{"key":"30_CR16","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1006\/inco.1996.0057","volume":"127","author":"A Joyal","year":"1996","unstructured":"Joyal, A., Nielsen, M., Winskel, G.: Bisimulation from open maps. Inf. Comput. 127, 164\u2013185 (1996)","journal-title":"Inf. Comput."},{"key":"30_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1007\/978-3-662-47666-6_23","volume-title":"Automata, Languages, and Programming","author":"D Kozen","year":"2015","unstructured":"Kozen, D., Mamouras, K., Petri\u015fan, D., Silva, A.: Nominal Kleene coalgebra. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015, Part II. LNCS, vol. 9135, pp. 286\u2013298. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47666-6_23"},{"key":"30_CR18","doi-asserted-by":"publisher","unstructured":"Kurz, A., Petrisan, D., Severi, P., de Vries, F.: Nominal coalgebraic data types with applications to lambda calculus. Logical Methods Comput. Sci. 9(4) (2013). https:\/\/doi.org\/10.2168\/LMCS-9(4:20)2013","DOI":"10.2168\/LMCS-9(4:20)2013"},{"issue":"1","key":"30_CR19","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(01)00023-8","volume":"280","author":"S Lasota","year":"2002","unstructured":"Lasota, S.: Coalgebra morphisms subsume open maps. Theor. Comput. Sci. 280(1), 123\u2013135 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"30_CR20","doi-asserted-by":"crossref","unstructured":"Milius, S.: A sound and complete calculus for finite stream circuits. In: Proceedings of the 25th Annual Symposium on Logic in Computer Science (LICS 2010), pp. 449\u2013458 (2010)","DOI":"10.1109\/LICS.2010.11"},{"key":"30_CR21","unstructured":"Milius, S., Pattinson, D., Schr\u00f6der, L.: Generic trace semantics and graded monads. In: Moss, L.S., Sobocinski, P. (eds.) Proceedings of 6th Conference on Algebra and Coalgebra in Computer Science, CALCO 2015. Leibniz International Proceedings in Informatics, vol. 35, pp. 253\u2013269 (2015). http:\/\/www8.cs.fau.de\/_media\/research:papers:traces-gm.pdf"},{"key":"30_CR22","doi-asserted-by":"publisher","first-page":"61","DOI":"10.3233\/FI-1999-381206","volume":"38","author":"M Nielsen","year":"1999","unstructured":"Nielsen, M., Hune, T.: Bisimulation and open maps for timed transition systems. Fundam. Inform. 38, 61\u201377 (1999)","journal-title":"Fundam. Inform."},{"key":"30_CR23","first-page":"167","volume":"104","author":"D Park","year":"1981","unstructured":"Park, D.: Concurrency and automata on infinite sequences. Theor. Comput. Sci. 104, 167\u2013183 (1981)","journal-title":"Theor. Comput. Sci."},{"key":"30_CR24","series-title":"Cambridge Tracts in Theoretical Computer Science","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139084673","volume-title":"Nominal Sets: Names and Symmetry in Computer Science","author":"AM Pitts","year":"2013","unstructured":"Pitts, A.M.: Nominal Sets: Names and Symmetry in Computer Science. Cambridge Tracts in Theoretical Computer Science, vol. 57. Cambridge University Press, Cambridge (2013)"},{"issue":"1","key":"30_CR25","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(00)00056-6","volume":"249","author":"J Rutten","year":"2000","unstructured":"Rutten, J.: Universal coalgebra: a theory of systems. Theor. Comput. Sci. 249(1), 3\u201380 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"30_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1007\/978-3-662-54458-7_8","volume-title":"Foundations of Software Science and Computation Structures","author":"L Schr\u00f6der","year":"2017","unstructured":"Schr\u00f6der, L., Kozen, D., Milius, S., Wi\u00dfmann, T.: Nominal automata with name binding. In: Esparza, J., Murawski, A.S. (eds.) FoSSaCS 2017. LNCS, vol. 10203, pp. 124\u2013142. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-54458-7_8"}],"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-030-17127-8_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T17:08:53Z","timestamp":1757092133000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17127-8_30"}},"subtitle":["Open Morphisms from Coalgebras with Non-deterministic Branching"],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030171261","9783030171278"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17127-8_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"5 April 2019","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":"Prague","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Czech Republic","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 April 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.etaps.org\/2019\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}