Diagnosis is defined as the process of detecting an abnormality/failure/fault in the system’s intended performance or behavior and isolating its cause or source.

Diagnosability is the ability of the system's model to detect and locate the faulty states in a finite number of steps.

From the conceptual view-point , existing methods of failure diagnosis can be categorized as :

  • Fault-tree based methods  : Fault trees give a graphical representation of cause-effect relationships of faults in a system. A fault tree is constructed by backward reasoning from the system failure to basic or primal failures that represent the root cause of the failure.
  • Quantitative, analytical model-based: It comprises of two major steps:
(a) generation of residuals and
(b) decision and fault isolation.

In the first step, residual signals are generated by comparing predicted values of system variables (from mathematical models of the system) with the actual observed values. These signals are near zero under normal working conditions and get accentuated on occurrences of failures.
In the second step, the residuals are examined for the likelihood of faults.

  • Expert systems and other knowledge-based : Considerable knowledge is acquired/accumulated to formulate the necessary set of heuristic rules for reliable diagnosis.This method is highly domain dependent
  • Model-based reasoning: The fundamental paradigm of this approach, is that of observation and prediction. These methods use a general purpose model of the structure and behaviour of the system built using AI(artificial intelligence) techniques like predicate logic, frames, constraints, and rules. The algorithms for diagnosis are also based on AI techniques, like theorem proving, heuristic search, constraint satisfaction and qualitative simulation.
  • Automata based: A timed automaton generates timed sequences of events – i.e. an alternating sequence of real-valued delays and events. The fault diagnosis involves identifying faulty behaviours from a given timed sequence of observable events of the system. There are two classes of such mechanisms, the class of deterministic timed automata (DTA) and the class of event-recording timed automata (ERA).
  • Petri nets based :Petri nets (PNs) have 2-way representation: graphical and mathematical.Also, the intrinsically distributed nature of PNs where the notion of state (i.e., marking) and action (i.e., transition) are localised, reduces the computational complexity of diagnostics.

Diagnosis approaches solve two types of problems namely: the diagnosis problem and diagnosability problem .
These two are commonly known as diagnosis on-line and diagnosis off-line, respectively, from their implementation viewpoint.

Diagnosability refers to the ability of fault location after a finite number of observations for any sequence (any behavior) of the system. Hence, to verify diagnosability we need to verify the ability to locate a fault after a finite number of observations for (most-likely) an infinite number of behaviors;
On the other hand, finding a solution to a diagnosis problem involves associating each observed string of events with a diagnosis state, such as “normal” or “faulty” or “uncertain".
In a discrete event model, states represent failure status of system components and events describe the tests and test results.Two types of diagnostic methods exist, namely: on-line diagnostics and offline diagnostics, depending on whether the system to be diagnosed is in normal operation or not.The main parameters related to diagnostics are controllability and observability.Diagnosing a system involves both system observation and sytem control.

To perform off-line diagnostics(i.e. system is in non-operating mode), the system is accessed, various tests conducted and responses measured that may not be available from the system outputs.During off-line diagnostics, the failure status of system components will not change unless such changes are made in purpose.The tests vectors can be flexibly designed and also the order of testing is not critical. In on-line diagnostics, the system to be diagnosed is in normal operating mode and hence it’s state changes constantly including those which cannot be prevented(uncontrollable).The responses/measurements available are limited to observed system outputs.Also the tests and the order in which the tests should be performed must be feasible from the current operating state

Discrete Event Model for Diagnostics

The system is modeled as a pair G=(M,∑c). M denotes a nondeterministic Mealy automaton:

M=(∑,S,Z,δ,h) where
∑ = set of finite events
S =set of states
Z = output space
δ: ∑ x S → 2S is state transition function
δ(σ,s) gives the set of possible next states if σ occurs at s
f : ∑ x S →Z is the output function
f(σ,s) is the observed output when σ occurs at s.

The second component ∑c ⊆ ∑ is the set of controllable events.
States of the system describe conditions of its components.Hence, to diagnose a failure is to identify which state or set of states the system belongs to.Thus depending on diagnostics requirements, the state space S can be partitioned into disjoint subsets(cells) and denote the desired partition by T. The state in the same cell are viewed as equivalent for failures under consideration.

Off-line diagnostics

For off-line diagnostics,events observed are assumed to be outputs,i.e.Z = ∑o , where ∑o ⊆∑ , is the set of observable events and the output map

f: ∑ x S → ∑o is defined as

f(σ,s) = σ if σ ∈ ∑o
ɛ otherwise,

