English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The McNaughton-Zielonka divide et impera algorithm is the simplest and mostflexible approach available in the literature for determining the winner in aparity game. Despite its theoretical worst-case complexity and the negativereputation as a poorly effective algorithm in practice, it has been shown torank among the best techniques for the solution of such games. Also, it provedto be resistant to a lower bound attack, even more than the strategyimprovements approaches, and only recently a family of games on which thealgorithm requires exponential time has been provided by Friedmann. An easyanalysis of this family shows that a simple memoization technique can help thealgorithm solve the family in polynomial time. The same result can also beachieved by exploiting an approach based on the dominion-decompositiontechniques proposed in the literature. These observations raise the questionwhether a suitable combination of dynamic programming and game-decompositiontechniques can improve on the exponential worst case of the original algorithm.In this paper we answer this question negatively, by providing a robustlyexponential worst case, showing that no intertwining of the above mentionedtechniques can help mitigating the exponential nature of the divide et imperaapproaches.

Robust Exponential Worst Cases for Divide-et-Impera Algorithms for Parity Games