We extend correctness and refinement reasoning methods in order to show how angelic nondeterminism can be systematically transformed into demonic nondeterminism or determinism. This kind of transformation is important because angelic nondeterminism assumes that an agent interested in establishing the postcondition will resolve the choices intelligently. When angelic nondeterminism is reduced into demonic nondeterminism or determinism, such intelligent choices are no longer necessary. Reducing angelic nondeterminism is generally not a refinement; however, when context is taken into consideration, it can be a correctness-preserving transformation.

Abstract We show how a parallel composition of action systems can be refined by refining the components separately, and checking non-interference against invariants and guarantee conditions, which are abstract and stable. The guarantee condition can be thought of as a very abstract specification of how a system affects the global state, and it allows us to show that an action system refinement is valid in a given environment, even if we do not know any of the details of that environment. The paper extends the traditional notion of action systems slightly, and it makes use of a generalisation of the attribute model for program variables.

An experiment with distance technology in a second-year Object-Oriented Systems Design course is described. Video and computer conferencing were used in tutorial sessions where a teacher and a student group developed and discussed solutions (both textual and graphical) to systems design problems. The experiment is evaluated, both from a technical, an economic and an educational point of view.

Abstract. Subtype polymorphism, based on syntactic conformance of objects' methods and used for substituting subtype objects for supertype objects, is a characteristic feature of the object-oriented programming style. While certainly very useful, typechecking of syntactic conformance of subtype objects to supertype objects is insufficient to guarantee correctness of object substitutability. In addition, the behaviour of subtype objects must be constrained to achieve correctness. In class-based systems classes specify the behaviour of the objects they instantiate. In this paper we define the class refinement relation which captures the semantic constraints that must be imposed on classes to guarantee correctness of substitutability in all clients of the objects these classes instantiate. Clients of class instances are modelled as programs making an iterative choice over invocation of class methods, and we formally prove that when a class C ′ refines a class C , substituting instances of C ′ for instances of C is refinement for the clients.

Abstract. Data refinement is the systematic replacement of a data structure with another one in program development. Data refinement between program statements can on an abstract level be described as a commutativity property where the abstraction relationship between the data structures involved is represented by an abstract statement (adecoding). We generalise the traditional notion of data refinement by defining anencoding operatorthat describes the least (most abstract) data refinement with respect to a given abstraction. We investigate the categorical and algebraic properties of encoding and describe a number of special cases, which include traditional notions of data refinement. The dual operator of encoding isdecoding, which we investigate and give an intuitive interpretation to. Finally we show a number of applications of encoding and decoding.

We consider the notion of a contract that governs the behavior of a collection of agents. In particular, we study the question of whether a group among these agents can achieve a given goal by following the contract. We show that this can be reduced to studying the existence of winning strategies in a two-person game. We define a weakest precondition semantics for contract statements that permits us to compute the initial states from which a group of agents has a winning strategy to reach their goal. This semantics generalizes the traditional predicate transformer semantics for program statements to contracts and games. Ordinary programs and interactive programs are special kinds of contracts. A notion of correctness and refinement is introduced for contracts. Contracts are shown to form a complete lattice with respect to the refinement ordering.

Abstract We propose a new format for writing proofs, called structured calculational proof . The format resembles the calculational style already familiar to many computer scientists, but extends it to allow the hierarchical decomposition of larger proofs into smaller ones. Structured calculation is actually an alternative presentation of natural deduction, a style of reasoning which uses hierarchical decomposition to great effect, but which is traditionally expressed in a notation that is inconvenient for writing calculational proofs. The hierarchical nature of structured calculational proofs can be used for browsing proofs in electronic publications.

We describe an embedding of higher order logic in the HOL theorem proving system. Types, terms, sequents and inferences are represented as new types in the logic of the HOL system, and notions of proof and provability are defined. Using this formalisation, it is possible to reason about the correctness of derived rules of inference and about the relations between different notions of proofs. The formalisation is also intended to make it possible to reason about programs that handle proofs as their data (e.g., proof checkers).

Abstract A theory of commands with weakest precondition semantics is formalised using the HOL proof assistant system. The concept of refinement between commands is formalised, a number of refinement rules are proved and it is shown how the formalisation can be used for proving refinements of actual program texts correct.