We present a new O(mlog n) algorithm to calculate branching bisimulation equivalence, which is the finest commonly used behavioural equivalence on labelled transition systems that takes the internal action τ into account. This algorithm combines the simpler data structure of an earlier algorithm for Kripke structures (without action labels) with the memory-efficiency of a later algorithm partitioning sets of labelled transitions. It employs a particularly elegant four-way split of blocks of states, which refines a block under two splitters and isolates all new bottom states, simultaneously. Benchmark results show that this new algorithm outperforms the best known algorithm for branching bisimulation both in time and space.

Slot machines can have fairly complex behaviour. Determining theRTP(return to player) can be involved, especially when a player has an influence on the course of the game. In this paper we present a formal model of the behaviour of slot machines and use the model to rigorously and fully automatically compute the RTP. We model the slot machines using probabilistic process specifications where the intervention of players is modelled using non-determinism. The RTP is formulated in quantitative modal logics which can be evaluated fully automatically on the behavioural specifications of these slot machines. We apply the method on an actual slot machine provided by the company Errèl Industries B.V. The most useful contribution of this paper is that we show how to describe the behaviour of slot machines both concisely and unequivocally. Using quantitative modal logics there is an extra bonus, as we can quite easily provide valuable insights by, among others, computing the exact RTP and obtaining the optimal player strategies.

Nowadays, the main advances in computational power are due to parallelism. However, most parallel languages have been designed with a focus on processors and threads. This makes dealing with data and memory in programs hard, which distances the implementation from its original algorithm. We propose a new paradigm for parallel programming, the data-autonomous paradigm, where computation is performed by autonomous data elements. Programs in this paradigm are focused on making the data collaborate in a highly parallel fashion. We furthermore present AuDaLa, the first data autonomous programming language, and provide a full formalisation that includes a type system and operational semantics. Programming in AuDaLais very natural, as illustrated by examples, albeit in a style very different from sequential and contemporary parallel programming. Additionally, it lends itself for the formal verification of parallel programs, which we demonstrate.

Abstract To stimulate the development and application of formal methods in industry, we need to promote research and development for the improvement of formal methods and tools for industrial applications, and we need to exchange experiences of the industrial usage of these methods and tools. This special issue of Software Tools for Technology Transfer presents various tools and experience reports that are targeting the use of formal methods in industry. The papers in this special issue are extended versions of selected conference papers from the proceedings of the 27th International Conference on Formal Methods for Industrial Critical Systems (FMICS 2022).

We study the problem of computing minimal distinguishing formulas for non-bisimilar states in finite LTSs. We show that this is NP-hard if the size of the formula must be minimal. Similarly, the existence of a short distinguishing trace is NP-complete. However, we can provide polynomial algorithms, if minimality is formulated as the minimal number of nested modalities, and it can even be extended by recursively requiring a minimal number of nested negations. A prototype implementation shows that the generated formulas are much smaller than those generated by the method introduced by Cleaveland.

We introduce the notion of a Real Equation System (RES), which lifts Boolean Equation Systems (BESs) to the domain of extended real numbers. Our RESs allow arbitrary nesting of least and greatest fixed-point operators. We show that each RES can be rewritten into an equivalent RES in normal form. These normal forms provide the basis for a complete procedure to solve RESs. This employs the elimination of the fixed-point variable at the left side of an equation from its right-hand side, combined with a technique often referred to as Gauß-elimination. We illustrate how this framework can be used to verify quantitative modal formulas with alternating fixed-point operators interpreted over probabilistic labelled transition systems.

Abstract Active automata learning has been a successful technique to learn the behaviour of state-based systems by interacting with them through queries. In this paper, we develop a compositional algorithm for active automata learning in which systems comprising interleaving parallel components are learned compositionally. Our algorithm automatically learns the structure of systems while learning the behaviour of the components. We prove that our approach is sound and that it learns a maximal set of interleaving parallel components. We empirically evaluate the effectiveness of our approach and show that our approach requires significantly fewer numbers of input symbols and resets while learning systems. Our empirical evaluation is based on a large number of subject systems obtained from a case study in the automotive domain.

