Rabin games and colourful universal trees

Majumdar R, Sağlam I, Thejaswini KS. 2024. Rabin games and colourful universal trees. 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. , LNCS, vol. 14572, 213–231.

Download
OA 2024_LNCS_Majumdar.pdf 462.17 KB [Published Version]

Conference Paper | Published | English

Scopus indexed
Author
Majumdar, Rupak; Sağlam, Irmak; Thejaswini, K. S.ISTA

Corresponding author has ISTA affiliation

Series Title
LNCS
Abstract
We provide an algorithmto solve Rabin and Streett games over graphs with n vertices,m edges, and k colours that runs in ˜O³mn(k!)1+o(1)´time and O(nk logk logn) space, where ˜O hides poly-logarithmic factors. Our algorithm is an improvement by a super quadratic dependence on k! from the currently best known run time of O³mn2(k!)2+o(1)´, obtained by converting a Rabin gameinto a parity game,while simultaneously improving its exponential space requirement. Our main technical ingredient is a characterisation of progress measures for Rabin games using colourful trees and a combinatorial construction of succinctlyrepresented, universal colourful trees. Colourful universal trees are generalisations of universal trees used by Jurdzi´nski and Lazi´c (2017) to solve parity games, as well as of Rabin progress measures of Klarlund and Kozen (1991). Our algorithm for Rabin games is a progress measure lifting algorithm where the lifting is performed on succinct, colourful, universal trees.
Publishing Year
Date Published
2024-04-06
Proceedings Title
30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems
Publisher
Springer Nature
Acknowledgement
This work is a part of the project VAMOS that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreements No 101020093. Rupak Majumdar was partially supported by the DFG project 389792660 TRR 248-CPEC.
Volume
14572
Page
213-231
ISSN
eISSN
IST-REx-ID

Cite this

Majumdar R, Sağlam I, Thejaswini KS. Rabin games and colourful universal trees. In: 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Vol 14572. Springer Nature; 2024:213-231. doi:10.1007/978-3-031-57256-2_11
Majumdar, R., Sağlam, I., & Thejaswini, K. S. (2024). Rabin games and colourful universal trees. In 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (Vol. 14572, pp. 213–231). Springer Nature. https://doi.org/10.1007/978-3-031-57256-2_11
Majumdar, Rupak, Irmak Sağlam, and K. S. Thejaswini. “Rabin Games and Colourful Universal Trees.” In 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 14572:213–31. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-57256-2_11.
R. Majumdar, I. Sağlam, and K. S. Thejaswini, “Rabin games and colourful universal trees,” in 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 2024, vol. 14572, pp. 213–231.
Majumdar R, Sağlam I, Thejaswini KS. 2024. Rabin games and colourful universal trees. 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. , LNCS, vol. 14572, 213–231.
Majumdar, Rupak, et al. “Rabin Games and Colourful Universal Trees.” 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, vol. 14572, Springer Nature, 2024, pp. 213–31, doi:10.1007/978-3-031-57256-2_11.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2024-05-22
MD5 Checksum
492be74f69cd6ea42d38681082d0b521


Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2401.07548

Search this title in

Google Scholar
ISBN Search