Abstract Parity games can be used to represent many different kinds of decision problems. In practice, tools that use parity games often rely on a specification in a higher-order logic from which the actual game can be obtained by means of an exploration. For many of these decision problems we are only interested in the solution for a designated vertex in the game. We formalise how to use on-the-fly solving techniques during the exploration process, and show that this can help to decide the winner of such a designated vertex in an incomplete game. Furthermore, we define partial solving techniques for incomplete parity games and show how these can be made resilient to work directly on the incomplete game, rather than on a set of safe vertices. We implement our techniques for symbolic parity games and study their effectiveness in practice, showing that speed-ups of several orders of magnitude are feasible and overhead (if unavoidable) is typically low.

Abstract In model checking, reduction techniques can be helpful tools to fight the state-space explosion problem. Partial-order reduction (POR) is a well-known example, and many POR variants have been developed over the years. However, none of these can be used in the context of model checking stutter-sensitive temporal properties. We propose POR techniques for parity games, a well-established formalism for solving a variety of decision problems, including model checking. As a result, we obtain the first POR method that is sound for the full modal $$\upmu $$ μ -calculus. We show how our technique can be applied to the fixed point logic called parameterised Boolean equation systems, which provides a high-level representation of parity games. Experiments with our implementation indicate that substantial reductions can be achieved.

Abstract Partial-order reduction (POR) is a well-established technique to combat the problem of state-space explosion. We propose POR techniques that are sound for parity games, a well-established formalism for solving a variety of decision problems. As a consequence, we obtain the first POR method that is sound for model checking for the full modal $$\mu $$ -calculus. Our technique is applied to, and implemented for the fixed point logic called parameterised Boolean equation systems, which provides a high-level representation of parity games. Experiments indicate that substantial reductions can be achieved.

Reasoning about the correctness of parallel and distributed systems requires automated tools. By now, the mCRL2 toolset and language have been developed over a course of more than fifteen years. In this paper, we report on the progress and advancements over the past six years. Firstly, the mCRL2 language has been extended to support the modelling of probabilistic behaviour. Furthermore, the usability has been improved with the addition of refinement checking, counterexample generation and a user-friendly GUI. Finally, several performance improvements have been made in the treatment of behavioural equivalences. Besides the changes to the toolset itself, we cover recent applications of mCRL2 in software product line engineering and the use of domain specific languages (DSLs).

We present a theory of abstraction for the framework of parameterised Boolean equation systems, a first-order fixpoint logic. Parameterised Boolean equation systems can be used to solve a variety of problems in verification. We study the capabilities of the abstraction theory by comparing it to an abstraction theory for Generalised Kripke modal Transition Systems (GTSs). We show that for model checking the modal μ-calculus, our abstractions can be exponentially more succinct than GTSs and our theory is as complete as the GTS framework for abstraction. Furthermore, we investigate the completeness of our theory irrespective of the encoded decision problem. We illustrate the potential of our theory through case studies using the first-order modal μ-calculus and a real-time extension thereof, conducted using a prototype implementation of a new syntactic transformation for parameterised Boolean equation systems.

Abstract This paper presents practices and experiences in developing the formal methods toolset mCRL2. Findings are presented based on years of experiences in developing tools in an academic environment. Practical problems and ways to solve them are discussed. We also present the direction that we foresee for the coming years of development in formal methods tool support. Copyright © 2010 John Wiley & Sons, Ltd.

This paper reports on two experiments with a Talking Head that explore the ability of eyebrow movements to cue focus. The first experiment tests how listeners react to synthetic stimuli in which the eyebrow movements coincide with pitch accents versus those in which these two occur on different words. Results show that subjects prefer those utterances in which pitch and eyebrow movements are aligned on the same word. The second experiment investigates whether listeners are sensitive to eyebrow movements when they have to rate the prominence of particular words in audiovisual stimuli. This experiment shows that eyebrow movements both boost the perceived prominence of words that also receive a pitch accent, and downscale the prominence of unaccented words in the immediate context of the accented word. 1.

Abstract When modeling spline surfaces of complex shape, one has to deal with an overwhelming number of control points. Modeling by direct manipulation of the control points is a tedious task. In particular, it is very difficult to maintain a generally pleasant looking surface shape. It becomes therefore increasingly important to build tools that allow the designer to specify only a few geometric constraints while automatically determining the explicit representation of the surface. The basic concept of such a tool is simple. In a first step one has to somehow measure the “fairness” (=quality) of a surface. Once this is achieved, an optimization process selects the one surface with optimal fairness from all surfaces satisfying the user specified geometric constraints. To measure the fairness, thin plate energy functionals are a good choice. However, for interactive use these functionals are far too complex. W e will present appropriate approximations to these functionals that allow an optimization nearly in real time. Thefunctionals are obtained by introducing reference surfaces thus leading to data dependent, quadratic approximations to the exact thin plate energy functionals. We apply the method to interactive surface manipulations based on energy constraints.

Abstract Modeling a curve through minimizing its energy yields an overall smooth curve. A common way to model shape features is to perform the minimization subject to a number of interpolation constraints. This way of modeling is attractive because the designer is not bothered with the precise representation of the curve (e.g. control points). However, local shape specification by means of interpolation constraints is very limited. On the other hand, local deformation by repositioning control points is powerful but very laborious, and destroys the minimal energy property. In this paper, deform operators are introduced for 3D curve modeling that have built‐in energy terms that have an intuitive effect. These operators allow local shape modification and do justice to the energy minimization way of modeling.