Back to search

University of Kent

Behavioural subtyping in process algebra

Abstract

dc:description.abstract

Subtyping relations embody a notion of substitutability, and are an important tool in formal methods. The downward simulation relation is well-known and widely used as a subtyping and refinement relation for state-based approaches, but there is no single relation which is widely accepted to be the subtyping relation for the behavioural setting; however, there are several candidate relations. Developments such as the multi-viewpoint specification method of RM-ODP encourage the use of several different formal methods in a single project. Thus, it becomes important to obtain implementations of a single notion of subtyping in several different paradigms. In this thesis, we attempt to find a process algebraic relation which corresponds to the state-based subtyping relation, downward simulation. While trying to achieve this, we define a translation between a state-based notation and a process algebra, and we uncover some of the similarities and differences between these two specification paradigms. In particular, we investigate the meaning of undefined behaviour in each setting. When a state-based specification does not define an operation, the intent is that the system's behaviour is unspecified (not well-defined) if that operation is invoked. In a process algebra with refusals semantics, however, a process is implicitly specified to refuse any action it is not specified to accept, and such a refusal constitutes well-defined behaviour. As part of our translation, we devise a method of representing the unspecified behaviour of the state-based world in a process definition. Finally, we use our translation to prove that the presence of subtyping between a pair of state-based specifications implies reduction between their LOTOS translations, but that the presence of reduction does not imply subtyping. We conclude that reduction itself does not correspond to state-based subtyping, but that any relation which does must be based on a stronger semantics than reduction, such as bisimulation semantics.

Degree

thesis:*
Name dc:type.qualificationname
phd
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Kent
Year dc:date.issued
2000

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Briscoe-Smith, C

Subjects

dc:subject × 2

Rights

Language dc:language
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
University of Kent
Base URL
kar.kent.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Briscoe-Smith, C. Behavioural subtyping in process algebra. doctoral thesis, University of Kent, 2000. https://kar.kent.ac.uk/86205/1/Behavioural_Subtyping_in_Process_Algebra.gz