Refinement is one of the cornerstones of the formal approach to software engineering, and its use in various domains has led to research on new applications and generalisation. This book brings together this important research in one volume, with the addition of examples drawn from different application areas. It covers four main themes:- data refinement and its application to Z;- generalisations of refinement that change the interface and atomicity of operations;- refinement in Object-Z;- and modelling state and behaviour by combining Object-Z with CSP.Refinement in Z and Object-Z: Foundations and Advanced Applications provides an invaluable overview of recent research for academic and industrial researchers, lecturers teaching formal specification and development, industrial practitioners using formal methods in their work, and postgraduate and advanced undergraduate students.

Questions asked by research into ODP Viewpoint Consistency led to fundamental questions in refinement and contributed greatly to insights and interest in Integrated Formal Methods; research in those areas is still ongoing, while the answers provided remain largely unincorporated into model driven development. In this paper we survey some of the work done on consistency checking for multiple viewpoints, and subsequent work on generalised notions of refinement, which in turn led to work on integrations of state-based and behavioural formal methods.

Data refinement in a state-based language such as Z is defined using a relational model in terms of the behaviour of abstract programs. Downward and upward simulation conditions form a sound and jointly complete methodology to verify relational data refinements, which can be checked on an event-by-event basis rather than per trace. In models of concurrency, refinement is often defined in terms of sets of observations, which can include the events a system is prepared to accept or refuse, or depend on explicit properties of states and transitions. By embedding such concurrent semantics into a relational framework, eventwise verification methods for such refinement relations can be derived. In this paper we continue our program of deriving simulation conditions for process algebraic refinement by defining further embeddings into our relational model: traces, completed traces, failure traces and extension. We then extend our framework to include various notions of automata based refinement.

This paper reconsiders refinements which introduce actions on the concrete level which were not present at the abstract level. It considers a range of different basic refinement relations, covering the standard ones for formalisms like Event-B, Z, action systems, and CSP. It also describes a number of ways in which new operations may be introduced: extended interfaces, internal actions, stuttering steps, and action refinement. The main contribution of this paper is in exploring the interaction between those two dimensions. In particular, it shows how the "refining skip" method is incompatible with failures-based refinement relations, and consequently some decisions in designing Event-B refinement are more entangled than previously highlighted.

Refinement is the notion of development between formal specifications. For specifications given in a relational formalism, downward and upward simulations are the standard method to verify that a refinement holds, their usefulness based upon their soundness and joint completeness. This is known to be true for total relational specifications and has been claimed to hold for partial relational specifications in both the non-blocking and blocking interpretations. In this paper we show that downward and upward simulations in the blocking interpretation, where domains are ''guards'', are not jointly complete. This contradicts earlier claims in the literature. We illustrate this with an example (based on one recently constructed by Reeves and Streader) and then construct a proof to show why joint completeness fails in general.

In this paper we explore the relation between refinement and reduction, especially as it is used in the context of cryptography. We show how refinement is a special case of reduction, and more interestingly, how reduction is an instance of a novel generalisation, ''refinement with context''.

Data refinement in a state-based language such as Z is defined using a relational model in terms of the behaviour of abstract programs. Downward and upward simulation conditions form a sound and jointly complete methodology to verify relational data refinements. On the other hand, refinement in a process algebra takes a number of different forms depending on the exact notion of observation chosen, which can include the events a system is prepared to accept or refuse. In this paper we continue our program of deriving relational simulation conditions for process algebraic refinement by defining further embeddings into our relational model: traces, completed traces, failure traces and extension.

Two styles of description arise naturally in formal specification: state-based and behavioural. In state-based notations, a system is characterised by a collection of variables, and their values determine which actions may occur throughout a system history. Behavioural specifications describe the chronologies of actions -- interactions between a system and its environment. The exact nature of such interactions is captured in a variety of semantic models with corresponding notions of refinement; refinement in state based systems is based on the semantics of sequential programs and is modelled relationally. Acknowledging that these viewpoints are complementary, substantial research has gone into combining the paradigms. The purpose of this paper is to do three things. First, we survey recent results linking the relational model of refinement to the process algebraic models. Specifically, we detail how variations in the relational framework lead to relational data refinement being in correspondence with traces-divergences, singleton failures and failures-divergences refinement in a process semantics. Second, we generalise these results by providing a general flexible scheme for incorporating the two main ''erroneous'' concurrent behaviours: deadlock and divergence, into relational refinement. This is shown to subsume previous characterisations. In doing this we derive relational refinement rules for specifications containing both internal operations and outputs that corresponds to failures-divergences refinement. Third, the theory has been formally specified and verified using the interactive theorem prover KIV.

Data refinement in a state-based language such as Z is defined using a relational model in terms of the input-output behaviour of abstract programs. Downward and upward simulations form a sound and jointly complete methodology for verifying relational data refinements. Refinement in a concurrent context, for example, as found in a process semantics, takes a number of different forms. Typically this is based on a notion of observation, for example, which events a system is prepared to accept or refuse. Concurrent refinement relations include trace refinement, failures-divergences refinement, readiness refinement and bisimulation. In this paper we survey recent results linking the relational model of refinement to the process algebraic models. Specifically, we detail how variations in the relational framework lead to relational data refinement being in correspondence with traces-divergences, singleton failures and failures-divergences refinement in a process semantics. We then extend these results by showing how the effect of internal operations can be incorporated into the relational model. As a consequence simulation rules for failures-divergences refinement can be derived.

Refinement in a concurrent context, as typified by a process algebra, takes a number of different forms depending on what is considered observable. Observations record, for example, which events a system is prepared to accept or refuse. Concurrent refinement relations include trace refinement, failures-divergences refinement, readiness refinement and bisimulation. Refinement in a state-based language such as Z, on the other hand, is defined using a relational model in terms of the input-output behaviour of abstract programs. These refinements are normally verified by using two simulation rules which help make the verification tractable. This paper unifies these two standpoints by generalising the standard relational model to include additional observable aspects. These are chosen in such a way that they represent exactly the notions of observation embedded in the various concurrent refinement relations. As a consequence, simulation rules for the tractable verification of concurrent refinement can be derived. We develop such simulation rules for failures-divergences refinement and readiness refinement in particular, using an alternative relational model in the latter case.

