The Complexity of Codiagnosability for Discrete Event and Timed Systems

Abstract : In this paper we study the fault codiagnosis problem for discrete event systems given by finite automata (FA) and timed systems gi\-ven by timed automata (TA). We provide a uniform characterization of codiagnosability for FA and TA which extends the necessary and sufficient condition that characterizes diagnosability. We also settle the complexity of the codiagnosability problems both for FA and TA and show that codiagnosability is PSPACE-complete in both cases. For FA this improves on the previously known bound (EXPTIME) and for TA it is a new result. Finally we address the codiagnosis problem for TA under bounded resources and show it is 2EXPTIME-complete.
Type de document :
Communication dans un congrès
Int. Symp. on Automated Technology for Verification and Analysis (ATVA'10), Sep 2010, Singapore, Singapore. 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00493640
Contributeur : Franck Cassez <>
Soumis le : lundi 21 juin 2010 - 06:06:33
Dernière modification le : lundi 21 juin 2010 - 08:27:59
Document(s) archivé(s) le : lundi 22 octobre 2012 - 12:35:55

Fichier

atva-10.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00493640, version 1

Citation

Franck Cassez. The Complexity of Codiagnosability for Discrete Event and Timed Systems. Int. Symp. on Automated Technology for Verification and Analysis (ATVA'10), Sep 2010, Singapore, Singapore. 2010. 〈inria-00493640〉

Partager

Métriques

Consultations de la notice

60

Téléchargements de fichiers

42