We claim that in scenarios involving a human operator with responsibility over systems being monitored by diagnoser, presenting said operator with a concise set of observations capturing the essence of a failure improves the operators' understanding of the diagnosis. We take this in the context of Discrete Event Systems and demonstrate how the idea can be applied to systems utilising event-based observations, which can contain implicit information. We introduce the notion of an abstracted event stream, called a sub-observation, that makes the implicit information explicit for the operator and allows a diagnoser to arrive at the same diagnosis. We call the most abstract of these the critical observation. We provide relevant definitions, properties, and a procedure for computing the critical observation in a diagnosis problem.
Diagnosis problems are concerned with the detection and identification of occurrences of specific events in a system, generally called faults or failures. These occurrences are difficult to detect as the fault events are typically not directly observable, however, they can be inferred from the system model (a description of the system behaviour) and the observations produced by the system.
Diagnosis is the first step in the fault recovery process. Once a fault has been detected and identified, the appropriate actions can be taken to mitigate its effects. The issue, however, is that this procedure acts as a black box; given a model and a sequence of observations, a diagnoser asserts a fault by claiming that there is no possible nominal execution of the system that would produce the observation sequence.
The present work is written under the assumption that a diagnosis procedure is fundamentally built for a human operator in charge of taking actions after a fault is identified. In this scenario, a black box approach does not allow for the presentation of the information relevant to the diagnosis. We assume that providing the operators with explanatory evidence is useful in convincing them of the validity of the diagnosis, in addition to providing information as to the causes of the fault.
Further, we assume that a more concise explanation is strictly preferred to more verbose explanation, and consequently that there is merit to isolating the “smallest” amount of supporting evidence, or what we call the critical observations. In cognitive psychology, the seminal paper on the topic of working memory in humans supports this view, giving the average working memory capacity as 7 ± 2 distinct pieces of information [1]. Providing only the observations critical to the diagnosis also has the additional benefit of ameliorating privacy concerns in systems where privacy is considered important.
We extend the results of Christopher et al. [2] to eventbased observations. We first present preliminary theory and notation, before going on to show that event-based observations contain implicit information. We then introduce what we call sub-observations that can capture this implicit information and make it available for use in diagnosis procedures. We then provide formal definitions of sufficiency and criticality in addition to several important properties that allow for a terminating algorithm. We present an algorithm for computing the critical observation and discuss its complexity. A discussion of alternate ways of defining subobservations precedes a brief discussion of related work and a conclusion. 2
The present work takes place in the context and standard framework of discrete event systems (DES) [3]. We denote as Σ the set of events that can take place on the system. A system run is a finite sequence of events, w = e1e2 . . . ek, and the system is modeled as the prefix-closed language LM ⊆ Σ⋆ that represents all possible runs.
The set of events is partitioned into observable events Σo—events that are recorded—and unobservable events Σu—those that are not. The observation o generated by run w = e1e2 . . . ek, hereafter called the trace of w, is the projection of w on the set of observable events (i.e., all unobservable events of the run are deleted): o = PΣo (w) = ( ε e1PΣo (e2 . . . ek) PΣo (e2 . . . ek) if k = 0 if k > 0 and e1 ∈ Σo otherwise.
The observed language of a trace o, denoted Lo, is the set of finite sequences of events that could produce the observed sequence: Lo = PΣ−o1(o) = { w ∈ Σ⋆ | PΣo (w) = o} . The set of unobservable events includes a subset of fault events, Σf ⊆ Σu. With slight abuse of notation we write f ∈ w as short for w ∈ Σ⋆f Σ⋆ (or “f appears in w”) and F ∩ w as short for { f ∈ F | f ∈ w} (or “the subset of events from F that appear in w”).
A set δ ⊆ Σf of faults is consistent with the model LM and the trace o if there exists a run w ∈ LM that would produce this trace (PΣo (w) = o) and that exhibits exactly these faults (w ∩ Σf = δ). The diagnosis of trace o, denoted Δ(o), is the collection of all consistent sets of faults: Δ(o) = δ ⊆ Σf ∃w ∈ LM.
PΣo (w) = o ∧ δ = w ∩ Σf (1)
Hereafter we use the hat notation (ˆ ) to indicate that the given symbol represents what actually occurred. Given a run wˆ, δˆ = wˆ ∩ Σf is the set of faults that occurred during the run; then the following result is trivial: wˆ ∈ LM ⇒ δˆ ∈ Δ(PΣo ( wˆ)). (The premise, completeness of the model, is assumed.)
We find it more convenient to define the diagnosis in terms of emptiness of languages. Let Lδ be the language that represents all sequences that contain exactly δ: Lδ = { w ∈ Σ⋆ | w∩Σf = δ} = \ Σ⋆f Σ⋆∩
\ (Σ\{ f } )⋆ f∈δ f∈Σf\δ
That is, Lδ represents the set of all runs containing all of the faults of δ, intersected with all possible runs where the faults not in δ never occur—the result is a set of all runs where the only faults that occur are those in δ. With Lδ defined, we can equivalently express the diagnosis as an emptiness of languages problem: δ ∈ Δ(o) ⇐⇒ LM ∩ Lo ∩ Lδ 6= ∅. (2) 3
We first discuss event-based observations, and in particula r that event-based observations contain implicit informati on that must be taken into consideration when performing diagnosis. We then introduce the notion of sub-observations , providing formal definitions and an explanatory example. Once this has been established, a procedure is given for diagnosing with sub-observations. 3.1
Event-based diagnosis, contrasted with state-based diagn osis, comes with a subtlety; specifically, there is a type of implicit information encoded in the trace. Take for example the repeated observation of a window being closed without there ever being an observation of the window opening; in this case, the fact that we never observed an open event is distinctly relevant to a diagnosis procedure.
To further illustrate this, we provide a simple abstract example in the form of a DES: Take Σ = { a, b, c, d, e, f1, f2} , with Σo = { a, b, c, d, e} , Σu = Σf = { f1, f2} . We provide the system model in the form of a NFA in Figure 1 and consider some example traces over it: o1 = abababc. The model specifies that f2 must have occurred in strings containing a followed by c. In this case, the intervening sequence is long (babab), and could be much longer. The important information, however, is that a was at some point followed by c. Reporting in some abstract sense start 1 8 a { b, e} 2 4 { a, d} b a f1 3 5 c f2 that a was followed by c is enough to convince an operator of the correctness of the diagnosis. o2 = ababaa. The model specifies that f1 must have occurred for there to be two a events that are not separated by another observable event. More specifically, the lack of an intervening event is the crucial piece of information that determines the fault. In this case, reporting in some abstract sense that multiple a occurred consecutively is enough to indicate the fault convincingly. 1. A sub-observation , θ, is an abstraction over a trace that represented an intentional relaxation (or weakening) of the concrete knowledge contained in the trace. 2. O is the space of possible sub-observations. 3. The symbol is a binary relation and partial order over O and relates two sub-observations θ, θ′ such that θ′ θ iff θ′ is a more abstracted form of θ. 4. sub is an injective function, mapping traces to maximal (w.r.t. ) sub-observations θ ∈ O:
sub : Σo∗ → O A sub-observation θ implicitly represents the set of traces for which it is a more abstract form of: ψ(θ) = { o ∈ Σo∗ | θ sub(o)} Therefore, θ′
θ ⇒ ψ(θ′) ⊇ ψ(θ).
The language of a sub-observation, denoted Lθ, represents the set of all possible runs θ could represent. However, these runs are already captured by Lo, and so Lθ can be expressed as the union of the languages of the traces it is a more abstract form of:
Lθ =
[ event in the system. A soft event is a subset of observable events, y ⊆ Σo, that any number (including zero) of which may have occurred along with any number of unobservable events.
We now explicitly characterize our construction of subobservations based on the general framework presented in Definition 1: Definition 2 A sub-observation, θ, is a strict time-ordered alternating sequence of soft and hard events, commencing and ending with a soft event: θ = y0x1y1 . . . xnyn. We denote O(o) the space of sub-observations for a given trace o. θ ∈ O has length | θ| = n. For readability, sub-observations may occasionally be written as a comma separated list. The language of θ can then also be expressed:
Lθ = (y0 ∪ Σu)∗x1(y1 ∪ Σu)∗ . . . xn(yn ∪ Σu)∗ By way of example, take the sub-observation θ = ({ b, d} , a, ∅, c, { a} ) – in this case, we say the singleton events x1 = a and x2 = c are hard and occurred in the specified order. The first soft event, y0 = { b, d} , represents the possibility of any number of b or d events in any order having occurred before the first hard event – similarly, y1 = ∅ indicates that no events occurred between the hard events x1 and x2, and y2 = { a} that any number of a events could have occurred after the final hard event. There are multiple traces oˆ that this could represent, ac being the simplest, but traces such as ddacaa or bac, or indeed up to infinite (or bounded length depending) other possibilities.
Definition 3 The function sub generates a sub-observation in O from a given trace by inserting empty soft events at the head of the trace, and after every hard event:
For o = e1 . . . en sub(o) = ∅x1∅ . . . xn∅ ∈ O
Where ∀i : xi = ei Definition 4 The relation over O is defined such that θ′ θ if and only if there exists a mapping function f : Given | θ′| = n, | θ| = m f : { 0, . . . , n + 1} → { 0, . . . , m + 1} such that f (i) < f (i + 1), f (0) = 0, f (n + 1) = m + 1 x′i = xf(i) yi′ ⊇
In words: θ′ θ if there exists some f that maps the hard events in θ′ to an equivalent sequence in θ, retaining the time-ordering of both, and each yi′ in θ′ captures the union of all intervening events – yj (inclusive) and xj (exclusive), for j ranging between f (i) and f (i + 1) − 1.
For example take θ = ({ ac} , b, { cd} , a, { c} , d, { c} , a, ∅) and θ′ = ({ abcd} , a, { bcd} , a, ∅). The hard events in θ′ are matched to x2 and x4 in θ, and each yi′ “swallows” the other information. Specifically, f (1) = 2, f (2) = 4, satisfies the constraints for θ′ θ. This is illustrated in Figure 2.
To summarize, a sub-observation, in a practical sense, can be thought of as a relaxation of the information presented in the original trace. By including soft events in the subobservation, we are allowing for the “hiding” (abstraction) of events such that an operator can be presented with only the most relevant information. { ac} b { cd} a { c} d { c} a ∅ { abcd} a { bcd} a ∅ We now formalize the usage of sub-observations in a diagnosis procedure by extending the procedure introduced for event-based diagnosis presented in § 2. This involves checking the consistency of a set of possible faults.
We therefore provide the construction of the diagnosis of θ, Δ(θ), the set of faults consistent with a given subobservation: Definition 5 The diagnoses of a sub-observation θ is the union of the diagnoses of the traces for which θ is the more abstract form of, represented by ψ(θ) as given in Definition 1: Δ(θ) =
Δ(o)
From Definition 5 we note that, given δˆ ∈ Δ(oˆ), that if θ sub(oˆ) then δˆ ∈ Δ(θ). That is, the actual diagnosis δˆ of the actual trace oˆ, will by definition be in Δ(θ) if θ is an abstraction of oˆ.
First, we observe the following lemma: Lemma 3.1 The possible traces permitted by the language of a more abstracted sub-observation strictly contains all the permitted traces of all its ascendants: θ′ θ =⇒ Lθ ⊆ Lθ ′ Proof This is a direct consequence of Equation 3
Equation 2 provided a formulation of the diagnosis as a question of emptiness in the intersection of languages – that is, is there some run that is simultaneously possible according to the system model, the observations, and the faults that occurred during the run. This can similarly be extended to a similar question for sub-observations. As Lθ is defined in Definition 2, then Δ(θ) can be equivalently extended: Δ(θ) ≡ { δ | L M ∩ Lδ ∩ Lθ 6= ∅} (4)
Definition 5 and Equation 4 provide a formal definition and a characterization of the diagnosis of a sub-observatio n, but do not specify how to implement the procedure, in particular given that ψ(θ) may be infinitely large.
The scientific literature is rich in works dealing with
abstract traces. These approaches were developed to handle
situations where observations can be lost [4]; sensors can
fail [5; 4]; the order between observations may be only
partially known [6; 4; 7; 8]; the observability can vary [
It is possible to interpret Equation 4 quite literally—build
three finite-state machines representing all three languag es
LM, Lδ, and Lθ, synchronize them, and verify emptiness.
Similarly, this emptiness verification can be reduced to a
planning problem [10; 11] or a model-checking one [
When the model is represented by a finite-state machine,
the specific definition of sub-observations makes it possibl e
to solve the problem by tracking the belief state (the set of
states that the system could be in) after each soft and hard
event in the sub-observation. Assuming the system state
incorporates the diagnosis information, then the diagnosis
can be inferred from the belief state at the end of the
subobservation. This procedure can be used on-line [
The primary objective of this work is to compute a minimal sub-observation that preserves the assertiveness of th e diagnosis: a critical observation. We first give a formal definition of this notion, followed by a discussion of some relevant properties and a procedure for computing the critical observation. 4.1
We say a sub-observation is sufficiently precise if it allows us to infer a given diagnosis: Definition 6 Given a diagnosis D, a sub-observation θ is sufficient to prove D if Δ(θ) = D. Given a trace oˆ, a subobservation θ sub(oˆ) is sufficient for oˆ if Δ(θ) = Δ(oˆ).
A corollary of Definition 5 gives us Δ(θ) ⊇ Δ(oˆ). As previously noted, abstracting away details to produce a subobservation sacrifices some information about the system behavior—sufficiency, then, is the property that this information loss did not affect the diagnosis by making feasible other potential diagnoses: Δ(θ) \ Δ(oˆ) = ∅ (5)
Our goal, then, is to return a sub-observation that is sufficient for the actual trace, oˆ. By Definitions 1, and 5, we see that the na¨ıve sub-observation, sub(oˆ), satisfies the criteria to be sufficient for oˆ, and means that at least one solution can be found: Δ(sub(oˆ)) =
Δ(o) = Δ(oˆ)
Given two sub-observations θ and θ′, a human operator will, from our initial assumptions, better understand and assimilate a diagnosis with θ′ if θ′ is more abstract than θ. We therefore search for a “most abstract”, or critical, subobservation, defined as follows: Definition 7 Given a trace oˆ, a sub-observation θ sub(oˆ) is critical for oˆ if it is sufficient for oˆ and there is no strict sub-observation of θ that is also sufficient: ∀θ′ ∈ O. (θ′
θ) ∧ (Δ(θ′) = Δ(oˆ)) ⇒ (θ′ = θ) . (6)
A critical sub-observation (more simply called a critical observation) is therefore a sufficient sub-observation tha t cannot be abstracted more without damaging (complicating) the precision of the diagnosis.
As is only a partial order, it is possible that there could be several critical sub-observations. For instance, using the example in Figure 1, both θ1 = ΣocΣoaΣo (the system emitted a c and later an a) and θ2 = (Σo \ { a} )dΣoaΣo (the system emitted anything bar an a, then a d and later an a) are critical observations for the trace oˆ = cda. 4.2
We now outline a procedure for computing a critical observation for a given problem. We rely on two fundamental properties: the finiteness of the set of sub-observations of interest, and the monotonicity of sufficiency.
Lemma 4.1 (Finiteness) Given a trace oˆ, the set O(oˆ) of sub-observations of oˆ ({ θ ∈ O | θ sub(oˆ)} ) is finite. Proof This can be demonstrated by the fact that, by definition of , the length of a sub-observation of oˆ must be equal to or smaller than that of oˆ. This can only decrease until | θ| = 1, at which point the set is exhausted.
Lemma 4.2 (Monotonicity) Given a trace oˆ and two subobservations θ1, θ2 such that θ1 θ2 sub(oˆ), if θ1 is sufficient for oˆ, then so is θ2.
Proof This is a straightforward consequence of the fact that ψ(θ1) ⊇ ψ(θ2).
Monotonicity guarantees that there is no unreachable “island” of sufficient sub-observations.
Finiteness provides us three decisive properties: One— that there always exists at least one critical observation (infinite domains can prevent the existence of minimal elements; e.g., there is no minimal real number strictly greater than 0), Two—that for any sufficient sub-observation θ, there exists a critical observation that is a sub-observation of θ (possibly θ itself), Three—the depth of a critical observation (the maximal number k of different sub-observations θi such that θ θ1 · · · θk sub(oˆ)) is finite.
As a consequence of these properties, as soon as a sufficient sub-observation θ is found the search for a critical observation can be limited to the set of sub-observations of θ (we call this a greedy approach). Another consequence of the above is that we can define a search algorithm that can find a sufficient, strict sub-observation of a given subobservation (or return that no such sub-observation exists ), that is guaranteed to terminate.
Finally, monotonicity together with finiteness, provides a practical characterization of criticality: a sufficient subobservation θ is critical if and only if none of its children (defined next) are sufficient.
Definition 8 A child of sub-observation θ is a strict subobservation θ′ of θ such that no sub-observation sits “between” θ′ and θ. θ′ ∈ children(θ) ⇐⇒ (θ′ ≺ θ) ∧ (∄θ′′ ∈ O. θ′ ≺ θ′′ ≺ θ) .
If, on the other hand, we find that one child of θ is sufficient, then, according to the greedy approach described previously, we can iteratively check criticality of this child.
The set of children for our definition of sub-observation is readily computable. We can prove that the children of a subobservation are exactly the sub-observations obtained by a pplying one of two operations which we will now define: the event-softening operation and the collapse operation. Definition 9 Given a sub-observation θ = y0x1 . . . xkyk, the event-softening operation θ′ = es(θ, i, e) adds event e to the ith soft event of the sub-observation: es(θ, i, e) = y0′x′1 . . . x′kyk′ (defined if e 6∈ yi) such that • ∀ j ∈ { 1, . . . , k} . x′j = xj , • ∀ j ∈ { 0, . . . , k} \ { i} . yj′ = yj , and • yi′ = yi ∪ { e} . Procedure FINDCRITICALOBSERVATION input: trace oˆ; output: critical observation diag := Δ(oˆ) θ := sub(oˆ) candidates := children(θ) while candidates 6= ∅ do θ′ := pop(candidates) if Δ(θ′) = diag then θ := θ′ candidates := children(θ) end if end while return θ Definition 10 Given a sub-observation θ = y0x1 . . . xkyk, the collapse operation θ′ = coll(θ, i) “forgets” the concrete occurrence of a hard event xi. This operation requires the soft events before and after xi to be equal and to allow for xi: coll(θ, i) = y0′x′1y1′ . . . x′k−1yk′−1 (defined if xi ∈ yi and yi−1 = yi) such that • ∀ j ∈ { 1, . . . , i − 1} . x′j = xj and yj′−1 = yj−1 and • ∀ j ∈ { i + 1, . . . , k} . x′j−1 = xj and yj′−1 = yj . • yi′−1 = yi−1 = yi Lemma 4.3 The children of a sub-observation θ are exactly all the sub-observations that can be obtained by applying either event-softening or collapse to θ. (See appendix for proof).
An algorithm for finding a critical observation is given in Figure 3. Starting from θ = sub(oˆ), the algorithm verifies whether any child of θ is sufficient. If this is the case, then θ is replaced with this child and the verification continues iteratively.
Theorem 4.4 Algorithm FINDCRITICALOBSERVATION always terminates and returns a critical observation.
This theorem is a direct consequence of the properties derived from the finiteness of O(sub(oˆ)) and the monotonicity of the property, as described before. 4.3
We now discuss the difficulty of finding a critical observation, defined in term of the number of Δ(· ) calls. Let n = | oˆ| be the length of oˆ (the number of observed events) and let m = | Σo| be the number of observable events.
The maximal depth, D, of a sub-observation, namely that of θ0 = { Σo} , is provably D = (n + 1) m + n: It is reached by softening m times each of the n + 1 soft events followed by collapsing the n hard events. Furthermore each sub-observation (of length k ≤ n), can be shown to have a bounded number of children, C, as given by Definition 8: At worst each soft event can be softened in any one of m ways ((k + 1)m), and a potentially up to k hard events can be collapsed, giving C = (k + 1) m + k, which we see is the same as D.
Consequently, the maximum number of Δ(· ) calls of Algorithm FINDCRITICALOBSERVATION is bounded by D × C, and therefore in O(n2m2). It can even be shown that, for some traces, a na¨ıve implementation may indeed call the diagnoser a number of times in Θ(n2m2) with different subobservations every time (see appendix for proof).
Fortunately it is possible to reduce this number drastically with heuristics. Indeed it is generally possible to prove that some children of θ′ are not sufficient simply because some children of the parent of θ′ were proven not sufficient, thus pruning the search tree significantly.
Consider for instance the sub-observation θ = a b a a∅ in the example of Figure 1 (with diagnosis: fault ∅ ∅ ∅ ∅ f1). The softening by b of the soft event y3 = ∅ between x3 = x4 = a leads to a sub-observation ( ∅a∅b∅a{ b} a∅) that is not sufficient, as the nominal diagnosis N becomes possible. Consider now the sub-observation θ′ = Σoa∅aΣo of θ. We can deduce automatically that the softening of y1′ = ∅ by b in θ′ leads to a non sufficient sub-observation, simply because the mapping function f of Definition 4 associates y1′ with y3.
It is therefore possible to “carry over” to the children of any sub-observation the information regarding which softening and collapse operations complicate the diagnosis and reduce precision. By doing so, the number of necessary calls provably drops to Θ(nm). 5
Other Definitions of SubO-bservations In this article we presented one definition of sub-observati on that, by no means, is the only viable one. We briefly discuss a few possible variants and then present the necessary elements that the reader would need to consider to use another definition.
In many circumstances the order between certain
observed facts is irrelevant. In the example of Figure 1, the
occurrence of both c and a, in any order, is symptomatic of
fault f2. Reminiscent of chronicles [
The hard events are currently defined as a single specific observable event; one could alter the definition to allow for it could be replaced by a set of events. Indeed in the example of Figure 1, a fault can be diagnosed when observing either c or d before e. A reason for not distinguishing c from d in this specific scenario is that these events could represent the same message emitted by different components, or different messages emitted by the same component: the exact emitter of the message or the exact content may be irrelevant to diagnose the fault. This is similar to logical uncertainty in observations [4].
One more elaborate abstraction could be to use first-order representations. For instance, a fault may be identified by demonstrating that some user who was to be explicitly refused access to some data was actually given access to that data; the identity of the actual user may be irrelevant.
To apply the theory presented in this paper to a different definition of sub-observations, one needs to define the sub-observation space as given in Definition 1, i.e., the set of sub-observations O, the partial order relation , and an inductive sub function that associates each observation with an equivalent maximal sub-observation in O. This also needs to be additionally equipped with a procedure to compute Δ(θ). Algorithm FINDCRITICALOBSERVATION is guaranteed to return a critical observation if the subobservation space is finite and if the children function exists and is specified.
We demonstrate a scenario where these conditions may not be satisfied: Assume that the set of observable events is infinite with each observable event associated with a rational number (modeling some continuous property, e.g., temperature). A natural abstraction would replace each event by a closed interval where the value associated with the event lies (the wider the interval, the most abstract the observation). There could, however, be no maximal interval in a situation where the relevant information about the observation is that the temperature measure is strictly positive. Furthermore, there is no notion of child in this particular sub-observati on space since Q is a dense set. Special attention must therefore be taken when defining new types of sub-observations. 6
Finding critical observations is a different issue from
optimizing sensor placement [
Consider again the trace o = abaa in the example of Figure 1 whose critical observation is θ = Σoa∅aΣo. Consider the question of whether the first observable event of the trace is a c. The sub-observation θ does not provide this information since it is not necessary to infer the diagnosis. A dynamic observer however, has to check this information because it is necessary to dismiss fault f2.
There has also been work on abstraction of event-based
observations, as mentioned at the end of section 3. The
subsumption ( ) between uncertain or partial observations has
been studied by Lamperti et al. [
In this work we defined a notion of critical observations for the diagnosis of discrete event systems. A critical observation is a maximally abstracted observation that allows only the same diagnosis to be inferred as was from the complete observation. Critical observations are beneficial in that they contain the core proof that supports the diagnosis. An important assumption of this work is that more abstract observations are easier for a human operator to understand and act on; an important extension will be to minimize the amount of information from the model—and not only from the observations—necessary to infer the diagnosis.
We also want to be able to handle incremental and
online diagnosis. Currently we assume that the critical
observation is extracted once the diagnosis has been performed;
however observations that are not critical for a given trace
might become critical when more observations are produced
by the system. We would like to identify as early as
possible what abstraction of the currently received observations
can be safely made without impairing the future diagnosis.
Kurien and Nayak tried to address a similar problem [
Critical observations are also good at reducing the amount
of information disclosed about the system behaviour. In
future work we want to explore this line of research and, in
particular, examine the problem of finding sub-observation s
that satisfy a privacy criterion, for instance, one defined by
opacity [
We provide proof sketches that will not be included in the final version of the paper.
a) proving that the event-softening operation produces only children; b) proving that the collapse operation produces only children;
Event-Softenings It is easy to see that θ2 es(θ1, i, e) ≺ θ1.
Assume now that θ2 θ3 θ1 and let f23 and f31 be the two mapping functions—as presented in Definition 4—used to verify the two ordering relations. | θ2B|y=de| fiθn1|iti(obny odfefin,it|iθo2n| ≤of | eθv3e|n≤t-so| ftθe1n| i.ngH),owtheevesirzseinocfe all three sub-observations are equal and f23 = f31 are the identity function.
As a consequence, xj3 = xj2 = xj1 for all j. Furthermore yj2 ⊇ yj3 ⊇ yj1 for all j. In particular, if j 6= i, since yj2 = yj1, then yj3 = yj2 = yj1. For i, yi2 = yi1 ∪ { e} , meaning that either yi3 = yi2 or yi3 = yi1.
Therefore either θ3 = θ2 or θ3 = θ1. def = Collapse Similarly, it is easy to see that θ2 coll(θ1, i) ≺ θ1.
Again assume that θ2 θ3 θ1 and let f23 and f31 be the functions defined as before.
The size of θ3 now either equals that of θ2 or θ1; let ℓ ∈ { 1, 2} denote the index such that | θ3| = | θℓ| . Notice that either f23 or f31 is the identity function. def = allow us to infer that yj3 = yjℓ for all j.
Therefore θ3 = θℓ.
By definition of , we know that xj3 = xjℓ . Furthermore the set inclusions as well as the relations between yj2 and yk1 No Other Children Assume now that θ′ is a child of θ that cannot be obtained by event-softening or collapse. Let f be the mapping function used to verify the ordering relation.
By definition of the partial order , the size of θ′ is smaller or equal to θ.
If | θ′| < | θ| (“multiple collapse”), then let i be an index such that f (i + 1) > f (i)+ 1 (such an index exists if the two sizes differ). If yi+1\yi 6= ∅, then let θ′′ = es(θ, i, e) (where e ∈ yi+1 \ yi) be the sub-observation obtained by softening yi with e; then, θ′ ≺ θ′′ ≺ θ. Similarly if yi ⊇ yi+1 with θ′′ = es(θ, i + 1, e) (where e ∈ yi \ yi+1). Lastly the same applies if yi = yi+1 with θ′′ = coll(θ, i).
If θ and θ′ have same size, then all x′ s equal the cori responding xis, and all the y′s are supersets of the corre
i sponding yis. Let i be an index such that yi′ 6= yi (if no such index exists, then θ′ = θ). Let θ′′ = es(θ, i, e) where e ∈ yi′ \ yi. Then θ′ ≺ θ′′ ≺ θ.
Complexity of FINDCRITICALOBSERVATION We show that the number of Δ(· ) calls in FINDCRITICALOBSERVATION could be in the order of n24m2 where n is the length of the trace and m the number of observable events.
4 c f start 1 A
A b c
A 2 b c 3
Clearly the trace reveals a faulty system since the number of cs exceeds the number of bs in this instance. The critical observation here is:
Σoa1{ c} b{ c} c{ c} . . . { c} b{ c} c{ c} cΣo, i.e., all the second half of the trace needs to be kept.
We assume that FINDCRITICALOBSERVATION always tries to perform event-softening from the end of the subobservation first, and only tries to collapse when no softening is possible. Neglecting the first steps where the c softenings are successful, the algorithm will need to make U = n2 × (m − 1) calls to Δ(· ), unsuccessfully trying to softening the second half of the sub-observation. The number of successful softenings however is S = n2 × m (all the first half of the sub-observation), meaning that the number of Δ(· ) calls will be at least U × S = n2m(4m−1) calls.
Proceedings of the 26th International Workshop on Principles of Diagnosis 126