We describe a framework for viewpoint specification using formal specification languages. In order to establish consistency and to further develop specifications, specifications need to be integrated ("unified"). This integration is not defined in terms of their semantics, but more abstractly in terms of, so-called, development relations, which represent acceptable "developments" (e.g., refinements) of each of the viewpoint specifications. The framework is motivated by its instantiations with a number of specification languages (e.g., LOTOS and Z) and different development relations.

Multiple Viewpoint models of system development are becoming increasingly important. Each viewpoint offers a different perspective on the target system and system development involves parallel refinement of the multiple views. Viewpoints related approaches have been considered in a number of different guises by a spectrum of researchers. Our work particularly focuses on the use of viewpoints in Open Distributed Processing (ODP) which is an ISO/ITU standardisation framework. The requirements of viewpoints modelling in ODP are very broad and, hence, demanding. Multiple viewpoints, though, prompt the issue of consistency between viewpoints. This paper describes a very general interpretation of consistency which we argue is broad enough to meet the requirements of consistency in ODP. We present a formal framework for this general interpretation; highlight basic properties of the interpretation and locate restricted classes of consistency. Strategies for checking consistency are also investigated. Throughout we illustrate our theory using the formal description technique LOTOS. Thus, the paper also characterises the nature of and options for consistency checking in LOTOS.

Refinement in a concurrent context, as typified by a process algebra, takes a number of different forms depending on what is considered observable, where observations record, for example, which events a system is prepared to accept or refuse. Examples of concurrent refinement relations include trace refinement, failures-divergences refinement and bisimulation. Refinement in a state-based language such as Z, on the other hand, is defined using a relational model in terms of input/output behaviour of abstract programs. These refinements are verified by using two simulation rules which help make the verification tractable. The purpose of this paper is to unify these two standpoints, and we do so by generalising the standard relational model to include additional observable aspects. The central result of the paper is then to develop simulation rules to verify relations such as failures-divergences refinement in a relational setting, and show how these might be applied in a specification language such as Z. http://www.elsevier.com/gej-ng/31/29/23/125/48/show/Products/notes/index.htt

http://www.springerlink.com/openurl.asp?genre=article&eissn=1433-299X&volume=13&issue=2&spage=111

The reference model of Open Distributed Processing (ODP) prescribes the use of a number of viewpoints (i.e., partial specifications). Specifications written in these viewpoints are likely to use different notations, e.g. the Computational Viewpoint is likely to include descriptions given in CORBA IDL, whilst the Information Viewpoint might well use a schema-based notation such as Z. To support such a specification scenario in this paper we describe a translation from a subset of CORBA IDL to the Z specification notation, which has been implemented in a prototype translator based on the IDL parsing tool HaskellDirect. Although our main motivation is to integrate CORBA IDL into an existing multi-language framework for viewpoint specification and consistency checking, the translation could also serve as the basis for a reverse translation from a subset of Z into IDL. In addition, it will help support a translation into Z from IDL specifications augmented with Z annotations that express behavioural constraints not expressible in IDL itself.

Open Distributed Processing (ODP) is a joint ITU/ISO standardisation framework for constructing distributed systems in a multi-vendor environment. Central to the ODP approach is the use of viewpoints for specification and design. Inherent in any viewpoint approach is the need to check and manage the consistency of viewpoints. In previous work we have described techniques for consistency checking, refinement, and translation between viewpoint specifications, in particular for LOTOS and Z/Object-Z. Here we present an overview of our work, motivated by a case study combining these techniques in order to show consistency between viewpoints specified in LOTOS and Object-Z.

Partial specification is a method of specifying complex systems in which the system is described by a collection of specifications, each approaching the system from a different viewpoint. The specification notation Z is often advocated as a suitable language for this style of specification. For collections of partial specifications to be meaningful, they need to be consistent, i.e. they should not impose contradictory requirements. This paper addresses how the consistency between partial specifications in Z can be checked, by constructing unifications, i.e. least common refinements, of viewpoint specifications.

There is increasing interest in models of system development which use Multiple Viewpoints. Each viewpoint offers a different perspective on the target system and system development involves parallel refinement of the multiple views. Multiple viewpoints though, prompt the issue of consistency between viewpoints. This paper describes an interpretation of consistency which is general enough to meet the requirements of consistency for very general viewpoints models. Furthermore, the paper investigates strategies for checking this consistency definition. Particular emphasis is placed on mechanisms to obtain global consistency (between an arbitrary number of viewpoints) from a series of binary consistency checks. The consistency checking strategies we develop are illustrated using the formal description technique LOTOS.

This paper concerns calculational methods of refinement in state-based specification languages. Data refinement is a well-established technique for transforming specifications of abstract data types into ones, which are closer to an eventual implementation. The conditions under which a transformation is a correct refinement are encapsulated into two simulation rules: downward and upward simulations. One approach for refining an abstract system is to specify the concrete data type, and then attempt to verify that it is a valid refinement of the abstract type. An alternative approach is to calculate the concrete specification based upon the abstract specification and a retrieve relation, which links the abstract and concrete states. In this paper we generalise existing calculational methods for downward simulations and derive similar results for upward simulations; we also document their use and application in a particular specification language, namely Z.

This paper presents a translation between the formal description technique LOTOS and the object-oriented specification language Object-Z. The need for such a translation lies in the use of formal methods in viewpoint specification, and in particular in the Open Distributed Processing standard. The use of viewpoints as a set of partial interlocking specifications brings an obligation to check the consistency of these partial specifications, and to do so we need to relate specifications written in differing languages. The work presented here aims to support the consistency checking of viewpoints written using formal methods by defining a translation from LOTOS to Object-Z. A LOTOS specification describes both an ADT component and a behavioural model, the former is translated into the Z type system, and the behavioural specification is translated into a collection of Object-Z classes where we relate LOTOS actions to operations in the Object-Z specification. A case study is presented which illustrates the translation and consistency checking techniques discussed in the paper.