We provide time lower bounds for sequential and parallel algorithms deciding bisimulation on labeled transition systems that use partition refinement. For sequential algorithms this is $\Omega((m \mkern1mu {+} \mkern1mu n ) \mkern-1mu \log \mkern-1mu n)$ and for parallel algorithms this is $\Omega(n)$, where $n$ is the number of states and $m$ is the number of transitions. The lowerbounds are obtained by analysing families of deterministic transition systems, ultimately with two actions in the sequential case, and one action for parallel algorithms. For deterministic transition systems with one action, bisimilarity can be decided sequentially with fundamentally different techniques than partition refinement. In particular, Paige, Tarjan, and Bonic give a linear algorithm for this specific situation. We show, exploiting the concept of an oracle, that this approach is not of help to develop a faster generic algorithm for deciding bisimilarity. For parallel algorithms there is a similar situation where these techniques may be applied, too.

This article presents a way to implement many-sorted term rewriting on a GPU. This is done by letting the GPU repeatedly perform a massively parallel evaluation of all subterms. Innermost many-sorted term rewriting is experimentally compared with a relaxed form of innermost many-sorted term rewriting, and two different garbage collection mechanisms, to remove terms that are no longer needed, are discussed and experimentally compared. It is concluded that when the many-sorted term rewrite systems exhibit sufficient internal parallelism, GPU rewriting substantially outperforms the CPU. Both relaxed innermost many-sorted rewriting and garbage collection further improve this performance. Since the implementation can probably be even further optimised, and because in any case GPUs will become much more powerful in the future, this suggests that GPUs are an interesting platform for (many-sorted) term rewriting. As term rewriting can be viewed as a universal programming language, this also opens a route towards programming GPUs by term rewriting, especially for irregular computations.

Abstract We present the first parallel algorithms that decide strong and branching bisimilarity in linear time. More precisely, if a transition system has n states, m transitions and $$\vert Act \vert $$ | A c t | action labels, we introduce an algorithm that decides strong bisimilarity in $$\mathcal {O}(n+\vert Act \vert )$$ O ( n + | A c t | ) time on $$\max (n,m)$$ max ( n , m ) processors and an algorithm that decides branching bisimilarity in $$\mathcal {O}(n+\vert Act \vert )$$ O ( n + | A c t | ) time using up to $$\max (n^2,m,\vert Act \vert n)$$ max ( n 2 , m , | A c t | n ) processors.

Item does not contain fulltext

An asymptotic lowerbound of Ω((m+n)log n) is established for partition refinement algorithms that decide bisimilarity on labeled transition systems. The lowerbound is obtained by subsequently analysing two families of deterministic transition systems - one with a growing action set and another with a fixed action set. For deterministic transition systems with a one-letter action set, bisimilarity can be decided with fundamentally different techniques than partition refinement. In particular, Paige, Tarjan, and Bonic give a linear algorithm for this specific situation. We show, exploiting the concept of an oracle, that the approach of Paige, Tarjan, and Bonic is not of help to develop a generic algorithm for deciding bisimilarity on labeled transition systems that is faster than the established lowerbound of Ω((m+n)log n).

This article improves the time bound for calculating the weak/branching bisimulation minimisation quotient on state-labelled discrete-time Markov chains from O(m n) to an expected-time O(m log⁴ n), where n is the number of states and m the number of transitions. For these results we assume that the set of state labels AP is small (|AP| ∈ O(m/n log⁴ n)). It follows the ideas of Groote et al. (ACM ToCL 2017) in combination with an efficient algorithm to handle decremental strongly connected components (Bernstein et al., STOC 2019).

Abstract Branching bisimilarity is a behavioural equivalence relation on labelled transition systems (LTSs) that takes internal actions into account. It has the traditional advantage that algorithms for branching bisimilarity are more efficient than ones for other weak behavioural equivalences, especially weak bisimilarity. With m the number of transitions and n the number of states, the classic $${O\left( {m n}\right) }$$ algorithm was recently replaced by an $$O({m (\log \left| { Act }\right| + \log n)})$$ algorithm [9], which is unfortunately rather complex. This paper combines its ideas with the ideas from Valmari [20], resulting in a simpler $$O({m \log n})$$ algorithm. Benchmarks show that in practice this algorithm is also faster and often far more memory efficient than its predecessors, making it the best option for branching bisimulation minimisation and preprocessing for calculating other weak equivalences on LTSs.

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).

