{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T08:14:25Z","timestamp":1783671265987,"version":"3.55.0"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031572272","type":"print"},{"value":"9783031572289","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T00:00:00Z","timestamp":1712275200000},"content-version":"vor","delay-in-days":95,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Temporal graphs are a popular modelling mechanism for dynamic complex systems that extend ordinary graphs with discrete time. Simply put, time progresses one unit per step and the availability of edges can change with time.<\/jats:p>\n                  <jats:p>\n                    We consider the complexity of solving\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\omega $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03c9<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -regular games played on temporal graphs where the edge availability is ultimately periodic and fixed a priori.\n                  <\/jats:p>\n                  <jats:p>\n                    We show that solving parity games on temporal graphs is decidable in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\textsf{PSPACE}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>PSPACE<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , only assuming the edge predicate itself is in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\textsf{PSPACE}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>PSPACE<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . A matching lower bound already holds for what we call\n                    <jats:italic>punctual<\/jats:italic>\n                    reachability games on static graphs, where one player wants to reach the target at a given, binary encoded, point in time. We further study syntactic restrictions that imply more efficient procedures. In particular, if the edge predicate is in  and is monotonically increasing for one player and decreasing for the other, then the complexity of solving games is only polynomially increased compared to static graphs.\n                  <\/jats:p>","DOI":"10.1007\/978-3-031-57228-9_5","type":"book-chapter","created":{"date-parts":[[2024,4,4]],"date-time":"2024-04-04T04:03:04Z","timestamp":1712203384000},"page":"79-98","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Parity Games on Temporal Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0238-8662","authenticated-orcid":false,"given":"Pete","family":"Austin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3662-3915","authenticated-orcid":false,"given":"Sougata","family":"Bose","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5274-8190","authenticated-orcid":false,"given":"Patrick","family":"Totzke","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,4,5]]},"reference":[{"key":"5_CR1","unstructured":"Automata Logics, and Infinite Games: A Guide to Current Research.Springer-Verlag (2002)"},{"key":"5_CR2","doi-asserted-by":"publisher","unstructured":"Akrida, E.C., Mertzios, G.B., Spirakis, P.G., Zamaraev, V.: Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences 107, 108\u2013123 (2020). https:\/\/doi.org\/10.1016\/j.jcss.2019.08.002","DOI":"10.1016\/j.jcss.2019.08.002"},{"key":"5_CR3","doi-asserted-by":"publisher","unstructured":"Alur, R., Dill, D.L.: A theory of timed automata. Theor. Comput. Sci. 126(2), 183 \u2013 235 (1994). https:\/\/doi.org\/10.1016\/0304-3975(94)90010-8","DOI":"10.1016\/0304-3975(94)90010-8"},{"key":"5_CR4","doi-asserted-by":"publisher","unstructured":"Avni, G., Ghorpade, P., Guha, S.: A Game of Pawns. In: International Conference on Concurrency Theory. Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0279, pp. 16:1\u201316:17. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2023.16","DOI":"10.4230\/LIPIcs.CONCUR.2023.16"},{"key":"5_CR5","doi-asserted-by":"publisher","unstructured":"Babai, L., Szemeredi, E.: On the complexity of matrix group problems i. In: Annual Symposium on Foundations of Computer Science. pp. 229\u2013240 (1984). https:\/\/doi.org\/10.1109\/SFCS.1984.715919","DOI":"10.1109\/SFCS.1984.715919"},{"key":"5_CR6","doi-asserted-by":"publisher","unstructured":"Calude, C.S., Jain, S., Khoussainov, B., Li, W., Stephan, F.: Deciding parity games in quasipolynomial time. In: Symposium on Theory of Computing. pp. 252\u2013263 (2017). https:\/\/doi.org\/10.1145\/3055399.3055409","DOI":"10.1145\/3055399.3055409"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. Journal of the ACM (JACM) 28(1), 114\u2013133 (1981)","DOI":"10.1145\/322234.322243"},{"key":"5_CR8","doi-asserted-by":"publisher","unstructured":"Chatterjee, K., Henzinger, T.A., Prabhu, V.S.: Timed Parity Games: Complexity and Robustness. Logical Methods in Computer Science Volume 7, Issue 4 (Dec 2011). https:\/\/doi.org\/10.2168\/LMCS-7(4:8)2011","DOI":"10.2168\/LMCS-7(4:8)2011"},{"key":"5_CR9","doi-asserted-by":"publisher","unstructured":"Colcombet, T., Fijalkow, N.: Universal Graphs and Good for Games Automata: New Tools for Infinite Duration Games. In: International Conference on Foundations of Software Science and Computational Structures. LNCS, vol. 11425, pp. 1\u201326. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-17127-8_1","DOI":"10.1007\/978-3-030-17127-8_1"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"De\u00a0Carufel, J.L., Flocchini, P., Santoro, N., Simard, F.: Cops & robber on periodic temporal graphs: Characterization and improved bounds. In: Structural Information and Communication Complexity. pp. 386\u2013405. Springer Nature Switzerland (2023)","DOI":"10.1007\/978-3-031-32733-9_17"},{"key":"5_CR11","doi-asserted-by":"publisher","unstructured":"Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. International Journal of Game Theory 8(2), 109\u2013113 (Jun 1979). https:\/\/doi.org\/10.1007\/BF01768705","DOI":"10.1007\/BF01768705"},{"key":"5_CR12","doi-asserted-by":"publisher","unstructured":"Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. Journal of Computer and System Sciences 119, 1\u201318 (2021). https:\/\/doi.org\/10.1016\/j.jcss.2021.01.005","DOI":"10.1016\/j.jcss.2021.01.005"},{"key":"5_CR13","unstructured":"Fijalkow, N., Bertrand, N., Bouyer-Decitre, P., Brenguier, R., Carayol, A., Fearnley, J., Gimbert, H., Horn, F., Ibsen-Jensen, R., Markey, N., Monmege, B., Novotn\u00fd, P., Randour, M., Sankur, O., Schmitz, S., Serre, O., Skomra, M.: Games on graphs (2023)"},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Mans, B., Santoro, N.: Exploration of periodically varying graphs. In: Algorithms and Computation. pp. 534\u2013543. Springer Berlin Heidelberg (2009)","DOI":"10.1007\/978-3-642-10631-6_55"},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"Haase, C.: A survival guide to presburger arithmetic. SIGLOG News 5(3), 67\u201382 (2018). https:\/\/doi.org\/10.1145\/3242953.3242964","DOI":"10.1145\/3242953.3242964"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Hansen, T.D., Ibsen-Jensen, R., Miltersen, P.B.: A faster algorithm for solving one-clock priced timed games (2013)","DOI":"10.1007\/978-3-642-40184-8_37"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"Holme, P., Saram\u00e4ki, J.: Temporal Network Theory (01 2019). https:\/\/doi.org\/10.1007\/978-3-030-23495-9","DOI":"10.1007\/978-3-030-23495-9"},{"key":"5_CR18","unstructured":"Holzer, M.: On emptiness and counting for alternating finite automata. In: International Conference on Developments in Language Theory. pp. 88\u201397 (1995)"},{"key":"5_CR19","doi-asserted-by":"publisher","unstructured":"Jan\u0107ar, P., Sawa, Z.: A note on emptiness for alternating finite automata with a one-letter alphabet. Inf. Process. Lett. 104(5), 164\u2013167 (2007). https:\/\/doi.org\/10.1016\/j.ipl.2007.06.006","DOI":"10.1016\/j.ipl.2007.06.006"},{"key":"5_CR20","doi-asserted-by":"publisher","unstructured":"Jiang, T., Ravikumar, B.: A note on the space complexity of some decision problems for finite automata. Inf. Process. Lett. 40(1), 25\u201331 (1991). https:\/\/doi.org\/10.1016\/S0020-0190(05)80006-7","DOI":"10.1016\/S0020-0190(05)80006-7"},{"key":"5_CR21","doi-asserted-by":"crossref","unstructured":"Jurdzi\u0144ski, M., Trivedi, A.: Reachability-time games on timed automata. In: International Colloquium on Automata, Languages and Programming. pp. 838\u2013849. Springer Berlin Heidelberg (2007)","DOI":"10.1007\/978-3-540-73420-8_72"},{"key":"5_CR22","doi-asserted-by":"publisher","unstructured":"Jurdzi\u0144ski, M.: Deciding the winner in parity games is in up $$\\cap $$ co-up. Inf. Process. Lett. 68(3), 119\u2013124 (1998). https:\/\/doi.org\/10.1016\/S0020-0190(98)00150-1","DOI":"10.1016\/S0020-0190(98)00150-1"},{"key":"5_CR23","doi-asserted-by":"crossref","unstructured":"Jurdzi\u0144ski, M., Lazi\u0107, R.: Succinct Progress Measures for Solving Parity Games. In: Annual IEEE Symposium on Logic in Computer Science. pp.\u00a01\u20139. IEEE Computer Society (2017).https:\/\/doi.org\/10.1109\/LICS.2017.8005092","DOI":"10.1109\/LICS.2017.8005092"},{"key":"5_CR24","doi-asserted-by":"publisher","unstructured":"Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Symposium on Theory of Computing. p. 513\u2013522. STOC \u201910, Association for Computing Machinery (2010). https:\/\/doi.org\/10.1145\/1806689.1806760","DOI":"10.1145\/1806689.1806760"},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"Lehtinen, K., Parys, P., Schewe, S., Wojtczak, D.: A Recursive Approach to Solving Parity Games in Quasipolynomial Time. Logical Methods in Computer Science 18(1), 8:1\u201318 (2022)","DOI":"10.46298\/lmcs-18(1:8)2022"},{"key":"5_CR26","doi-asserted-by":"publisher","unstructured":"Lehtinen, K., Boker, U.: Register Games. Logical Methods in Computer Science 16(2), 6:1\u20136:25 (2020). https:\/\/doi.org\/10.23638\/LMCS-16(2:6)2020","DOI":"10.23638\/LMCS-16(2:6)2020"},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"Lifshits, Y., Lohrey, M.: Querying and embedding compressed texts. In: International Symposium on Mathematical Foundations of Computer Science. pp. 681\u2013692. Springer Berlin Heidelberg (2006)","DOI":"10.1007\/11821069_59"},{"key":"5_CR28","doi-asserted-by":"crossref","unstructured":"Maler, O., Pnueli, A., Sifakis, J.: On the synthesis of discrete controllers for timed systems. In: International Symposium on Theoretical Aspects of Computer Science. pp. 229\u2013242. Springer Berlin Heidelberg (1995)","DOI":"10.1007\/3-540-59042-0_76"},{"key":"5_CR29","doi-asserted-by":"publisher","unstructured":"Mertzios, G.B., Molter, H., Niedermeier, R., Zamaraev, V., Zschoche, P.: Computing maximum matchings in temporal graphs. Journal of Computer and System Sciences 137, 1\u201319 (2023). https:\/\/doi.org\/10.1016\/j.jcss.2023.04.005","DOI":"10.1016\/j.jcss.2023.04.005"},{"key":"5_CR30","doi-asserted-by":"crossref","unstructured":"Mertzios, G.B., Molter, H., Zamaraev, V.: Sliding window temporal graph coloring. Journal of Computer and System Sciences 120, 97\u2013115 (2021). https:\/\/doi.org\/10.1016\/j.jcss.2021.03.005","DOI":"10.1016\/j.jcss.2021.03.005"},{"key":"5_CR31","doi-asserted-by":"crossref","unstructured":"Michail, O.: An Introduction to Temporal Graphs: An Algorithmic Perspective, pp. 308\u2013343. Springer International Publishing (2015). https:\/\/doi.org\/10.1007\/978-3-319-24024-4_18","DOI":"10.1007\/978-3-319-24024-4_18"},{"key":"5_CR32","doi-asserted-by":"crossref","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Causality, influence, and computation in possibly disconnected synchronous dynamic networks. Journal of Parallel and Distributed Computing 74(1), 2016\u20132026 (2014)","DOI":"10.1016\/j.jpdc.2013.07.007"},{"key":"5_CR33","doi-asserted-by":"crossref","unstructured":"Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. In: International Symposium on Mathematical Foundations of Computer Science. pp. 553\u2013564. Springer Berlin Heidelberg (2014)","DOI":"10.1007\/978-3-662-44465-8_47"},{"key":"5_CR34","doi-asserted-by":"crossref","unstructured":"Pnueli, A., Rosner, R.: On the synthesis of a reactive module. In: Annual Symposium on Principles of Programming Languages. p. 179\u2013190. POPL \u201989, Association for Computing Machinery (1989). https:\/\/doi.org\/10.1145\/75277.75293","DOI":"10.1145\/75277.75293"},{"key":"5_CR35","doi-asserted-by":"crossref","unstructured":"Pnueli, A.: The temporal logic of programs. In: Annual Symposium on Foundations of Computer Science. p. 46\u201357. SFCS \u201977, IEEE Computer Society (1977). https:\/\/doi.org\/10.1109\/SFCS.1977.32","DOI":"10.1109\/SFCS.1977.32"},{"key":"5_CR36","doi-asserted-by":"crossref","unstructured":"Ravi, R.: Rapid rumor ramification: Approximating the minimum broadcast time. In: Proceedings 35th Annual Symposium on Foundations of Computer Science. pp. 202\u2013213 (1994)","DOI":"10.1109\/SFCS.1994.365693"},{"key":"5_CR37","doi-asserted-by":"publisher","unstructured":"Scarpellini, B.: Complexity of subcases of presburger arithmetic. Transactions of the American Mathematical Society 284, 203\u2013218 (1984). https:\/\/doi.org\/10.1090\/s0002-9947-1984-0742421-9","DOI":"10.1090\/s0002-9947-1984-0742421-9"},{"key":"5_CR38","unstructured":"Trivedi, A.: Competitive optimisation on timed automata. Ph.D. thesis, University of Warwick (April 2009)"}],"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-57228-9_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T07:28:47Z","timestamp":1783668527000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-57228-9_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031572272","9783031572289"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-57228-9_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"5 April 2024","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":"Luxembourg City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 April 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2024\/conferences\/fossacs\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}