© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Behavioural Subtyping in Process Algebra
Charles Peter Briscoe-Smith
PhD thesis, University of Kent at Canterbury, Canterbury, UK, November 2000.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.
Download publication 444 kbytesBibtex Record
@phdthesis{1184, author = {Charles Peter Briscoe-Smith}, title = {Behavioural Subtyping in Process Algebra}, month = {November}, year = {2000}, pages = {182-196}, keywords = {determinacy analysis, Craig interpolants}, note = {}, doi = {}, url = {http://www.cs.kent.ac.uk/pubs/2000/1184}, publication_type = {phdthesis}, submission_id = {13144_983789781}, school = {University of Kent at Canterbury}, address = {Canterbury, UK}, }