Unfolding-based Diagnosis of Systems with an Evolving Topology

Paolo Baldan 1 Thomas Chatain 2 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 should hence be easily applicable to a wide class of system models, including graph grammars and Petri nets.
Type de document :
Article dans une revue
Information and Computation, Elsevier, 2010, 10, pp.1169-1192. 〈10.1016/j.ic.2009.11.009〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

Contributeur : Stefan Haar <>
Soumis le : vendredi 4 novembre 2011 - 11:49:19
Dernière modification le : jeudi 14 juin 2018 - 10:54:02
Document(s) archivé(s) le : dimanche 5 février 2012 - 02:21:53


Fichiers produits par l'(les) auteur(s)




Paolo Baldan, Thomas Chatain, Stefan Haar, Barbara König. Unfolding-based Diagnosis of Systems with an Evolving Topology. Information and Computation, Elsevier, 2010, 10, pp.1169-1192. 〈10.1016/j.ic.2009.11.009〉. 〈inria-00638204〉



Consultations de la notice


Téléchargements de fichiers