Resilience in Discrete Event Systems

International audience; This paper explores the notion of resilience of a fault in a DES, as the ability to spontaneously return to a normal behavior, without leaking information about this fault occurrence to an external observer. Resilience expresses some form of insensitivity or robustness, related but different from classical notions like diagnosability or opacity. Different definitions of resilience are examined, expressed in terms of recovery points or of language relations. It is shown that verifying resilience is PSPACE-complete. However, the complexity reduces to PTIME for the recently introduced history deterministic automata, a sub-class of NFA. We examine in detail the instructive pathway to this complexity reduction, which could be instrumental for the complexity reduction of other DES problems.