The Library
The Strahler number of a parity game
Tools
Tools
Tools
Daviaud, Laure, Jurdzinski, Marcin and Thejaswini, K. S. (2020) The Strahler number of a parity game. In: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 8-11 Jul 2020. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 168 123:1-123:19. doi:10.4230/LIPIcs.ICALP.2020.123 ISSN 1868-8969.
|
PDF
WRAP-The-Strahler-number-parity-game-Jurdzinski-2020.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (550Kb) | Preview |
Official URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2020.123
Abstract
The Strahler number of a rooted tree is the largest height of a perfect binary tree that is its minor. The Strahler number of a parity game is proposed to be defined as the smallest Strahler number of the tree of any of its attractor decompositions. It is proved that parity games can be solved in quasi-linear space and in time that is polynomial in the number of vertices n and linear in (d/(2k))^k, where d is the number of priorities and k is the Strahler number. This complexity is quasi-polynomial because the Strahler number is at most logarithmic in the number of vertices. The proof is based on a new construction of small Strahler-universal trees. It is shown that the Strahler number of a parity game is a robust, and hence arguably natural, parameter: it coincides with its alternative version based on trees of progress measures and - remarkably - with the register number defined by Lehtinen (2018). It follows that parity games can be solved in quasi-linear space and in time that is polynomial in the number of vertices and linear in (d/(2k))^k, where k is the register number. This significantly improves the running times and space achieved for parity games of bounded register number by Lehtinen (2018) and by Parys (2020). The running time of the algorithm based on small Strahler-universal trees yields a novel trade-off k ⋅ lg(d/k) = O(log n) between the two natural parameters that measure the structural complexity of a parity game, which allows solving parity games in polynomial time. This includes as special cases the asymptotic settings of those parameters covered by the results of Calude, Jain Khoussainov, Li, and Stephan (2017), of Jurdziński and Lazić (2017), and of Lehtinen (2018), and it significantly extends the range of such settings, for example to d = 2^O(√{lg n}) and k = O(√{lg n}).
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Binary system (Mathematics), Arithmetic, Quasi-metric spaces, PI-algebras | ||||||
| Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
| Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||||
| ISSN: | 1868-8969 | ||||||
| Official Date: | 29 June 2020 | ||||||
| Dates: |
|
||||||
| Volume: | 168 | ||||||
| Page Range: | 123:1-123:19 | ||||||
| Article Number: | 23 | ||||||
| DOI: | 10.4230/LIPIcs.ICALP.2020.123 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||
| Date of first compliant deposit: | 12 May 2020 | ||||||
| Date of first compliant Open Access: | 14 May 2020 | ||||||
| RIOXX Funder/Project Grant: |
|
||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) | ||||||
| Type of Event: | Conference | ||||||
| Date(s) of Event: | 8-11 Jul 2020 | ||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
