IEEE Transactions on Systems Man and Cybernetics Systems · 2022 · 12 citations · 25 references
ComputingComputer EngineeringComputer ScienceFault-tolerant ComputingFault-tolerant SystemsReal-time SystemsAutomata TheoryDiscrete-event System ModelingFault DetectionFault DiagnosisDiagnosabilityDiscrete-event ModelingDiscrete-event SystemsFault Occurrence Modeling
This article investigates diagnosability and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula> -diagnosability for discrete-event systems modeled by unambiguous max-plus automata (UMPAs). More precisely, diagnosability requires that the occurrence of any fault can be detected within a finite number of events after the fault has occurred. <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula> -diagnosability requires that the occurrence of any fault can be detected within a delay of at most <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula> time units after its occurrence. First, we propose a polynomial-time algorithm based on the construction of a nondeterministic finite automaton over a weighted alphabet for diagnosability verification of a UMPA. Second, we prove that <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula> -diagnosability of a UMPA can be studied by reducing it to the problem of diagnosability. Third, we introduce an approach to calculate the upper on the time needed for detecting fault occurrence for a diagnosable UMPA, and its complexity is of sixth order in the number of states of the UMPA.
25
Rajeev Alur, David L. Dill · Theoretical Computer Science · 1994 · 6.5K citations
Diagnosability of discrete-event systems
Meera Sampath, Raja Sengupta, Stéphane Lafortune et al. · IEEE Transactions on Automatic Control · 1995 · 1.6K citations