The Complexity of Codiagnosability for Discrete Event and Timed Systems

Details The Complexity of Codiagnosability for Discrete Event and Timed Systems The Complexity of Codiagnosability for Discrete Event and Timed Systems

2010-04-15

arxiv.org/abs/1004.2550v1

Computer Science

Formal Languages and Automata Theory

24 pages.

Scientific paper

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. Finally we address the codiagnosis problem for TA under bounded resources and show it is 2EXPTIME-complete.

Affiliated with

Also associated with

No associations

Rating

The Complexity of Codiagnosability for Discrete Event and Timed Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Complexity of Codiagnosability for Discrete Event and Timed Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Codiagnosability for Discrete Event and Timed Systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-379495