Software metrics are widely used to measure the quality of software and to give an early indication of the efficiency of the development process in industry. There are many well-established frameworks for measuring the quality of source code through metrics, but limited attention has been paid to the quality of software models. In this article, we evaluate the quality of state machine models specified using the Analytical Software Design (ASD) tooling. We discuss how we applied a number of metrics to ASD models in an industrial setting and report about results and lessons learned while collecting these metrics. Furthermore, we recommend some quality limits for each metric and validate them on models developed in a number of industrial projects.

We provide a new algorithm to determine stuttering equivalence with time complexity O ( m log n ), where n is the number of states and m is the number of transitions of a Kripke structure. This algorithm can also be used to determine branching bisimulation in O ( m (log | Act | + log n )) time, where Act is the set of actions in a labeled transition system. Theoretically, our algorithm substantially improves upon existing algorithms, which all have time complexity of the form O ( mn ) at best. Moreover, it has better or equal space complexity. Practical results confirm these findings: they show that our algorithm can outperform existing algorithms by several orders of magnitude, especially when the Kripke structures are large. The importance of our algorithm stretches far beyond stuttering equivalence and branching bisimulation. The known O ( mn ) algorithms were already far more efficient (both in space and time) than most other algorithms to determine behavioral equivalences (including weak bisimulation), and therefore they were often used as an essential preprocessing step. This new algorithm makes this use of stuttering equivalence and branching bisimulation even more attractive.

We evaluate the effect of applying the commercial formal technique Analytical Software Design (ASD) to an industrial project. In ASD, interfaces and software designs are modelled using a formal tabular notation. The ASD tool set supports formal checks of these models, such as deadlock freedom and interface compliance. In addition, full code can be generated from design models. ASD has been applied at Philips Healthcare to develop parts of the software of interventional X-ray systems. We report about the experiences with the embedding of ASD into the development processes. The quality of the resulting code and the productivity has been analysed and compared to code developed with other techniques. We observe that the use of ASD leads to a strong reduction of the number of defects and an increase in productivity. The results are also compared to the literature about standards and related projects at other companies.

During the last two decades, we modelled the behaviour of a large number of systems. We noted that different styles of modelling had quite an effect on the size of the state spaces of the modelled systems. The differences were so substantial that some specification styles led to far too many states to verify the correctness of the model, whereas with other styles, the number of states was so small that verification was a straightforward activity. In this article, we summarize our experience by providing seven specification guidelines to keep state spaces small. For each guideline, we provide an application, generally from the realm of traffic light controllers, for which we provide a ‘bad’ model with a large state space, and a ‘good’ model with a small state space. The good and bad models are both suitable for their purpose but are not behaviourally equivalent. For all guidelines, we discuss circumstances under which it is reasonable to apply the guidelines. Copyright © 2014 John Wiley & Sons, Ltd.

This paper reports on the steps to formally specify and verify the behavior of a controller of a power distribution unit (PDU) using the Analytical Software Design (ASD) method. The controller of the underlying PDU mainly controls the distribution of power and network messages to a number of attached PCs and devices of X-ray systems. The behavioral correctness of the controller is critical in order to provide the clinical users the expected behavior of the system. The design of the controller was thoroughly reviewed by team members but, as a result of the behavioral verification using ASD, two previously unrevealed errors were identified within the design of the PDU controller. According to the development team of the PDU the work has had a major benefit of improving the design of the controller and locating errors that would have been hard to find otherwise by traditional testing.

The mCRL2 language is a formal specification language that is used to specify, model, analyze and verify behavioral properties for distributed systems and protocols. The semantics of the mCRL2 language is defined formally using Structural Operational Semantics (SOS). In [32] we propose an approach that takes the SOS of a formal language, along with a concrete model, that serves as an initialization, and transforms it to a Linear Process Specification (LPS). In this paper we extend the approach and show that it can be applied to a formal language that in practice is used to specify and model discussed systems. Hence, we take mCRL2's own operational semantics and transform it into an mCRL2 specification. In essence, this means that we are feeding the mCRL2 toolset its own formal language definition. This semantic dogfooding approach validates the implemented behavior for the mCRL2 language against its formal definition. By performing this exercise we revealed gaps between the defined and implemented semantics. These gaps have subsequently been resolved.

