Skip to main content

Relational Concurrent Refinement II: Internal Operations and Outputs

Boiten, Eerke Albert, Derrick, John, Schellhorn, Gerhard (2008) Relational Concurrent Refinement II: Internal Operations and Outputs. Formal Aspects of Computing, 21 (1-2). pp. 65-102. ISSN 0934-5043. (doi:10.1007/s00165-007-0066-z) (KAR id:14524)

PDF Author's Accepted Manuscript
Language: English
Click to download this file (393kB) Preview
[thumbnail of rcrioo.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL:


Two styles of description arise naturally in formal specification: state-based and behavioural. In state-based notations, a system is characterised by a collection of variables, and their values determine which actions may occur throughout a system history. Behavioural specifications describe the chronologies of actions -- interactions between a system and its environment. The exact nature of such interactions is captured in a variety of semantic models with corresponding notions of refinement; refinement in state based systems is based on the semantics of sequential programs and is modelled relationally. Acknowledging that these viewpoints are complementary, substantial research has gone into combining the paradigms. The purpose of this paper is to do three things. First, we survey recent results linking the relational model of refinement to the process algebraic models. Specifically, we detail how variations in the relational framework lead to relational data refinement being in correspondence with traces-divergences, singleton failures and failures-divergences refinement in a process semantics. Second, we generalise these results by providing a general flexible scheme for incorporating the two main ''erroneous'' concurrent behaviours: deadlock and divergence, into relational refinement. This is shown to subsume previous characterisations. In doing this we derive relational refinement rules for specifications containing both internal operations and outputs that corresponds to failures-divergences refinement. Third, the theory has been formally specified and verified using the interactive theorem prover KIV.

Item Type: Article
DOI/Identification number: 10.1007/s00165-007-0066-z
Additional information: Accepted for publication
Uncontrolled keywords: Data refinement, Z, simulations, process algebraic semantics,
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: Eerke Boiten
Date Deposited: 24 Nov 2008 18:04 UTC
Last Modified: 16 Nov 2021 09:52 UTC
Resource URI: (The current URI for this page, for reference purposes)
Boiten, Eerke Albert:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.