Prespecification in data refinement
type: Item
instance of: scholarly article
title: Prespecification in data refinement
zbMATH Open document ID: 0624.68027
DOI: 10.1016/0020-0190(87)90224-9
author: Tony Hoare
author: Jifeng He
author: Jeff W. Sanders
published in: Information Processing Letters
publication date: 1987-01-01T00:00:00Z
review text: In data refinement, a concrete data type replaces an abstract data type used in the design of an algorithm or system. 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, 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 \textit{E. W. Dijkstra}'s [A discipline of programming (Englewood Cliffs 1976; Zbl 0368.68005)]. Operations (in general, nondeterministic) are represented by relations, and significant use is made of prespecification and postspecification [\textit{C. A. R. Hoare} and \textit{J. He}, Ann. Soc. Math. Polon., Ser. IV, Fundam. Inf. 9, 51-84 (1986; Zbl 0603.68009)].
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 4014014
zbMATH Keywords: data refinement
zbMATH Keywords: concrete data type
zbMATH Keywords: abstract data type
zbMATH Keywords: weakest specification
zbMATH Keywords: nondeterministic procedural programming language
zbMATH Keywords: prespecification
zbMATH Keywords: postspecification
MaRDI profile type: Publication
full work available at URL: 0020-0190(87)90224-9
OpenAlex ID: W2152198540
cites work: Programming as a Discipline of Mathematical Nature
cites work: Q3713577
cites work: Proof of correctness of data representations
cites work: The weakest prespecification
cites work: Q3859249
cites work: A calculus of communicating systems
cites work: Non-deterministic data types: Models and implementations
cites work: Q3907077
description: scientific article; zbMATH DE number 4014014