Briscoe-Smith, C. (2000) Behavioural Subtyping in Process Algebra. PhD thesis, University of Kent at Canterbury.
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.
|Item Type:||Thesis (PhD)|
|Uncontrolled keywords:||process algebra; formal methods; formal specification; LOTOS; RM-ODP|
|Subjects:||Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,|
|Divisions:||Faculties > Science Technology and Medical Studies > School of Computing > Theoretical Computing Group|
|Depositing User:||Mark Wheadon|
|Date Deposited:||13 Sep 2009 18:33|
|Last Modified:||09 May 2012 08:58|
|Resource URI:||http://kar.kent.ac.uk/id/eprint/21936 (The current URI for this page, for reference purposes)|
- Depositors only (login required):