Deciding parity games in quasipolynomial time
It is shown that the parity game can be solved in quasipolynomial time. The parameterised
parity game-with n nodes and m distinct values (aka colours or priorities)-is proven to be in …
parity game-with n nodes and m distinct values (aka colours or priorities)-is proven to be in …
Sampling-based motion planning with deterministic μ-calculus specifications
S Karaman, E Frazzoli - … of the 48h IEEE Conference on …, 2009 - ieeexplore.ieee.org
In this paper, we propose algorithms for the on-line computation of control programs for
dynamical systems that provably satisfy a class of temporal logic specifications. Such …
dynamical systems that provably satisfy a class of temporal logic specifications. Such …
The mu-calculus and Model Checking
J Bradfield, I Walukiewicz - Handbook of Model Checking, 2018 - Springer
This chapter presents that part of the theory of the μ μ-calculus that is relevant to the model-
checking problem as broadly understood. The μ μ-calculus is one of the most important …
checking problem as broadly understood. The μ μ-calculus is one of the most important …
Oink: An implementation and evaluation of modern parity game solvers
T van Dijk - International Conference on Tools and Algorithms for …, 2018 - Springer
Parity games have important practical applications in formal verification and synthesis,
especially to solve the model-checking problem of the modal mu-calculus. They are also …
especially to solve the model-checking problem of the modal mu-calculus. They are also …
DAG-width and parity games
Tree-width is a well-known metric on undirected graphs that measures how tree-like a graph
is and gives a notion of graph decomposition that proves useful in algorithm development …
is and gives a notion of graph decomposition that proves useful in algorithm development …
The dag-width of directed graphs
Tree-width is a well-known metric on undirected graphs that measures how tree-like a graph
is and gives a notion of graph decomposition that proves useful in algorithm design. Tree …
is and gives a notion of graph decomposition that proves useful in algorithm design. Tree …
A recursive approach to solving parity games in quasipolynomial time
Zielonka's classic recursive algorithm for solving parity games is perhaps the simplest
among the many existing parity game algorithms. However, its complexity is exponential …
among the many existing parity game algorithms. However, its complexity is exponential …
The complexity of solving stochastic games on graphs
D Andersson, PB Miltersen - International Symposium on Algorithms and …, 2009 - Springer
We consider some well-known families of two-player zero-sum perfect-information stochastic
games played on finite directed graphs. The families include stochastic parity games …
games played on finite directed graphs. The families include stochastic parity games …
Parity games: Zielonka's algorithm in quasi-polynomial time
P Parys - arXiv preprint arXiv:1904.12446, 2019 - arxiv.org
Calude, Jain, Khoussainov, Li, and Stephan (2017) proposed a quasi-polynomial-time
algorithm solving parity games. After this breakthrough result, a few other quasi-polynomial …
algorithm solving parity games. After this breakthrough result, a few other quasi-polynomial …
A higher order modal fixed point logic
M Viswanathan, R Viswanathan - International Conference on …, 2004 - Springer
We present a higher order modal fixed point logic (HFL) that extends the modal μ-calculus to
allow predicates on states (sets of states) to be specified using recursively defined higher …
allow predicates on states (sets of states) to be specified using recursively defined higher …