Formal methods are being applied to the development of software of various applications at Philips Healthcare. In particular, the Analytical Software Design (ASD) method is being used as a formal technology for developing defect-free control software of highly sophisticated X-ray equipments. In this paper we analyze the effects of applying ASD to the development of various control software units developed for the X-ray machines. We compare the quality of these units with other units developed in traditional development methods. The results indicate that applying ASD as a formal technology for developing control software could result in fewer defects.

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.

It has been our long time wish to combine the best parts of the real-time verification methods based on timed automata (TA) (the use of regions and zones), and of the process-algebraic approach of languages like LOTOS and timed muCRL. This could provide us with additional verification possibilities for real-time systems, not available in existing timed-automata-based tools like UPPAAL. In this paper we extend the applicability of such discretization to extensions of TA available in UPPAAL as networks of timed automata and shared variables. To this end, we make use of mCRL2, the newer version of muCRL that includes time and multi-actions. The multi-actions are used to model the simultaneous access to shared variables and action synchronization.

We present the first step towards combining the best parts of the real-time verification methods based on timed automata (the use of regions and zones), and of the process-algebraic approach of languages like LOTOS and muCRL. This could provide with additional verification possibilities for real-time systems, not available in existing timed-automata-based tools like UPPAAL. We aim to transfer the successful techniques of regions and zones as used for the analysis of timed automata to the realm of timed muCRL. First, we aim at replacing all parameters of sort time occurring in the resulting process equation by parameters of discrete sorts. To achieve this goal we apply process-algebraic transformations and abstraction techniques to the given process equation. As a result we obtain a process equation that is closely related to the given one in the following sense. If we abstract from the fractional parts of the time stamps in the actions, both of the equations will be timed bisimilar

How do we know if our students are beginning to think like computer scientists? In this study we have defined four levels of abstraction in the thinking of computer science students about the concept of algorithm. We constructed a list of questions about algorithms to measure the answering level as an indication for the thinking level. This list was presented to various groups of Bachelor Computer Science students. The mean answering level increased between successive year groups as well as within year groups during the year, mainly from the second to the third level. Little relation was found between answering levels and test results on algorithm oriented courses. The study was inspired by the tradition of mathematics education research.

Abstract We prove the correctness of a sliding window protocol with an arbitrary finite window size n and sequence numbers modulo 2 n . The correctness consists of showing that the sliding window protocol is branching bisimilar to a queue of capacity 2 n . The proof is given entirely on the basis of an axiomatic theory, and has been checked in the theorem prover PVS.

Abstract. We present an algebraic verification of Segall’s propagation of information with feedback algorithm and we report on the verification of the proof using the PVS system. This algorithm serves as a nice benchmark for verification exercises (see [2, 8, 17]). The verification is based on the methodology presented in [7] and demonstrates its suitability to deliver mechanically verifiable correctness proofs of highly nondeterministic distributed algorithms.

Summary form only given. In multiprogrammed systems, synchronization often turns out to be a performance bottleneck and the source of poor fault-tolerance. Wait-free and lock-free algorithms can do without locking mechanisms, and therefore do not suffer from these problems. We present an efficient almost wait-free algorithm for parallel accessible hashtables, which promises more robust performance and reliability than conventional lock-based implementations. Our solution is as efficient as sequential hashtables. It can easily be implemented using C-like languages and requires on average only constant time for insertion, deletion or accessing of elements. The algorithm allows the hashtables to grow and shrink when needed. A true problem of wait-free and lock-free algorithms is that they are hard to design correctly, even when apparently straightforward. The reason for this is that processes can execute all statements in every conceivable order. Since our algorithm is quite large and rather complex, we turned to the interactive theorem prover PVS to prove safety of our algorithm, which we could not have done reliably by hand. To our knowledge no algorithms of comparable complexity have ever been mechanically verified. Wait-freedom is shown informally.

While studying the specification of the operational semantics of different programming languages and formalisms, one can observe the following three facts. Firstly, Plotkin's style of structured operational semantics (SOS) has become a standard in defining operational semantics. Secondly, congruence with respect to some notion of bisimilarity is an interesting property for such languages and it is essential in reasoning about them. Thirdly, there are numerous languages that contain an explicit data part in the state of the operational semantics. The first two facts have resulted in a line of research exploring syntactic formats of operational rules to derive the desired congruence property for free. However, the third point (in combination with the first two) is not sufficiently addressed and there is no standard congruence format for operational semantics with an explicit data state. In this paper, we address this problem by studying the implications of the presence of a data state on the notion of bisimilarity. Furthermore, we propose a number of formats for congruence.