Abstract An important aspect in the specification of distributed systems is the role of the internal (or unobservable) operation. Such operations are not part of the interface to the environment (i.e. the user cannot invoke them), however, they are essential to our understanding and correct modelling of the system. In this paper we are interested in the use of the formal specification notation Z for the description of distributed systems. Various conventions have been employed to model internal operations when specifying such systems in Z. If internal operations are distinguished in the specification notation, then refinement needs to deal with internal operations in appropriate ways. Using an example of a telecommunications protocol we show that standard Z refinement is inappropriate for refining a system when internal operations are specified explicitly. We present a generalization of Z refinement, called weak refinement, which treats internal operations differently from observable operations when refining a system. We discuss the role of internal operations in a Z specification, and in particular whether an equivalent specification not containing internal operations can be found. The nature of divergence through livelock is also discussed. Keywords: Z; Refinement; Distributed Systems; Internal Operations; Process Algebras; Concurrency.

The task of software production is to build software systems which are to fulfil certain requirements. For years the approach has been to build up by trial and error a program which, having satisfied carefully prepared test data, offers a plausible solution to the problem. But is it correct? Even for toy examples this is not obvious. In particular, it is often not even clear whether the original problem has been fully understood. The reason for this dilemma is that the transition from the informal problem statement to the final program is too big to be intellectually managable. To master these problems, we advocate a software development method where the whole process is split into smaller steps by introducing formal specifications for (parts of) the problem and then stepwisely deriving efficient programs by correctness-preserving transformations.

Condensed version of the /pubs/1990/165 and PhD thesis chapter, including aspects of /pubs/1992/159/ Presented at Seminar on Formal Techniques in Programming Technology, G''od, Hungary, September 3-6, 1990.

E.A. Boiten , http://adam.fwi.uva.nl/~markvdb/ , http://www.sci.kun.nl/cgi-bin-thalia/smoelfind?medewerkers/niekd.html , http://www.sci.kun.nl/cgi-bin-thalia/smoelfind?medewerkers/kees.html , http://www.informatik.uni-ulm.de/pm/mitarbeiter/helmuth.html & http://www.fernuni-hagen.de/DVT/Mitarbeiter/voelker.html : USTOPIA Requirements - Thoughts on a User-friendly System for Transformation Of Programs In Abstracto Transformational programming is a program development method which is usually applied using ''pen and paper''. Since this requires a lot of clerical work (copying expressions, consistent substitution) which is tiresome and prone to error, some form of machine support is desirable. We describe a number of systems that have already been built to this aim. Some of their shortcomings and limitations are identified. Based on our experience with program transformation and transformation systems, we present a long list of features that would be useful in an ''utopian'' transformation system. This list is presented using an orthogonal division of the problem area. A number of problems with the realisation of some aspects of our ''utopian'' system is identified, and some areas for further research are indicated. Technical Report 90-12, Dept. of Informatics, University of Nijmegen, 1990. Also: Periodica Polytechnica Ser. El. Eng., 35(2):101-123, 1992. Copies available on request by mailto:E.A.Boiten@ukc.ac.uk.

The paper presents a synthetic view of transformations that invert the order of evaluation of recursive functions. Techniques for linear recursive functions are presented. A consideration of stacks motivates the introduction of a general control structure for tabulation. Several transformations for tree-like recursive functions are given.

This paper reconsiders refinements which introduce actions on the concrete level which were not present at the abstract level. It draws a distinction between concrete actions which are ''perspicuous'' at the abstract level, and changes of granularity of actions between different levels of abstraction. The main contribution of this paper is in exploring the relation between these different methods of ''action refinement'', and the basic refinement relation that is used. In particular, it shows how the ''refining skip'' method is incompatible with failures-based refinement relations, and consequently some decisions in designing Event-B refinement are entangled. See http://eptcs.org/content.cgi?Refine2011.

Data refinement in a state-based language such as Z is defined using a relational model in terms of the behaviour of abstract programs. Downward and upward simulation conditions form a sound and jointly complete methodology to verify relational data refinements, which can be checked on an event-by-event basis rather than per trace. In models of concurrency, refinement is often defined in terms of sets of observations, which can include the events a system is prepared to accept or refuse, or depend on explicit properties of states and transitions. By embedding such concurrent semantics into a relational one, eventwise verification methods for such refinement relations can be derived. In this paper we continue our program of deriving simulation conditions for process algebraic refinement by considering how notions of time should be embedded into a relational model, and thereby deriving relational notions of timed refinement.

The formal methods and refinement community should be able to contribute to the specification and verification of security protocols. This talk describes a few of the essential differences, or problems. First, security properties go beyond functional correctness, and are fundamentally different for different applications. Moreover, tomorrow's attacks may not be anticipated by yesterday's security properties. Second, notions of security may not be absolute: it may be good enough if guessing our secret is merely hard rather than impossible â?? and in some cases that may be provably the best we can get. Where does that leave us in wanting to provide security protocols ''correct by construction''?

Data refinement in a state-based language such as Z is defined using a relational model in terms of the behaviour of abstract programs. Downward and upward simulation conditions form a sound and jointly complete methodology to verify relational data refinements. On the other hand, refinement in a process algebra takes a number of different forms depending on the exact notion of observation chosen, which can include the events a system is prepared to accept or refuse. In this paper we investigate how divergence can be modelled relationally, and in particular show how differing process algebraic interpretations of divergence can be embedded in a relational framework. In doing so we derive relational simulation conditions for process algebraic refinement incorporating divergence.

We describe a method for combining formal program development with a disciplined and documented way of introducing realistic compromises, for example necessitated by resource bounds. Idealistic specifications are identified with the limits of sequences of more ''realistic'' specifications, and such sequences can then be refined in their entirety. Compromises amount to focusing the attention on a particular element of the sequence instead of the sequence as a whole. This method addresses the problem that initial formal specifications can be abstract or complete but rarely both. Various potential application areas are sketched, some illustrated with examples. Key research issues are found in identifying metric spaces and properties that make them usable for refinement using approximations.

In this work we study the unification of heterogeneous partial specifications using category theory. We propose an alternative to institution morphisms, which we call (abstract) correspondences carrying specifications. Our methodology is illustrated using a categorical specification style inspired by the state-and-operations style of Z as well as a categorical unification procedure.

