Dell'Erba, Daniele 
ORCID: 0000-0003-1196-6110 and Schewe, Sven ORCID: 0000-0002-9093-9518
(2022)
Smaller progress measures and separating automata for parity games.
Frontiers in Computer Science, 4.
936903-.
Abstract
<jats:p>Calude et al. have recently shown that parity games can be solved in quasi-polynomial time, a landmark result that has led to several approaches with quasi-polynomial complexity. Jurdzinski and Lazic have further improved the precise complexity of parity games, especially when the number of priorities is low (logarithmic in the number of positions). Both of these algorithms belong to a class of game solving techniques now often called separating automata: deterministic automata that can be used as witness automata to decide the winner in parity games up to a given number of states and colors. We suggest several adjustments to the approach of Calude et al. that lead to smaller statespaces. These include and improve over those earlier introduced by Fearnley et al. We identify two of them that, together, lead to a statespace of exactly the same size Jurdzinski and Lazic's concise progress measures, which currently hold the crown as the smallest statespace. The remaining improvements, hence, lead to a further reduction in the size of the statespace, making our approach the most succinct progress measure available for parity games.</jats:p>
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | parity games, progress measures, value iteration, separating automata, quasi-polynomial algorithms |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 18 Oct 2022 07:55 |
| Last Modified: | 15 Mar 2024 09:05 |
| DOI: | 10.3389/fcomp.2022.936903 |
| Open Access URL: | https://www.frontiersin.org/articles/10.3389/fcomp... |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3165560 |
Dimensions
Dimensions
