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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We address the problem of solving parity games with imperfect information onfinite graphs of bounded structural complexity. It is a major open problemwhether parity games with perfect information can be solved in PTIME.Restricting the structural complexity of the game arenas, however, often leadsto efficient algorithms for parity games. Such results are known for graphclasses of bounded tree-width, DAG-width, directed path-width, andentanglement, which we describe in terms of cops and robber games. Conversely,the introduction of imperfect information makes the problem more difficult, itbecomes EXPTIME-hard. We analyse the interaction of both approaches.  We use a simple method to measure the amount of "unawareness"' of a player,the amount of imperfect information. It turns out that if it is unbounded, lowstructural complexity does not make the problem simpler. It remainsEXPTIME-hard or PSPACE-hard even on very simple graphs.  For games with bounded imperfect information we analyse the powersetconstruction, which is commonly used to convert a game of imperfect informationinto an equivalent game with perfect information. This construction preservesboundedness of directed path-width and DAG-width, but not of entanglement or oftree-width. Hence, if directed path-width or DAG-width are bounded, paritygames with bounded imperfect information can be solved in PTIME. For DAG-widthwe follow two approaches. One leads to a generalization of the known fact thatperfect information parity games are in PTIME if DAG-width is bounded. We provethis theorem for non-monotone DAG-width. The other approach introduces a copsand robbers game (with multiple robbers) on directed graphs, consideredRicherby and Thilikos forundirected graphs. We show a tight linear bound forthe number of additional cops needed to capture an additional robber.

Parity Games, Imperfect Information and Structural Complexity