The Library
A technique to speed up symmetric attractor-based algorithms for parity games
Tools
Thejaswini, K. S., Ohlmann, Pierre and Jurdzinski, Marcin (2022) A technique to speed up symmetric attractor-based algorithms for parity games. In: The 42nd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Chennai, India, 15-20 Dec 2022. Published in: Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022), 250 44:1-44:20. ISBN 9783959772617. doi:10.4230/LIPIcs.FSTTCS.2022.32 ISSN 1868-8969.
|
PDF
WRAP-A-technique-to-speed-up-symmetric-attractor-based-algorithms-for-parity-games-Thejaswini-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (552Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2022.32
Abstract
The classic McNaughton-Zielonka algorithm for solving parity games has excellent performance in practice, but its worst-case asymptotic complexity is worse than that of the state-of-the-art algorithms. This work pinpoints the mechanism that is responsible for this relative underperformance and proposes a new technique that eliminates it. The culprit is the wasteful manner in which the results obtained from recursive calls are indiscriminately discarded by the algorithm whenever subgames on which the algorithm is run change. Our new technique is based on firstly enhancing the algorithm to compute attractor decompositions of subgames instead of just winning strategies on them, and then on making it carefully use attractor decompositions computed in prior recursive calls to reduce the size of subgames on which further recursive calls are made. We illustrate the new technique on the classic example of the recursive McNaughton-Zielonka algorithm, but it can be applied to other symmetric attractor-based algorithms that were inspired by it, such as the quasi-polynomial versions of the McNaughton-Zielonka algorithm based on universal trees.
Item Type: | Conference Item (Paper) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Library of Congress Subject Headings (LCSH): | Trees (Graph theory), Trees (Graph theory) -- Data processing, Machine theory, Computational complexity, Formal languages | |||||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||
Journal or Publication Title: | Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) | |||||||||
Publisher: | Leibniz International Proceedings in Informatics | |||||||||
ISBN: | 9783959772617 | |||||||||
ISSN: | 1868-8969 | |||||||||
Official Date: | 2022 | |||||||||
Dates: |
|
|||||||||
Volume: | 250 | |||||||||
Page Range: | 44:1-44:20 | |||||||||
Article Number: | 32 | |||||||||
DOI: | 10.4230/LIPIcs.FSTTCS.2022.32 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||
Date of first compliant deposit: | 26 October 2022 | |||||||||
Date of first compliant Open Access: | 28 October 2022 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Conference Paper Type: | Paper | |||||||||
Title of Event: | The 42nd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) | |||||||||
Type of Event: | Conference | |||||||||
Location of Event: | Chennai, India | |||||||||
Date(s) of Event: | 15-20 Dec 2022 | |||||||||
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