Author name cluster

Tom van Dijk

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

CSL Conference 2024 Conference Paper

The Worst-Case Complexity of Symmetric Strategy Improvement

Tom van Dijk
Georg Loho
Matthew T. Maat

Symmetric strategy improvement is an algorithm introduced by Schewe et al. (ICALP 2015) that can be used to solve two-player games on directed graphs such as parity games and mean payoff games. In contrast to the usual well-known strategy improvement algorithm, it iterates over strategies of both players simultaneously. The symmetric version solves the known worst-case examples for strategy improvement quickly, however its worst-case complexity remained open. We present a class of worst-case examples for symmetric strategy improvement on which this symmetric version also takes exponentially many steps. Remarkably, our examples exhibit this behaviour for any choice of improvement rule, which is in contrast to classical strategy improvement where hard instances are usually hand-crafted for a specific improvement rule. We present a generalized version of symmetric strategy iteration depending less rigidly on the interplay of the strategies of both players. However, it turns out it has the same shortcomings.

Details

GandALF Workshop 2020 Workshop Paper

Symbolic Parity Game Solvers that Yield Winning Strategies

Oebele Lijzenga
Tom van Dijk

Parity games play an important role for LTL synthesis as evidenced by recent breakthroughs on LTL synthesis, which rely in part on parity game solving. Yet state space explosion remains a major issue if we want to scale to larger systems or specifications. In order to combat this problem, we need to investigate symbolic methods such as BDDs, which have been successful in the past to tackle exponentially large systems. It is therefore essential to have symbolic parity game solving algorithms, operating using BDDs, that are fast and that can produce the winning strategies used to synthesize the controller in LTL synthesis. Current symbolic parity game solving algorithms do not yield winning strategies. We now propose two symbolic algorithms that yield winning strategies, based on two recently proposed fixpoint algorithms. We implement the algorithms and empirically evaluate them using benchmarks obtained from SYNTCOMP 2020. Our conclusion is that the algorithms are competitive with or faster than an earlier symbolic implementation of Zielonka's recursive algorithm, while also providing the winning strategies.

PDF Details DOI

GandALF Workshop 2019 Workshop Paper

A Parity Game Tale of Two Counters

Tom van Dijk

Parity games are simple infinite games played on finite graphs with a winning condition that is expressive enough to capture nested least and greatest fixpoints. Through their tight relationship to the modal mu-calculus, they are used in practice for the model-checking and synthesis problems of the mu-calculus and related temporal logics like LTL and CTL. Solving parity games is a compelling complexity theoretic problem, as the problem lies in the intersection of UP and co-UP and is believed to admit a polynomial-time solution, motivating researchers to either find such a solution or to find superpolynomial lower bounds for existing algorithms to improve the understanding of parity games. We present a parameterized parity game called the Two Counters game, which provides an exponential lower bound for a wide range of attractor-based parity game solving algorithms. We are the first to provide an exponential lower bound to priority promotion with the delayed promotion policy, and the first to provide such a lower bound to tangle learning.

PDF Details DOI

GandALF Workshop 2019 Workshop Paper

Simple Fixpoint Iteration To Solve Parity Games

Tom van Dijk
Bob Rubbens

A naive way to solve the model-checking problem of the mu-calculus uses fixpoint iteration. Traditionally however mu-calculus model-checking is solved by a reduction in linear time to a parity game, which is then solved using one of the many algorithms for parity games. We now consider a method of solving parity games by means of a naive fixpoint iteration. Several fixpoint algorithms for parity games have been proposed in the literature. In this work, we introduce an algorithm that relies on the notion of a distraction. The idea is that this offers a novel perspective for understanding parity games. We then show that this algorithm is in fact identical to two earlier published fixpoint algorithms for parity games and thus that these earlier algorithms are the same. Furthermore, we modify our algorithm to only partially recompute deeper fixpoints after updating a higher set and show that this modification enables a simple method to obtain winning strategies. We show that the resulting algorithm is simple to implement and offers good performance on practical parity games. We empirically demonstrate this using games derived from model-checking, equivalence checking and reactive synthesis and show that our fixpoint algorithm is the fastest solution for model-checking games.

PDF Details DOI

Highlights Conference 2018 Conference Abstract

Solving parity games with tangles

Tom van Dijk

ABSTRACT. Parity games are well known for their applications in formal verification and synthesis, especially to solve both the model-checking and synthesis problems of the modal mu-calculus and related logics like LTL. We have published two novel contributions to this field in the past year and are working on a third. This presentation is based on publications at TACAS'2018 and CAV'2018 containing the following contributions. Oink is a new implementation of parity game solvers much like the well known PGSolver, but it has a much improved practical performance and we use Oink to perform a new modern comparison of parity game solvers. The tool is designed for easy integration with other toolchains and for easy replication of research results. We propose a new algorithm to solve parity games called tangle learning. The idea is that all algorithms for parity games explore so-called "tangles" in the parity game and they often repeat exploring the same tangle again and again, which can lead to exponential runtimes. The insight ("highlight") of the tangle learning algorithm is that these tangles can be combined with the attractor computation and then we can use this with a memoization strategy ("learning") to never explore the same tangle twice. The tangles are very much related to another concept called "distractions" that we're currently developing further, and we can show that the interaction of tangles and distractions drives parity game difficulty.

Details