One way of making UML more suitable for the development of critical systems is to define a formal notion of development (or refinement) for it. We explore refinement indirectly: through unification. Different UML diagrams may contain information on the same system element, which may or may not be contradictory. Such diagrams may be part of the same UML model, or taken from different models representing ''viewpoints''. A representation of the combined information of diagrams is a unification. Implicit in this is a notion of ''information content'' which needs to be formalised. A unification is not only a representation of combined information, it also witnesses consistency between the models. The theory of consistency and unifications for viewpoint specification is well-developed for formal methods. In general, such unification methods are parameterised by a notion of refinement (i.e., how to compare information content), and a notion of correspondence (relating the information between specifications). In particular, in Z all of these can be expressed syntactically, and a variety of refinement relations have been developed inspired by different styles of viewpoint specification. This paper considers a number of small UML models, their intuitive ''unifying'' diagrams, and how these would relate to the unifications of formalisations of the original diagrams. In this way, desirable properties for a formal development notion in UML emerge.

Relational theories of refinement using simulations exist based on total and on partial relations, modelling partial and total correctness. In order to model partialities such as non-termination and deadlock, domains of relations are often extended with, or assumed to include, a ``bottom'' value bot. This paper explores a number of such theories, all providing sound and jointly complete notions of simulations, concentrating on the role of bot.

In this paper we survey recent work on generalising refinement in a state-based setting. Such generalisations challenge a number of assumptions embedded in the standard formalisation of refinement in a language such as Z, and lead to simulation conditions that allow one to verify a refinement in a number of different contexts.

In this paper we discuss a framework by which one might approach questions of consistency in UML. The framework derives from work undertaken in the Open Distributing Processing (ODP) standardisation initiative which looked at consistency checking across the ODP viewpoints. This work has resonance with some of the problems facing those using the many different aspects of UML, and the purpose of this paper is to discuss how the existing work could be applied in a UML context.

This volume contains the Proceedings of the REFINE 2002 workshop. The Workshop was held in Copenhagen, Denmark on July 20 and 21, 2002, as a satellite event to FLoC'02 as an FME-affiliated workshop. Refinement is one of the cornerstones of a formal approach to software engineering. Refinement is the process of developing a more detailed design or implementation from an abstract specification through a sequence of mathematically-based steps that maintain correctness with respect to the original specification. The aim of this BCS FACS refinement workshop was to bring together people who are interested in the development of more concrete designs or executable programs from abstract specifications using formal notations, tool support for formal software development, and practical experience with formal refinement methodologies. The purpose of the workshop was to provide a forum for discussion of common ground and key differences. Topics of interest included: • Simulation techniques • Foundations and semantics • Case studies (specification and verification) • Compositional and modular reasoning • Object-orientation • Time • Specification notations • Programming models • Verification and tool support

http://www.springer.de/cgi/svcat/search_book.pl?isbn=3-540-43857-2

We sketch a framework for viewpoint specification using formal specification languages. In order to establish consistency and to further develop specifications, specifications need to be integrated (''unified''). This integration is not defined in terms of their semantics, but more abstractly in terms of, so-called, development relations, which represent acceptablelinebreak ''developments'' (e.g. refinements) of each of the viewpoint specifications. The framework is motivated by its instantiations with a number of specification languages (e.g., LOTOS and Z) and different development relations.

Integrating Specifications: Development Relations and Correspondences Realistic system specifications consist of many sub-specifications in a heterogeneous collection of notations. We have investigated what it means for such ''partial specifications'' to collectively describe possible implementations of the system, and what it means for them to be consistent. The crucial notion in this is the ''development relation'' which relates a specification to acceptable developments or implementations. Our current focus is on correspondences: how do we cross-reference between two partial specifications, especially when they are written in different notations? What does it mean for specifications to be integrated with respect to such a correspondence relation?

Open Distributed Processing (ODP) is a viewpoints based ISO framework for specifying open distributed systems. This paper considers an application of ODP to the specification of an air traffic control (ATC) system. The key issues that arise from this are discussed further in the context of the formal specification of a simpler model - the Information Viewpoint in Z, and the Computational Viewpoint in Object-Z.

Z is a specification notation with a model-based semantics, but in contrast to most such languages, its normal refinement relation is not defined in terms of model containment. This paper investigates this phenomenon, leading to a variety of observations concerning the relation between Z semantics and refinement.

The aim of this paper is to discuss what formal support can be given to the process of living with inconsistencies in Z, rather than eradicating them. Logicians have developed a range of logics to continue to reason in the presence of inconsistencies. We present one representative of such paraconsistent logics, namely Hunter's quasi-classical logic, and apply it to the analysis of inconsistent Z schemas. In the presence of inconsistency quasi-classical logic allows us to derive less, but more ``useful'', information. Consequently, inconsistent Z specifications can be analysed in more depth than at present. Part of the analysis of a Z operation is the calculation of the precondition. However, in the presence of an inconsistency, information about the intended application of the operation may be lost. It is our aim to regain this information. We introduce a new classification of precondition areas, based on the notions of definedness, overdefinedness and undefinedness. We then discuss two options to determine these areas both of which are based on restrictions of classical reasoning.

The 'viewpoint' approach, in which a system is described by several partial specifications, has been proposed as a way of making complex computing systems more understandable. The ISO's Open Distributing Processing (ODP) framework is an architecture for open distributed systems, involving five named viewpoints. This paper compares two partial specifications of a lending library --- from the ODP's Enterprise and Information Viewpoints --- and discusses the relation between them. Both specifications are written in Object-Z, an object-oriented variant of Z. Examining how such partial specifications might be unified raises broader issues of refinement and mutual consistency of partial specifications in Object-Z.

In this paper we describe how we can refine both objects and operations in an Object-Z specification. In particular, we will be concerned with changes of granularity of both objects and operations. Objects in that we wish to change the structure of objects in a specification. Operations in that we wish to provide explicit support for action refinement in this language. There are clear advantages in being able to change such levels of granularity when performing a refinement. In this paper we discuss the issues surrounding such refinements and derive general rules to support their use. We illustrate our ideas by looking at a specification of a cash point machine at a bank.

