Tom Van Dijk

Tom Van Dijk

orcid

Research Focus & Metrics

Academic Career Length

14Years (2013-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 January 2015
Verified
Book Chapter
Closed access
PDF file
GKGijs Kant
Gijs Kant
ALAlfons Laarman
Alfons Laarman
JMJeroen Meijer
Jeroen Meijer
JPJaco van de Pol
Jaco van de Pol
SBStefan Blom
Stefan Blom
TDTom Van Dijk
Tom Van Dijk

19 October 2016 in International Journal on Software Tools for Technology Transfer
Verified
Journal Article
Open access
PDF file
TDTom Van Dijk
Tom Van Dijk
JPJaco van de Pol
Jaco van de Pol
Decision diagrams, such as binary decision diagrams, multi-terminal binary decision diagrams and multi-valued decision diagrams, play an important role in various fields. They are especially useful to represent the characteristic function of sets of states and transitions in symbolic model checking. Most implementations of decision diagrams do not parallelize the decision diagram operations. As performance gains in the current era now mostly come from parallel processing, an ongoing challenge is to develop datastructures and algorithms for modern multi-core architectures. The decision diagram package Sylvan provides a contribution by implementing parallelized decision diagram operations and thus allowing sequential algorithms that use decision diagrams to exploit the power of multi-core machines. This paper discusses the design and implementation of Sylvan, especially an improvement to the lock-free unique table that uses bit arrays, the concurrent operation cache and the implementation of parallel garbage collection. We extend Sylvan with multi-terminal binary decision diagrams for integers, real numbers and rational numbers. This extension also allows for custom MTBDD leaves and operations and we provide an example implementation of GMP rational numbers. Furthermore, we show how the provided framework can be integrated in existing tools to provide out-of-the-box parallel BDD algorithms, as well as support for the parallelization of higher-level algorithms. As a case study, we parallelize on-the-fly symbolic reachability in the model checking toolset LTSmin. We experimentally demonstrate that the parallelization of symbolic model checking for explicit-state modeling languages, as supported by LTSmin, scales well. We also show that improvements in the design of the unique table result in faster execution of on-the-fly symbolic reachability.

12 April 2018
Verified
Book Chapter
Open access
PDF file
TDTom Van Dijk
Tom Van Dijk
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 interesting from the theory perspective, as they are widely believed to admit a polynomial solution, but so far no such algorithm is known. In recent years, a number of new algorithms and improvements to existing algorithms have been proposed. We implement a new and easy to extend tool Oink, which is a high-performance implementation of modern parity game algorithms. We further present a comprehensive empirical evaluation of modern parity game algorithms and solvers, both on real world benchmarks and randomly generated games. Our experiments show that our new tool Oink outperforms the current state-of-the-art.

1 January 2014
Verified
Book Chapter
Closed access
PDF file
TDTom Van Dijk
Tom Van Dijk
JPJaco C. van de Pol
Jaco C. van de Pol

1 January 2015
Verified
Book Chapter
Closed access
PDF file
TDTom Van Dijk
Tom Van Dijk
JPJaco van de Pol
Jaco van de Pol

1 October 2017
Verified
Conference Paper
Closed access
ABArmin Biere
Armin Biere
TDTom Van Dijk
Tom Van Dijk
KHKeijo Heljanko
Keijo Heljanko