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 provide an algorithm to solve Rabin and Streett games over graphs with $n$vertices, $m$ edges, and $k$ colours that runs in$\tilde{O}\left(mn(k!)^{1+o(1)} \right)$ time and $O(nk\log k \log n)$ space,where $\tilde{O}$ hides poly-logarithmic factors. Our algorithm is animprovement by a super quadratic dependence on $k!$ from the currently bestknown run time of $O\left(mn^2(k!)^{2+o(1)}\right)$, obtained by converting aRabin game into a parity game, while simultaneously improving its exponentialspace requirement.  Our main technical ingredient is a characterisation of progress measures forRabin games using \emph{colourful trees} and a combinatorial construction ofsuccinctly-represented, universal colourful trees. Colourful universal treesare generalisations of universal trees used by Jurdzi\'{n}ski and Lazi\'{c}(2017) to solve parity games, as well as of Rabin progress measures of Klarlundand Kozen (1991). Our algorithm for Rabin games is a progress measure liftingalgorithm where the lifting is performed on succinct, colourful, universaltrees.

Rabin Games and Colourful Universal Trees