No Cover Image

Conference Paper/Proceeding/Abstract 505 views

Modular bisimulation theory for computations and values / Martin Churchill; Peter Mosses

FOSSACS: Foundations of Software Science and Computation Structures, Volume: 7794, Pages: 97 - 112

Swansea University Author: Peter, Mosses

Full text not available from this repository: check for access using links below.

Abstract

For structural operational semantics (SOS) of process algebras, various notions of bisimulation have been studied, together with rule formats ensuring that bisimilarity is a congruence. For programming languages, however, SOS generally involves auxiliary entities (e.g. stores) and computed values, a...

Full description

Published in: FOSSACS: Foundations of Software Science and Computation Structures
ISSN: 0302-9743 1611-3349
Published: Berlin Springer 2013
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa14363
Tags: Add Tag
No Tags, Be the first to tag this record!
Abstract: For structural operational semantics (SOS) of process algebras, various notions of bisimulation have been studied, together with rule formats ensuring that bisimilarity is a congruence. For programming languages, however, SOS generally involves auxiliary entities (e.g. stores) and computed values, and the standard bisimulation and rule formats are not directly applicable.Here, we first introduce a notion of bisimulation based on the distinction between computations and values, with a corresponding liberal congruence format. We then provide metatheory for a modular variant of SOS (MSOS) which provides a systematic treatment of auxiliary entities. This is based on a higher order form of bisimulation, and we formulate an appropriate congruence format. Finally, we show how algebraic laws can be proved sound for bisimulation with reference only to the (M)SOS rules defining the programming constructs involved in them. Such laws remain sound for languages that involve further constructs.
Item Description: Lecture Notes in Computer Science
College: College of Science
Start Page: 97
End Page: 112