The complexity of codiagnosability for discrete event and timed systems

Franck Cassez*

*Corresponding author for this work

Research output: Contribution to journalArticle

25 Citations (Scopus)

Abstract

In this paper, we study the fault codiagnosis problem for discrete event systems given by finite automata (FA) and timed systems given 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. We then generalize the previous results to the case of dynamic observers. Finally we show that the codiagnosis problem for TA under bounded resources is 2EXPTIME-complete.

Original languageEnglish
Article number6125230
Pages (from-to)1752-1764
Number of pages13
JournalIEEE Transactions on Automatic Control
Volume57
Issue number7
DOIs
Publication statusPublished - 2012
Externally publishedYes

Keywords

  • Discrete-event systems
  • fault diagnosis
  • timed automata

Fingerprint Dive into the research topics of 'The complexity of codiagnosability for discrete event and timed systems'. Together they form a unique fingerprint.

  • Cite this