In data refinement, a concrete data type replaces an abstract data type used in the design of an algorithm or system (Gries and Prins, 1985; Hoare, 1972; Jones, 1980). We present two methods for calculating the weakes...
详细信息
In data refinement, a concrete data type replaces an abstract data type used in the design of an algorithm or system (Gries and Prins, 1985; Hoare, 1972; Jones, 1980). We present two methods for calculating the weakest specification of each operation on a concrete data type from the specification of the corresponding abstract operation, together with a single simulation relation (Milner, 1980; Park, 1981), which specifies the correspondence between the two types. The methods are proved sound and (jointly) complete for a nondeterministic procedural programming language slightly more powerful than Dijkstra's (1976). Operations (in general, nondeterministic) are represented by relations, and significant use is made of prespecification and postspecification (Hoare and He, Jifeng, 1987).
A generalization of Dijkstra's weakest precondition, called the weakest prespecification, is presented. The increase in generally is obtained at the cost of some increase in complexity, which can be justified only...
详细信息
A generalization of Dijkstra's weakest precondition, called the weakest prespecification, is presented. The increase in generally is obtained at the cost of some increase in complexity, which can be justified only when it is needed. Suggestions for the design and development of correct programs are obtained from this approach.
Program transformation is used to develop the alpha-beta pruning algorithm from a specification of minimaxing. The pruning algorithm is nontrivial, and yet the transformation turns out to be relatively straightforward...
详细信息
Program transformation is used to develop the alpha-beta pruning algorithm from a specification of minimaxing. The pruning algorithm is nontrivial, and yet the transformation turns out to be relatively straightforward. The exercise is regarded as providing yet more evidence of the importance of transformational techniques, both for producing efficient programs and explaining them.
The Distributed computing Software project at Oxford University is using formal spécification techniques to explore the design of services in a distributed operating system. Our goal is to construct and publish t...
详细信息
This paper reports experience gained in applying formal specification techniques to an existing transaction processing system. The system is the IBM Customer Information Control System (CICS) and the work has concentr...
详细信息
This paper reports experience gained in applying formal specification techniques to an existing transaction processing system. The system is the IBM Customer Information Control System (CICS) and the work has concentrated on specifying a number of modules of the CICS application programmer's interface.
We study 2- and 3-dimensional digital geometry in the context of almost arbitrary adjacency relations. (Previous authors have based their work on particular adjacency relations). We define a binary digital picture to ...
详细信息
We study 2- and 3-dimensional digital geometry in the context of almost arbitrary adjacency relations. (Previous authors have based their work on particular adjacency relations). We define a binary digital picture to be a pair whose components are a set of lattice-points and an adjacency relation on the whole lattice. We show how a wide class of digital pictures have natural “continuous analogs.” This enables us to use methods of continuous topology in studying digital pictures. We are able to prove general results on the connectivity of digital borders, which generalize results that have appeared in the literature. In the 3-dimensional case we consider the possibility of using a uniform relation on the whole lattice. (In the past authors have used different types of adjacency for “object” and “background.”)
Functional programmers often use higher order functions such as map, reduce and filter in writing programs. By giving such higher order functions geometric as well as behavioural interpretation, we use similar techniq...
详细信息
暂无评论