Event Category: Colloquium

Since 2013, the leading SAT solvers in the SAT competition all use inprocessing, which unlike preprocessing, interleaves search with simplifications. However, applying inprocessing frequently can still be a bottle neck, i.e., for hard or large formulas. In this work, we introduce the first attempt to parallelize inprocessing on GPU architectures. As memory is a scarce …continue reading

A question haunting me for a while is whether the O(m log n) algorithm for strong bisimulation is optimal. We found a family of graphs that shows that any  reasonable partition refinement algorithm is necessarily Omega(n log n), n being the number of states, steps to calculate strong bisimulation.  This appeared to answer the question. …continue reading

It is known that deciding bisimilarity is a P-complete problem. This means it is thought of as a problem that is inherently sequential and hard to solve in parallel. Despite this fact efforts have been made to construct increasingly efficient parallel algorithms. In a previous colloquium I presented a parallel algorithm that decides bisimilarity in …continue reading

The notion of refinement plays an important role in software engineering. It is the basis of a stepwise development methodology in which the correctness of a system can be established by proving, or computing, that a system refines its specification. There are many refinement relations described in the literature. Fair testing is the coarsest liveness-preserving …continue reading

Model-driven system engineering is a practice also employed in the design of controllers for cyber-physical systems. The method allows controllers to be modelled and verified before they are implemented in software, allowing potential glitches and design flaws to be uncovered, before they emerge in the time and resource intensive testing phase. Some of the modelling …continue reading

Reconfigurability is a concept that appeared recently in several areas including manufacturing, aerospace, medical, robotic, and telecommunication systems. This concept provides systems with an aspect of flexibility allowing them to easily adapt with their external environment during their working process. Reconfiguration provides many advantages to various existing systems. However, by adopting such aspect, some issues …continue reading