Equivalences and Refinement

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We investigate equivalence notions for concurrent systems. We consider “linear time” approaches where the system behaviour is characterised as the set of possible runs as well as “branching time” approaches where the conflict structure of systems is taken into account. We show that the usual interleaving equivalences, and also the equivalences based on steps (multisets of concurrently executed actions) are not preserved by refinement of actions. We prove that “linear time” partial order semantics, where causality in runs is explicit, is invariant under refinement. Finally, we consider various bisimulation equivalences based on partial orders and show that the strongest one of them is preserved by refinement whereas the others are not.

Original languageEnglish
Title of host publicationSemantics of Systems of Concurrent Processes: LITP Spring School on Theoretical Computer Science, La Roche Posay, France, April 23–27, 1990 Proceedings
EditorsI. Guessarian
Number of pages25
ISBN (Electronic)978-3-540-46897-4
ISBN (Print)978-3-540-53479-2
Publication statusPublished - 28 Nov 1990
EventThe 1990 LITP Spring School on Theoretical Computer Science - La Roche Posay, France
Duration: 23 Apr 199027 Apr 1990

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin, Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


OtherThe 1990 LITP Spring School on Theoretical Computer Science
CityLa Roche Posay


Dive into the research topics of 'Equivalences and Refinement'. Together they form a unique fingerprint.

Cite this