A tactic language for refinement of state-rich concurrent specifications

Circus is a refinement language in which specifications define both data and behavioural aspects of concurrent systems using a combination of Z and CSP. Its refinement theory and calculus are distinctive, but since refinements may be long and repetitive, the practical application of this technique can be hard. Useful strategies have been identified, described, and used, and by documenting them as tactics, they can be expressed and repeatedly applied as single transformation rules. Here, we present ArcAngelC, a language for defining such tactics; we present the language, its semantics, and its application in the formalisation of an existing strategy for verification of Ada implementations of control systems specified by Simulink diagrams. We also discuss its mechanisation in a theorem prover, ProofPower-Z.     

A refinement calculus for specifications in Hennessy-Milner logic with recursion

This paper is about specification and verification of processes, modelled as CCS-agents. We show, by means of examples that Hennessy-Milner Logic (HML) with recursion is a suitable language for expressing implicit or partial specifications. By extending this specification language withrefinement operators, i.e. operators that describe the internal structure of a system, we obtain a calculus for stepwise refinement of agents from a specification in HML to a realisation in CCS. The method is demonstrated by proving the alternating-bit protocol under weak assumptions about the unreliable media.This paper has also be presented at the BCS-FACS workshop on Specification and Verification of Concurrent Systems, University of Stirling, July 1988, under the title: Hennessy-Milner logic with recursion as a specification language, and a refinement calculus based on it.     

Automating the refinement of specifications for distributed systems via syntactic transformations

The idea of successively refining an abstract specification until it contains enough detail to suggest an implementation has been investigated by numerous researchers. The emphasis to date has been on techniques that, unfortunately, lead to a large amount of manual formal labour for each refinement step. With such techniques, both the cost and the possibility of errors arising informal manipulation are high. Using a theorem prover can reduce the number of manipulation errors, but, given current technology, the amount of labour is still daunting. This research explores an alternative solution to the refinement problem, namely the use of syntactic transformations to realize each refinement step. We reduce formal labour by employing automatic transformations that guarantee the preservation of desirable properties—e.g., deadlock-freedom. Automatic transformations are particularly appealing for the development of large, complex distributed systems, where a manual approach to refinement would be prohibitively expensive. Distributed computations are, by nature, reactive and concurrent, so their correctness cannot be specified as a simple functional relationship between inputs and outputs. Instead, specifications must describe the time-varying behaviour of the system. Further difficulty is caused by the fact that such important characteristics of distributed systems as deadlock-freedom are global properties that cannot be achieved through considering local structures only. Transformations generally must encompass the entire system. This paper presents two syntactic transformations—the left-sequence introduction and the right-sequence introduction—and demonstrates that they preserve deadlock-freedom.     

Data refinement by calculation

Summary Data refinement is the systematic substitution of one data type for another in a program. Usually, the new data type is more efficient than the old, but possibly more complex; the purpose of the data refinement in that case is to make progress in program construction from more abstract to more concrete formulations. A recent trend in program construction is to calculate programs from their specifications; that contrasts with proving that a given program satisfies some specification. We investigate to what extent the trend can be applied to data refinement.Supported by British Petroleum Ltd.     

Data refinement and singleton failures refinement are not equivalent

In this paper, we give simple example abstract data types, with atomic operations, that are related by data refinement under a definition used widely in the literature, but these same abstract data types are not related by singleton failure refinement. This contradicts results found in the literature.     

Fast animation of debris flow with mixed adaptive grid refinement

Animating debris flow is one of the most challenging tasks in computer graphics, because of its complex dynamic mechanism and the interaction between flows and solids in so large scale region. The difficulty focuses on how to resolve the contradiction between lower computational load and higher request of animating quality. A highly effective method of modeling and animating of debris flow with adaptive grid is presented. First, the debris flow is modeled as Bingham plastic fluid with view‐dependent adaptive grid that is adopted to model the flow volume, and the boundless grids can cover the large scale region of debris flow. Then the mixed grids are built for confluent flows, and the two‐way coupling interaction between flows and environment is considered. After extracting the debris flow surface, adaptive surface tension combining wave particles equation is used to enhance the details and sprays are generated by particles considering the interaction between two fluid volumes. Finally, different dynamic realistic scenes with debris flow are successfully animating at interactive rates. Copyright © 2013 John Wiley & Sons, Ltd.     

Generation of 3D mixed element meshes using a flexible refinement approach

This paper describes and discusses the main characteristics and implementation issues of a 3D mixed element mesh generator based on a generalization of the modified octree approach. This mesh generator uses primitive elements of different type as internal nodes, a flexible refinement approach as refinement strategy (primitive elements are not always bisected), and bricks, pyramids, prisms and tetrahedra as final elements. The mesh generation process is divided in several steps: the generation of the initial mesh composed of primitive elements, the refinement of primitive elements until the point density requirements are fulfilled, the generation of a graded mesh between dense and coarse regions, and finally, the recognition of the final elements. The main algorithms and data structures are described in detail for each step of the mesh generation process. As result, examples of meshes that satisfy the Delaunay condition and that can be used with the control volume method are shown.     

Deriving protocol specifications from service specifications written in LOTOS

