I am an assistant professor at the Formal Methods and Tools group at the University of Twente.
My research is connected to formal verification and synthesis, including the efficient solving of parity games, using binary decision diagrams in formal methods and SAT/SMT solving with multi-core parallelism. I like making and improving usable research tools.
My PhD thesis was on parallelizing decision diagram algorithms.
I implemented the Sylvan multi-core decision diagram package, which supports binary decision diagrams and multi-way (list) decision diagrams with custom leaves (booleans, integers, rational functions, etc), that is, binary and multi-way algebraic decision diagrams.
The package is used in several applications, including the model checkers LTSmin, Storm and IscasMC, as well as the symbolic bisimulation minimisation tool SigrefMC.
After my PhD, I worked as a Postdoc in the Formal Models and Verification group of Armin Biere, where I mostly studied parity games.
I implemented the Oink parity game solver as a platform for studying different parity game algorithms and with the additional objective of practical performance. Oink is now the state-of-the-art in practical parity game solving. I also implemented the synthesis tool Knor for the SYNTCOMP competition, which accepts as input a parity automaton in the HOA specification language, and constructs as output a Mealy controller as an and-inverter-graph in the AIGER format.
I continue designing algorithms that solve parity games. Hopefully one of these runs in polynomial time. My algorithms mostly use the tangle attractor to partition a parity game and its subgames into smaller regions, learning new tangles until winning regions are found.
My Research Tools
Sylvan – A multi-core implementation of decision diagrams.
Lace – Work-stealing framework in C, similar to Cilk.
SigrefMC – Symbolic bisimulation minimisation for LTS, CTMC and IMC systems.
Oink – Library/implementation of various parity game algorithms.
Knor - Reactive controller synthesis from parity automaton (HOA format) to controller (AIGER format).
Students (BSc, MSc, etc) are welcome to study questions about parity games, binary decision diagrams, and related topics.
I have a number of open questions and assignments available.
BSc Design projects
Design projects are for students who work in a group to design a piece of software, i.e., Module 11 TCS students.
A graphical user interface for parity games
The primary objective is to understand and develop parity game algorithms.
The GUI should let a user create, load and change parity games.
The GUI should offer various tools to manipulate vertices of the game and to change the layout.
Ideally, a GUI should allow pattern-based generation of parity games.
The GUI should support viewing step-by-step execution of different parity game algorithms.
BSc/MSc Research topics
Topics on parity games:
Can you efficiently derive a strategy for the winning player in the fixpoint algorithm?
Can you do it using binary decision diagrams? Now solved, see this 2019 paper with Bob Rubbens and this 2020 paper with Oebele Lijzenga.
Can you implement Lehtinen’s register games solver without constructing the intermediary safety game? See her 2018 paper. First implement the safety game construction of the paper and use it to solve parity games; can we find an algorithm that solves the safety game on-the-fly without constructing it explicitly?
How can we solve parity games and obtain small strategies? For example using incremental parity game solving techniques, starting with the vertices that correspond to the initial state of the input game. Current algorithms implemented in Oink are very fast but may also result in very large strategies, ultimately resulting in large controllers rather than small controllers.
Find a parity game family that runs in exponential time for two-player distraction-free tangle learning. The idea is that two-player distraction-free tangle learning probably requires exponential time, but I do not yet have an example parity game family for this.
Can we find ordered trees in parity game solvers that use tangle attractors?
On using binary decision diagrams to solve parity games symbolically:
Can you implement the “tangle learning” algorithm using binary decision diagrams? The challenge is to find a good way to encode tangles using binary decision diagrams.
On proving properties using a theory prover (like Isabelle):
Can you prove that the “priority promotion” algorithm is correct?
Can you prove that the “tangle learning” algorithm is correct?
Can you prove that the “Two Counters” parameterised parity game is exponential for several parity game algorithms?
Can you prove that the work stealing deque in Lace is correct?
Related to parity games are questions like:
How do tangles arise the translation of LTL synthesis/model-checking to Parity Games? And how do distractions / nested structures of tangles and distractions arise in these applications? The idea here is to investigate encodings from LTL synthesis to parity games, and to investigate how tangles in the parity game correspond with features of the encoding.
How to use tangle attractors for energy parity games and for mean payoff games? This topic is quite open. Energy parity games and mean payoff games are related to parity games; the idea is to investigate whether the tangle learning idea can be reused for these related games.
What is the effect of different LTL-to-PG constructions on the size of the final constructed controller?
Can you solve Rabin games using attractors and tangles? Rabin games are an alternative to parity games for applications such as LTL synthesis.
Related to my research on binary decision diagrams (my Sylvan package):
How to implement and tune parallel dynamic variable reordering for BDDs in Sylvan?
Try new hash tables like F14 in Sylvan. Since my research on this in 2012-2016, there are probably faster hash tables. Sylvan uses a custom hash table based on linear probing, and there is a variant using chaining. For the evaluation, most important is the parallel performance of the hash table.
Using a hash table per variable level instead of a single hash table for everything in Sylvan.
Apply parallel dynamic variable reordering in Sylvan to fault trees. One of the applications of BDDs is the analysis of fault trees. Finding a good variable order is a challenge, and dynamic variable reordering using sifting is one of the solutions. We have an implementation in Sylvan, but need to apply it to fault trees.
Related to parallel programming, that is, load balancing by work stealing (my Lace framework):
How do the load balancing frameworks Lace, Cilk, OpenMP and Intel TBB compare? While there are already some benchmarks, what lacks is a comprehensive benchmark suite that compares Lace to Cilk and OpenMP and Intel TBB or similar technologies.
Porting Lace to Rust/C++/Java. Lace works very well and with very little overhead in C. How well does it work using other programming languages?
I am open for collaboration on topics related to parity games, LTL synthesis and binary decision diagrams. If you want to use Sylvan for something that is not currently supported, feel free to contact me.
Journal Reviewer: IEEE Transactions on Computers (2014), Formal Methods in System Design (2018), Software Tools for Technology Transfer (2018, 2019), MDPI Algorithms (2018), VLSI Integration (2018), JSAT (2019), JAR (2019).
Formal Methods and Tools
University of Twente
E-mail: t dot vandijk at utwente dot nl.