{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T18:43:59Z","timestamp":1783709039567,"version":"3.55.0"},"publisher-location":"Cham","reference-count":24,"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":"Abstract<\/jats:title>\n \n We consider two-player games over finite graphs in which both players are restricted by fairness constraints on their moves. Given a two player game graph\n \n \n $$G=(V,E)$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n =<\/mml:mo>\n (<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and a set of fair moves\n \n \n $$E_f\\subseteq E$$<\/jats:tex-math>\n \n \n \n E<\/mml:mi>\n f<\/mml:mi>\n <\/mml:msub>\n \u2286<\/mml:mo>\n E<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n a player is said to play\n fair<\/jats:italic>\n in\n G<\/jats:italic>\n if they choose an edge\n \n \n $$e\\in E_f$$<\/jats:tex-math>\n \n \n e<\/mml:mi>\n \u2208<\/mml:mo>\n \n E<\/mml:mi>\n f<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n infinitely often whenever the source node of\n e<\/jats:italic>\n is visited infinitely often. Otherwise, they play\n unfair<\/jats:italic>\n . We equip such games with two\n \n \n $$\\omega $$<\/jats:tex-math>\n \n \u03c9<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -regular winning conditions\n \n \n $$\\alpha $$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and\n \n \n $$\\beta $$<\/jats:tex-math>\n \n \u03b2<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n deciding the winner of mutually fair and mutually unfair plays, respectively. Whenever one player plays fair and the other plays unfair, the fairly playing player wins the game. The resulting games are called\n fair<\/jats:italic>\n \n \n $$\\alpha \/\\beta $$<\/jats:tex-math>\n \n \n \u03b1<\/mml:mi>\n \/<\/mml:mo>\n \u03b2<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n games<\/jats:italic>\n .\n <\/jats:p>\n \n We formalize fair\n \n \n $$\\alpha \/\\beta $$<\/jats:tex-math>\n \n \n \u03b1<\/mml:mi>\n \/<\/mml:mo>\n \u03b2<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n games and show that they are determined. For fair parity\/parity games, i.e., fair\n \n \n $$\\alpha \/\\beta $$<\/jats:tex-math>\n \n \n \u03b1<\/mml:mi>\n \/<\/mml:mo>\n \u03b2<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n games where\n \n \n $$\\alpha $$<\/jats:tex-math>\n \n \u03b1<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and\n \n \n $$\\beta $$<\/jats:tex-math>\n \n \u03b2<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n are given each by a parity condition over\n G<\/jats:italic>\n , we provide a polynomial reduction to (normal) parity games via a gadget construction inspired by the reduction of stochastic parity games to parity games. We further give a direct\n symbolic fixpoint algorithm<\/jats:italic>\n to solve fair parity\/parity games. On a conceptual level, we illustrate the translation between the gadget-based reduction and the direct symbolic algorithm which uncovers the underlying similarities of solution algorithms for fair and stochastic parity games, as well as for the recently considered class of fair games in which only one player is restricted by fair moves.\n <\/jats:p>","DOI":"10.1007\/978-3-031-57228-9_2","type":"book-chapter","created":{"date-parts":[[2024,4,4]],"date-time":"2024-04-04T04:03:04Z","timestamp":1712203384000},"page":"13-33","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Fair $$\\omega $$-Regular Games"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0935-8602","authenticated-orcid":false,"given":"Daniel","family":"Hausmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8242-5357","authenticated-orcid":false,"given":"Nir","family":"Piterman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4757-1631","authenticated-orcid":false,"given":"Irmak","family":"Sa\u011flam","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2801-639X","authenticated-orcid":false,"given":"Anne-Kathrin","family":"Schmuck","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,4,5]]},"reference":[{"key":"2_CR1","doi-asserted-by":"publisher","unstructured":"Aminof, B., Ball, T., Kupferman, O.: Reasoning about systems with transition fairness. In: Baader, F., Voronkov, A. (eds.) Logic for Programming, Artificial Intelligence, and Reasoning, 11th International Conference, LPAR 2004, Montevideo, Uruguay, March 14-18, 2005, Proceedings. Lecture Notes in Computer Science, vol.\u00a03452, pp. 194\u2013208. Springer (2004). https:\/\/doi.org\/10.1007\/978-3-540-32275-7_14","DOI":"10.1007\/978-3-540-32275-7_14"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Aminof, B., Giacomo, G.D., Rubin, S.: Stochastic fairness and language-theoretic fairness in planning in nondeterministic domains. In: Beck, J.C., Buffet, O., Hoffmann, J., Karpas, E., Sohrabi, S. (eds.) Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling, Nancy, France, October 26-30, 2020. pp. 20\u201328. AAAI Press (2020), https:\/\/ojs.aaai.org\/index.php\/ICAPS\/article\/view\/6641","DOI":"10.1609\/icaps.v30i1.6641"},{"key":"2_CR3","doi-asserted-by":"publisher","unstructured":"Baldan, P., K\u00f6nig, B., Mika-Michalski, C., Padoan, T.: Fixpoint games on continuous lattices. Proc. ACM Program. Lang. 3(POPL), 26:1\u201326:29 (2019). https:\/\/doi.org\/10.1145\/3290339","DOI":"10.1145\/3290339"},{"key":"2_CR4","doi-asserted-by":"publisher","unstructured":"Banerjee, T., Majumdar, R., Mallik, K., Schmuck, A., Soudjani, S.: Fast symbolic algorithms for omega-regular games under strong transition fairness. TheoretiCS 2 (2023). https:\/\/doi.org\/10.46298\/theoretics.23.4","DOI":"10.46298\/theoretics.23.4"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"B\u00fcchi, J., Landweber, L.: Solving sequential conditions by finite-state strategies. Trans. Amer. Math. Soc. 138, 295\u2013311 (1969)","DOI":"10.1090\/S0002-9947-1969-0280205-0"},{"key":"2_CR6","doi-asserted-by":"publisher","unstructured":"Chatterjee, K., de\u00a0Alfaro, L., Faella, M., Majumdar, R., Raman, V.: Code aware resource management. Formal Methods Syst. Des. 42(2), 146\u2013174 (2013). https:\/\/doi.org\/10.1007\/s10703-012-0170-4","DOI":"10.1007\/s10703-012-0170-4"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Jurdzinski, M., Henzinger, T.: Simple stochastic parity games. In: In Proceedings of the International Conference for Computer Science Logic (CSL). pp. 100\u2013113 (2003), http:\/\/chess.eecs.berkeley.edu\/pubs\/729.html","DOI":"10.1007\/978-3-540-45220-1_11"},{"key":"2_CR8","unstructured":"Church, A.: Application of recursive arithmetic to the problem of circuit synthesis. Journal of Symbolic Logic 28(4) (1963)"},{"key":"2_CR9","doi-asserted-by":"publisher","unstructured":"D\u2019Ippolito, N., Rodr\u00edguez, N., Sardi\u00f1a, S.: Fully observable non-deterministic planning as assumption-based reactive synthesis. J. Artif. Intell. Res. 61, 593\u2013621 (2018). https:\/\/doi.org\/10.1613\/jair.5562","DOI":"10.1613\/jair.5562"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Hausmann, D., Piterman, N., Sa\u011flam, I., Schmuck, A.K.: Fair $$\\omega $$-regular games (2024), extended version available at https:\/\/arxiv.org\/abs\/2310.13612","DOI":"10.1007\/978-3-031-57228-9_2"},{"key":"2_CR11","doi-asserted-by":"publisher","unstructured":"Majumdar, R., Mallik, K., Schmuck, A.K., Soudjani, S.: Symbolic control for stochastic systems via finite parity games. Nonlinear Analysis: Hybrid Systems 51, 101430 (2024). https:\/\/doi.org\/10.1016\/j.nahs.2023.101430","DOI":"10.1016\/j.nahs.2023.101430"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Martin, D.: Borel determinacy. Annals of Mathematics 65, 363\u2013371 (1975)","DOI":"10.2307\/1971035"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Mazala, R.: Infinite games. In: Gr\u00e4del, E., Thomas, W., Wilke, T. (eds.) Automata, Logics, and Infinite Games: A Guide to Current Research. Lecture Notes in Computer Science, vol.\u00a02500, pp. 23\u201342. Springer (2001)","DOI":"10.1007\/3-540-36387-4_2"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Meyer, P.J., Sickert, S., Luttenberger, M.: Strix: Explicit reactive synthesis strikes back! In: 30th International Conference on Computer Aided Verification. Lecture Notes in Computer Science, vol. 10981, pp. 578\u2013586. Springer (2018)","DOI":"10.1007\/978-3-319-96145-3_31"},{"key":"2_CR15","doi-asserted-by":"publisher","unstructured":"Nilsson, P., Ozay, N., Liu, J.: Augmented finite transition systems as abstractions for control synthesis. Discret. Event Dyn. Syst. 27(2), 301\u2013340 (2017). https:\/\/doi.org\/10.1007\/s10626-017-0243-z","DOI":"10.1007\/s10626-017-0243-z"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Piterman, N., Pnueli, A., Sa\u2019ar, Y.: Synthesis of reactive(1) designs. In: Proceedings of the 7th International Conference on Verification, Model Checking, and Abstract Interpretation. p. 364\u2013380. VMCAI\u201906, Springer-Verlag, Berlin, Heidelberg (2006)","DOI":"10.1007\/11609773_24"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"Pnueli, A., Rosner, R.: A framework for the synthesis of reactive modules. In: Proc. Intl. Conf. on Concurrency: Concurrency 88. Lecture Notes in Computer Science, vol.\u00a0335, pp. 4\u201317. Springer-Verlag (1988)","DOI":"10.1007\/3-540-50403-6_28"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Rabin, M.: Decidability of second order theories and automata on infinite trees. Trans. Amer. Math. Soc. 141, 1\u201335 (1969)","DOI":"10.1090\/S0002-9947-1969-0246760-1"},{"key":"2_CR19","unstructured":"Sa\u011flam, I., Schmuck, A.K.: Solving odd-fair parity games. In: 42th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2023), (to appear)"},{"key":"2_CR20","unstructured":"Schewe, S., Finkbeiner, B.: Bounded synthesis. In: 4th Int. Symp. on Automated Technology for Verification and Analysis. Lecture Notes in Computer Science, vol.\u00a04218, pp. 245\u2013259. Springer (2006)"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Thistle, J.G., Malham\u00e9, R.: Control of $$\\omega $$-automata under state fairness assumptions. Systems & control letters 33(4), 265\u2013274 (1998)","DOI":"10.1016\/S0167-6911(97)00106-0"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Languages, automata, and logic. Handbook of Formal Language Theory III, 389\u2013455 (1997)","DOI":"10.1007\/978-3-642-59126-6_7"},{"key":"2_CR23","doi-asserted-by":"publisher","unstructured":"Walukiewicz, I.: Monadic second-order logic on tree-like structures. Theor. Comput. Sci. 275(1-2), 311\u2013346 (2002). https:\/\/doi.org\/10.1016\/S0304-3975(01)00185-2","DOI":"10.1016\/S0304-3975(01)00185-2"},{"key":"2_CR24","doi-asserted-by":"publisher","unstructured":"Zielonka, W.: Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theor. Comput. Sci. 200(1-2), 135\u2013183 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(98)00009-7","DOI":"10.1016\/S0304-3975(98)00009-7"}],"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_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T07:28:39Z","timestamp":1783668519000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-57228-9_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031572272","9783031572289"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-57228-9_2","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"}}]}}