Performance preorder and competitive equivalence
type: Item
instance of: scholarly article
title: Performance preorder and competitive equivalence
zbMATH Open document ID: 0878.68081
author: Flavio Corradini
author: Roberto Gorrieri
author: Marco Roccetti
published in: Acta Informatica
publication date: 1997-09-11T00:00:00Z
review text: A preorder based on execution speed, called performance preorder, is introduced for a simple process algebra with durational actions. Two processes \(E\) and \(F\) are related -- \(E\sqsubseteq_p F\) -- if they have the same functionality (in this case, we have chosen strong bisimulation equivalence) and \(E\) is at least as fast as \(F\). Hence, this preorder supports the stepwise refinement ``from specification to implementation'' by increasing efficiency while retaining the same functionality. We show that the problem of finding faster implementations for a specification is connected to the problem of finding more distributed implementations of the same specification. Both performance preorder and the induced equivalence, called competitive equivalence, are provided with sound and complete axiomatizations for finite agents.
Mathematics Subject Classification ID: 68Q55
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 68Q60
zbMATH DE Number: 1000550
zbMATH Keywords: semantics for process description languages
zbMATH Keywords: parallelism
zbMATH Keywords: concurrency
zbMATH Keywords: performance preorder
zbMATH Keywords: process algebra with durational actions
zbMATH Keywords: strong bisimulation equivalence
zbMATH Keywords: stepwise refinement
zbMATH Keywords: specification
zbMATH Keywords: implementation
zbMATH Keywords: induced equivalence
zbMATH Keywords: competitive equivalence
zbMATH Keywords: axiomatizations for finite agents
MaRDI profile type: Publication
full work available at URL: s002360050107
OpenAlex ID: W2010241460
DOI: 10.1007/S002360050107
description: scientific article; zbMATH DE number 1000550