Abstract
We introduce the novel notion of winning cores in parity games and develop a deterministic polynomial-time under-approximation algorithm for solving parity games based on winning core approximation. Underlying this algorithm are a number properties about winning cores which are interesting in their own right. In particular, we show that the winning core and the winning region for a player in a parity game are equivalently empty. Moreover, the winning core contains all fatal attractors but is not necessarily a dominion itself. Experimental results are very positive both with respect to quality of approximation and running time. It outperforms existing state-of-the-art algorithms significantly on most benchmarks.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '16) |
| Publisher | Association for Computing Machinery |
| Publication date | 2016 |
| Pages | 662-671 |
| ISBN (Print) | 978-1-4503-4391-6 |
| DOIs | |
| Publication status | Published - 2016 |
| Event | 31st Annual ACM/IEEE Symposium on Logic in Computer Science - New York, United States Duration: 5 Jul 2016 → 8 Jul 2016 Conference number: 31 https://ieeexplore.ieee.org/xpl/conhome/8508870/proceeding http://lics.rwth-aachen.de/lics16/ |
Conference
| Conference | 31st Annual ACM/IEEE Symposium on Logic in Computer Science |
|---|---|
| Number | 31 |
| Country/Territory | United States |
| City | New York |
| Period | 05/07/2016 → 08/07/2016 |
| Sponsor | Association for Computing Machinery, European Association for Computer Science Logic, IEEE |
| Internet address |
Keywords
- Parity Games
- Winning Cores
- Algorithms
- Computational Complexity