{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T00:00:38Z","timestamp":1762300838296,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031757778"},{"type":"electronic","value":"9783031757785"}],"license":[{"start":{"date-parts":[[2024,11,18]],"date-time":"2024-11-18T00:00:00Z","timestamp":1731888000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,11,18]],"date-time":"2024-11-18T00:00:00Z","timestamp":1731888000000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-75778-5_20","type":"book-chapter","created":{"date-parts":[[2024,11,17]],"date-time":"2024-11-17T12:09:00Z","timestamp":1731845340000},"page":"423-445","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Compositional Solution of\u00a0Mean Payoff Games by\u00a0String Diagrams"],"prefix":"10.1007","author":[{"given":"Kazuki","family":"Watanabe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Clovis","family":"Eberhart","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuyuki","family":"Asada","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ichiro","family":"Hasuo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,11,18]]},"reference":[{"key":"20_CR1","doi-asserted-by":"publisher","unstructured":"Alur, R., Stanford, C., Watson, C.: A robust theory of series parallel graphs. Proc. ACM Program. Lang. 7(POPL), 1058\u20131088 (2023). https:\/\/doi.org\/10.1145\/3571230DOI","DOI":"10.1145\/3571230"},{"key":"20_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/978-3-030-45237-7_18","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"M Benerecetti","year":"2020","unstructured":"Benerecetti, M., Dell\u2019Erba, D., Mogavero, F.: Solving mean-payoff games via quasi dominions. In: TACAS 2020. LNCS, vol. 12079, pp. 289\u2013306. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45237-7_18"},{"issue":"2","key":"20_CR3","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s10703-018-0315-1","volume":"52","author":"M Benerecetti","year":"2018","unstructured":"Benerecetti, M., Dell\u2019Erba, D., Mogavero, F.: Solving parity games via priority promotion. Formal Methods Syst. Des. 52(2), 193\u2013226 (2018)","journal-title":"Formal Methods Syst. Des."},{"key":"20_CR4","doi-asserted-by":"publisher","unstructured":"Bonchi, F., Holland, J., Piedeleu, R., Sobocinski, P., Zanasi, F.: Diagrammatic algebra: from linear to concurrent systems. Proc. ACM Program. Lang. 3(POPL), 25:1\u201325:28 (2019). https:\/\/doi.org\/10.1145\/3290338","DOI":"10.1145\/3290338"},{"key":"20_CR5","doi-asserted-by":"publisher","unstructured":"Brim, L., Chaloupka, J., Doyen, L., Gentilini, R., Raskin, J.: Faster algorithms for mean-payoff games. Formal Methods Syst. Des. 38(2), 97\u2013118 (2011). https:\/\/doi.org\/10.1007\/s10703-010-0105-x","DOI":"10.1007\/s10703-010-0105-x"},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-540-45212-6_9","volume-title":"Embedded Software","author":"A Chakrabarti","year":"2003","unstructured":"Chakrabarti, A., de Alfaro, L., Henzinger, T.A., Stoelinga, M.: Resource Interfaces. In: Alur, R., Lee, I. (eds.) EMSOFT 2003. LNCS, vol. 2855, pp. 117\u2013133. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45212-6_9"},{"key":"20_CR7","doi-asserted-by":"publisher","unstructured":"Clarke, E.M., Long, D.E., McMillan, K.L.: Compositional model checking. In: Proceedings of the Fourth Annual Symposium on Logic in Computer Science (LICS \u201989), Pacific Grove, California, USA, June 5-8, 1989. pp. 353\u2013362. IEEE Computer Society (1989). https:\/\/doi.org\/10.1109\/LICS.1989.39190","DOI":"10.1109\/LICS.1989.39190"},{"key":"20_CR8","doi-asserted-by":"publisher","unstructured":"Comin, C., Posenato, R., Rizzi, R.: Hyper temporal networks - A tractable generalization of simple temporal networks and its relation to mean payoff games. Constraints An Int. J. 22(2), 152\u2013190 (2017). https:\/\/doi.org\/10.1007\/s10601-016-9243-0","DOI":"10.1007\/s10601-016-9243-0"},{"key":"20_CR9","doi-asserted-by":"publisher","unstructured":"Comin, C., Rizzi, R.: Dynamic consistency of conditional simple temporal networks via mean payoff games: A singly-exponential time dc-checking. In: Grandi, F., Lange, M., Lomuscio, A. (eds.) 22nd International Symposium on Temporal Representation and Reasoning, TIME 2015, Kassel, Germany, September 23-25, 2015. pp. 19\u201328. IEEE Computer Society (2015). https:\/\/doi.org\/10.1109\/TIME.2015.18","DOI":"10.1109\/TIME.2015.18"},{"key":"20_CR10","unstructured":"Cruttwell, G.S.: Normed spaces and the change of base for enriched categories. Ph.D. thesis, Dalhousie University (2008)"},{"issue":"2","key":"20_CR11","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"RJ Duffin","year":"1965","unstructured":"Duffin, R.J.: Topology of series-parallel networks. J. Math. Anal. Appl. 10(2), 303\u2013318 (1965)","journal-title":"J. Math. Anal. Appl."},{"issue":"2","key":"20_CR12","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01768705","volume":"8","author":"A Ehrenfeucht","year":"1979","unstructured":"Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. Internat. J. Game Theory 8(2), 109\u2013113 (1979)","journal-title":"Internat. J. Game Theory"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Eilenberg, S., Kelly, G.M.: Closed categories. In: Eilenberg, S., Harrison, D.K., MacLane, S., R\u00f6hrl, H. (eds.) Proceedings of the Conference on Categorical Algebra, pp. 421\u2013562. Springer Berlin Heidelberg, Berlin, Heidelberg (1966)","DOI":"10.1007\/978-3-642-99902-4_22"},{"issue":"1","key":"20_CR14","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0890-5401(92)90041-D","volume":"98","author":"D Eppstein","year":"1992","unstructured":"Eppstein, D.: Parallel recognition of series-parallel graphs. Inf. Comput. 98(1), 41\u201355 (1992)","journal-title":"Inf. Comput."},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-642-04761-9_15","volume-title":"Automated Technology for Verification and Analysis","author":"O Friedmann","year":"2009","unstructured":"Friedmann, O., Lange, M.: Solving parity games in practice. In: Liu, Z., Ravn, A.P. (eds.) ATVA 2009. LNCS, vol. 5799, pp. 182\u2013196. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-04761-9_15"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Grellois, C., Melli\u00e8s, P.A.: Finitary semantics of linear logic and higher-order model-checking. In: International Symposium on Mathematical Foundations of Computer Science, pp. 256\u2013268. Springer (2015)","DOI":"10.1007\/978-3-662-48057-1_20"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Heunen, C., Vicary, J.: Categories for Quantum Theory: an introduction. Oxford University Press (2019)","DOI":"10.1093\/oso\/9780198739623.001.0001"},{"issue":"3","key":"20_CR18","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1017\/S0305004100074338","volume":"119","author":"A Joyal","year":"1996","unstructured":"Joyal, A., Street, R., Verity, D.: Traced monoidal categories. Math. Proc. Cambridge Philos. Soc. 119(3), 447\u2013468 (1996)","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"key":"20_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/3-540-46541-3_24","volume-title":"STACS 2000","author":"M Jurdzi\u0144ski","year":"2000","unstructured":"Jurdzi\u0144ski, M.: Small progress measures for solving parity games. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 290\u2013301. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-46541-3_24"},{"key":"20_CR20","doi-asserted-by":"publisher","unstructured":"Kelly, G., Laplaza, M.: Coherence for compact closed categories. J. Pure Appl. Algebra 19, 193\u2013213 (1980). https:\/\/doi.org\/10.1016\/0022-4049(80)90101-2. https:\/\/www.sciencedirect.com\/science\/article\/pii\/0022404980901012","DOI":"10.1016\/0022-4049(80)90101-2"},{"issue":"2","key":"20_CR21","doi-asserted-by":"publisher","first-page":"665","DOI":"10.2140\/agt.2002.2.665","volume":"2","author":"M Khovanov","year":"2002","unstructured":"Khovanov, M.: A functor-valued invariant of tangles. Algebraic Geometric Topol. 2(2), 665\u2013741 (2002)","journal-title":"Algebraic Geometric Topol."},{"key":"20_CR22","doi-asserted-by":"publisher","unstructured":"Kwiatkowska, M.Z., Norman, G., Parker, D., Qu, H.: Compositional probabilistic verification through multi-objective model checking. Inf. Comput. 232, 38\u201365 (2013). https:\/\/doi.org\/10.1016\/j.ic.2013.10.001","DOI":"10.1016\/j.ic.2013.10.001"},{"key":"20_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4721-8","volume-title":"Categories for the working mathematician, Graduate Texts in Mathematics","author":"S Mac Lane","year":"1978","unstructured":"Mac Lane, S.: Categories for the working mathematician, Graduate Texts in Mathematics, vol. 5, 2nd edn. Springer-Verlag, New York (1978)","edition":"2"},{"key":"20_CR24","doi-asserted-by":"publisher","unstructured":"Moggi, E.: Notions of computation and monads. Inf. Comput. 93(1), 55\u201392 (1991). https:\/\/doi.org\/10.1016\/0890-5401(91)90052-4","DOI":"10.1016\/0890-5401(91)90052-4"},{"key":"20_CR25","doi-asserted-by":"publisher","unstructured":"Piedeleu, R., Kartsaklis, D., Coecke, B., Sadrzadeh, M.: Open system categorical quantum semantics in natural language processing. In: Moss, L.S., Sobocinski, P. (eds.) 6th Conference on Algebra and Coalgebra in Computer Science, CALCO 2015, June 24-26, 2015, Nijmegen, The Netherlands. LIPIcs, vol.\u00a035, pp. 270\u2013289. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2015). https:\/\/doi.org\/10.4230\/LIPIcs.CALCO.2015.270","DOI":"10.4230\/LIPIcs.CALCO.2015.270"},{"key":"20_CR26","doi-asserted-by":"publisher","unstructured":"Rathke, J., Sobocinski, P., Stephens, O.: Compositional reachability in Petri nets. In: Ouaknine, J., Potapov, I., Worrell, J. (eds.) Reachability Problems - 8th International Workshop, RP 2014, Oxford, UK, September 22-24, 2014. Proceedings. Lecture Notes in Computer Science, vol.\u00a08762, pp. 230\u2013243. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-319-11439-2_18","DOI":"10.1007\/978-3-319-11439-2_18"},{"key":"20_CR27","unstructured":"Stephens, O.: Compositional specification and reachability checking of net systems. Ph.D. thesis, University of Southampton, UK (2015), http:\/\/eprints.soton.ac.uk\/385201\/"},{"key":"20_CR28","doi-asserted-by":"publisher","unstructured":"Tomita, T., Ueno, A., Shimakawa, M., Hagihara, S., Yonezaki, N.: Safraless LTL synthesis considering maximal realizability. Acta Informatica 54(7), 655\u2013692 (2017). https:\/\/doi.org\/10.1007\/s00236-016-0280-3","DOI":"10.1007\/s00236-016-0280-3"},{"key":"20_CR29","doi-asserted-by":"crossref","unstructured":"Tsukada, T., Ong, C.L.: Compositional higher-order model checking via $$\\omega $$-regular games over B\u00f6hm trees. In: Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS \u201914, Vienna, Austria, July 14 - 18, 2014. pp. 78:1\u201378:10. ACM (2014)","DOI":"10.1145\/2603088.2603133"},{"key":"20_CR30","doi-asserted-by":"publisher","unstructured":"Watanabe, K., Eberhart, C., Asada, K., Hasuo, I.: A compositional approach to parity games. In: Sokolova, A. (ed.) Proceedings 37th Conference on Mathematical Foundations of Programming Semantics, MFPS 2021, Hybrid: Salzburg, Austria and Online, 30th August - 2nd September, 2021. EPTCS, vol.\u00a0351, pp. 278\u2013295 (2021) https:\/\/doi.org\/10.4204\/EPTCS.351.17","DOI":"10.4204\/EPTCS.351.17"},{"key":"20_CR31","doi-asserted-by":"publisher","unstructured":"Watanabe, K., Eberhart, C., Asada, K., Hasuo, I.: Compositional probabilistic model checking with string diagrams of MDPs. In: Enea, C., Lal, A. (eds.) Computer Aided Verification - 35th International Conference, CAV 2023, Paris, France, July 17-22, 2023, Proceedings, Part III. Lecture Notes in Computer Science, vol. 13966, pp. 40\u201361. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-37709-9_3","DOI":"10.1007\/978-3-031-37709-9_3"},{"key":"20_CR32","doi-asserted-by":"crossref","unstructured":"Watanabe, K., Eberhart, C., Asada, K., Hasuo, I.: Compositional solution of mean payoff games by string diagrams. CoRR abs\/2307.08034 (2023)","DOI":"10.1007\/978-3-031-75778-5_20"},{"key":"20_CR33","doi-asserted-by":"crossref","unstructured":"Watanabe, K., van\u00a0der Vegt, M., Hasuo, I., Rot, J., Junges, S.: Pareto curves for compositionally model checking string diagrams of MDPs. In: TACAS (2). LNCS, vol. 14571, pp. 279\u2013298. Springer (2024)","DOI":"10.1007\/978-3-031-57249-4_14"},{"key":"20_CR34","doi-asserted-by":"crossref","unstructured":"Watanabe, K., van\u00a0der Vegt, M., Junges, S., Hasuo, I.: Compositional value iteration with pareto caching. In: CAV (3). LNCS, vol. 14683, pp. 467\u2013491. Springer (2024)","DOI":"10.1007\/978-3-031-65633-0_21"}],"container-title":["Lecture Notes in Computer Science","Principles of Verification: Cycling the Probabilistic Landscape"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-75778-5_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,17]],"date-time":"2024-11-17T13:03:22Z","timestamp":1731848602000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-75778-5_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,18]]},"ISBN":["9783031757778","9783031757785"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-75778-5_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,11,18]]},"assertion":[{"value":"18 November 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}