where ɛ is the empty string.
In off-line diagnostics, all events are assumed to be controllable. Hence, ∑c = ∑ Since failure status of system components do not change, information derived from all the test outputs are updated and relevant.
During off-line diagnostic, if an event σ ∈ ∑o is observed , then possible state of system is S(σ) .Hence we know whether the system is in S(σ) or S - S(σ) state after observing σ .Thus, each observable event partitions the state space into:

Tσ = [S(σ) , S - S(σ)]

We can observe all observable events that are physically possible and determine which states the system is in.If this information is sufficient to detect the faulty component(i.e, which cell of T the system is in), then the system is off-line diagnosable.
The degree of diagnosability is another aspect that has to be dealt with analytically and mathematically.For reasons of simplicity, it is not dealt with in this article.

On-line diagnostics

During on-line diagnostics , not all events are controllable(i.e, can be initiated). Only events in ∑c can be initiated. We denote by ∑*c the set of all strings of events over ∑c , including the empty string ɛ.
A string u ∈ ∑*c is called a control.
For on-line diagnostics, we assume that M is a deterministic Moore automaton,

i.e, δ : ∑ x S →S is a deterministic map and f : S→ Z is the state output map.

We can add an extra state sd to S and define δ(σ,s) = sd. The map f is usually many to one i.e, the states may not be distinguishable from the outputs and diagnostics need to be performed.Since the failure status of system components may change during on-line diagnostics, only the current state output is updated and relevant.
The goal of diagnostics is to find which cell of T the system G belongs to by issuing a sequence of control
u ∈∑*c and observing the outputs.The expected output is inferred from behavior of G , which is described by all possible strings of events that can occur in G.
After a sequence of control u ∈∑*c is issued, the behavior of G is restricted because G must execute the events in u and also in the order given by u. Other events ∑ - ∑c may also occur , for they are not controllable. Hence, the behavior of G under control u is described by

B(u) = P-1{u}
Where P : ∑* → ∑*c is defined recursively as
Pɛ = ɛ
P(sσ) = Ps if σ ∉ ∑c
=(Ps) if σ ∈ ∑c

The initial state of G is from the state I⊆Q (or in worst case I = Q ).
To conclude, we can say that u diagnoses G w.r.t. T if, after executing u, which cell of T the current state of G belongs to can be determined by observing the current output of G.


  • Fault Diagnosis of DES is a mature scientific area
--established and well-recognized formal methods and models
  • Many extension of initial results: modeling tools, system structure, algorithmic efficiency, design methods
--but too many diagnosability notions & ad hoc algorithms to construct diagnosers & verify diagnosability
  • Complexity of calculations due to the curse of dimensionality
--Heuristics & abstractions to optimize the search space for diagnosability
  • Need to develop (software) tools
  • Need to combine DES based methods with techniques from:
--AI, PR & machine learning to provide practical diagnosis approaches for complex systems
--continuous systems to deal with hybrid system dynamics


  • Diagnosability of Discrete Event Systems and Its Applications by Feng Lin
  • Observability of Discrete Event Systems, by F.Lin ,W.M.Wonham
  • On Fault Diagnosis Methods of Discrete Event Systems,Janan Zaytoon,University of Reims Champagne Ardenne,France
  • A Discrete Event Systems Approach to Failure Diagnosis:Theory & Applications, Stéphane Lafortune ,Department of EECS,University of Michigan & Meera Sampath
  • Fault Diagnosis in Discrete-Event Systems:Incomplete Models and Learning,David L. Yeung, Raymond H. Kwong
  • Failure Diagnosis Using Discrete-Event Models,Meera Sampath, Student Member, IEEE, Raja Sengupta, Stephane Lafortune,. Member, IEEE,Kasim Sinnamohideen, Member, IEEE, and Demosthenis C. Teneketzis, Member, IEEE
  • Diagnosability of Discrete-Event Systems Meera Sampath, Raja Sengupta, StCphane Lafortune, Member, IEEE,Kasim Sinnamohideen, Member, IEEE, and Demosthenis Teneketzis, Member, IEEE
  • Automated Fault Diagnosis Using a Discrete Event Systems F’ramework ,Saqiiv Baviehi and Edwin K. P. Chong
This article uses material from the Wikipedia article A formal introduction to diagnosability of DES systems, that was deleted or is being discussed for deletion, which is released under the Creative Commons Attribution-ShareAlike 3.0 Unported License.
Author(s): הסרפד Search for "A formal introduction to diagnosability of DES systems" on Google
View Wikipedia's deletion log of "A formal introduction to diagnosability of DES systems"

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.