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
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
4 SUMO - SUpervision of large MOdular and distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
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 Connect in order to contact the contributor
Submitted on : Wednesday, January 2, 2013 - 6:36:04 PM
Last modification on : Wednesday, April 27, 2022 - 4:11:55 AM
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