The Complexity of Codiagnosability for Discrete Event and Timed Systems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

The Complexity of Codiagnosability for Discrete Event and Timed Systems

Résumé

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.
Fichier principal
Vignette du fichier
atva-10.pdf (167.54 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00493640 , version 1 (21-06-2010)

Identifiants

  • HAL Id : inria-00493640 , version 1

Citer

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. ⟨inria-00493640⟩
28 Consultations
108 Téléchargements

Partager

Gmail Facebook X LinkedIn More