Zielonka's Recursive Algorithm: dull, weak and solitaire games and tighter bounds
Dull, weak and nested solitaire games are important classes of parity games, capturing, among others, alternation-free mu-calculus and ECTL* model checking problems. These classes can be solved in polynomial time using dedicated algorithms. We investigate the complexity of Zielonka's Recursive...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2013-07-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1307.4465v1 |
| _version_ | 1818695937136001024 |
|---|---|
| author | Maciej Gazda Tim A.C. Willemse |
| author_facet | Maciej Gazda Tim A.C. Willemse |
| author_sort | Maciej Gazda |
| collection | DOAJ |
| description | Dull, weak and nested solitaire games are important classes of parity games, capturing, among others, alternation-free mu-calculus and ECTL* model checking problems. These classes can be solved in polynomial time using dedicated algorithms. We investigate the complexity of Zielonka's Recursive algorithm for solving these special games, showing that the algorithm runs in O(d (n + m)) on weak games, and, somewhat surprisingly, that it requires exponential time to solve dull games and (nested) solitaire games. For the latter classes, we provide a family of games G, allowing us to establish a lower bound of 2^(n/3). We show that an optimisation of Zielonka's algorithm permits solving games from all three classes in polynomial time. Moreover, we show that there is a family of (non-special) games M that permits us to establish a lower bound of 2^(n/3), improving on the previous lower bound for the algorithm. |
| first_indexed | 2024-12-17T13:53:24Z |
| format | Article |
| id | doaj.art-c1788b3b7e8c44a1ac154fc735e2c8a4 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-17T13:53:24Z |
| publishDate | 2013-07-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-c1788b3b7e8c44a1ac154fc735e2c8a42022-12-21T21:45:59ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802013-07-01119Proc. GandALF 201372010.4204/EPTCS.119.4Zielonka's Recursive Algorithm: dull, weak and solitaire games and tighter boundsMaciej GazdaTim A.C. WillemseDull, weak and nested solitaire games are important classes of parity games, capturing, among others, alternation-free mu-calculus and ECTL* model checking problems. These classes can be solved in polynomial time using dedicated algorithms. We investigate the complexity of Zielonka's Recursive algorithm for solving these special games, showing that the algorithm runs in O(d (n + m)) on weak games, and, somewhat surprisingly, that it requires exponential time to solve dull games and (nested) solitaire games. For the latter classes, we provide a family of games G, allowing us to establish a lower bound of 2^(n/3). We show that an optimisation of Zielonka's algorithm permits solving games from all three classes in polynomial time. Moreover, we show that there is a family of (non-special) games M that permits us to establish a lower bound of 2^(n/3), improving on the previous lower bound for the algorithm.http://arxiv.org/pdf/1307.4465v1 |
| spellingShingle | Maciej Gazda Tim A.C. Willemse Zielonka's Recursive Algorithm: dull, weak and solitaire games and tighter bounds Electronic Proceedings in Theoretical Computer Science |
| title | Zielonka's Recursive Algorithm: dull, weak and solitaire games and tighter bounds |
| title_full | Zielonka's Recursive Algorithm: dull, weak and solitaire games and tighter bounds |
| title_fullStr | Zielonka's Recursive Algorithm: dull, weak and solitaire games and tighter bounds |
| title_full_unstemmed | Zielonka's Recursive Algorithm: dull, weak and solitaire games and tighter bounds |
| title_short | Zielonka's Recursive Algorithm: dull, weak and solitaire games and tighter bounds |
| title_sort | zielonka s recursive algorithm dull weak and solitaire games and tighter bounds |
| url | http://arxiv.org/pdf/1307.4465v1 |
| work_keys_str_mv | AT maciejgazda zielonkasrecursivealgorithmdullweakandsolitairegamesandtighterbounds AT timacwillemse zielonkasrecursivealgorithmdullweakandsolitairegamesandtighterbounds |