The Complexity of Codiagnosability for Discrete Event and Timed Systems
Author:
- 6 January 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 57 (7) , 1752-1764
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.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- The Complexity of Codiagnosability for Discrete Event and Timed Systems2010
- Fault Diagnosis Using Timed Automata2005
- Polynomial-time verification of diagnosability of partially observed discrete-event systemsIEEE Transactions on Automatic Control, 2002
- Fault Diagnosis for Timed Automata2002
- Is your model checker on time? On the complexity of model checking for timed modal logicsThe Journal of Logic and Algebraic Programming, 2002
- A polynomial algorithm for testing diagnosability of discrete-event systemsIEEE Transactions on Automatic Control, 2001
- Diagnosability of discrete-event systemsIEEE Transactions on Automatic Control, 1995
- A theory of timed automataTheoretical Computer Science, 1994
- The control of discrete event systemsProceedings of the IEEE, 1989
- Modular Feedback Logic for Discrete Event SystemsSIAM Journal on Control and Optimization, 1987