The ”state explosion problem” can be alleviated by using partial order reduction techniques. These methods rely on expanding only a fragment of the full state space of a program, which is sufficient for verifying the formulas of temporal logics LTL −X or CTL −X * (i.e., LTL or CTL * without the next state operator). This is guaranteed by preserving either a stuttering maximal trace equivalence or a stuttering bisimulation between the full and the reduced state space. Since a stuttering bisimulation is much more restrictive than a stuttering maximal trace equivalence, resulting in less powerful reductions for CTL −X * , we study here partial order reductions that preserve equivalences ”in-between”, in particular a stuttering simulation which is induced by the universal fragment of CTL: −X * , called ACTL −X * The reductions generated by our method preserve also branching simulation and weak simulation, but surprisingly, they do not appear to be included into the reductions obtained by Peled's method for verifying LTL −X properties. Therefore, in addition to ACTL −X * reduction method we suggest also an improvement of the LTL −X reduction method. Moreover, we prove that reduction for concurrency fair version of ACTL −X * is more efficient than for ACTL −X * .

Abstract. A new notion, covering, generalising independence is introduced. It enables improved effects of partial-order reduction techniques when applied to real-time systems. Furthermore, we formulate a number of locally checkable conditions for covering that can be used as the basis for a practical algorithm. Correctness is proven with respect to a chosen discretisation method.

The advent of ever more complex reactive systems in increasingly critical areas calls for the development of automated verification techniques.Model checking is one such technique, which has proven quite successful.However, the state-explosion problem remains a major stumbling block.Recent experience indicates that solutions are to be found in the application of techniques for property-preserving abstraction and successive approximation of models.Most such applications have so far been based solely on the property-preserving characteristics of simulation relations.A major drawback of all these results is that they do not offer a satisfactory formalization of the notion of precision of abstractions.The theory of Abstract Interpretation offers a framework for the definition and justification of property-preserving abstractions.Furthermore, it provides a method for the effective computation of abstract models directly from the text of a program, thereby avoiding the need for intermediate storage of a full-blown model.Finally, it formalizes the notion of optimality, while allowing to trade precision for speed by computing suboptimal approximations.For a long time, applications of Abstract Interpretation have mainly focused on the analysis of universal safety properties, i.e., properties that hold in all states along every possible execution path.In this article, we extend Abstract Interpretation to the analysis of both existential and universal reactive properties, as expressible in the modal µ-calculus.It is shown how abstract models may be constructed by symbolic execution of programs.A notion of approximation between abstract models is defined while conditions are given under which optimal models can be constructed.Examples are given to illustrate this.We indicate conditions under which also falsehood of formulae is preserved.Finally, we compare our approach to those based on simulation relations.

A compositional network proof theory for specifying and verifying fault tolerant real-time distributed systems is presented. Important in such systems is the failure hypothesis that stipulates the class of failures that must be tolerated. In the formalism presented, the failure hypothesis of a system is represented by a predicate which expresses how faults might transform the behavior of the system. The approach is illustrated by investigating a triple modular redundant system.>

A denotational, hence, compositional semantics for a subset of Concurrent Prolog is developed and related to an operational semantics. The denotational semantics makes divergence and the resultant substitutions of finite computations together with the termination mode-success, failure, or deadlock-observable. Relative to this notion of observation it is proved that the denotational semantics is fully abstract in the sense that it records the minimal amount of extra information beyond the observables to make it compositional. Full abstraction is an important property because it quantifies the information that one needs in order to reason about individual program-parts independently. This is believed to be the first such result in the area of concurrent logic programming.>

We present a fully abstract semantics for real-time distributed computing of the Ada and OCCAM kind in a denotational style. This semantics turns termination, communication along channels, and the time communication takes place, into observables. Yet it is the coarsest semantics to do so which is syntax-directed (this is known as full abstraction). It extends the linear history semantics for CSP of Francez, Lehman and Pnueli. Our execution model is based on maximizing concurrent activity as opposed to interleaving (in which only one action occurs at the time and arbitrary delays are incurred between actions). It is a variant of the maximal parallelism model of Salwicki and Müldner.

This paper addresses the problem of obtaining formal proof systems that support reasoning about temporal properties of parallel programs in a way that is compositional or 'syntax directed' - the distinctive feature of e.g. Hoare style proof systems. Now, temporal properties of programs express properties about execution traces of these programs. In the presence of concurrency, compositionality is obtained by concentrating exclusively on the execution traces associated with the atomic actions of programs - the so-called transitions of those programs. To reason about such transitions in a compositional way, 'Transition Logic' is proposed, expressing properties of the form “every transition of a program, say α, that starts in a state satisfying assertion p, must end in a state validating ”: [p]α[q]. Essential is that these assertions can express properties of control locations of programs, too. For this logic, a compositional proof system is obtained which is proved to be sound and relatively complete. An interesting feature of the proof system is the axiomatization of the flow-of-control of programs. The relevance of this logic is supported by the fact that the temporal behaviour of a program is ultimately provable in terms of properties of its transitions, as shown by the work of Z. Manna and A. Pnueli [16].