Skip to Main content Skip to Navigation

Scenario realizability with constraint optimization

Rouwaida Abdallah 1 Arnaud Gotlieb 1, 2, 3 Loïc Hélouët 4 Claude Jard 1, 5
1 DISTRIBCOM - Distributed and Iterative Algorithms for the Management of Telecommunications Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
2 CELTIQUE - Software certification with semantic analysis
IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL, Inria Rennes – Bretagne Atlantique
4 SUMO - SUpervision of large MOdular and distributed systems
IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL, Inria Rennes – Bretagne Atlantique
Abstract : This work considers implementation of requirements expressed as High-level Message Sequence Charts (HMSCs). All HMSCs are not implementable, and the question of whether an HMSC speci cation can be implemented by communicating machines is undecidable in general. However, several subclasses such as local HMSCs can be implemented using a simple projection operation. This paper proposes a new technique to transform an arbitrary HMSC speci cation into a local HMSC, hence allowing implementation.We show that this transformation can be automated as a constraint optimization problem. The impact of modi cations brought to the original speci cation can be minimized w.r.t. a cost function. The approach was evaluated on a large number of randomly generated HMSCs. The results of this experimentation are presented and analyzed. In particular, the evaluation shows an average runtime of a few seconds, which demonstrates applicability of the technique.
Document type :
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Rouwaida Abdallah <>
Submitted on : Wednesday, January 2, 2013 - 6:36:04 PM
Last modification on : Tuesday, June 15, 2021 - 4:16:10 PM
Long-term archiving on: : Wednesday, April 3, 2013 - 3:49:04 AM


Files produced by the author(s)


  • HAL Id : hal-00769656, version 1


Rouwaida Abdallah, Arnaud Gotlieb, Loïc Hélouët, Claude Jard. Scenario realizability with constraint optimization. [Research Report] 2013. ⟨hal-00769656⟩



Record views


Files downloads