In the common Z specification style operations are, in general, partial relations. The domains of these partial operations are traditionally called preconditions, and there are two interpretations of the result of applying an operation outside its domain. In the traditional interpretation anything may result whereas in the alternative, guarded, interpretation the operation is blocked outside its precondition. In fact these two interpretations can be combined, and this allows representation of both refusals and underspecification in the same model. In this paper we explore this issue, and we extend existing work in this area by allowing arbitrary predicates in the guard. To do so we adopt a non-standard three valued interpretation of an operation by introducing a third truth value. This value corresponds to a situation where we don't care what effect the operation has, i.e.~the guard holds but we may be outside the precondition. Using such a three valued interpretation leads to a simple and intuitive semantics for operation refinement, where refinement means reduction of undefinedness or reduction of non-determinism. We illustrate the ideas in the paper by means of a small example.

Traditional rules for refinement of abstract data types suggest a software development process in which much of the detail has to be present already in the initial specification. In particular, the set of available operations and their interfaces need to be fixed. In contrast, many formal and informal software development methods rely on changes of granularity and require introduction of detail in a gradual way during the development process. This paper discusses several generalisations and extensions of the traditional refinement rules, which are compatible with each other and, more importantly, with the semantic grounding of data refinement. Together they should provide a semantic justification to a larger spectrum of development steps. The discussion takes place in the context of the formal specification language Z and its relational underpinnings.

The structuring of the specification and development of distributed systems according to viewpoints, as advocated by the Reference Model for Open Distributed Processing, raises the question of when such viewpoint specifications may be considered consistent with one another. In this paper, we analyse the notion of consistency in the context of formal process specification. It turns out that different notions of correctness give rise to different consistency relations. Each notion of consistency is formally characterised and placed in a spectrum of consistency relations. An example illustrates the use of these relations for consistency checking.

This paper discusses the refinement of systems specified in Z when we relax the assumption that the refinement will preserve the atomicity of operations. Data refinement is a well established technique for transforming specifications of abstract data types into ones which are closer to an eventual implementation. To verify a refinement a retrieve relation is used which relates the concrete to abstract states and allow the comparison between the data types to be made on a step by step basis by comparing an abstract operation with its concrete counterpart. A step by step comparison is possible because the two abstract data types are assumed to be conformal, i.e. there is a one-one correspondence between abstract and concrete operations, so each abstract operation has a concrete counterpart. In this paper we relax that assumption to discuss refinements where an abstract operation is refined by, not one: but a sequence of concrete operations. Such non-conformal or non-atomic refinements arise naturally in a number of settings and we illustrate our derivations with a simple example of a bank accounting system.

In this paper we discuss how the specification of components may be separated from the description of the context in which they are used. There are a number of ways in which this might be possible and here we show how to use the technique of promotion in Object-Z to combine components which are specified using process algebras. We discuss two approaches, the first is to separate out the specification into two distinct viewpoints written in different languages. These viewpoints are then combined by a process of translation and unification. The second approach will be to use hybrid languages composed of a combination of CSP and Object-Z. We also consider how to refine such component based descriptions and consider issues of compositionality.

One of the potential benefits of formal methods is that they offer the possibility of reducing the costs of testing. A specification acts as both the benchmark against which any implementation is tested, and also as the means by which tests are generated. There has therefore been interest in developing test generation techniques from formal specifications, and a number of different methods have been derived for state based languages such as Z, B and VDM. However, in addition to deriving tests from a formal specification, we might wish to refine the specification further before its implementation. The purpose of this paper is to explore the relationship between testing and refinement. As our model for test generation we use a DNF partition analysis for operations written in Z, which produces a number of disjoint test cases for each operation. In this paper we discuss how the partition analysis of an operation alters upon refinement, and we develop techniques that allow us to refine abstract tests in order to generate test cases for a refinement. To do so we use (and extend existing) methods for calculating the weakest data refinement of a specification.

We present a generalisation of data refinement in Z, called IO-refinement, that allows changes in input and output parameters of operations. Several informal motivations for the desirability of such a refinement relation are given, followed by a formal derivation that demonstrates its theoretical soundness. It is proved that IO-refinement indeed generalizes data refinement. Several theorems are presented that give sufficient conditions for IO-refinement to hold in simpler situations, e.g. just adding inputs and outputs. Some examples of the use of IO-refinement are also given. http://www1.bcs.org.uk/DocsRepository/02700/2702/boiten.pdf on BCS website; see also chapter 10 in /pubs/2001/1200/.

We introduce the concepts of grey box and display box data types. These make explicit the idea that state variables in abstract data types are not always hidden. Programming languages have visibility rules which make representations observable and modifiable. Specifications in model-based notations may have implicit assumptions about visible state components, or are used in contexts where the representation does matter. Grey box data types are like the ``standard'' black box data types, except that they contain explicit subspaces of the state which are modifiable and observable. Display boxes indirectly observe the state by adding displays to a black box. Refinement rules for both these alternative data types are given, based on their interpretations as black boxes.

LOTOS is a formal specification language, designed for the precise description of open distributed systems and protocols. The definition of, so called, implementation relations has made it possible also to use LOTOS as a specification technique for the design of such systems. These LOTOS based specification techniques usually (ab)use non-determinism to achieve implementation freedom. Unfortunately, this is unsatisfactory when specifying non-deterministic processes. We, therefore, propose to extend LOTOS with a disjunction operator in order to achieve more implementation freedom while maintaining the possibility to describe non-deterministic processes. In contrast with similar proposals we maintain the operational semantics.

Specification by viewpoints is advocated as a suitable method of specifying complex systems. Each viewpoint describes the envisaged system from a particular perspective, using concepts and specification languages best suited for that perspective. Inherent in any viewpoint approach is the need to check or manage the consistency of viewpoints and to show that the different viewpoints do not impose contradictory requirements. In previous work we have described a range of techniques for consistency checking, refinement, and translation between viewpoint specifications, in particular for the languages LOTOS and Z. These two languages are advocated in a particular viewpoint model, viz. that of the Open Distributed Processing (ODP) reference model. In this paper we present a case study which demonstrates how all these techniques can be combined in order to show consistency between a viewpoint specified in LOTOS and one specified in Z. Keywords: Viewpoints; Consistency; Z; LOTOS; ODP.

We define the notion of a coupling schema in Z, and describe the role it plays in data refinement, view composition, and viewpoint unification. In each case coupling schemas relate several state schemas. In data refinement they occur as retrieve relations (abstraction schemas). In specification by views, coupling schemas provide a link between the various views. For viewpoint specification, coupling schemas are closely related to correspondence relations between state schemas in the viewpoints. Simple properties of coupling schemas (e.g. totality, functionality, and consistency) are shown to have important consequences in the techniques listed, and to be very useful for exhibiting the relations between these techniques. It turns out that views and viewpoints can both be seen as variations on, or even as generalisations of, data refinement.