Summary.  A complete communication system is broken down into a number of protocol layers each of which provides services to the layer above it and uses services provided by its underlying layer. A service specification defines a particular ordering of the operations that a given layer provides to the layer above it. The active elements in each layer are called entities and they use a protocol in order to implement their service definition. On the basis of this relation between the service and protocol concepts we have developed algorithms for deriving protocol entity specifications from a formal service specification. The derived protocol entities ensure the correct ordering of the service primitives by exchanging synchronization messages through an underlying communication medium. This paper presents an extended version of our earlier derivation algorithms. This version of the algorithm can handle all operators and unrestricted process invocation and recursion as defined by basis LOTOS. The correctness of this derivation algorithm is formally proved. Received: January 1992 / Accepted: February 1996     

Crypt-equivalent algebraic specifications

Summary Equivalence is a fundamental notion for the semantic analysis of algebraic specifications. In this paper the notion of crypt-equivalence is introduced and studied w.r.t. two loose approaches to the semantics of an algebraic specification T: the class of all first-order models of T and the class of all term-generated models of T. Two specifications are called crypt-equivalent if for one specification there exists a predicate logic formula which implicitly defines an expansion (by new functions) of every model of that specification in such a way that the expansion (after forgetting unnecessary functions) is homologous to a model of the other specification, and if vice versa there exists another predicate logic formula with the same properties for the other specification. We speak of first-order crypt-equivalence if this holds for all first-order models, and of inductive crypt-equivalence if this holds for all term-generated models. Characterizations and structural properties of these notions are studied. In particular, it is shown that first order crypt-equivalence is equivalent to the existence of explicit definitions and that in case of positive definability two first-order crypt-equivalent specifications admit the same categories of models and homomorphisms. Similarly, two specifications which are inductively crypt-equivalent via sufficiently complete implicit definitions determine the same associated categories. Moreover, crypt-equivalence is compared with other notions of equivalence for algebraic specifications: in particular, it is shown that first-order cryptequivalence is strictly coarser than abstract semantic equivalence and that inductive crypt-equivalence is strictly finer than inductive simulation equivalence and implementation equivalence.     

Assessment of safety-critical specifications

Formal methods can reduce the ambiguity in specifications and provide a basis for verification later on-especially important for safety-critical systems. The author compares specifications in the software cost reduction method and in the Vienna Definition Method for a safety-critical system and identifies several key assessment issues: understandability, assessment criteria, and semantic capabilities     

Animation of requirements specifications

Requirements analysis has been recognized as one of the most critical and difficult tasks in software engineering. The need for tool support is essential. This paper reports some work done to provide such support for interpretation and validation of requirements specifications by animation. The Animator provides facilities for the selection and execution of a transaction to reflect the specified behaviour of a particular scenario specified in the requirements specification. Actions are described in terms of input-output mappings and or functions with pattern matching. Simple rules can be specified to control the triggering of actions. In addition, facilities are provided to replay and interact with transactions. User interaction during animation includes the ability to change data values or role play selected actions as desired. A full graphical interface is supported. The approach has been tested by the provision of an Animator for the requirements analysis method CORE and an associated ‘Analyst Workstation’. Animation has been tested on a number of small examples and a major case study. This paper describes the Animator, justifies the approach taken and discusses experience and future work.     

Crypt-equivalent algebraic specifications

Summary Equivalence is a fundamental notion for the semantic analysis of algebraic specifications. In this paper the notion of “crypt-equivalence” is introduced and studied w.r.t. two “loose” approaches to the semantics of an algebraic specificationT: the class of all first-order models ofT and the class of all term-generated models ofT. Two specifications are called crypt-equivalent if for one specification there exists a predicate logic formula which implicitly defines an expansion (by new functions) of every model of that specification in such a way that the expansion (after forgetting unnecessary functions) is homologous to a model of the other specification, and if vice versa there exists another predicate logic formula with the same properties for the other specification. We speak of “first-order crypt-equivalence” if this holds for all first-order models, and of “inductive crypt-equivalence” if this holds for all term-generated models. Characterizations and structural properties of these notions are studied. In particular, it is shown that firstorder crypt-equivalence is equivalent to the existence of explicit definitions and that in case of “positive definability” two first-order crypt-equivalent specifications admit the same categories of models and homomorphisms. Similarly, two specifications which are inductively crypt-equivalent via sufficiently complete implicit definitions determine the same associated categories. Moreover, crypt-equivalence is compared with other notions of equivalence for algebraic specifications: in particular, it is shown that first-order cryptequivalence is strictly coarser than “abstract semantic equivalence” and that inductive crypt-equivalence is strictly finer than “inductive simulation equivalence” and “implementation equivalence”.     

Merging behavior specifications

This paper describes a method for merging behavior specifications modeled by transition systems. Given two behavior specificationsB1 andB2, Merge (B1,B2) defines a new behavior specification that extendsB1 andB2. Moreover, provided that a necessary and sufficient condition holds, Merge(B1,B2) is a cyclic extension ofB1 andB2. In other words, Merge (B1,B2) extendsB1 andB2, and any cyclic trace inB1 orB2 remains a cyclic in Merge(B1,B2). Therefore, in the case of cyclic traces ofB1 orB2, Merge(B1,B2) transforms into Merge(B1,B2), and may exhibit, in a recursive manner, behaviors ofB1 andB2. If Merge(B1,B2) is a cyclic extension ofB1 andB2, then Merge(B1,B2) represents the least common cyclic extension ofB1 andB2. This approach is useful for the extension and integration of system specifications.This research was supported by a grant from the Canadian Institute for Telecommunications Research under the NCE program of the Govemment of Canada and by an IBM research fellowship.