Formal Aspects of Computing is devoted to the best papers presented at the third ERCIM workshop on Formal Methods for Industrial Critical Systems (FMICS98), held at the CWI in Amsterdam. The FMICS workshops are intended to bring together scientists who are active in the area of formal methods and who are interested in exchanging their experiences in industrial usage of these methods. They also aim at the promotion of research and development for the improvement of the theory and their tools for industrial applications. We are satisfied to see that time and again, the application of these methods clarifies the structure and inner workings of many systems and exposes many mistakes and conceptual errors. We are particularly delighted, as the reader may see when browsing through this special issue, that throughout the years a steady improvement can be observed regarding the size and complexity of systems that are being investigated. We hope and expect that this trend will continue throughout the forthcoming FMICS workshops. We want to thank all those that have helped in producing this special issue. Especially the program committee, assisted by numerous referees, as well as the authors of the contributions and the participants of the workshop.

Abstract This paper reports on the first steps towards the formal verification of correctness proofs of real-life protocols in process algebra. We show that such proofs can be verified, and partly constructed, by a general purpose proof checker. The process algebra we use isμCRL, ACPτaugmented with data, which is expressive enough for the specification of real-life protocols. The proof checker we use is Coq, which is based on the Calculus of Constructions, an extension of simply typed lambda calculus. The focus is on the translation of the proof theory ofμCRL andμCRL-specifications to Coq. As a case study, we verified the Alternating Bit Protocol.

We model a one-bit sliding window protocol and prove that its external behaviour is a bi-directional buffer of capacity 2. The proof is given in μCRL, which is a process algebra extended with data. Due to the abundant parallelism in this protocol, the behaviour is quite complicated. The complexity has been mastered by explicitly identifying invariants and foci of cones in the protocol. Both concepts seem promising as tools for the verification of larger and more complex protocols.

Abstract We extend process algebra with guards, comparable to the guards in guarded commands or conditions in common programming constructs such as ‘if — then — else — fi’ and ‘while — do — od’. The extended language is provided with an operational semantics based on transitions between pairs of a process and a (data-)state. The data-states are given by a data environment that also defines in which data-states guards hold and how atomic actions (non-deterministically) transform these states. The operational semantics is studied modulo strong bisimulation equivalence. For basic process algebra (without operators for parallelism) we present a small axiom system that is complete with respect to a general class of data environments. Given a particular data environmentL we add three axioms to this system, which is then again complete, provided weakest preconditions are expressible andL is sufficiently deterministic. Then we study process algebra with parallelism and guards. A two phase-calculus is provided that makes it possible to prove identities between parallel processes. Also this calculus is complete. In the last section we show that partial correctness formulas can easily be expressed in this setting. We use process algebra with guards to prove the soundness of a Hoare logic for linear processes by translating proofs in Hoare logic into proofs in process algebra.

We present a general theory for the use of negative premises in the rules of Transition System Specifications (TSS's). We formulate a criterion that should be satisfied by a TSS in order to be meaningful, i.e. to unequivocally define a transition relation. We also provide powerful techniques for proving that a TSS satisfies this criterion, meanwhile constructing this transition relation. Both the criterion and the techniques originate from logic programming [8, 7] to which TSS's are close. As in [10], we show that the bisimulation relation induced by a TSS is a congruence, provided that it is in ntyft/ntyxt -format and can be proved meaningful using our techniques. As a running example, we study the combined addition of priorities and abstraction to Basic Process Algebra (BPA). Under some reasonable conditions we show that this TSS is indeed meaningful, which could not be shown by other methods [2, 10]. Finally, we provide a sound and complete axiomatization for this example. We have omitted most proofs here; they can be found in [3]. The first author is partly supported by the European Communities under ESPRIT Basic Research Action 3020 (Integration). The second author is supported by the European Communities under RACE project no. 1046 (SPECS) and ESPRIT Basic Research Action 3006 (CONCUR). These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.