{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T17:05:22Z","timestamp":1742922322085,"version":"3.40.3"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031562211"},{"type":"electronic","value":"9783031562228"}],"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:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-56222-8_2","type":"book-chapter","created":{"date-parts":[[2024,3,19]],"date-time":"2024-03-19T08:02:30Z","timestamp":1710835350000},"page":"22-50","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Restricted Flow Games"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-0150-9620","authenticated-orcid":false,"given":"Ravid","family":"Alon","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4699-6117","authenticated-orcid":false,"given":"Orna","family":"Kupferman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,3,20]]},"reference":[{"issue":"3","key":"2_CR1","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1006\/jcss.1999.1627","volume":"58","author":"S Abiteboul","year":"1999","unstructured":"Abiteboul, S., Vianu, V.: Regular path queries with constraints. J. Comput. Syst. Sci. 58(3), 428\u2013452 (1999)","journal-title":"J. Comput. Syst. Sci."},{"unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall Englewood Cliffs (1993)","key":"2_CR2"},{"key":"2_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-030-62536-8_1","volume-title":"Descriptional Complexity of Formal Systems","author":"R Alon","year":"2020","unstructured":"Alon, R., Kupferman, O.: Mutually accepting capacitated automata. In: Jir\u00e1skov\u00e1, G., Pighizzini, G. (eds.) DCFS 2020. LNCS, vol. 12442, pp. 1\u201312. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-62536-8_1"},{"issue":"3","key":"2_CR4","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1137\/S0097539798337716","volume":"30","author":"C Barrett","year":"2000","unstructured":"Barrett, C., Jacob, R., Marathe, M.: Formal-language-constrained path problems. SIAM J. Comput. 30(3), 809\u2013837 (2000)","journal-title":"SIAM J. Comput."},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"10","DOI":"10.3141\/1588-02","volume":"1588","author":"V Blue","year":"1997","unstructured":"Blue, V., Adler, J., List, G.: Real-time multiple-objective path search for in-vehicle route guidance systems. J. Transp. Res. Board 1588, 10\u201317 (1997)","journal-title":"J. Transp. Res. Board"},{"issue":"4","key":"2_CR6","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/959060.959076","volume":"32","author":"D Calvanese","year":"2003","unstructured":"Calvanese, D., de Giacomo, G., Lenzerini, M., Vardi, M.Y.: Reasoning on regular path queries. SIGMOD Rec. 32(4), 83\u201392 (2003)","journal-title":"SIGMOD Rec."},{"key":"2_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/BFb0025774","volume-title":"Logics of Programs","author":"EM Clarke","year":"1982","unstructured":"Clarke, E.M., Emerson, E.A.: Design and synthesis of synchronization skeletons using branching time temporal logic. In: Kozen, D. (ed.) Logic of Programs 1981. LNCS, vol. 131, pp. 52\u201371. Springer, Heidelberg (1982). https:\/\/doi.org\/10.1007\/BFb0025774"},{"unstructured":"Clarke, E.M., Grumberg, O., Peled, D.: Model Checking. MIT Press (1999)","key":"2_CR8"},{"doi-asserted-by":"crossref","unstructured":"Cook, S.A.: Path systems and language recognition. In: Proceedings of the 2nd ACM Symposium on Theory of Computing, pp. 70\u201372 (1970)","key":"2_CR9","DOI":"10.1145\/800161.805151"},{"unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press and McGraw-Hill (1990)","key":"2_CR10"},{"issue":"5","key":"2_CR11","first-page":"1277","volume":"11","author":"EA Dinic","year":"1970","unstructured":"Dinic, E.A.: Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math. Doklady 11(5), 1277\u20131280 (1970). English translation by RF. Rinehart","journal-title":"Soviet Math. Doklady"},{"doi-asserted-by":"crossref","unstructured":"Even, S.: Graph Algorithms, 2nd edn. Cambridge University Press (2011)","key":"2_CR12","DOI":"10.1017\/CBO9781139015165"},{"issue":"3","key":"2_CR13","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"LR Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8(3), 399\u2013404 (1956)","journal-title":"Can. J. Math."},{"key":"2_CR14","volume-title":"Flows in Networks","author":"LR Ford","year":"1962","unstructured":"Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)"},{"key":"2_CR15","first-page":"123","volume":"82","author":"Z F\u00fcredi","year":"1991","unstructured":"F\u00fcredi, Z., Reimer, D., Seress, A.: Triangle-free game and extremal graph problems. Congr. Numer. 82, 123\u2013128 (1991)","journal-title":"Congr. Numer."},{"unstructured":"Garey, M., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company (1979)","key":"2_CR16"},{"doi-asserted-by":"crossref","unstructured":"Goldberg, A.V., Tardos, \u00c9., Tarjan, R.E.: Network flow algorithms. Technical report, DTIC Document (1989)","key":"2_CR17","DOI":"10.21236\/ADA214689"},{"issue":"4","key":"2_CR18","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"AV Goldberg","year":"1988","unstructured":"Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum-flow problem. J. ACM 35(4), 921\u2013940 (1988)","journal-title":"J. ACM"},{"unstructured":"Guha, S., Kupferman, O., Vardi, G.: Multi-player flow games. In: Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, pp. 104\u2013112 (2018)","key":"2_CR19"},{"key":"2_CR20","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ejc.2015.05.017","volume":"41","author":"D Hefetz","year":"2016","unstructured":"Hefetz, D., Krivelevich, M., Naor, A., Stojakovi\u0107, M.: On saturation games. Eur. J. Comb. 41, 315\u2013335 (2016)","journal-title":"Eur. J. Comb."},{"unstructured":"Hefetz, D., Kupferman, O., Lellouche, A., Vardi, G.: Spanning-tree games. In: 43rd International Symposium on Mathematical Foundations of Computer Science, volume 117 of LIPIcs, pp. 35:1\u201335:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)","key":"2_CR21"},{"issue":"1","key":"2_CR22","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V Kann","year":"1991","unstructured":"Kann, V.: Maximum bounded 3-dimensional matching is MAX-SNP-complete. Inf. Process. Lett. 37(1), 27\u201335 (1991)","journal-title":"Inf. Process. Lett."},{"doi-asserted-by":"crossref","unstructured":"Kupferman, O.: Examining classical graph-theory problems from the viewpoint of formal-verification methods. In: Proceedings of the 49th ACM Symposium on Theory of Computing, p. 6 (2017)","key":"2_CR23","DOI":"10.1145\/3055399.3079075"},{"unstructured":"Kupferman, O., Tamir, T.: Properties and utilization of capacitated automata. In: Proceedings of the 34th Conference on Foundations of Software Technology and Theoretical Computer Science, volume 29 of LIPIcs, pp. 33\u201344. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany (2014)","key":"2_CR24"},{"unstructured":"Kupferman, O., Vardi, G.: Eulerian paths with regular constraints. In: 41st International Symposium on Mathematical Foundations of Computer Science, volume 58 of Leibniz International Proceedings in Informatics (LIPIcs), p. 62:1 (2016)","key":"2_CR25"},{"unstructured":"Kupferman, O., Vardi, G.: The unfortunate-flow problem. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, volume 107 of LIPIcs, pp. 157:1\u2013157:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)","key":"2_CR26"},{"unstructured":"Kupferman, O., Vardi, G., Vardi, M.Y.: Flow games. In: Proceedings of the 37th Conference on Foundations of Software Technology and Theoretical Computer Science, volume 93 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 38:38\u201338:16 (2017)","key":"2_CR27"},{"issue":"6","key":"2_CR28","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/S009753979122370X","volume":"24","author":"AO Mendelzon","year":"1995","unstructured":"Mendelzon, A.O., Wood, P.T.: Finding regular simple paths in graph databases. SIAM J. Comput. 24(6), 1235\u20131258 (1995)","journal-title":"SIAM J. Comput."},{"unstructured":"Papadimitriou, C.H.: Computational Complexity, 2nd edn. Addison-Wesley (1994)","key":"2_CR29"},{"doi-asserted-by":"crossref","unstructured":"Petrank, E.: The hardness of approximation: gap location. In: The 2nd Israel Symposium on Theory and Computing Systems, pp. 275\u2013284 (1993)","key":"2_CR30","DOI":"10.1109\/ISTCS.1993.253461"},{"key":"2_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"LJ Stockmeyer","year":"1977","unstructured":"Stockmeyer, L.J.: The polynomial-time hierarchy. Theoret. Comput. Sci. 3, 1\u201322 (1977)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"2_CR32","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"2_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1994.1092","volume":"115","author":"MY Vardi","year":"1994","unstructured":"Vardi, M.Y., Wolper, P.: Reasoning about infinite computations. Inf. Comput. 115(1), 1\u201337 (1994)","journal-title":"Inf. Comput."}],"container-title":["Lecture Notes in Computer Science","Taming the Infinities of Concurrency"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-56222-8_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,6]],"date-time":"2024-11-06T22:02:46Z","timestamp":1730930566000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-56222-8_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031562211","9783031562228"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-56222-8_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"20 March 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}