Unfolding-based Diagnosis of Systems with an Evolving Topology

Paolo Baldan 1 Thomas Chatain 2, 3 Stefan Haar 2, 3 Barbara König 4
3 MEXICO - Modeling and Exploitation of Interaction and Concurrency
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : We propose a framework for model-based diagnosis of systems with mobility and variable topologies, modelled as graph transformation systems. Generally speaking, model-based diagnosis is aimed at constructing explanations of observed faulty behaviours on the basis of a given model of the system. Since the number of possible explanations may be huge we exploit the unfolding as a compact data structure to store them, along the lines of previous work dealing with Petri net models. Given a model of a system and an observation, the explanations can be constructed by unfolding the model constrained by the observation, and then removing incomplete explanations in a pruning phase. The theory is formalised in a general categorical setting: constraining the system by the observation corresponds to taking a product in the chosen category of graph grammars, so that the correctness of the procedure can be proved by using the fact that the unfolding is a right adjoint and thus it preserves products. The theory thus should be easily applicable to a wide class of system models, including graph grammars and Petri nets.
Type de document :
Communication dans un congrès
van Breugel, Franck and Chechik, Marsha. Proceedings of the 19th International Conference on Concurrency Theory (CONCUR'08), 2008, Toronto, Canada, Canada. Springer, 5201, pp.203-217, 2008, 〈10.1007/978-3-540-85361-9_19〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00638300
Contributeur : Stefan Haar <>
Soumis le : vendredi 4 novembre 2011 - 15:00:54
Dernière modification le : jeudi 14 juin 2018 - 10:54:02

Lien texte intégral

Identifiants

Collections

Citation

Paolo Baldan, Thomas Chatain, Stefan Haar, Barbara König. Unfolding-based Diagnosis of Systems with an Evolving Topology. van Breugel, Franck and Chechik, Marsha. Proceedings of the 19th International Conference on Concurrency Theory (CONCUR'08), 2008, Toronto, Canada, Canada. Springer, 5201, pp.203-217, 2008, 〈10.1007/978-3-540-85361-9_19〉. 〈inria-00638300〉

Partager

Métriques

Consultations de la notice

190