This paper presents a translation between the formal description technique LOTOS and the object-oriented specification language Object-Z. The need for such a translation lies in the use of formal methods in viewpoint specification, and in particular in the Open Distributed Processing standard. The use of viewpoints as a set of partial interlocking specifications brings an obligation to check the consistency of these partial specifications, and to do so we need to relate specifications written in differing languages. The work presented here supports the consistency checking of viewpoints written using formal methods by defining a translation from full LOTOS to Object-Z. A common semantic model is provided for the languages, and we verify the translation with respect to this model. The translation is illustrated with a small example. http://www1.bcs.org.uk/DocsRepository/02700/2749/derrick.pdf on BCS website; see also /pubs/1999/954/.

An important aspect in the specification of distributed systems is the role of the internal (or unobservable) operation. Such operations are not part of the user interface (i.e. the user cannot invoke them), however, they are essential to our understanding and correct modelling of the system. Various conventions have been employed to model internal operations when specifying distributed systems in Z. If internal operations are distinguished in the specification notation, then refinement needs to deal with internal operations in appropriate ways. However, in the presence of internal operations, standard Z refinement leads to undesirable implementations. In this paper we present a generalization of Z refinement, called weak refinement, which treats internal operations differently from observable operations when refining a system. We illustrate some of the properties of weak refinement through a specification of a telecommunications protocol. Keywords Refinement; Distributed Systems; Internal Operations; Process Algebras; Concurrency.

This paper discusses the issues of specification style and refinement that arise in connection with viewpoint modelling. In particular, we consider the support needed in order to deal with viewpoints at different levels of abstraction. The motivation for this work arises from the use of viewpoints in distributed systems design, in particular the Open Distributed Processing standard. Full proceedings of the workshop it was presented at can be found on WWW: A. Finkelstein and G. Spanoudakis (eds.): http://web.soi.city.ac.uk/homes/gespan/VP_FSE.html, ACM SIGSOFT Foundations of Software Engineering 4, 1996.

This paper compares the LOTOS and Z refinement relations. The motivation for such a comparison is the use of multiple viewpoints for specifying complex systems defined by the reference model of the Open Distributed Processing (ODP) standardization initiative. The ODP architectural semantics describes the application of formal description techniques (FDTs) to the specification of ODP systems. Of the available FDTs, Z is likely to be used for at least the information, and possibly other, viewpoints, whilst LOTOS is a strong candidate for use in the computational viewpoint. Mechanisms are clearly needed to support the parallel development, and integration of, viewpoints using these FDTs. We compare the LOTOS bisimulation relations and the reduction relations to the Z refinement relation showing that failure-traces refinement corresponds closely to refinement in Z.

Multiple viewpoints are used in Open Distributed Processing (ODP) in order to decompose the complexity inherent in specifying distributed systems. Multiple viewpoints prompt the issue of consistency between viewpoints. The ODP reference model alludes to three different interpretations of consistency. We show that our interpretation, firstly, satisfies all the basic requirements of a definition of consistency and, secondly, can be specialised to any of the three ODP reference model definitions. The generality of our definition will be illustrated through instantiation in the FDT LOTOS.

This paper discusses theoretical background for the use of Z as a language for partial specification, in particular techniques for checking consistency between viewpoint specifications. The main technique used is unification, i.e. finding a (candidate) least common refinement. The corresponding notion of consistency between specifications turns out to be different from the known notions of consistency for single Z specifications. A key role is played by correspondence relations between the data types used in the various viewpoints. Note: extended version available as /pubs/1999/607/.

This paper describes a translation of full LOTOS into Z. A common semantic model is defined and the translation is proved correct with respect to the semantics. The motivation for such a translation is the use of multiple viewpoints for specifying complex systems defined by the reference model of the Open Distributed Processing (ODP) standardization initiative. The postscript version available here is an extended version of what was published.

This paper discusses the unification of Z specifications, in particular specifications that maintain different representations of what is intended to be the same datatype. Essentially this amounts to integrating previously published techniques for combining multiple viewpoints and for combining multiple views. It is shown how the technique proposed in this paper indeed produces unifications, and that it generalises both previous techniques.

We describe a framework for the derivation of programs for arbitrary (in particular, parallel) architectures, motivated by a generalization of the derivation process for sequential algorithms. The central concept in this approach is that of a skeleton: on the one hand, a higher-order function for targeting transformational derivations at, on the other hand representing an elementary computation on the architecture aimed at. Skeletons thus form a basis for intermediate languages, that can be implemented once and for all, as a process separate from individual program developments. The available knowledge on the derivation of (higher-order) functional programs can be used for deriving parallel ones. In: H. Wijshoff, ed.: Computing Science in the Netherlands 1993, pp. 97-108. Copies on email request or (probably easiest) by clicking ftp://ftp.win.tue.nl/pub/math.prog.construction/skel.ps.Z.

It is shown how parsing can be described as a problem in the class ISBES, Intersections of Sets and Bags of Extended Substructures, defined in /pubs/1991/161/, by viewing parsing as a generalization of pattern matching in several ways. The resulting description is shown to be a good starting point for the transformational derivation of the Cocke-Kasami-Younger tabular parsing algorithm that follows. This derivation is carried out at the level of bag comprehensions.

Techniques from the area of formal specification are shown to be useful in the analysis of combinatorial problems. A problem description is given, using an abstract data type. By gradual elimination of the equivalences on the data types a unique representation of the type is derived which reduces the new problem to a known one.

Formal specifications that exhibit similarities will often have similar solutions. Thus, it is useful to construct generalized specifications that describe classes of problems, since (partial) solutions to the generalized problem can be used for obtaining solutions for the specific problems. In this paper we study a class of generalized pattern matching problems, in which the essential operation is the intersection of a particular set and a bag of extended substructures of a structured object. We present a formalization of bags of extended substructures and define the ISBES (Intersection of Sets and Bags of Extended Substructures) class of problems. Some example ISBES specifications are shown, and we present some first ideas about applicable program transformation strategies for ISBES problems.

