Performance preorder and competitive equivalence

DOI10.1007/S002360050107MaRDI QIDQ678252zbMATH OpenOpenAlexFDO

Authors Flavio Corradini, Roberto Gorrieri, Marco Roccetti

Publication date 11 September 1997

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s002360050107

zbMATH Keywords

axiomatizations for finite agentscompetitive equivalenceconcurrencyimplementationinduced equivalenceparallelismperformance preorderprocess algebra with durational actionssemantics for process description languagesspecificationstepwise refinementstrong bisimulation equivalence

Mathematics Subject Classification ID

Partial orders, general (06A06) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Semantics in the theory of computing (68Q55) Specification and verification (program logics, model checking, etc.) (68Q60)

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.

Recommendations

• Performance preorder: ordering processes with respect to speed
• An efficiency preorder for processes
• An efficiency preorder for processes
• On efficiency preorders
• On performance congruences for process algebras

Cited in

(13)

• On performance congruences for process algebras
• An efficiency preorder for processes
• Faster asynchronous systems.
• Decidability of performance equivalence for basic parallel processes
• Bisimulation on speed: a unified approach
• On efficiency preorders
• Performance preorder: ordering processes with respect to speed
• Undecidability of performance equivalence of Petri nets
• An efficiency preorder for processes
• Bisimulation on speed: Lower time bounds
• Fast asynchronous systems in dense time
• On the semantics of durational actions
• Bisimulation on speed: Worst-case efficiency

This page was built for publication: Performance preorder and competitive equivalence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q678252)