Back to search

University of Southampton

Performance-Oriented Refinement

Abstract

dc:description.abstract

We introduce the probabilistic action system formalism which combines refinement with performance. Performance is expressed by means of probability and expected costs. Probability is needed to express uncertainty present in physical environments. Expected costs express physical or abstract quantities that describe a system. They encode the performance objective. The behaviour of probabilistic action systems is described by traces of expected costs. Corresponding notions of refinement and simulation-based proof rules are introduced. Formal notations like B or action systems support a notion of refinement. Refinement relates an abstract specification AA to a more deterministic concrete specification CC. Knowing AA and CC one proves CC refines, or implements, specification AA. In this study we consider specification AA as given and concern ourselves with a way to find a good candidate for implementation CC. To this end we classify all implementations of an abstract specification according to their performance. The performance of a specification AA is a value val.AA associated with some optimal behaviour it may exhibit. We distinguish performance from correctness. Concrete systems that do not meet the abstract specification are excluded. Only the remaining correct implementations CC are considered with respect to their performance. A good implementation of a specification is identified by having some optimal behaviour in common with it. In other words, a good refinement corresponds to a reduction of non-optimal behaviour. This also means that the abstract specification sets a boundary val.AA for the performance of any implementation. An implementation may perform worse than its specification but never better. Probabilistic action systems are based on discrete-time Markov decision processes. Numerical methods solving the optimisation problems posed by Markov decision processes are well-known, and used in a software tool that we have developed. The tool computes an optimal behaviour of a specification AA, and the associated value val.AA, thus assisting in the search for a good implementation CC. We present examples and case studies to demonstrate the use of probabilistic action systems.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
2001

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hallerstede, Stefan

Rights

Language dc:language.dcterms_iso639_2
eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Hallerstede, Stefan. Performance-Oriented Refinement. doctoral thesis, University of Southampton, 2001.