This paper explores the possibilities of reuse of transformational developments. Although it has often been claimed that this could be done fully mechanically, the experience with a number of derivations in this chapter indicates that this claim is somewhat preposterous. Only by describing the transformation steps in a very abstract way (using just natural language) and by considering very general specifications, can the developments be reused. The central concept is similarity, and several definitions of this informal notion are given, each leading to a particular kind of reuse of derivations. Variants of a derivation of linear search lead to several interesting search algorithms, culminating in derivations by reuse of two complicated string matching algorithms.

This is an earlier presentation of part of /pubs/1992/159. The latter paper is also part of my PhD thesis.

Participants' proceedings. They are not available electronically, as they will appear in http://www.entcs.org soon. Until then, please mailto:E.A.Boiten@kent.ac.uk to request a paper copy. See http://www.softeng.ox.ac.uk/ifm2007/refinement.html for the workshop programme. There will also be a special issue of Formal Aspects of Computing dedicated to this workshop, but that will not appear before mid 2008.

This document contains a collection of programming exercises in the functional programming language Haskell. The exercises are all concerned with the infamous Travelling Salesman Problem (TSP for short), both its exact solution and heuristic approximations.

Abstraction of specifications is a method of making verification and validation of specifications and implementations more tractable. This paper considers the special case where the abstraction is defined by eliding input or output variables in state based specifications - in particular, conditions for such abstractions to be sound and complete with respect to a refinement semantics. Output abstractions turn out to be unconditionally sound, and combinations of output abstractions are complete in certain circumstances. Concrete results are developed in the state-based notation Z, and then considered in the underlying semantic framework and for similar languages.

This document contains a collection of programming exercises in the functional programming language Haskell. The exercises are all concerned with Turtle Graphics - interpreting and generating programs for ''turtles''.

Open Distributed Processing (ODP) is a framework for specifying open distributed systems, under development by the International Standards Organisation (ISO). It is based on the general idea of viewpoints - i.e. partial specifications of an overall system, from different perspectives - but assumes five specific, named viewpoints, which are described informally in the ODP Reference Model (RM-ODP). This paper summarises some observations regarding an attempt to use ODP to specify a complex air traffic control system. Some of the key issues that arise are discussed further in the context of the formal specification of a simpler, idealised model, involving two formalised viewpoints - the Information Viewpoint (a high-level, abstract specification, in Z), and the Computational Viewpoint (a specification of distributed components and objects, in Object-Z).

Multiple Viewpoint models of system development are becoming increasingly important. Each viewpoint offers a different perspective on the target system and system development involves parallel refinement of the multiple views. Viewpoints related approaches have been considered in a number of different guises by a spectrum of researchers. Our work particularly focuses on the use of viewpoints in Open Distributed Processing (ODP) which is an ISO/ITU standardisation framework. The requirements of viewpoints modelling in ODP are very broad and, hence, demanding. Multiple viewpoints, though, prompt the issue of consistency between viewpoints. This paper describes a very general interpretation of consistency which we argue is broad enough to meet the requirements of consistency in ODP. We present a formal framework for this general interpretation; highlight basic properties of the interpretation and locate restricted classes of consistency. Strategies for checking consistency are also investigated. Throughout we illustrate our theory using the formal description technique LOTOS. Thus, the paper also characterises the nature of and options for consistency checking in LOTOS.

We describe some prototype tools for performing unification (i.e. deriving the least common refinement) of simple Z specifications. The techniques used are those described in http://alethea.ukc.ac.uk/Dept/Computing/Research/NDS/consistency/cccfpsiZ.html on viewpoint specification in Z; the tools have been implemented in Generic http://public.logica.com/formaliser (a product of Logica UK Limited). UKC Computing Laboratory technical report 10-97. The prototype tools themselves (in the form of Generic Formaliser grammars) will be made available later.

A point-free calculus of so-called ''collection types'' is presented, similar to the monadic calculus of http://www.cis.upenn.edu/~db/home.html. We observe that our calculus is parametrised by a monad thus making the calculus ''polytypic''. A novel contribution of the paper is to discuss situations in which a single application involves more than one collection type. In particular, we outline the contribution to database research that may be obtained by exploiting current developments in polytypic programming.

There is increasing interest in models of system development which use multiple viewpoints. Each viewpoint offers a different perspective on the target system and system development involves parallel refinement of the multiple views. Our work particularly focuses on the use of viewpoints in Open Distributed Processing (ODP) which is an ISO/ITU standardisation framework. Multiple viewpoints, though, prompt the issue of consistency between viewpoints. This paper describes an interpretation of consistency which is general enough to meet the requirements of consistency in ODP. Furthermore, the paper investigates strategies for checking this consistency definition. Particular emphasis is placed on mechanisms to obtain global consistency (between an arbitrary number of viewpoints) from a series of binary consistency checks. The consistency checking strategies we develop are illustrated using the formal description technique LOTOS. Keywords: Viewpoints, Consistency, ODP, Formal Description Techniques, LOTOS.

Viewpoint models of system development are becoming increasingly important. A major requirement for viewpoints modelling is to be able to check that the multiple viewpoint specifications are consistent with one another. The work presented in this report makes a contribution to this task. Our work is particularly influenced by the viewpoints model used in the ISO standardisation architecture for Open Distributed Processing. This report focuses on the issue of strategies for consistency checking. In particular, it considers how global consistency (between any arbitrary number of viewpoints) can be obtained from binary consistency (between two viewpoints). The report documents a number of different classes of consistency checking, from those that are very poorly behaved to those that are very well behaved. The report is intended as a companion to the work presented in [1] and it should be read in association with this document. In particular, the body of this report is a single chapter which should be viewed as additional to the chapters included in [1]. This report contains complete proofs of all relevant results, even though some of the results are obvious and some of the proofs are trivial. A much compressed version of the report is being submitted for publication. Thus, the main value of this report is as a reference document for readers who require a complete presentation of the technical. [1] E. Boiten, H. Bowman, J. Derrick and M. Steen ''Cross Viewpoint Consistency in Open Distributed Processing (Intra Language Consistency)'', Technical Report, Computing Laboratory, University of Kent at Canterbury, report No. 8-95, 1995. Phone: +44 1227 827913, Fax: 44 1227 762811 Email: H.Bowman,E.A.Boiten,J.Derrick,mwas@ukc.ac.uk.

