Briscoe-Smith, C. (2020) Behavioural Subtyping in Process Algebra. Doctor of Philosophy (PhD) thesis, University of Kent at Canterbury. (doi:10.22024/UniKent/01.02.21936) (KAR id:21936)
Other (zp)
Other
Language: English
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
|
|
Download this file (Other/455kB) |
![]() |
Official URL: https://doi.org/10.22024/UniKent/01.02.21936 |
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.
Item Type: | Thesis (Doctor of Philosophy (PhD)) |
---|---|
DOI/Identification number: | 10.22024/UniKent/01.02.21936 |
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: | Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing |
Depositing User: | Mark Wheadon |
Date Deposited: | 13 Sep 2009 18:33 UTC |
Last Modified: | 10 Dec 2021 23:09 UTC |
Resource URI: | https://kar.kent.ac.uk/id/eprint/21936 (The current URI for this page, for reference purposes) |
- Link to SensusAccess
- Export to:
- RefWorks
- EPrints3 XML
- BibTeX
- CSV
- Depositors only (login required):