When are Timed Automata Weakly Timed Bisimilar to Time Petri Nets?

Abstract : We study sensor minimization problems in the context of fault diagnosis. Fault diagnosis consists in synthesizing a diagnoser that observes a given plant and identifies faults in the plant as soon as possible after their occurrence. Existing literature on this problem has considered the case of fixed static observers, where the set of observable events is fixed and does not change during execution of the system. In this paper, we consider static observers where the set of observable events is not fixed, but needs to be optimized (e.g., minimized in size). We also consider dynamic observers, where the observer can ``switc'' sensors on or off, thus dynamically changing the set of events it wishes to observe. It is known that checking diagnosability (i.e., whether a given observer is capable of identifying faults) can be solved in polynomial time for static observers, and we show that the same is true for dynamic ones. On the other hand, minimizing the number of (static) observable events required to achieve diagnosability is NP-complete. We show that this is true also in the case of mask-based observation, where some events are observable but not distinguishable. For dynamic observers' synthesis, we prove that a most permissive finite-state observer can be computed in doubly exponential time, using a game-theoretic approach. We further investigate optimization problems for dynamic observers and define a notion of cost of an observer. We show how to compute an optimal observer using results on mean-payoff games by Zwick and Paterson.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2008, 403 (2--3), pp.202--220
Liste complète des métadonnées

https://hal.inria.fr/inria-00363024
Contributeur : Franck Cassez <>
Soumis le : vendredi 20 février 2009 - 00:42:38
Dernière modification le : vendredi 31 août 2018 - 09:25:53
Document(s) archivé(s) le : mardi 8 juin 2010 - 22:44:16

Fichier

BCHLR-tcs08.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00363024, version 1

Citation

Béatrice Bérard, Franck Cassez, Serge Haddad, Didier Lime, Olivier Henri Roux. When are Timed Automata Weakly Timed Bisimilar to Time Petri Nets?. Theoretical Computer Science, Elsevier, 2008, 403 (2--3), pp.202--220. 〈inria-00363024〉

Partager

Métriques

Consultations de la notice

226

Téléchargements de fichiers

111