Abstract | ||
---|---|---|
We consider the verification of the properties of diagnosability and codiagnosability in discrete event systems where observations are dynamic. Instead of having a fixed set of observable events, it is assumed that the observability properties of an event are state-dependent: an event occurrence at a state will be observable to a diagnosing agent if that agent activates in time the sensor corresponding to the event or receives a communication about the occurrence of the event. In this context, the known polynomial-complexity tests based on verifier automata for the properties of diagnosability and codiagnosability with fixed observable event set(s) are no longer directly applicable. We develop a new testing procedure that can handle state-based dynamic observations and remains of polynomial complexity in the state space of the system. This new testing procedure employs a covering of the state space of the system based on cluster automata, which enhances its computational efficiency. Based on cluster automata, a new type of verifier automaton is built, called the C-VERIFIER. Our use of cluster automata and C-VERIFIERS also yields computational savings in the special case of fixed observable event sets. |
Year | Venue | Keywords |
---|---|---|
2009 | Control Conference | automata theory,computational complexity,discrete event systems,multi-robot systems,observability,polynomials,sensors,state-space methods,c-verifier,cluster automata,codiagnosability verification,computational efficiency,diagnosing agent,fixed observable event set,observability properties,polynomial-complexity test,sensor,state space,state-based dynamic observations,testing procedure,verifier automata,automata,testing,indexes |
Field | DocType | ISBN |
Observability,Automata theory,Observable,Polynomial,Automaton,Theoretical computer science,Polynomial complexity,State space,Mathematics,Special case | Conference | 978-3-9524173-9-3 |
Citations | PageRank | References |
2 | 0.43 | 11 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Weilin Wang | 1 | 62 | 7.29 |
Girard, A.R. | 2 | 2 | 0.43 |
StéPhane Lafortune | 3 | 1738 | 181.23 |
Feng Lin | 4 | 426 | 56.30 |