Book contents
- Frontmatter
- Contents
- Preface
- Contributors
- 1 The Complexity of Algorithms
- 2 Building Novel Software: the Researcher and the Marketplace
- 3 Prospects for Artificial Intelligence
- 4 Structured Parallel Programming: Theory meets Practice
- 5 Computer Science and Mathematics
- 6 Paradigm Merger in Natural Language Processing
- 7 Large Databases and Knowledge Re-use
- 8 The Global-yet-Personal Information System
- 9 Algebra and Models
- 10 Real-time Computing
- 11 Evaluation of Software Dependability
- 12 Engineering Safety-Critical Systems
- 13 Semantic Ideas in Computing
- 14 Computers and Communications
- 15 Interactive Computing in Tomorrow's Computer Science
- 16 On the Importance of Being the Right Size
- References
- Index
9 - Algebra and Models
Published online by Cambridge University Press: 10 December 2009
- Frontmatter
- Contents
- Preface
- Contributors
- 1 The Complexity of Algorithms
- 2 Building Novel Software: the Researcher and the Marketplace
- 3 Prospects for Artificial Intelligence
- 4 Structured Parallel Programming: Theory meets Practice
- 5 Computer Science and Mathematics
- 6 Paradigm Merger in Natural Language Processing
- 7 Large Databases and Knowledge Re-use
- 8 The Global-yet-Personal Information System
- 9 Algebra and Models
- 10 Real-time Computing
- 11 Evaluation of Software Dependability
- 12 Engineering Safety-Critical Systems
- 13 Semantic Ideas in Computing
- 14 Computers and Communications
- 15 Interactive Computing in Tomorrow's Computer Science
- 16 On the Importance of Being the Right Size
- References
- Index
Summary
Summary
Science makes progress by constructing mathematical models, deducing their observable consequences, and testing them by experiment. Successful theoretical models are later taken as the basis for engineering methods and codes of practice for design of reliable and useful products. Models can play a similar central role in the progress and practical application of computing science.
A model of a computational paradigm starts with choice of a set of potential direct or indirect observations that can be made of a computational process. A particular process is modelled as the subset of observations to which it can give rise. Process composition is modelled by relating observations of a composite process to those of its components. Indirect observations play an essential role in such compositions. Algebraic properties of the composition operators are derived with the aid of the simple theory of sets and relations. Feasibility is checked by a mapping from a more operational model.
A model constructed as a family of sets is easily adapted as a calculus of design for total correctness. A specification is given by an arbitrary set containing all observations permitted in the required product. It should be expressed as clearly as possible with the aid of the full power of mathematics and logic. A product meets a specification if its potential observations form a subset of its permitted observations. This principle requires that all envisaged failure modes of a product are modelled as indirect observations, so that their avoidance can be proved. Specifications of components can be composed mathematically by the same operators as the components themselves. This permits top-down proof of correctness of designs even before their implementation begins. Algebraic properties and reasoning are helpful throughout development.
- Type
- Chapter
- Information
- Computing TomorrowFuture Research Directions in Computer Science, pp. 158 - 187Publisher: Cambridge University PressPrint publication year: 1996
- 3
- Cited by