This document contains the first deliverable of a research project on `Cross Viewpoint Consistency in Open Distributed Processing', carried out at the Computing Laboratory of the University of Kent. Open Distributed Processing (ODP) is recognised as an important area of standardisation activity. The ODP model seeks to provide a standardised architecture for building potentially global distributed systems with components from many vendors. Thus, ODP will realise the open systems ethos in the distributed systems domain. A central concept in ODP is that of a viewpoint. Distributed systems are viewed to be so complex that a process of separation of concerns must be employed when describing such systems. Viewpoints provide such a separation of concerns by presenting five distinct views of a single system; these are the enterprise viewpoint, information viewpoint, computational viewpoint, engineering viewpoint and technology viewpoint. It should be clear that in such viewpoint models it is essential that specifications in different viewpoinmts are related in order to determine whether the muyltiple specifications impose conflicting requirements. The project being reported here responds to this need by investigating how to check that multiple viewpoint specifications are in some sense ''consistent''. The objective of the project is to assess the feasibility of cross viewpoint consistency checking for specifications written in Z and LOTOS. We aim to develop prototype tools and techniques for consistency checking in and between these two specification languages. This deliverable describes the initial phase of the project which has focused on consistency checking methods for individual formalisms. It also contains a fully general framework for consistency checking. Keywords: ODP, LOTOS, Z, consistency, formal methods, distributed systems, software engineering

Several descriptions of basically one transformation technique, viz. accumulation, are compared. Their basis, viz. the associativity and the existence of a neutral element inherent in a monoid, is identified.

Formal specifications that exhibit similarities will often have similar solutions. Thus, it is useful to construct generalized specifications that describe classes of problems, since (partial) solutions to the generalized problem can be used for obtaining solutions for the specific problems. In this paper we study a class of generalized pattern matching problems, in which the essential operation is the intersection of a particular set and a bag of extended substructures of a structured object. We present a formalization of bags of extended substructures and define the ISBES (Intersection of Sets and Bags of Extended Substructures) class of problems. Some example ISBES specifications are shown, and we present some first ideas about applicable program transformation strategies for ISBES problems. The second paper discusses conditions under which the non-standard specification mechanism of a bag comprehension may be safely used. The first paper has been published (/pubs/1991/161/) and included in my PhD thesis.

As an example of the transformational programming method, a previously unknown algorithm for calculating factorials is derived. The derivation is done by the unfold-fold strategy with transformation rules for changing the recursion structure of functions. These transformation rules ( inv.html and splitting recursion) are presented and explained. The derivation which proceeds from a system of linear recursive functions, via tail-recursive functions, to an efficient imperative program. The resulting program is, in our opinion, only intelligible by way of its derivation. It is also shown how a similar derivation leads to a version of the algorithm that may be executed on 2 processors. Technical Report 90-18, Dept. of Informatics, University of Nijmegen, 1990, revised version as chapter 3 in my PhD thesis. A shorter version appeared in Periodica Polytechnica Ser. El. Eng., 35(2):77-99, 1992, Copies available on request by mailto:E.A.Boiten@ukc.ac.uk.

A formal specification describes a problem to be solved on a high level - ideally, it specifies what has to be done, but not how. Such descriptive specifications facilitate the derivation of any of the possible solutions, whereas operational specifications suggest only particular ones. Formal derivations in this framework consist of semantics preserving transformations, i.e. steps that proceed from solutions to the initial specification to other, more defined, more operational, or more efficient ones. Thus, the resulting programs are correct by construction with respect to their initial specifications. This thesis contains a number of case studies aiming at the exploration of new territories in the area of program specification and transformation. /pubs/1992/159/''Improving recursive functions by inverting the order of evaluation'' gives a comprehensive survey of one particular transformation strategy (a larger conceptual step in a transformational development that can be described at a more abstract level). This strategy for recursive functions entails the derivation of equivalent functions that use in their recursive evaluations the same arguments in an inverted order. This is an important optimization strategy, in particular for tree-like recursive functions, that are often defined in such a way that several function calls need to be evaluated more than once. By evaluating the function in an inverted order, such multiple evaluations are eliminated. /pubs/1990/165/ ''Factorization of the factorial'', illustrates a number of the transformations in chapter 2, and also demonstrates the state of the art in recursion simplification transformations. Directed by a small set of simple and well-known heuristics, a previously unknown algorithm for computing factorials is derived. Also, a similar development is shown leading to a corresponding program for a simple pipeline architecture. /pubs/1991/162/ ''A note on similarity of specifications and reusability of transformational developments'', written together with http://www.informatik.uni-ulm.de/pm/mitarbeiter/helmuth.html , explores the possibilities of reuse of transformational developments. Although it has often been claimed that this could be done fully mechanically, the experience with a number of derivations in this chapter indicates that this claim is somewhat preposterous. Only by describing the transformation steps in a very abstract way (using just natural language) and by considering very general specifications, can the developments be reused. The central concept is similarity, and several definitions of this informal notion are given, each leading to a particular kind of reuse of derivations. Variants of a derivation of linear search lead to several interesting search algorithms, culminating in derivations by reuse of two complicated string matching algorithms. /pubs/1991/161/ ''Intersections of sets and bags of extended substructures - a class of problems'', generalizes the specification of pattern matching. It describes a class of problems that can be viewed as a generalization of pattern matching problems. The essence of pattern matching is considered to be the intersection of a particular set with a bag (multiset) of extended substructures of a structured object. The set contains the patterns, the extended substructures are possible occurrences, extended with labels that mark their positions in the original object. This leads to the first ideas on an (interesting) theory on (extended) substructures. It is shown how the abstract description of this class of problems lends itself to calculation in a BMF style. Also, clearly exhibiting the basic structure of such problems facilitates connecting them with various solution strategies. /pubs/1991/156/ ''Solving a combinatorial problem by transformation of abstract data types'', gives an application of techniques from the area of formal program development in a different area, viz. combinatorics. By describing a given combinatorial problem in terms of abstract data types with equivalences, and transforming those data types, a reduction to a known problem is obtained. Abstract data types proved to be a more suitable specification mechanism in this case than context free grammars, since arbitrary equivalences could be introduced on the data types.