# diagnosis_of_deep_discreteevent_systems__e0d7498e.pdf

Journal of Artiﬁcial Intelligence Research 69 (2020) 1473-1532 Submitted 05/2020; published 12/2020

Diagnosis of Deep Discrete-Event Systems

Gianfranco Lamperti GIANFRANCO.LAMPERTI@UNIBS.IT Marina Zanella MARINA.ZANELLA@UNIBS.IT Department of Information Engineering, University of Brescia Via Branze 38, 25123 Brescia, Italy

Xiangfu Zhao XIANGFUZHAO@GMAIL.COM School of Computer and Control Engineering, Yantai University 30, Qingquan RD, Laishan District, Yantai 264005, China

An abduction-based diagnosis technique for a class of discrete-event systems (DESs), called deep DESs (DDESs), is presented. A DDES has a tree structure, where each node is a network of communicating automata, called an active unit (AU). The interaction of components within an AU gives rise to emergent events. An emergent event occurs when speciﬁc components collectively perform a sequence of transitions matching a given regular language. Any event emerging in an AU triggers the transition of a component in its parent AU. We say that the DDES has a deep behavior, in the sense that the behavior of an AU is governed not only by the events exchanged by the components within the AU but also by the events emerging from child AUs. Deep behavior characterizes not only living beings, including humans, but also artifacts, such as robots that operate in contexts at varying abstraction levels. Surprisingly, experimental results indicate that the hierarchical complexity of the system translates into a decreased computational complexity of the diagnosis task. Hence, the diagnosis technique is shown to be (formally) correct as well as (empirically) efﬁcient.

1. Introduction

Diagnosis is the task of ﬁnding the possible causes of given symptoms. As such, it can be applied not only to living creatures, including humans, but also to possibly complex engineering artifacts, such as aircraft or nuclear power plants. As several other tasks, diagnosis can be automated to varying degrees based on different paradigms. Among them is model-based diagnosis (Reiter, 1987; Hamscher, Console, & de Kleer, 1992), where the discrepancy between the expected behavior of the system (inferred by a given model) and the actual observation allows for the generation of candidate diagnoses, each candidate being a set of faulty components, i.e., a minimal set such that assuming that all the components in it do not behave normally while all the others do is consistent with the observation. Although being general in nature, this consistency-based diagnosis technique was initially conceived for static systems, such as combinational circuits. When time-varying (dynamical) systems come into play, consistency-based diagnosis is far less adopted. Some notable exceptions can be recorded in the realm of diagnostic reasoning about formal requirements (Schuppan, 2012; Pill & Quaritsch, 2013) expressed in Linear Temporal Logic (LTL) (Pnueli, 1977) or about discrete-event systems (DESs) (Pencol e, Steinbauer, M uhlbacher, & Trav e-Massuy es, 2018). Dynamical systems can be modeled as DESs (Cassandras & Lafortune, 2008), these typically being represented by ﬁnite automata (FAs), possibly communicating with one another (Brand & Zaﬁropulo, 1983). Model-based diagnosis of DESs is grounded on the seminal work by Sampath et al. (1996). Compared with the technique by Reiter (1987), the approach by Sampath et al. (1996) is

2020 AI Access Foundation. All rights reserved.

LAMPERTI, ZANELLA, & ZHAO

characterized (among others) by two peculiarities: (1) the system speciﬁcation involves not only the normal behavior of the DES but also its abnormal (faulty) behavior, and (2) the diagnosis approach is not consistency-based but rather abduction-based as each candidate is the set of all the (component) faults included in a trajectory (i.e. a sequence of state changes) of the DES that entails the observation. In abduction-based diagnosis of DESs, the behavior of the system (or a diagnosisoriented surrogate of it, typically a diagnoser) is checked against a given sequence of observable events in order to elicit the trajectory (or trajectories) of the DES that explain the observation. This way, faulty events within abnormal trajectories (that produce the given observation) are ﬁltered out as diagnosis results. Active systems (ASs) are a special class of asynchronous DESs, for which abduction-based diagnosis techniques were proposed more than two decades ago (Baroni, Lamperti, Pogliano, & Zanella, 1998, 1999, 2000). At that time, a novelty consisted in the diagnosis task not requiring the generation of the global model of the system, which was instead necessary to generate the diagnoser in in the approach by Sampath et al. (1996).1

The evolution from ASs to deep DESs (DDESs) was not instantaneous. It was spurred by the idea of injecting some sort of semantics into diagnosis of ASs (Lamperti & Zanella, 2010), based on the consideration that there is a gap between the model of a complex DES, which integrates several components, and its diagnosis, which is still anchored to individual components. Trivially, a (sub)AS is faulty only if it includes a faulty component. A candidate diagnosis of an AS is a set of component faults, irrespective of the role each component plays within the aggregate it belongs to and within the system. The idea of enriching diagnosis results with some semantics then evolved into the notion of context-sensitive diagnosis, proposed by Lamperti and Zanella (2011) and reﬁned by Lamperti and Zhao (2014). Diagnosis is context-sensitive when faults are deﬁned for a hierarchy of abstractions describing the system. The notion of a context-sensitive fault has progressively been extended as the notion of context has progressively been generalized. In the current paper, a context-sensitive (or contextual) fault is not necessarily a fault in the traditional sense, i.e. the record of something that has broken, instead it can correspond, for instance, to a violation of the expected function of a subsystem, a violation that has possibly taken place even if no component has broken: in this example, the context is the subsystem and the role it has to play within the considered system. ASs with a deep behavior, that is, where the behavior (both normal and abnormal) of lower hierarchical levels can affect the behavior of upper levels, were ﬁrst introduced by Lamperti and Zhao (2013a, 2013b). From a terminological point of view, the attribute deep takes inspiration from deep learning, by analogy with the structure of neural networks in Machine Learning as far as the presence of several layers is concerned. In the domain of DDESs, deep behavior is equivalently called behavior stratiﬁcation. Considering different levels of abstraction is a common means to face the complexity of both natural systems and artifacts, for it induces a separation of concerns. For instance, in biology, the human brain is regarded as being organized in multiple layers: the primitive reptilian brain at the bottom, the emotional mammal brain in the middle, and the rational primate brain on top, with each brain being composed of several parts (amygdala, prefrontal cortex, temporal lobes, etc.). The OSI model, the layered architecture of a software system or an operating system, a cognitive architecture, all are examples of stratiﬁcation in artifacts.

1. In the worst case, if the DES includes n components and each component model includes k states, then the global model of the DES will include up to kn states, a number that can be very large even for a few tens of components. With this numbers, the generation of the global model (and thus of the diagnoser) in real systems (possibly involving thousands of components) is quite out of the question, even if performed ofﬂine.

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

Basically a DDES consists of several ASs; each AS is a node in a hierarchy. A child AS exerts its inﬂuence over its parent AS by sending special events to it, called emergent events. An AS can trivially be regarded as a DDES consisting just of one AS, in which case there is no need for emergent events. If the DDES consists of a single AS, the method for carrying out the diagnosis task is the same as for ASs. Although some existing AS models can be regarded as a DDES consisting of more than one hierarchical layer, in general the translation of an AS to/from a DDES with several layers is not straightforward (and it is out of the scope of the paper). Modeling and processing an AS as a multi-layer DDES2 is beneﬁcial from the point of view of both the CPU time and the RAM storage, as shown by the experimental results reported in Section 6.7. However, efﬁciency is not the reason for DDESs have been introduced. The rationale behind the proposal of DDESs is that a deep behavior representation can be much more intuitive and natural for the design, analysis, monitoring, and diagnosis of dynamical systems operating at different abstraction levels, such as robots (Khalastchi & Kalech, 2018), as they have a dynamic context nature natively. Remarkably, a robot can perform a variety of tasks in a changing environment: its current operating context consists in the speciﬁc environment with which the robot is interacting (as sensed by the robot itself) and the speciﬁc task it is accomplishing. Observations that are legitimate under one context might not be legitimate under another: the latter are clues about contextual faults. For instance, a zero airspeed value is not legitimate while an unmanned aerial vehicle (UAV) is ﬂying. A DDES allows for the leaf ASs of the hierarchy to represent simple contexts, while intermediate ASs in the hierarchy can represent an aggregate of contexts, along with the transitions from a simple context, dealt with as a unit, to another context, and so on. The AS at the root of the hierarchy can represent the transitions from a context aggregate to another context aggregate. The bottom-up communications in the hierarchy can represent, among other things, how (far) contextual faults can propagate. Diagnosing a (ﬂat) AS amounts to reconstructing its behavior by performing the asynchronous composition of the behaviors of all its components as constrained by the given observation. The diagnosis method inherited from the framework of ASs can be adapted to be used also for DDESs. Applying this method amounts to reconstructing the overall behavior of the DDES, by performing the asynchronous composition of the reconstructed behaviors of all the ASs it includes, as constrained by the given observation, and then to decorating the states with the set of faults relevant to the trajectories leading to them. Being a DDES a container of ASs, its size is usually larger than that of an AS, hence the space limits are soon reached, as illustrated in Section 6.7. However, a more efﬁcient diagnosis technique that is able to exploit the speciﬁcities of DDESs (thus avoiding the reconstruction of the overall behavior of the considered DDES) is available. In fact, in order to diagnose a DDES, the behavior of each single node in the hierarchy, as constrained by the given observation and by the events coming from its child nodes, is computed starting from the leaf nodes and going upward in the hierarchy. Once the behavior of a parent node has been constructed, the constraints relevant to this behavior are propagated to its children, so as only the diagnoses (sets of faults) that comply with the parent behavior are considered. These diagnoses are properly combined with those relevant to the parent node; therefore, once the parent node has been processed, its associated diagnoses are relevant to the whole subtree rooted in it and they comply with the observations of all the nodes in the subtree. This way, once the root node has been processed, its associated set of diagnoses turns out to be a sound and complete set of candidates relevant to the whole hierar-

2. Modeling an existing system requires adherence to reality; this means that we have not to model an AS as a multilayer DDES if this is far from the way the real system works. Instead, modeling a new system as a multi-layer DDES can provide useful hints for the system design, in order to enhance its understandability and explainability.

LAMPERTI, ZANELLA, & ZHAO

chy, that is, to the whole DDES. According to this method, each single AS, is processed separately, which is usually manageable. An analogous viable technique for the diagnosis of ASs having a deep behavior was ﬁrst presented by Lamperti et al. (2016, 2016b) and subsequently extended (2016a). However, neither the formalization of the technique nor support for its correctness (soundness and completeness) was provided. This paper integrates and extends the authors previous research by formalizing the abductionbased diagnosis technique for DDESs brieﬂy described above, including a proof of correctness and experimental results that show that its efﬁciency is greater than that of the AS diagnosis method, as adapted to DDESs. To the best of our knowledge, apart from the works cited above, no approach to diagnosis of DDESs has been proposed so far. Still, several works can be related to this paper in varying degrees, as discussed at the end of the paper. In the rest of this paper, Section 2 recalls the notion of an AS and the relevant technique for solving a diagnosis problem. Section 3 introduces the notion of an active unit (AU), the building block of a DDES, along with emergent events, the basic means of upward hierarchical communication between AUs within the DDES. Section 4 deﬁnes the notion of a DDES and a corresponding diagnosis problem. It also highlights the inadequacy of the problem-solving technique adopted for ASs if we are willing to adapt it to DDESs. Section 5 presents a method for preprocessing DDES speciﬁcations in order to support effective detection of emergent events during the diagnosis task. Section 6 outlines a technique speciﬁcally designed for solving DDES diagnosis problems, which is feasible as well as sound and complete, along with relevant experimental results. Section 7 illustrates the genesis of DDESs and their advantages. Section 8 compares the proposal with a selection of related works. Conclusions are drawn in Section 9.

2. Active Systems

This background section deﬁnes the concept of an AS, upon which the next sections will progressively build the new notion of a DDES. First, the modeling primitives of an AS are described. Later, the diagnosis problem, relevant to an AS and a speciﬁc observation, is deﬁned, along with an abductive method for the generation of the set of candidate diagnoses. An AS is a network of (active) components (ACs), with each AC being modeled by a (possibly nondeterministic) communicating automaton M D .S; I; X; O; Y; /, where S is the set of states, I the set of input events, X the set of input terminals, O the set of output events, Y the set of output terminals, and the transition function, W S .I X/ 2.O Y / 7! 2S. In general, a transition t of a component c from a state s to a state s0 is triggered by an event e 2 I at an input terminal x 2 X, and generates a (possibly empty) set of output events fe1.y1/; : : : ; ek.yk/g, where 8i 2 Œ1 :: k , ei 2 O, yi 2 Y , denoted by the triple

t.c/ D s; .e.x/; fe1.y1/; : : : ; ek.yk/g/; s0 :

When e.x/ is consumed, the state s0 is reached and the output events (if any) are generated at the relevant output terminals. An AC can change its state without the need for a ready event on any input terminal: this is a spontaneous transition, which is typically used for modeling state changes caused by external events (e.g. a lightning may cause the reaction of a sensor in a protection system). The absence of an event on the input terminal x is denoted by e.x/ D ", where " is the empty event. Components within an AS are connected with one another through links. A link l is a pair .y; x0/, where y is an output terminal of a component c and x0 is an input terminal of another

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

Figure 1: Active system A (center), and models of the sensor s (left) and of the breaker b (right).

component c0, with c0 c. When a transition of c generates an output event e.y/, the event e is ready at the input terminal x0, namely e.x0/ is ready. If e.x0/ is ready, then the link l is loaded and no further transition of c generating an output event at y can occur. Each terminal can be connected with (at most) one link.3 Hence, if an (either input or output) terminal z is connected with a link, the latter can be identiﬁed as link.z/. If a terminal is not connected with a link, then the terminal is dangling. We assume that only input terminals can be dangling in an AS. If an AS A includes dangling terminals, then A is open. Based on this terminology, the transition t.c/ is triggerable (can occur) iff: .a/ the input terminal x is dangling4 or e.x/ D " or e.x/ is ready, and .b/ all links exiting the output terminals y1; : : : ; yk are empty (not loaded). An AS is succinctly represented by a triple A D .C; L; D/, where C is the array of components, L the array of links, and D the array of dangling (input) terminals. Notice that the above modeling does not make any distinction between normal and faulty behavior. Since this distinction is crucial in order to perform abductive diagnostic reasoning (which, in our approach, means ﬁnding out all the behaviors that entail a given observation), further modeling primitives are needed: they will be introduced in subsequent sections.

Example 1 Outlined in Figure 1 is an AS A that includes two components, a sensor s and a breaker b. These components are connected through a link .y; x/, where y is the output terminal of s and x the input terminal of b. A is designed to protect a device from short circuits. In a normal behavior, when a short circuit is detected by the sensor, the latter commands the breaker to open. Likewise, when the short circuit is extinguished, the sensor commands the breaker to close. The component models of s and b are depicted on the left and right side of Figure 1, respectively. Speciﬁcally, the transitions within the model of the sensor s are: s1 D hidle; ."; fop.y/g/; awakeni: s detects a short circuit and outputs op.y/; s2 D hawaken; ."; fcl.y/g/; idlei: s detects the end of the short and outputs cl.y/; s3 D hidle; ."; fcl.y/g/; awakeni: s detects a short circuit and outputs cl.y/; s4 D hawaken; ."; fop.y/g/; idlei: s detects the end of the short and outputs op.y/. Transitions within the model of breaker b are: b1 D hclosed; .op.x/; ;/; openi: b consumes event op.x/ and opens; b2 D hopen; .cl.x/; ;/; closedi: b consumes event cl.x/ and closes; b3 D hclosed; .op.x/; ;/; closedi: b consumes op.x/ and keeps being closed; b4 D hopen; .cl.x/; ;/; openi: b consumes cl.x/ and keeps being open; b5 D hclosed; .cl.x/; ;/; closedi: b consumes event cl.x/ and keeps being closed; b6 D hopen; .op.x/; ;/; openi: b consumes op.x/ and keeps being open. Notice how the transitions

3. If a component transition generates two output events that are input to the same component, then we need two distinct links between such components, with each link connecting two distinct pairs of terminals. 4. In this case, we assume that the terminal x is connected with another component outside the AS A. This occurs when A, which is the focus of the diagnosis task, is a portion of a larger AS. In principle, output terminals too could be dangling. However, as clariﬁed in Section 3, in the context of a DDES, only dangling input terminals are eventually connected with special links aimed at connecting extended ASs to one another. That way, the DDES turns out to be closed (without dangling terminals).

LAMPERTI, ZANELLA, & ZHAO

s3 and s4 in the sensor, and b3 and b4 in the breaker, are somehow abnormal (faulty); the model of A, however, does not identify the faulty transitions.

2.1 Space and Trajectory

Like an AC, an AS A can be in different states, each AS state corresponding to the array of states of its components and the array of events stored in links. Assume that A is in the initial state 0 where all links are empty. At the occurrence of a transition of a component c, A moves from 0 to a new state, say 1, where the state of c is changed and possibly output events are placed within some links. The presence of events ready at the input terminals of other components causes A to change its state by means of new component transitions. This process continues until all links become empty anew, namely when A has reached a ﬁnal (quiescent) state5. We say that A has performed a trajectory in its space, where the space of A is a deterministic ﬁnite automaton (DFA) whose language over the alphabet of all the component transitions is the set of all possible trajectories of A starting at 0. All these concepts are formalized below.

Deﬁnition 1 (Space) Let A D .C; L; D/ be an AS, where C D .c1; : : : ; cn/ and L D .l1; : : : ; lm/. The space of A, denoted A , is a DFA6

A D . ; A; ; 0; Af/ (1)

where the alphabet is the set of transitions of components in C; A is the set of states .S; E/, where S is the array of states of the components in C and E is the array of the (possibly empty) events loaded in links in L; 0 D .S0; E0/ is the initial state, where all events in E0 are empty; Af A is the set of ﬁnal states .Sf; Ef/, where all events in Ef are empty; is the transition function, W A 7! A, where: h.S; E/; t.ci/; .S 0; E 0/i 2 iff:

t.ci/ D Nsi; .e.x/; f Ne1.y1/; : : : ; Nek.yk/g/; Ns0 i is triggerable;

S D .s1; : : : ; sn/, S 0 D .s0 1; : : : ; s0 n/, si D Nsi, 8j 2 Œ1 :: n : if j D i then s0 j D Ns0 i, otherwise s0 j D sj .

E D .e1; : : : ; em/, E 0 D .e0 1; : : : ; e0 m/, if x is not dangling and e.x/ " then EŒlink.x/ D e7 and E 0Œlink.x/ D ", and 8j 2 Œ1 :: m : if Ne.y/ is an output event in t.ci/ and link.y/ D lj then e0 j D Ne, otherwise e0 j D ej .

Example 2 With reference to the AS A deﬁned in Example 1, assume that, in the initial state, the sensor s is idle, the breaker b is closed, and the link .y; x/ is empty, namely 0 D .S0; E0/ D ..idle; closed/; ."//. Outlined on the left side of Figure 2 is A , the space of A, where ﬁnal states (double circled) are 0, 3, 4, and 11. Details on state contents are provided on the right side.

5. The reachability of a quiescent state (where all links are empty) is a simplifying assumption. 6. Despite the transitions of components in A being possibly nondeterministic, the space A is deterministic because its alphabet is the set of component transitions rather than the set of triggering events. Still, the intrinsic nondeterminism of the behavior of a component is somewhat embodied in A because two (different) component transitions exiting a state in A may be triggered by the same input event. 7. The index of E can be either an integer i 2 Œ1 :: m or a link, as here.

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

State S E 0 .idle; closed/ ."/ 1 .awaken; closed/ .op/ 2 .awaken; closed/ .cl/ 3 .awaken; open/ ."/ 4 .awaken; closed/ ."/ 5 .idle; open/ .cl/ 6 .awaken; open/ .op/ 7 .idle; open/ .op/ 8 .awaken; open/ .cl/ 9 .idle; closed/ .cl/ 10 .idle; closed/ .op/ 11 .idle; open/ ."/

Figure 2: Space A of AS A (left), along with state details (right).

Deﬁnition 2 (Trajectory) A trajectory T within a space A D . ; A; ; 0; Af/ is a ﬁnite sequence of contiguous transitions of components in A, namely T D Œ t1.c1/; : : : ; tq.cq/ , such that

8i 2 Œ1 :: q ; h i 1; ti.ci/; ii 2 ; and q 2 Af: (2)

The (possibly inﬁnite) set of trajectories of A is denoted k A k. A preﬁx of a trajectory T is a semi-trajectory within A . A contiguous subsequence of T is a subtrajectory within A .

Example 3 A trajectory within the space A outlined in Figure 2 is T D Œ s1; b3; s2; b5 .

2.2 Viewer and Temporal Observation

The modeling of an AS A does not provide any information on the observability of A. Providing information about observability means deﬁning, for each component in A, which transitions are observable and which ones are unobservable. A transition is observable if, when occurring, it generates a label that can be perceived by an external observer; otherwise, the transition is unobservable. Therefore, specifying the observability of A amounts to deﬁning a mapping from observable transitions to corresponding observable labels. This is captured by the notion of a viewer.

Deﬁnition 3 (Viewer) Let A be an AS, and a domain of observable labels. A viewer V for A is a surjective mapping from a subset of the transitions of the components in A to .8 If .t.c/; / 2 V, then the transition t.c/ is observable; otherwise, t.c/ is unobservable.9

Example 4 With reference to the AS A introduced in Example 1, a viewer V is deﬁned as follows: V D f.s1; awk/, .s2; ide/; .s3; awk/; .s4; ide/; .b1; bop/; .b2; bcl/g, with observable labels having the following meaning: awk = the sensor awakes, ide = the sensor becomes idle, bop = the breaker opens, and bcl = the breaker closes.

8. Since the mapping is surjective, each label in is associated with (at least) one of these transitions. 9. In fact, V can be represented as a set of pairs .t.c/; /, where t.c/ is a transition of the component c and is the associated observable label.

LAMPERTI, ZANELLA, & ZHAO

Deﬁnition 4 (Temporal Observation) Let T be a trajectory in A and V a viewer for A. The temporal observation of T based on V, written Obs.T; V/, is the sequence of observable labels associated with the observable transitions of T ,

Obs.T; V/ D Œ j t.c/ 2 T; .t.c/; / 2 V : (3)

Example 5 With reference to the trajectory T in Example 3 and the viewer V in Example 4, the temporal observation of T based on V is the sequence Obs.T; V/ D Œ awk; ide .

2.3 Ruler and Diagnosis

As remarked already, the modeling of an AS A does not make any distinction between normal and faulty behavior. Providing speciﬁcation for this distinction means deﬁning, for each component in A, which transitions are normal and which ones are faulty. In other words, faults are associated with component transitions. This way, a transition h ; t.c/; 0i of A is faulty if and only if t.c/ is faulty. Thus, specifying the abnormal behavior of A amounts to deﬁning a mapping from faulty component transitions to faults, just as specifying the observability of A amounts to deﬁning a mapping from observable component transitions to observable labels. This is captured by the notion of a ruler.

Deﬁnition 5 (Ruler) Let A be an AS, and F a domain of faults. A ruler R for A is a surjective mapping from a subset of transitions of components in A to F . If .t.c/; / 2 R, then the transition t.c/ is faulty; otherwise, t.c/ is normal.

Example 6 With reference to the AS A introduced in Example 1, a ruler R is deﬁned as follows: R D f.s3; fso/, .s4; fsc/; .b3; fbo/; .b4; fbc/g, where faults have the following meaning: fso = failure of s in sending the opening command, fsc = failure of s in sending the closing command, fbo = failure of b in opening, and fbc = failure of b in closing.

Deﬁnition 6 (Diagnosis) Let T be a trajectory within A and R a ruler for A. The diagnosis of T based on R, denoted Dgn.T; R/, is the set of faults involved in the faulty transitions of T , namely

Dgn.T; R/ D f f j t.c/ 2 T; .t.c/; f / 2 R g: (4)

Since a diagnosis is a set (rather than a sequence), the same fault cannot be duplicated within the diagnosis. Consequently, two trajectories covering the same subgraph within A by traversing the same cycle a different number of times yield the same diagnosis. This is why the set of possible diagnoses is always ﬁnite, regardless the set of trajectories being possibly inﬁnite.

Proposition 1 Let F be the set of faults involved in the ruler of an AS A. The set of possible diagnoses of A is ﬁnite, speciﬁcally a subset of the powerset 2F .

Example 7 With reference to the trajectory T in Example 3 and the ruler R in Example 6, the diagnosis of T based on R is the singleton Dgn.T; R/ D f fbo g.

A handy (binary) operator to combine sets of diagnoses is deﬁned as follows.

Deﬁnition 7 (Join) Let 1 and 2 be two sets of diagnoses. The join operator is deﬁned as

1 2 D f ı j ı D ı1 [ ı2; ı1 2 1; ı2 2 2 g : (5)

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

The join is commutative, namely 1 2 D 2 1. The neutral element of the join is the singleton f;g, since f;g D f;g D .

Example 8 Let 1 D fffso; fbog, ffsc; fbcgg and 2 D fffso; fbcg, ffsogg. We have 1 2 D fffso, fbo, fbcg, ffso, fbog, ffso, fsc, fbcgg. Notice how, owing to the removal of the duplicated diagnosis ffso; fsc; fbcg, the cardinality of 1 2 is less than the product of the cardinality of 1 and the cardinality of 2.

2.4 Diagnosis Problem

Assume that an AS A performs a trajectory starting from the initial state 0. The temporal observation O of this trajectory is a sequence of observable labels based on a viewer V of A. Assume further that R is the ruler for A. Now comes the question: What can we say about the behavior of A based on the information we have, namely the initial state 0, the viewer V, the temporal observation O, and the ruler R? This is formalized by the notion of a diagnosis problem.

Deﬁnition 8 (Diagnosis Problem) Let A be an AS, 0 the initial state of A, V a viewer for A, O a temporal observation of A, and R a ruler for A. The quadruple

}.A/ D . 0; V; O; R/ (6)

is a diagnosis problem for A. The solution to }.A/, denoted .}.A//, is the set of (candidate) diagnoses deﬁned as

.}.A// D Dgn.T; R/ j T 2 A ; Obs.T; V/ D O : (7)

When Obs.T; V/ D O, we say that T implies O.

Example 9 Consider the AS A introduced in Example 1. A diagnosis problem for A is }.A/ D . 0; V; O; R/, where 0 D .S0; E0/ D ..idle; closed/; ."//, the viewer V is deﬁned in Example 4, O D Œ awk; ide , and the ruler R is deﬁned in Example 6. According to the space A outlined in Figure 2, there are four trajectories T such that Obs.T; V/ D O, namely T1 D Œs1; b3; s2; b5 , T2 D Œs1; b3; s4; b3 , T3 D Œs3; b5; s2; b5 , and T4 D Œs3; b5; s4; b3 . Based on eqn. (7), the solution to }.A/ is .}.A// D fı1; ı2; ı3; ı4g, where ı1 D Dgn.T1; R/ D ffbog, ı2 D Dgn.T2; R/ D ffbo; fscg, ı3 D Dgn.T3; R/ D ffsog, and ı4 D Dgn.T4; R/ D ffso; fsc; fbog.

Still, generating the solution to a diagnosis problem based on eqn. (7) is impractical for two reasons: .a/ A is not available, as its materialization is prohibitively expensive in real systems, and .b/ possibly, an inﬁnite set of trajectories should be considered. As to point .a/, a more practical technique is required, which exploits the constraints imposed by the temporal observation (cf. Section 2.5). As to point .b/, only a signiﬁcant ﬁnite set of trajectories is considered, which is however sufﬁcient to determine the solution to the diagnosis problem (cf. Section 2.6).

2.5 Constrained Space

According to eqn. (7), what is essential to generate a candidate diagnosis is a trajectory of A that implies the temporal observation O. The set of trajectories implying the temporal observation O is a subset of k A k. If the set of trajectories of A is inﬁnite, then the subset of trajectories implying O

LAMPERTI, ZANELLA, & ZHAO

State S E = ˇ0 .idle; closed/ ."/ 0 ˇ1 .awaken; closed/ .op/ 1 ˇ2 .awaken; closed/ .cl/ 1 ˇ3 .awaken; closed/ ."/ 1 ˇ4 .idle; closed/ .cl/ 2 ˇ5 .idle; closed/ .op/ 2 ˇ6 .idle; closed/ ."/ 2

Figure 3: O-constrained space A O of AS A (left), along with state details (right).

can be inﬁnite too. The point is, since A is a DFA embodying (in its language) a possibly inﬁnite set of trajectories, chances are we can devise a technique for generating a DFA whose language is exactly the subset of the language of A that includes all (and only) the trajectories implying the temporal observation. We call this DFA the O-constrained space of A, as deﬁned below.

Deﬁnition 9 (O-constrained Space) Let A be an AS, 0 the initial state of A, V a viewer for A, and O D Œ 1; : : : ; n a temporal observation of A. The O-constrained space of A is a DFA

A O D . ; B; ; ˇ0; Bf/ (8)

such that the set of trajectories in A O is a subset of the set of trajectories in A , namely k A Ok k A k, where equals the alphabet of A ; B is the set of states .S; E; =/, where .S; E/ is a state of A , and = is an index of O, namely = 2 Œ0 :: n ; ˇ0 D .S0; E0; 0/ is the initial state, where .S0; E0/ D 0; Bf B is the set of ﬁnal states .Sf; Ef; n/, where .Sf; Ef/ is a ﬁnal state of A ; is the transition function, W B 7! B, where h.S; E; =/; t.c/; .S 0; E 0; =0/i 2 iff h.S; E/; t.c/; .S 0; E 0/i is a transition in A , and

( = C 1 if .t.c/; / 2 V and D =C1 = if t.c/ is unobservable: (9)

Example 10 Let A be the space of A displayed in Figure 2, and O D Œawk; ide . The Oconstrained space of A, namely A O, is outlined in Figure 3. Notice that A O includes the trajectories T1, T2, T3, and T4 deﬁned in Example 9, each one implying O.

2.6 Decoration and Solution

Building the O-constrained space A O is the ﬁrst step of the diagnosis technique. Then, we need to associate with each trajectory in A O the corresponding diagnosis. At a ﬁrst glance, when the set of trajectories is inﬁnite, this might seem an endless task, as we have to consider each trajectory one by one in order to generate the associated diagnosis. However, the set of diagnoses is always ﬁnite because a diagnosis is a set (rather than a multiset) of faults, so that duplicated faults within the same trajectory are removed. This means that, for the purpose of diagnosis generation, only a ﬁnite set of trajectories sufﬁces to be considered. This ﬁnite set is composed of all the trajectories in which possible cycles are traversed once at most. This is good news because we can associate with

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

State Diagnosis set ˇ0 f;g ˇ1 f;g ˇ2 fffsogg ˇ3 fffbog; ffsogg ˇ4 fffbog; ffsogg ˇ5 fffbo; fscg; ffso; fscgg ˇ6 fffbog; ffbo; fscg; ffsog; ffso; fsc; fbogg

Figure 4: Decoration of the O-constrained space A O, with diagnosis sets detailed on the right side.

each state ˇ of A O a ﬁnite set of diagnoses, with each diagnosis corresponding to a semi-trajectory T ending at ˇ, such that T does not traverse a cycle more than once. That is, we can generate the set of diagnoses associated with the state ˇ by considering only a ﬁnite subset of the (possibly inﬁnite) set of semi-trajectories ending at ˇ. Generating the set of diagnoses associated with each state of the constrained behavior is the second step of the diagnosis technique, as detailed below.

Deﬁnition 10 (Decorated Constrained Space) Let A O be the O-constrained space of an AS A, and R a ruler for A. The decorated O-constrained space of A, denoted Ad O, is the DFA obtained from A O by marking each state ˇ of the latter with a diagnosis set (or decoration) .ˇ/ based on the application of the following two rules:

1. (Basis) For the initial state ˇ0, ; 2 .ˇ0/;

2. (Induction) For each transition hˇ; t.c/; ˇ0i, for each ı 2 .ˇ/, if .t.c/; f / 2 R, then ı [ ff g 2 .ˇ0/, else ı 2 .ˇ0/.

Based on the ﬁrst rule in Deﬁnition 10, the empty diagnosis corresponds to the empty semitrajectory. Based on the second rule, if the decoration of the state ˇ includes a diagnosis ı, then there is at least one semi-trajectory T , ending at ˇ, whose diagnosis is ı.10 Consequently, there is a semi-trajectory T [ Œ t.c/ 11 ending at ˇ0 whose diagnosis is either the extension of ı by the fault f associated with t.c/ in R, when .t.c/; f / 2 R, or ı, when .t.c/; f / R. Unlike the ﬁrst rule, which represents the base case and is applied only once, the second rule is inductive in nature. This means that, for the sake of completeness of the decoration, the second rule should be continuously applied until the decoration of the behavior cannot be changed. As such, if ˇ is a ﬁnal state of Ad O, then, for each trajectory T 2 k Ad Ok ending in ˇ, the diagnosis of T , namely ı, is part of the decoration of ˇ, that is, ı 2 .ˇ/.

Proposition 2 Let }.A/ D . 0; V; O; R/ be a diagnosis problem and Ad O the decorated Oconstrained space of A. The solution to }.A/ is

.}.A// D [ .ˇ/; where ˇ is a ﬁnal state of Ad O: (10)

10. The notion of a diagnosis deﬁned in eqn. (4) for a trajectory is applicable to semi-trajectories too. 11. When the (overloaded) operator [ is applied to sequences, it denotes concatenation.

LAMPERTI, ZANELLA, & ZHAO

Example 11 Consider the O-constrained space A O displayed in Figure 3. Outlined on the left side of Figure 4 is the same space where the identiﬁers of the faulty transitions are replaced with the corresponding faults. The diagnosis sets associated with each state are listed on the right side of the ﬁgure. According to Proposition 2, the solution to }.A/ is the diagnosis set associated with the ﬁnal state ˇ6, namely .}.A// D .ˇ6/ D fffbog; ffbo; fscg; ffsog; ffso; fsc; fbogg, which in fact equals the solution determined in Example 9 based on eqn. (7).

3. Active Units

As described in the previous section, an AS is a network of communicating ACs. Within an AS A, communication from a component c to a component c0 is achieved by the generation of output events at the occurrence of a transition in c. Since c is assumed to be connected with c0 by links, the events generated by c are available (ready) at the input terminals of c0. This allows for a temporal cascade of component transitions within A, namely a trajectory of A (cf. Section 2.1). Intuitively, an active unit (AU) is meant to allow an AS to communicate with other ASs via special events. In order to make an AS A communicate with another AS A0, we need to: (1) equip A with output terminals, (2) equip A0 with input terminals, (3) provide links from the output terminals of A to the input terminals of A0, and (4) specify the circumstances under which the output events are generated by A. Of the four points listed above, the last is the most critical one. Unlike an AC, whose behavior is speciﬁed by a communicating automaton, no behavior is explicitly deﬁned for an AS. In a sense, the behavior of the AS A is its space A , which is determined by the interaction of components. In this space, a transition of A is caused by a transition of one component of A. That is, the behavior of A corresponds to the mode in which the components perform state transitions and interact with one another by means of exchanged events. In so doing, A does not generate any output event on its own, speciﬁcally directed toward another AS. In other words, no deep behavior exists. To enable deep behavior, we associate with A a set of events that are generated upon the occurrence of a string (sequence) of component transitions matching a given regular expression (cf. Section 3.1). To stress the mode in which these events occur, they are called emergent events.12

Since each emergent event e in A is associated with one output terminal y of A, the occurrence of e places the latter on the terminal y, exactly like the generation of an output event by a component c places the event on a speciﬁc output terminal of c. Therefore, in order for A to communicate with the AS A0, a link from the output terminal y of A to an input terminal x0 of A0 should be deﬁned (point 3 above). To this end, we require that each dangling (input) terminal of A0 be connected with an output terminal of another AS. That is, the input terminals of A0 are the dangling input terminals of its components. For instance, if a link is deﬁned from the output terminal y of A to the input terminal x0 of A0, with x0 being a dangling input terminal of a component c0 in A0, then the occurrence of an emergent event e.y/ makes e ready at the terminal x0 of c0. Once ready, e.x0/ can be consumed by a transition of c0, just like any other event generated by a component in A0. The enhancement of an AS by input terminals, output terminals, and emergent events leads to the notion of an AU deﬁned below.

12. The qualiﬁer emergent applied to these events is inherited from the science of complex systems, which inspired the present work. The basic characteristics of a complex system is the emergence of unpredictable behavior resulting from the interaction among individual components. This emergent behavior cannot be explained by the superimposition of the behavior of the interacting components. This paradigm is applicable to natural systems, such as animals, as well to artiﬁcial systems, such as cities, companies, and economies (Atay & Jost, 2004; Bossomaier & Green, 2007; Licata & Sakaji, 2008; Goles & Martinez, 2001).

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

e.y/ Regular expression Description di b1 Disconnection co b2 Connection nd s3 j s1 b3 Failure in disconnecting nc s4 j s2 b4 Failure in connecting

Figure 5: AU P (left) and corresponding emergent events (right).

Deﬁnition 11 (Active Unit) An active unit is a quadruple U D .A; I; O; E/ where A is an AS, I the set of input terminals, these being the dangling input terminals of all the components in A, O is the set of output terminals, and E is the set of emergent events; each emergent event is deﬁned by a pair .e.y/; r/, where e is the event, y 2 O, and r is a regular expression on transitions of components in A.

Example 12 Consider the AS A deﬁned in Example 1 and depicted in Figure 1. Outlined on the left side of Figure 5 is an AU P D .A; I; O; E/ derived from A, where I D ;, O D fyg, and the set E of emergent events is fdi; co; nd; ncg, with the following meaning: di = disconnected, co = connected, nd = not disconnected (failure), and nc = not connected (failure). The regular expressions of the emergent events are deﬁned on the right side of Figure 5, the alphabet of each regular expression being D fs1; s2; s3; s4; b1; b2; b3; b4; b5; b6g.13 For instance, nd (failure in disconnecting) occurs when either the sensor s detects the short circuit but sends the wrong command to the breaker b, namely the transition s3, or s detects the short circuit and commands b to open but b keeps being closed, namely the transition s1 followed by the transition b3.

The notions of viewer, ruler, and temporal observation for ASs are applicable to AUs also.

3.1 More on Emergent Events

As pointed out in Section 2, within an AS A, events are generated upon the occurrence of component transitions. These events are called internal events, meaning that they are generated (and consumed) within A. When an AU U D .A; I; O; E/ is considered, a new class of events is speciﬁed, namely the class of emergent events, those deﬁned in E. Speciﬁcally,

E D f.e1.y1/; r1/; : : : ; .eh.yh/; rh/g (11)

where 8i 2 Œ1 :: h , ei is an event, yi an output terminal of U (yi 2 O), and ri a regular expression whose alphabet is a (not necessarily strict) subset of the transitions of components in A. Given .e.y/; r/, the emergent event e occurs in U (and is placed at the output terminal y) whenever a subtrajectory S within A matches r, in other words, whenever S 2 krk (S is a string of the regular language of r). In order to keep tracking the matching of any subtrajectory with r, a DFA is generated (cf. Section 5), called the matcher of .e.y/; r/, denoted .e.y/; r/. As clariﬁed in

13. Basically, a regular expression is deﬁned inductively on an alphabet as follows. The empty symbol " is a regular expression. If a 2 , then a is a regular expression. If x and y are regular expressions, then the followings are regular expressions: x j y (alternative), xy (concatenation), x (optionality), x (repetition zero or more times), and x C (repetition one or more times). When parentheses are missing, the concatenation has precedence over the alternative; for example, ab j c equates to .ab/ j c.

LAMPERTI, ZANELLA, & ZHAO

Figure 6: Matcher .e.y/; r/, where r D t1 .t2 j t3/Ct2, D ft1; t2; t3g.

Section 5, a matcher .e.y/; r/ is not simply the DFA recognizing the language of r, as the strings in r may overlap in a trajectory.

Example 13 Let U D .A; I; O; E/ be an AU, .e.y/; r/ an emergent event in U, and D ft1; t2; t3g the alphabet of r, where r D t1 .t2 j t3/Ct2 is the regular expression associated with e.y/. Assume the following trajectory for A:

T D Œ t2; t3; t1; t2; t1; t3; t2

T 0 ; t4; t1; t1; t2; t3; t3; t2

T 00 ; t3 (12)

where the two subtrajectories of T matching the regular expression r are T 0 D Œt1; t3; t2 and T 00 D Œt1; t2; t3; t3; t2 . Accordingly, the emergent event e.y/ is generated at the occurrence of the last transition in either subtrajectory, namely t2. The matcher .e.y/; r/ is displayed in Figure 6, where the ﬁnal state 3 is marked with the emergent event e.y/.14 Starting from the initial state 0, a state transition is performed in .e.y/; r/ at any component transition ti 2 T belonging to the alphabet . If no transition exiting the current state is marked with ti, then such a mismatch causes the current state to become the initial state 0. Shown in Table 1 is the association between each component transition in the trajectory T (top), the corresponding state in the matcher .e.y/; r/ (middle), and the occurrences of emergent events (bottom). The instances of the ﬁnal state 3 in bold correspond to the generation of the two occurrences of the emergent event e.y/.

t2 t3 t1 t2 t1 t3 t2 t4 t1 t1 t2 t3 t3 t2 t3 0 0 1 2 1 2 3 3 1 1 2 2 2 3 2 e.y/ e.y/

Table 1: Detection of emergent events.

3.2 Unit Space

Since an AU U is an extension of an AS A by means of a set of output terminals and a set of emergent events generated on these terminals (deﬁned by regular expressions on component transitions), the notion of a space for A, namely A , can be naturally extended to U, namely U . In so doing, a state in U is the extension of a state in A , namely .S; E/, by an additional ﬁeld M representing the array of states of the matchers of the regular expressions associated with the emergent events. Hence, a state in U is a triple .S; E; M/ where .S; E/ is a state in A . When U moves to a state

14. Details on the construction of a matcher are given in Section 5.

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

Figure 7: Matchers of the emergent events di, co, nd, and nc, at the output terminal y of the AU P .

in which M includes a ﬁnal state of the matcher associated with an emergent event e.y/, the event e is generated at the output terminal y of U.

Deﬁnition 12 (Unit Space) Let U D .A; I; O; E/ be an AU, where A D . ; A; A; 0; Af/, and E D ..e1.y1/; r1/, : : : ; .eh.yh/; rh// with corresponding array of matchers .E/ D . 1; : : : ; h/. The space of U, denoted U , is a DFA

U D . ; U; ; uo; Uf/ (13)

where: the alphabet is the set of transitions of the components in A (the same alphabet as that of A ); U is the set of states .S; E; M/, where .S; E/ 2 A, and M D .m1; : : : ; mh/ is the array of states of the matchers in .E/; u0 D .S0; E0; M0/ is the initial state, where .S0; E0/ D 0 and M0 D .m10; : : : ; mh0/ is the array of initial states of the matchers in .E/; Uf U is the set of ﬁnal states .Sf; Ef; Mf/, where .Sf; Ef/ 2 Af; is the transition function, W U 7! U , where h.S; E; M/; t.c/; .S 0; E 0; M 0/i 2 iff: (1) h.S; E/; t.c/; .S 0; E 0/i 2 A (the transition function of A ), and (2) M D .m1; : : : ; mh/, M 0 D .m0 1; : : : ; m0 h/, and 8i 2 Œ1 :: h we have

Nmi if t.c/ 2 .ri/ and hmi; t.c/; Nmii 2 i mi 0 if t.c/ 2 .ri/ and no transition marked with t.c/ exits mi in i mi if t.c/ .ri/:

Example 14 With reference to the AU P deﬁned in Example 12, displayed in Figure 7 are the matchers of the emergent events di, co, nd, and nc, where the alphabet of the regular expressions is assumed to be the totality of the transitions of the components in P . Outlined on the left side of Figure 8 is the unit space P , where relevant states are marked with the emergent events (the output terminal y is omitted). The details of the states are listed on the right side of the ﬁgure, where a bold state in M indicates the detection of an emergent event by the corresponding matcher (cf. Figure 7).

The notions of trajectory, semi-trajectory, and subtrajectory introduced in Section 2.1 are still valid when AU spaces are considered.

4. Deep Discrete-Event Systems

Intuitively, a DDES is a hierarchical network of AUs. Like components within an AS, AUs are connected with one another through links. Speciﬁcally, a link l connects an output terminal y of an

LAMPERTI, ZANELLA, & ZHAO

State S E M u0 .idle; closed/ ."/ .0; 0; 0; 0/ u1 .awaken; closed/ .op/ .0; 0; 1; 0/ u2 .idle; closed/ .cl/ .0; 0; 0; 1/ u3 .awaken; closed/ .cl/ .0; 0; 2; 0/ u4 .awaken; open/ ."/ .1; 0; 0; 0/ u5 .awaken; closed/ ."/ .0; 0; 2; 0/ u6 .awaken; closed/ ."/ .0; 0; 0; 0/ u7 .idle; open/ .cl/ .0; 0; 0; 1/ u8 .idle; open/ .op/ .0; 0; 0; 2/ u9 .awaken; closed/ ."/ .0; 1; 0; 0/ u10 .idle; closed/ .op/ .0; 0; 0; 2/ u11 .idle; closed/ ."/ .0; 1; 0; 0/ u12 .idle; open/ ."/ .0; 0; 0; 2/ u13 .idle; open/ ."/ .0; 0; 0; 0/ u14 .idle; open/ ."/ .1; 0; 0; 0/ u15 .awaken; closed/ .op/ .0; 0; 0; 2/ u16 .awaken; closed/ .cl/ .0; 0; 0; 1/ u17 .awaken; open/ .op/ .0; 0; 1; 0/ u18 .awaken; open/ .cl/ .0; 0; 2; 0/ u19 .awaken; open/ ."/ .0; 0; 0; 0/

Figure 8: Space of the AU P (left) and content of the states (right).

AU U with an input terminal x0 of another AU U0. When an emergent event e occurs at the terminal y and is loaded in the link l, e.x0/ is ready to be consumed by the component in U0 having x0 as an input terminal.15 The mode in which the AUs are linked together should be consistent with the following topological constraints (cf. Figure 9): (1) all links exiting an AU U enter the same AU U0, where U is called a child of U0 and U0 the parent of U, (2) every output terminal of U is exited by exactly one link, and (3) every input terminal of U0 is entered by exactly one link. Constraint 1 forces the topology to be hierarchical, as in the abstract example outlined in Figure 9, where nodes denote AUs and arcs denote links from child to parent AUs.

Deﬁnition 13 (DDES) A DDES X is a pair X D .U; L/, where U is an array of AUs and L an array of (external) links between these AUs.

Choosing whether to represent a physical system as a DDES rather than a DES primarily depends on the complexity of the system. If the system is inherently hierarchical in structure, where each subsystem in the hierarchy is characterized by a behavior that is more abstract than the behavior of its children, then a DDES may be a better choice than a DES, because the abstractions of the physical system can be represented in a natural way in the DDES. For instance, for the purpose of diagnosis, an aircraft (or a part of it) may be better represented by a DDES rather than a DES. For redundancy reasons related to safety, the engine of the aircraft may be composed of several physical engines. In the DDES, the engine may be an AU, with the physical engines being its child AUs. Since a fault in a physical engine does not necessarily

15. As remarked in Section 3, the input terminals of an AU U D .A; I; O; E/ are all the dangling terminals of the AS A, namely the input terminals of the components in A that are not connected with a link in A.

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

Figure 9: Hierarchy of a DDES: nodes are AUs and arcs are links.

jeopardize the behavior of the engine as a whole, this information should be reﬂected in the diagnosis information.16

Modeling a complex physical system as a DDES combines the advantages of modeling a simple physical system as a DES at each level of the hierarchical structure. Ideally, the speciﬁcation of the behavior of each AU (each subsystem in the hierarchy) is expected to require substantially the same effort regardless of the level in which the AU is placed in the hierarchy, just as the effort for coding a function in a complex software system should not depend on the level of abstraction at which this function is placed within the software architecture. In other words, hierarchical modularity is the most signiﬁcant feature of a physical system being modeled as a DDES. If a physical system is not hierarchically modular in nature, there is (in principle) no reason to modeling it as a DDES. In order to model a physical system as a DDES, namely X, the following steps are suggested: (1) deﬁne the tree of X based on the hierarchical structure of the physical system; (2) associate with each node of the tree an AU with relevant components and links; (3) specify the emergent events for each AU; (4) for each AU, specify the model of each component in terms of a communicating automaton; (5) for each AU, specify a viewer (observable transitions) and a ruler (faulty transitions). In these steps, it is convenient to think with a teleological attitude, considering that the modeling of the physical system as a DDES is meant for diagnosis purposes. In other words, the model of the physical system expressed by the DDES X is not general-purpose in nature: it is special-purpose, that is, oriented to the task of diagnosis. This, however, does not prevent a priori X to be exploited for other purposes, such as simulation or monitoring.17

Example 15 In Example 1 of Section 2 we have deﬁned an AS A that includes a sensor and a breaker. In Example 12 of Section 3, A has been extended to an AU P. Interestingly, P can be part of the hierarchical structure of a DDES modeling a power transmission line. Outlined in Figure 10 is the schema of a protected power transmission line. The line is equipped with a protection apparatus on each side. On the left side, the apparatus involves the sensor s, the primary breaker b, the monitor m, and the recovery breaker r. The behavior of s and b is the one described in Example 1: if a short circuit strikes the line, then the sensor s commands the breaker b to open. To provide some sort of fault tolerance in the protection apparatus, if a misbehavior occurs (either s does not command b to open or, even if correctly commanded, b does not open), then the monitor m intervenes by commanding the recovery breaker r to open and, at the same time, by informing the monitor m0 on the opposite side to perform the same recovery action on the breaker r0. For safety reasons, once opened, the recovery breakers cannot be closed again, thereby leaving the line isolated. The same

16. Compare with the notions of negative/positive paradox introduced by Lamperti and Zanella (2011). 17. In fact, monitoring-based diagnosis is a natural extension of the diagnosis task for DDESs proposed in this paper.

LAMPERTI, ZANELLA, & ZHAO

Figure 10: Schema of a protected power transmission line.

applies to the protection apparatus on the right side of the line. The protected transmission line in Figure 10 can be modeled as the DDES X displayed in Figure 11.

X incorporates four AUs, namely the protection apparata P and P 0 on the bottom of the hierarchy, the monitoring apparatus M on the middle, and the line L on the top. The output terminals of the AUs P and P 0 are connected with the input terminals of the components m and m0 (in M), respectively. Moreover, the AU M is equipped with two output terminals, namely y1 and y2, each one being connected with an input terminal of l. In order to complete the speciﬁcation of X, we need to provide the models of the monitor and the line, as well as the speciﬁcation of the emergent events of M. The model of the monitor is outlined in Figure 12, in terms of relevant input/output terminals (left) and communicating automaton (right), with transitions being detailed in Table 2. The monitor moves from state watch to trigger upon the occurrence of either the event nd (failure in disconnecting the side of the line) emerging from the protection apparatus or the event rc (request of recovery action) coming from the other monitor. In the ﬁrst scenario, based on m1, the monitor commands the corresponding recovery breaker to open and informs the other monitor. However, based on m2, the monitor can command the corresponding recovery breaker to open without informing the other monitor. In the second scenario (consumption of rc), the monitor commands the corresponding recovery breaker to open (transition m3). Transitions m4 m10 consume the input event (emerging from the protection apparatus) without changing state. According to Figure 11, the AU M is provided with the output terminals y1 and y2 (which have not to be confused with the homonymous terminals of both monitors m and m0). In either terminal, three emergent events can be placed, namely (1) nr: the corresponding side of the line cannot be reconnected, (2) ni: the corresponding side of the line cannot be isolated, and (3) ps: the short circuit persists on the corresponding side of the line. The speciﬁcation of these emergent events in terms of regular expressions

Figure 11: DDES X, with AUs L, M, P , and P 0.

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

Figure 12: Model of the monitor component in the DDES depicted in Figure 11.

Transition From state Input event Output events To state m1 watch nd.x1/ fop.y1/; rc.y2/g trigger m2 watch nd.x1/ fop.y1/g trigger m3 watch rc.x2/ fop.y1/g trigger m4 trigger nd.x1/ ; trigger m5 watch di.x1/ ; watch m6 watch co.x1/ ; watch m7 watch nc.x1/ ; watch m8 trigger di.x1/ ; trigger m9 trigger co.x1/ ; trigger m10 trigger nc.x1/ ; trigger

Table 2: Transition details for the monitor automaton displayed on the right side of Figure 12.

is provided in Table 3.18 The matchers of these events are depicted in Figure 13. The model of the line is shown in Figure 14, with the transitions being detailed in Table 4. The line moves from the state normal to shorted, isolated, or persistent, without generating any output event. Since the input terminals x1 and x2 of the line are connected with the output terminals of the AU M, the transitions in the line are triggered by the emergent events in M.

4.1 DDES Space and Trajectory

Since a DDES X is a (hierarchical) network of AUs connected by (external) links, just as an AS is a network of components connected by (internal) links, a state of X is identiﬁed by a pair .U ; E/, where U is the array of states of the AUs in X, and E is the array of emergent events that are loaded in the (external) links.

Deﬁnition 14 (DDES Space) Let X D .U; L/ be a DDES, where U D .U1; : : : ; Un/, and L D .l1; : : : ; lm/. The space of X, denoted X , is a DFA

X D . ; X; ; xo; Xf/ (15)

where the alphabet is the union of the sets of the transitions in U i , i 2 Œ1 :: n ; X is the set of states .U ; E/, where U D .u1; : : : ; un/ is the array of states of the AUs in U, E D .e1; : : : ; em/ is the array of the (possibly empty) emergent events loaded within the links in L;19 x0 D .U0; E0/ is

18. The table speciﬁes only the emergent events at the output terminal y1. The same events generated at the terminal y2 have a similar speciﬁcation, where m and r are replaced with m0 and r0, respectively. 19. If nonempty, these emergent events are ready at the corresponding input terminals of the AUs in U, so they can be consumed by the components.

LAMPERTI, ZANELLA, & ZHAO

e.y1/ Alphabet Regular expression nr.y1/ f m7.m/; m10.m/; b1.r/ g m7.m/ j m10.m/ j b1.r/ ni.y1/ f m1.m/; m2.m/; m4.m/; b3.r/ g .m1.m/ j m2.m/ j m4.m// b3.r/ j b3.r/ m4.m/ ps.y1/ f m5.m/; m6.m/ g m6.m/ m5.m/

Table 3: Emergent events at output terminal y1 of M.

the initial state, where U0 D .u10; : : : ; un0/ is the array of initial states of the AUs in U, while E0 D ."; : : : ; "/, that is, all emergent events in E0 are empty; Xf X is the set of the ﬁnal states .Uf; Ef/, where Uf D .u1f; : : : ; unf/, 8i 2 Œ1 :: n , uif is a ﬁnal state in U i , while all emergent events in Ef are empty; is the transition function, W X 7! X, where h.U ; E/; t.Ui/; .U 0; E 0/i 2 iff:

U D .u1; : : : ; un/, U 0 D .u0 1; : : : ; u0 n/, E D .e1; : : : ; em/, E 0 D .e0 1; : : : ; e0 m/;

t.Ui/ D hui; Nt.c/; Nuii, Nt.c/ D hs; .e.x/; E/; s0i, where fe0 1.y0 1/; : : : ; e0 h.y0 h/g E is the subset of the output events generated by Nt.c/ at the output terminals of Ui;

8j 2 Œ1 :: n u0 j D Nui if i D j uj otherwise

If x is an input terminal of Ui, then E.x/ D e;

8j 2 Œ1 :: h E.y0 j / D " ;

8j 2 Œ1 :: m

e0 i if e0 i.y0 i/ 2 E; i 2 Œ1 :: h ; and link.y0 i/ D lj " if x is an input terminal of Ui and link.x/ D lj EŒj otherwise

A trajectory T D Œ t1.c1/; : : : ; tq.cq/ within the space X D . ; X; ; x0; Xf/ is a ﬁnite sequence of transitions of the components within the AUs in U such that, 8i 2 Œ1 :: q , xi 1; t.Uj /; xi 2 ; t.Uj / D u; ti.ci/; u0 ; and xq 2 Xf: (16)

The set of all the trajectories in X is written k X k.

Figure 13: Matchers of emergent events nr, ni, and ps, generated at terminal y1 of M (cf. Table 3).

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

Figure 14: Model of the line component (cf. Figure 11).

Transition From state Input event Output events To state l1 normal ni.x1/ ; shorted l2 shorted ni.x1/ ; shorted l3 normal ni.x2/ ; shorted l4 shorted ni.x2/ ; shorted l5 normal nr.x1/ ; isolated l6 isolated nr.x1/ ; isolated l7 normal nr.x2/ ; isolated l8 isolated nr.x2/ ; isolated l9 normal ps.x1/ ; persistent l10 persistent ps.x1/ ; persistent l11 normal ps.x2/ ; persistent l12 persistent ps.x2/ ; persistent

Table 4: Transition details for the line automaton displayed on the right side of Figure 14.

Example 16 With reference to the DDES X in Example 15, assuming that initially the breakers are closed, the sensors are idle, the monitors are in watch mode, and the line is normal, a trajectory in X is T D Œ s1.s/; b3.b/; s1.s0/; b1.b0/; m2.m/; b1.r/; l5.l/; m5.m0/ , which can be paraphrased as follows: the sensor s detects a short circuit and commands the breaker b to open; however, b does not open; the sensor s0 detects a short circuit and commands the breaker b0 to open; b0 opens; the monitor m detects the malfunction within the protection apparatus on the left side of the line and commands the recovery breaker r to open without however informing the monitor m0; r opens; the line l cannot be reconnected because, for safety reasons, the recovery breakers cannot be closed; m acknowledges the disconnection of the left side of the line.

4.2 DDES Viewer and Temporal Observation

The notions of a viewer and a temporal observation, deﬁned in Section 2.2 for an AS and naturally inherited by an AU, can be extended to a DDES, as outlined below.

Deﬁnition 15 (DDES Viewer) Let X D .U; L/ be a DDES, where U D .U1; : : : ; Un/. A viewer for X is an array V D .V1; : : : ; Vn/, where 8i 2 Œ1 :: n , Vi is a viewer for Ui.

LAMPERTI, ZANELLA, & ZHAO

Example 17 With reference to Example 15, a viewer for X is V D .VP ; VP 0; VM; VL/, where:

VP D f.s1.s/; awk/; .s2.s/; ide/; .s3.s/; awk/; .s4.s/; ide/; .b1.b/; bop/; .b2.b/; bcl/g

VP 0 D f.s1.s0/; awk0/; .s2.s0/; ide0/; .s3.s0/; awk0/; .s4.s0/; ide0/; .b1.b0/; bop0/; .b2.b0/; bcl0/g

VM D f.m1.m/; trg/; .m2.m/; trg/; .m3.m/; trg/; .b1.r/; rop/; .b2.r/; rcl/; .m1.m0/; trg0/;

.m2.m0/; trg0/; .m3.m0/; trg0/; .b1.r0/; rop0/; .b2.r0/; rcl0/g:

VL D ;, therefore the AU L (line) is unobservable .

Deﬁnition 16 (DDES Temporal Observation) Let T be a trajectory within a space X . The temporal observation of T based on the viewer V, denoted Obs.T; V/, is the array Obs.T; V/ D .O1; : : : ; On/; where 8i 2 Œ1 :: n , Oi D Œ j t.c/ 2 T; c 2 Ui; .t.c/; / 2 Vi .

Example 18 With reference to the trajectory T of X in Example 16 and the viewer V of X in Example 17, the temporal observation of T based on V is Obs.T; V/ D .Œ awk , Œ awk0; bop0 ; Œ trg; rop ; Œ /.

4.3 DDES Ruler and Diagnosis

The notions of a ruler and a diagnosis, deﬁned in Section 2.3 for an AS and naturally inherited by an AU, can be extended to a DDES, as detailed below.

Deﬁnition 17 (DDES Ruler) Let X D .U; L/ be a DDES, where U D .U1; : : : ; Un/. A ruler for X is an array R D .R1; : : : ; Rn/, where 8i 2 Œ1 :: n , Ri is a ruler for Ui.

Example 19 With reference to Example 15, a ruler for X is R D .RP ; RP 0; RM; RL/, where:

RP D f.s3.s/; fso/; .s4.s/; fsc/; .b3.b/; fbo/; .b4.b/; fbc/g

RP 0 D f.s3.s0/; fso0/; .s4.s0/; fsc0/; .b3.b0/; fbo0/; .b4.b0/; fbc0/g

RM D f.m2.m/; fm/; .b3.r/; fro/; .m2.m0/; fm0/; .b3.r0/; fro0/g

RL D f.l1.l/; ﬂs/; .l2.l/; ﬂs/; .l3.l/; ﬂs0/; .l4.l/; ﬂs0/; .l5.l/; ﬂi/; .l6.l/; ﬂi/; .l7.l/; ﬂi0/;

.l8.l/; ﬂi0/; .l9.l/; ﬂp/; .l10.l/; ﬂp/; .l11.l/; ﬂp0/; .l12.l/; ﬂp0/g:

The meaning of the faults is explained in Table 5. Since, by assumption, the recovery breakers r and r0 cannot be closed once opened, the transition b4 is not involved in RM.

Deﬁnition 18 (DDES Diagnosis) Let T be a trajectory in X . The diagnosis of T based on a ruler R D .R1; : : : ; Rn/, denoted Dgn.T; R/, is the set of faults

Dgn.T; R/ D f f j t.c/ 2 T; c 2 Ui; .t.c/; f / 2 Ri; i 2 Œ1 :: n g : (17)

Example 20 With reference to the trajectory T in Example 16 and the ruler R in Example 19, the diagnosis of T based on R is Dgn.T; R/ D f fbo; fm; ﬂi g, that is, b fails to open, m fails to alert m0, and the line l is isolated because a breaker on the left side remains open.

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

Fault Meaning fso Sensor s in P commands breaker b to close instead of open fsc Sensor s in P commands breaker b to open instead of close fbo Breaker b in P keeps being closed instead of opening fbc Breaker b in P keeps being open instead of closing fso0 Sensor s0 in P 0 commands breaker b0 to close instead of open fsc0 Sensor s0 in P 0 commands breaker b0 to open instead of close fbo0 Breaker b0 in P 0 keeps being closed instead of opening fbc0 Breaker b0 in P 0 keeps being open instead of closing fm Monitor m in M does not alert monitor m0 for recovery fro Recovery breaker r in M keeps being closed instead of opening fm0 Monitor m0 in M does not alert monitor m for recovery fro0 Recovery breaker r0 in M keeps being closed instead of opening ﬂs Line l in L keeps being shorted since no breaker on the left side opened ﬂs0 Line l in L keeps being shorted since no breaker on the right side opened ﬂi Line l in L keeps being isolated since a breaker on the left side remains open ﬂi0 Line l in L keeps being isolated since a breaker on the right side remains open ﬂp The short on line l in L persists after reclosing breaker b in P ﬂp0 The short on line l in L persists after reclosing breaker b0 in P 0

Table 5: Faults deﬁned in Example 19.

4.4 DDES Diagnosis Problem

The notion of a diagnosis problem for an AS and relevant solution, deﬁned in Section 2.4, can be extended to a DDES.

Deﬁnition 19 (DDES Diagnosis Problem) Let X be a DDES, x0 the initial state of X, V a viewer for X, O a temporal observation of X, and R a ruler for X. The quadruple

}.X/ D .x0; V; O; R/ (18)

is a diagnosis problem for X. The solution to }.X/ is the set of diagnoses

.}.X// D Dgn.T; R/ j T 2 k X k; Obs.T; V/ D O : (19)

Example 21 A diagnosis problem for the DDES X deﬁned in Example 15 is }.X/ D .x0; V; O; R/, where in the initial state x0 the breakers are closed, the sensors are idle, the monitors are watch, and the line is normal, while the viewer V is deﬁned in Example 17, O D .OP ; OP 0; OM; OL/, with OP D Œawk , OP 0 D Œawk0; bop0 , OM D Œtrg; rop , and OL D Œ , and the ruler R is deﬁned in Example 19.

4.5 Practical Issues in Solving Diagnosis Problems for DDESs

Generating the solution to a diagnosis problem for a DDES based on eqn. (19) is overwhelmingly impractical for the same reasons given in Section 2.4 for ASs. Worse still, the technique provided in Section 2.5 and Section 2.6, namely generation and decoration of the O-constrained space, is bound to become inadequate for solving a diagnosis problem for a DDES. In principle, we might

LAMPERTI, ZANELLA, & ZHAO

extend the notion of an O-constrained space to a DDES, namely X O. In so doing, a state of X O would be identiﬁed by a triple .U ; E; =/, where .U ; E/ is a state in the space X , while = is the array .=1; : : : ; =n/ of indexes of the temporal observations in O. Now, assume that, on average, each AU includes m components. In the worst case, the number of states in X O becomes at least20 exponential with the product n m, where n is the number of AUs in X. Hence, the worst-case complexity is at least exponential with the total number (n m) of components in X, a disturbing perspective. Therefore, solving a DDES diagnosis problem requires more sophisticated (and efﬁcient) techniques than those adopted in diagnosis of ASs. Speciﬁcally, building something analogous to the O-constrained space X O is out of the question. After all, the solution to a diagnosis problem }.X/ is a set of candidate diagnoses, not a set of candidate trajectories within X O. Therefore, chances are that the solution to }.X/ can be determined without generating X O. The challenge is to design a technique for solving a diagnosis problem for X that is, on the one hand, viable, thereby not requiring the generation of the O-constrained space of X (hence, neither the space X nor the O-constrained space X O should be generated) and, on the other, sound and complete, thereby providing exactly the set .}.X// of candidate diagnoses deﬁned in eqn. (19).

5. Preprocessing

To speed up the task performed by the diagnosis engine online, that is, while the DDES is being operated, a certain amount of preprocessing is to be carried out ofﬂine, before the DDES starts being operated. Typically, the speciﬁcation of X is compiled into a variety of data structures, among which are the matchers of the regular expressions associated with the emergent events deﬁned in the AUs (Section 3.1). In general, for each AU U in X, a set E of emergent events is deﬁned as in eqn. (11). In order to trace the occurrences of each emergent event ei.yi/ 2 E, i 2 Œ1 :: h , based on the regular expression ri, a DFA .ei.yi/; ri/ needs to be generated ofﬂine, with each ﬁnal state being marked with ei.yi/. However, since strings of component transitions generating the same emergent event may overlap, the regular language of the matcher is in general wider than the language of the regular expression. To clarify the point, consider the example below.

Example 22 Let .e.y/; r/ be an emergent event in the AU U, with D ft1; t2; t3g being the alphabet of the regular expression r D t1 t C 2 t3 j t2 t C 3 t1. Assume the following trajectory T in U :

t1; t2; t3 t1; ; t1

T 00 ; t3 : (20)

T includes two overlapping subtrajectories matching r, namely T 0 D Œ t1; t2; t3 and T 00 D Œ t2; t3; t1 , where the sufﬁx Œ t2; t3 of T 0 is a preﬁx of T 00. Hence, two occurrences of the emergent event e.y/ are expected in T in correspondence of the last transition of T 0 and T 00, respectively. Assume further to trace the occurrences of e.y/ based on the recognizer of r on the left side of Figure 15, a DFA with the same regular language as r, whose ﬁnal state is marked with the emergent event e.y/. When the ﬁnal state 5 is reached, the emergent event e is generated at the output terminal y of U. The sequence of states of this recognizer is outlined in the second row of Table 6, where each state is reached by the corresponding transition of T listed in the ﬁrst row of

20. For more accurate ﬁgures (and even increasing complexity), we also need to account for the combinations of arrays of events in links.

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

state NFA states 0 f0g 1 f0; 1g 2 f0; 2g 3 f0; 2; 3g 4 f0; 4g 5 f0; 4; 5g 6 f0; 1; 5g

Figure 15: From left to right: (1) recognizer of r D t1 t C 2 t3 j t2 t C 3 t1, where D ft1; t2; t3g; (2) NFA obtained by the insertion of the "-transitions; (3) matcher .e.y/; r/ resulting from the determinization of the NFA; and (4) state details for the matcher .

the table. As indicated in the third row, the emergent event e.y/ is correctly generated at the fourth transition in T , which is the last transition of the subtrajectory T 0. At this point, since no transition exits the ﬁnal state 5, the recognizer starts again from the initial state 0 in order to keep matching. It ﬁrst changes state to 1 in correspondence of t1, and with t3 (mismatch) it returns to 0. The result is that, owing to the overlapping of the subtrajectories T 0 and T 00, the second occurrence of e.y/ is not detected.

Given the pair .e.y/; r/, in order to recognize all (possibly overlapping) instances of r, we need to transform the recognizer of r into a matcher of r, as follows:

1. An "-transition is inserted into the recognizer from each non-initial state to the initial state;21

2. The nondeterministic ﬁnite automaton (NFA) obtained in step 1 is determinized into an equivalent DFA;

3. The DFA generated in step 2 is minimized, thereby obtaining the matcher of r.

The ﬁnal states of the minimized DFA (the matcher) are marked with the emergent event e.y/.

Example 23 With reference to Example 22, consider the recognizer of the regular expression r displayed on the left side of Figure 15. Outlined on the right of the recognizer is the NFA obtained by inserting ﬁve "-transitions (dashed arrows) toward the initial state (step 1). The DFA resulting from the determinization of the NFA is displayed next to the NFA (step 2), with states being detailed in the table. Incidentally, this DFA is also minimal, thus minimization (step 3) is not applied. In conclusion, the DFA on the right side of Figure 15 is the matcher .e.y/; r/, with the ﬁnal states 5 and 6 being marked with e.y/. The dynamics of the matching performed by .e.y/; r/ on the trajectory T is outlined in the last two rows of Table 6. In sharp contrast with the recognizer of r, which produces only one e.y/, the matcher correctly detects the emergent event twice, based on the two overlapping subtrajectories of T , namely T 0 D Œ t1; t2; t3 and T 00 D Œ t2; t3; t1 . Unlike the recognizer of r, after reaching the state 5 and generating e.y/, the next transition t1 moves the matcher to the other ﬁnal state 6, thereby generating the second occurrence of e.y/ correctly.

LAMPERTI, ZANELLA, & ZHAO

Transitions in T t3 t1 t2 t3 t1 t3 States of recognizer of r 0 1 3 5 1 0 Detected emergent events e.y/ States of matcher .e.y/; r/ 0 1 3 5 6 0 Detected emergent events e.y/ e.y/

Table 6: Detection of emergent events with overlapping.

A formal peculiarity of a matcher is that, since it is a DFA, it is always in a single state regardless of the trajectory under consideration. Speciﬁcally, whatever the number of overlapping events, the mode in which the matcher is derived from the NFA (where the "-transitions are inserted) allows the matcher to account for the recognition of all these events by means of a single state (simultaneously). But, is the set of emergent events detected by a matcher actually sound and complete? The answer to this question is given by the following proposition.

Proposition 3 Let .e.y/; r/ be a matcher for an active unit U. The set of emergent events detected by .e.y/; r/ is sound and complete.

Proof. Grounded on Lemma 3.1, Lemma 3.2, Lemma 3.3, and Lemma 3.4.

Lemma 3.1 Let N be the NFA from which the matcher .e.y/; r/ is generated by Subset Construction. Each state of .e.y/; r/ includes the initial state of N .

Proof. Since N is the NFA obtained from the recognizer of r by the insertion of an "- transition from each state of to the initial state of , each state of the matcher generated by Subset Construction by means of an "-closure will include the initial state of N .

Lemma 3.2 Let m be a state of the matcher .e.y/; r/ and T a string in the language of r. There exists a sequence of transitions in the matcher, from m to a ﬁnal state, that generates T .

Proof. According to Lemma 3.1, the state m includes the initial state n0 of the NFA N . Thus, m includes the "-closure of n0, namely the initial state m0 of the matcher. Let T D Œt1; : : : ; tk . Since t1 exits m0, t1 exits m also. By induction on T , since T leads to a ﬁnal state mf of the matcher, the state m0 reached by m with T will include the set of N states identifying mf. Hence, m0 is ﬁnal also; in other words, T is generated starting from m.

Lemma 3.3 (Soundness) Let u D .S; E; M/ be a state of U where the state m in M relevant to .e.y/; r/ is ﬁnal. There exists a subtrajectory Tij entering u such that the subsequence Tij . / of Tij that includes the transitions in the alphabet of r is a string in the language of r.

Proof. By contradiction. Assume that there is no such Tij in U . If so, either there is a set of subtrajectories entering u such that the subsequence of a preﬁx of them that includes the transitions in is a preﬁx of a string in the language of r or not. If these subtrajectories exist, the state m in M relevant to .e.y/; r/ cannot be ﬁnal. If no such subtrajectory exists, based on Deﬁnition 12, m equals the initial state of .e.y/; r/. Both cases contradict the assumption that m is ﬁnal.

21. So, if the recognizer includes n states, then the number of "-transitions will be n 1.

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

Lemma 3.4 (Completeness) Let Tij D Œti; ti C1; : : : ; tj be a subtrajectory of U entering a state .S; E; M/ of the unit space U . Let Tij . / be the subsequence of Tij that includes the transitions in the alphabet of r. If Tij . / is a string in the language of r, then the state m in M relevant to the matcher .e.y/; r/ is marked with the emergent event e.y/.

Proof. Let m be the state of the matcher .e.y/; r/ when Tij . / starts being recognized. By virtue of Lemma 3.2, Tij . / is generated from m to a ﬁnal state of the matcher, upon which the emergent event e.y/ is generated.

Eventually, the proof of Proposition 3 comes from Lemma 3.3 and Lemma 3.4.

6. Lazy Problem-Solving

As pointed out in Section 4.5, solving a diagnosis problem for a DDES X by adapting the technique designed for solving diagnosis problems of (plain) ASs is impractical. Speciﬁcally, we can no longer rely on the generation of the O-constrained space of X (cf. Section 2.5). On the other hand, whatever the alternative problem-solving technique, soundness and completeness are required. In other words, any (viable) alternative technique is expected to generate the solution to the diagnosis problem deﬁned in eqn. (19), that is, exactly the same set of candidate diagnoses. This section introduces a lazy technique for solving a DDES diagnosis problem. The technique is called lazy inasmuch it does not require the generation of the O-constrained space of the (whole) DDES X. Instead, it generates an extended constrained space of each AU incorporated in X. Basically, the idea stems from the following considerations. Since the AUs in X are accommodated hierarchically, and since the events emerging in one unit U are consumed by the parent unit U0 only, it follows that U can inﬂuence the behavior of U0. Conversely, since an emergent event in U cannot be generated if the corresponding link is not empty, it follows that U0 (which may or may not consume the emergent event already stored in the link) may inﬂuence the behavior of U. Hence, the behavior of each AU is constrained by the behavior of other units only loosely, that is, through emergent events. This opens the way to the possibility of focusing on the generation of the subspace of each single AU U based on the constraints coming from its child units. In generating this new sort of constrained space of U, a subset of the behavior of any child unit of U can be inconsistent and, as such, it is pruned. The same applies to the behavior of U when considered in the generation of the constrained space of its parent unit, up to the root node of the hierarchy. In summary, we can envisage a viable technique that generates the constrained behavior of each AU rather than the constrained behavior of the whole system. The behavior is constrained not only by the temporal observation of the unit, but also by the emergent events generated by the child AUs. The question now becomes: How is it possible to focus on the constrained space of each single AU and, at the same time, guarantee the soundness and completeness of the diagnosis result? The answer to this question stems from the mode in which the constraints from child AUs are enforced. In fact, it is not the constrained space of a child AU that is considered but, rather, its interface. The interface of a constrained space carries information on the emergent events generated by the child AU U and the associated candidate diagnoses relevant to all the AUs in the DDES rooted in U.22

It is of utmost importance noticing that, in addition to the emergent events, the interface carries absolutely no information on the trajectories relevant to the sub-DDESs rooted in the child units, but

22. Roughly, any subtree in the DDES hierarchy is a (sub-)DDES on its own.

LAMPERTI, ZANELLA, & ZHAO

only the diagnoses relevant to these trajectories. Thus, the top-down inﬂuence of a parent unit on its child units translates to the removal of the set of diagnoses associated with inconsistent emergent events. This way, both types of inﬂuence on the behavior, namely from children to parent and from parent to children, can be managed in a single bottom-up traversing of the DDES, where the inﬂuence of the parent unit on the child units is accounted for by pruning the inconsistent emergent events along with the associated diagnosis sets (as underlined above, the diagnosis sets associated with the emergent events coming from a child unit U are relevant to all the AUs in the DDES rooted in U). Eliminating the set of diagnoses associated with the inconsistent emergent events is equivalent to removing the inconsistent trajectories of the sub-DDESs rooted in the child units. As a result, when generating the constrained space of the root node Ux of X, the transitions are marked with the candidate diagnoses of the subtrees rooted in the child units of Ux. By exploiting this extra piece of diagnosis information on child units, the eventual decoration of the constrained space of Ux will generate the (sound and complete) set of candidate diagnoses for X, as proven in Theorem 1 (Appendix A). The formalization of the lazy diagnosis technique is presented in the next sections, where the (circular) notions of interface constraint (Section 6.1), constrained unit space (Section 6.2), fragment (Section 6.3), interface (Section 6.4), and hidden set (Section 6.5) are introduced.

6.1 Interface Constraint

The lazy problem-solving technique generates an extended constrained space for each AU of the DDES. This is carried out bottom-up, starting from leaf AUs up to the root of the hierarchy. For each AU U, the corresponding constrained space is generated based on an interface constraint.

Deﬁnition 20 (Interface Constraint) Let U be an AU, u0 the initial state of U, V a viewer for U, O a temporal observation of U, R the array of rulers for the AUs in the subtree rooted in U, .U1; : : : ; Uk/ the (possibly empty) array of child AUs of U, and I the array of interfaces of the constrained AU spaces U 1 1; : : : ; U k k.23 The 5-tuple

D .u0; V; O; R; I/ (21)

is an interface constraint for U.

The interface constraint may be thought of as a sort of extended diagnosis problem for U, with the additional ﬁeld I. This way, the unit space constrained by (Section 6.2) accounts not only for the model and the temporal observation of U, but for the mode in which emergent events are generated by the child AUs and consumed by U. Notice that, if U is a leaf node, then the array I is null.

Example 24 Consider the AU P within the DDES X deﬁned in Example 15 (Figure 11). An interface constraint for P is P D .u0; VP ; OP ; .RP /; IP /, where u0 D .idle; closed/, VP is the viewer deﬁned in Example 17, OP is the temporal observation deﬁned in Example 21, RP is the ruler deﬁned in Example 19, and IP is null (P is a leaf AU in the hierarchy of X). Similarly, an interface constraint for the AU P 0 is P 0 D .u0 0; VP 0; OP 0; .RP 0/; IP 0/, where u0 0 D .idle; closed/, VP 0 is the viewer deﬁned in Example 17, OP 0 is the temporal observation deﬁned in Example 21, RP 0 is the ruler deﬁned in Example 19, and IP 0 is null (P 0 is a leaf AU in X).

23. As detailed in Section 6.4, an interface is a DFA derived from a constrained unit space (Section 6.2).

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

6.2 Constrained Unit Space

As outlined in Section 6.1, within an interface constraint D .u0; V; O; R; I/, the i-th element of the array I, i 2 Œ1 :: k , is the interface of the constrained space of the i-th child AU of U, denoted Int.U i i/. As formalized in Section 6.4, Int.U i i/ is a DFA whose alphabet is a set of pairs .E; /, where E is a set of (output) emergent events in Ui, while is a set of diagnoses associated with the trajectories of the DDES rooted in Ui. The interfaces of the child AU constrained spaces are exploited for the generation of the constrained space of the parent AU U by maintaining the conﬁgurations of the links exiting the output terminals of the child units, thereby enforcing the constraints imposed by the interaction of the child units with the parent unit. In particular, a transition of the constrained space of U is marked either by a transition of a component in U (along with the associated emergent output events in U and associated fault, if any), or by the pair marking a transition in one of the child-unit constrained-space interfaces. In other words, the constrained space of U carries mixed information in its transitions, speciﬁcally either:

A triple .t.c/; E; fıg/, where t.c/ is a component transition in U, E is the set of emergent output events of U occurring at t.c/, and ı is either ;, if t.c/ is normal, or ff g, if f is the fault associated with the faulty transition t.c/; or

A pair .E; /, where E is the set of emergent events occurring in one child AU, and is the set of diagnoses of the trajectories of the DDES rooted in the child unit that are associated with the occurrence of E.

Compared with a state of the unit space deﬁned in Section 3.2, namely .S; E; M/, a state of the constrained unit space will involve three additional ﬁelds, namely:

H , the array of (possibly empty) emergent events stored in the links exiting the output terminals of the child AUs;

I, the array of states of the interfaces of the constrained child units;

= the index of the temporal observation.

Deﬁnition 21 (Constrained Unit Space) Let U D . u; U; u; u0; Uf/ be the space of an AU U and D .u0; V; O; R; I/ an interface constraint for U, where O D Œ 1; : : : ; n and RU 2 R the ruler relevant to U. The spurious space of U constrained by is a DFA

NU D . ; W; ; w0; Wf/: (22)

Speciﬁcally, the alphabet is T 2E ffıgg [ 1[: : :[ k, where T is the set of transitions of components in U, E the set of emergent events deﬁned in U, ı either ; or the singleton ff g, with f being a fault of the ruler RU, and i, i 2 Œ1 :: k , the alphabet of Int.U i i/. W is the set of states .S; E; M; H ; I; =/, where .S; E; M/ is a state in U , H D .e1; : : : ; eh/ the array of the (possibly empty) emergent events ready at input terminals of U, I D .I1; : : : ; Ik/ the array of states of the interfaces in I, and = an index of O. The initial state is w0 D .S0; E0; M0; H0; I0; 0/, where .S0; E0; M0/ is the initial state u0 of U , H0 D ."; : : : ; "/, and I0 D .I10; : : : ; Ik0/ the array of initial states of the interfaces in I. Wf W is the set of ﬁnal states .S; E; M; H ; I; n/, where

LAMPERTI, ZANELLA, & ZHAO

.S; E; M/ 2 Uf, H D ."; : : : ; "/, I D .I1; : : : ; Ik/ such that 8i 2 Œ1 :: k , Ii is ﬁnal in the i-th interface in I. The transition function is W W 7! W , where either: .S; E; M; H ; I; =/; Ej ; j ; .S; E; M; H 0; I0; =/ 2 (23)

if and only if:

D Ij ; .Ej ; j /; I 0 j E is a transition in the j-th interface in I, j 2 Œ1 :: k ;

8e.y/ 2 Ej , H Œlink.y/ D ";

8i 2 Œ1 :: h ; H 0Œi D e if e.y/ 2 Ej and link.y/ D li H Œi otherwise;

8i 2 Œ1 :: k ; I0Œi D I 0 j if i D j IŒi otherwise;

or .S; E; M; H ; I; =/; t.cj /; NE; N ; .S 0; E 0; M 0; H 0; I; =0/ 2 (24)

if and only if:

.S; E; M/; t.cj /; .S 0; E 0; M 0/ is a transition in U ;

NE is the set of emergent events generated by the above transition in U , on condition that NE includes at most one event for the same output terminal, that is, fe.y/; e0.y/g ª NE;

t.cj / D hs; .e.x/; fe1.y1/; : : : ; ev.yv/g/; s0i;

e.x/ D ", or x is not linked with an input terminal of U24, or x is linked with an input terminal of U and H Œlink.x/ D e;

If x is not linked with an input terminal of U then H 0 D H , else

8i 2 Œ1 :: k ; H 0Œi D " if link.x/ D li H Œi otherwise;

=0 D = C 1 if .t.cj /; / 2 V and D =C1 = if .t.cj /; / VI

N D fff gg if .t.cj /; f / 2 RU f;g otherwise.

The space of U constrained by , namely U , is the DFA obtained from the (spurious) NU by pruning all states and transitions that are not connected with any ﬁnal state. A pathp within U D . ; W; ; w0; Wf/ is a ﬁnite sequence of contiguous transitions in ,

p D hw0; 1; w1i; hw1; 2; w2i; : : : ; wq 1; q; wq (25)

where i 2 , i 2 Œ1 :: q , and wq 2 Wf. The (ﬁnite) sequence Œ 1; : : : ; q of symbols marking the transitions of p is denoted .p/. The (possibly inﬁnite) set of paths within U is denoted k U k.

24. In this case, it means that x is connected with a link embedded in U.

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

State S E M = 0 .idle; closed/ ."/ .0; 0; 0; 0/ 0 1 .awaken; closed/ .op/ .0; 0; 1; 0/ 1 2 .awaken; closed/ .cl/ .0; 0; 2; 0/ 1 3 .awaken; closed/ ."/ .0; 0; 2; 0/ 1 4 .awaken; closed/ ."/ .0; 0; 0; 0/ 1

Figure 16: Constrained space P P of the AU P (left); the state contents are detailed in the table on the right side (bold states in M indicate the detection of the output emergent event).

Example 25 Consider the interface constraint P deﬁned in Example 24. The space of P constrained by P , namely P P is displayed in Figure 16 (left), along with state details (right). Since P is a leaf AU in X, the ﬁelds I and H are empty (that s why they are not considered). Likewise, displayed in Figure 17 is the space of the AU P 0 constrained by P 0, which is deﬁned in Example 24.

6.3 Fragment

To deﬁne the interface of a constrained AU space (Section 6.4), we ﬁrst need to introduce the notion of a fragment of a constrained AU space U . This is because a state of the interface is a set of fragments. A fragment is associated with a state of U , starting from the initial state w0. Roughly, given a state Nw of U , the corresponding fragment U . Nw/ is the subgraph of U that is reachable from Nw by transitions either marked with a pair .E; / or a triple .t.c/; ;; fıg/, that is, where no emergent event is generated upon t.c/. Besides, each state w incorporated in the fragment is extended with a diagnosis information, namely the set of diagnoses relevant to the paths connecting Nw with w. These diagnoses are generated by joining the diagnoses marking the transitions in each path (by means of the join operator deﬁned in Section 2.3). This way, each state of the fragment carries (partial) diagnosis information of the entire (sub-)DDES rooted in U.

State S E M = 0 .idle; closed/ ."/ .0; 0; 0; 0/ 0 1 .awaken; closed/ .op/ .0; 0; 1; 0/ 1 2 .awaken; open/ ."/ .1; 0; 0; 0/ 2

Figure 17: Constrained space P 0 P0 of the AU P 0 (left); the state contents are detailed in the table on the right side (bold states in M indicate the detection of the output emergent event).

LAMPERTI, ZANELLA, & ZHAO

Figure 18: Fragment relevant to the initial state of the constrained space of AU P in Figure 16.

Deﬁnition 22 (Fragment) Let U D . ; W; 0; w0; Wf/ be a constrained unit space, and Nw 2 W . The fragment of U rooted in state Nw is a DFA

U . Nw/ D . ; ; ; '0/: (26)

The set of states is W 2ı, where ı is the domain of the possible diagnoses including the faults involved in the array of rulers in the constraint . The transition function W 7! is deﬁned as follows. Each state .w; / 2 is such that is the minimal set deﬁned by the following two rules:

1. If w D Nw, then ; 2 ;

2. If .w0; 0/; E; N ; .w; / 2 or .w0; 0/; t.c/; ;; N ; .w; / 2 , then 0 N .

'0 D . Nw; N / is the initial state. The transition function is deﬁned as follows: .w; /; E; N ; .w0; 0/ 2 if and only if w; E; N ; w0 2 0

or .w; /; t.c/; ;; N ; .w0; 0/ 2 if and only if w; t.c/; ;; N ; w0 2 0:

Example 26 With reference to the constrained space P P displayed in Figure 16 (Example 25), the fragment relevant to the initial state, namely P P .0/, is shown in Figure 18.

6.4 Interface

As outlined in Section 6.2, the constrained space of an AU must comply with the interfaces of the child AU constrained spaces. The interface of a constrained space of an AU U is a DFA where states are sets of fragments of the constrained space, while transitions are marked with pairs .E; /, where E is a set of output emergent events, and is the associated set of diagnoses for the DDES rooted in U. Thus, each diagnosis in may involve faults relevant to any unit in the subtree rooted in U. More precisely, each diagnosis in is relevant to a subtrajectory of the DDES NU rooted in U. As such, is the diagnosis surrogate of the (possibly inﬁnite) set of semi-trajectories of the DDES NU within the fragment (including the component transition in U exiting the fragment).

Deﬁnition 23 (Interface) Let U D . 0; W; 0; Nw0; Wf/ be a constrained unit space, where D .u0; V; O; R; I/. The interface of U , namely Int.U /, is a DFA:

Int.U / D . ; I; ; i0; If/: (27)

Speciﬁcally, the alphabet is D 2E 2ı, where E is the set of emergent events in U, and ı is the domain of possible diagnoses that include faults relevant to R. The set of states is I D

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

Figure 19: Interface of the constrained space of the AU P in Figure 16, namely Int.P P / (left) and interface of the constrained space of the AU P 0 in Figure 17, namely Int.P 0 P0/ (right).

2 , where is the set of all fragments of U . The initial state is the singleton including the fragment relevant to w0, namely i0 D f U .w0/ g. The set of the ﬁnal states is If I, where 8if 2 If . ' 2 if; .w; / 2 .'/; w 2 Wf / : The transition function is W I 7! I, where: hi; .E; /; i0i 2 iff ' 2 i, .w; N / 2 .'/, hw; .t.c/; E; /; w0i 2 0, E ;, D N , and U .w0/ 2 i0. A pathp within an interface Int.U / is a ﬁnite contiguous sequence of transitions in , p D hi0; .E1; 1/; i1i; hi1; .E2; 2/; i2i; : : : ; iq 1; .Eq; q/; iq , where iq 2 If. The (ﬁnite) sequence Œ .E1; 1/; : : : ; .Eq; q/ of symbols marking the transitions of p is denoted .p/. The (possibly inﬁnite) set of paths within Int.U / is denoted k Int.U /k.

Example 27 With reference to Example 25, consider the constrained spaces P P and P 0 P0 displayed in Figure 16 and Figure 17, respectively. The corresponding interfaces Int.P P / and Int.P 0 P0/ are shown in Figure 19. Based on these interfaces, we can determine the constrained space of the AU M, the monitoring apparatus (Figure 11), along with the corresponding interface. An interface constraint for M is M D .m0; VM; OM; .RP ; RP 0; RM/; IM/, where m0 D .watch; closed; watch, closed/, VM is the viewer deﬁned in Example 17, OM is the temporal observation deﬁned in Example 21, RP ; RP 0, and RM are the rulers deﬁned in Example 19, and IM D .Int.P P /; Int.P 0 P0//. The space of M constrained by M, namely M M is shown in Figure 20, with details of the states being listed in Table 7. The interface, namely Int.M M/ is outlined in Figure 21.

6.5 Hidden Set

As pointed out in Section 6.2, the transitions within the constrained space of an AU U are marked with sets of diagnoses relevant either to U or to the DDESs rooted in the child units of U. Thus, joining together the set of diagnoses relevant to a path in the constrained space is bound to generate a set of candidate diagnoses for the DDES rooted in U. In particular, if U is the root node of the hierarchy of the DDES X, then these should be the candidate diagnoses of X, that is, a subset of the solution to the diagnosis problem for X.25 However, if we consider how the constrained space

25. To obtain all the candidate diagnoses, we need to consider every path in the constrained space.

LAMPERTI, ZANELLA, & ZHAO

Figure 20: Constrained space M M of the AU M; the content of the states is detailed in Table 7.

is generated, we will ﬁnd out that some diagnosis information is missing. Speciﬁcally, there is a set of diagnoses that is hidden in the constrained space, which we call the hidden set. To simplify the picture, consider a DDES X, with U being the root node, and U1 and U2 the child units of U. No other AU is included in X (hence, U1 and U2 are leaf nodes). Consider a path p within the constrained space of U, from the initial state w0 to a ﬁnal state wq. Let Œ 0; 1; : : : ; q be the sequence of diagnosis sets involved in p. The combination of such diagnosis sets, namely D 0 1 q, generates a set of diagnoses for X. However, in order for a set ı of faults to be a candidate diagnosis of X, ı shall be relevant to a complete trajectory of X. To this end, we need to consider the tail of the trajectories of X that are encapsulated within the fragments included in the ﬁnal states I1 and I2 of the interfaces of the constrained spaces of U1 and U2, which are part of the ﬁnal state wq of the path p. Considering a set of faults ı 2 , in order for ı to be a candidate diagnosis of X, we need to extend ı with a diagnosis in N 1 such that . Nw1; N 1/ is a state of a fragment in I1 where Nw1 is ﬁnal, and a diagnosis in N 2 such that . Nw2; N 2/ is a state of a fragment in I2 where Nw2 is ﬁnal. This way, we enrich ı with the set of faults relevant to the transitions of the components in U1 and U2 that complete a trajectory in X. To obtain the complete set of candidate diagnoses, this operation should be performed for each ı 2 and for each state .w; / within the fragments relevant to I1 and I2, respectively, such that w is ﬁnal in the corresponding constrained space.

Deﬁnition 24 (Hidden Set) Let X be a DDES, U an AU in X, U D . ; W; ; w0; Wf/ the unit space constrained by D .u0; V; O; R; I/, and w D .S; E; M; H ; I; =/ a state in W . The hidden set of w, namely r.w/, is the set of diagnoses recursively deﬁned as follows:

r.w/ D f;g if U is a leaf node in X N i2I r.i/ otherwise (28)

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

State S E M H I = 0 .watch; closed; watch; closed/ ."; "; "; "/ .0; 0; 0; 0; 0; 0/ ."; "/ .0; 0/ 0 1 .watch; closed; watch; closed/ ."; "; "; "/ .0; 0; 0; 0; 0; 0/ .nd; "/ .1; 0/ 0 2 .watch; closed; watch; closed/ ."; "; "; "/ .0; 0; 0; 0; 0; 0/ ."; di0/ .0; 1/ 0 3 .watch; closed; watch; closed/ ."; "; "; "/ .0; 0; 0; 0; 0; 0/ .nd; "/ .2; 0/ 0 4 .trigger; closed; watch; closed/ .op; "; "; "/ .0; 1; 0; 0; 0; 0/ ."; "/ .1; 0/ 1 5 .watch; closed; watch; closed/ ."; "; "; "/ .0; 0; 0; 0; 0; 0/ .nd; di0/ .1; 1/ 0 6 .watch; closed; watch; closed/ ."; "; "; "/ .0; 0; 0; 0; 0; 0/ ."; "/ .0; 1/ 0 7 .watch; closed; watch; closed/ ."; "; "; "/ .0; 0; 0; 0; 0; 0/ .nd; di0/ .2; 1/ 0 8 .trigger; closed; watch; closed/ .op; "; "; "/ .0; 1; 0; 0; 0; 0/ ."; "/ .2; 0/ 1 9 .trigger; open; watch; closed/ ."; "; "; "/ .1; 1; 0; 0; 0; 0/ ."; "/ .1; 0/ 2 10 .trigger; closed; watch; closed/ .op; "; "; "/ .0; 1; 0; 0; 0; 0/ ."; di0/ .1; 1/ 1 11 .watch; closed; watch; closed/ ."; "; "; "/ .0; 0; 0; 0; 0; 0/ .nd; "/ .1; 1/ 0 12 .watch; closed; watch; closed/ ."; "; "; "/ .0; 0; 0; 0; 0; 0/ .nd; "/ .2; 1/ 0 13 .trigger; closed; watch; closed/ .op; "; "; "/ .0; 1; 0; 0; 0; 0/ ."; di0/ .2; 1/ 1 14 .trigger; open; watch; closed/ ."; "; "; "/ .1; 1; 0; 0; 0; 0/ ."; "/ .2; 0/ 2 15 .trigger; open; watch; closed/ ."; "; "; "/ .1; 1; 0; 0; 0; 0/ ."; di0/ .1; 1/ 2 16 .trigger; closed; watch; closed/ .op; "; "; "/ .0; 1; 0; 0; 0; 0/ ."; "/ .1; 1/ 1 17 .trigger; closed; watch; closed/ .op; "; "; "/ .0; 1; 0; 0; 0; 0/ ."; "/ .2; 1/ 1 18 .trigger; open; watch; closed/ ."; "; "; "/ .1; 1; 0; 0; 0; 0/ ."; di0/ .2; 1/ 2 19 .trigger; open; watch; closed/ ."; "; "; "/ .1; 1; 0; 0; 0; 0/ ."; "/ .1; 1/ 2 20 .trigger; open; watch; closed/ ."; "; "; "/ .1; 1; 0; 0; 0; 0/ ."; "/ .2; 1/ 2

Table 7: Transition details for the states in the constrained space of M displayed in Figure 20.

where r.i/ is the hidden set of an interface state i, deﬁned as follows:26

'2i;.wf; f/2 .'/;wf2Wf

8 : f r.wf/ 9 ; : (29)

Example 28 In order to see a meaningful example, we assume a hypothetical scenario in which the constrained space of the AU L includes a ﬁnal state w such that I D .i/, where i is a state of the interface of the constrained space of M. We assume that i includes just one fragment involving two ﬁnal states, namely w1 and w2, with associated diagnosis sets .w1/ D fffm; frogg and .w2/ D f;g. On their turn, w1 involves the ﬁeld I D .i1; i0 1/, while w2 involves the ﬁeld I D .i2; i0 2/. We assume that the states i1; i0 1; i2, and i0 2 include one fragment each, involving one ﬁnal state, namely Nw1, Nw2, Nw0 1, and Nw0 2, respectively, where . Nw1/ D fffsog; ffbogg, . Nw2/ D f;g, . Nw0 1/ D fffsc0; fbo0gg, and . Nw0 2/ D fffsc0g; ffso0; fbo0gg. According to eqn. (28) and eqn. (29), the hidden

26. Note the circular dependency between .w/ and r.i/.

LAMPERTI, ZANELLA, & ZHAO

Figure 21: Interface of M M (Figure 20); in fragments, only the diagnosis sets associated with the states are outlined, with the labels associated with the transitions being omitted.

set of w is

r.w/ D r.i/ D . .w1/ r.w1// [ . .w2/ r.w2//

D .w1/ r.i1/ r.i0 1/ [ .w2/ r.i2/ r.i0 2/

D .w1/ . . Nw1/ f;g/ . Nw0 1/ f;g [

.w2/ . . Nw2/ f;g/ . Nw0 2/ f;g

D fffm; frogg .fffsog; ffbogg f;g/ .fffsc0; fbo0gg f;g/ [

f;g .f;g f;g/ .fffsc0g; ffso0; fbo0gg f;g/

D fffm; frogg fffsog; ffbogg fffsc0; fbo0gg [ fffsc0g; ffso0; fbo0gg

D fffm; fro; fso; fsc0; fbo0g; ffm; fro; fbo; fsc0; fbo0g; ffsc0g; ffso0; fbo0gg:

Each diagnosis in the hidden set of w includes the faults relevant to the inferior AUs in the hierarchy, namely M, P, and P 0.

6.6 Final Decoration

Assume that U is the root node of a DDES X. Once the constrained space of U, namely U , has been generated, we are ready to derive the solution to the diagnosis problem for X by means of a decoration technique similar to that outlined in Section 2.6 for (plain) ASs. Intuitively, we have to

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

consider each path p 2 k U k, and combine the diagnosis sets marking p along with the hidden set of the ﬁnal state of p. Practically, we perform a decoration of U , where the ﬁnal states are marked with the candidate diagnoses of X.

Deﬁnition 25 (Decorated Constrained Space) Let X be a DDES, U the root node of X, and U D . ; W; ; w0; Wf/ the unit space of U constrained by D .u0; V; O; R; I/. The decorated constrained space of U is the DFA Ud obtained from U by marking each state w with the minimal set .w/ of diagnoses based on the following two rules:

1. ; 2 .w0/;

2. If either w; E; N ; w0 2 or w; t.c/; E; N ; w0 2 , then .w0/ 8 : .w/ N 9 ;.

The diagnosis set of Ud , .Ud /, is the set of diagnoses

8 : .wf/ r.wf/ 9 ; : (30)

Remarkably, .Ud / is the solution to the diagnosis problem }.X/ deﬁned in eqn. (19) of Section 4.4, as claimed in Theorem 1.

Theorem 1 Let }.X/ D .x0; V; O; R/ be a diagnosis problem for the DDES X, U the root node in X, and Ud the decorated constrained space of U. We have

.}.X// D Ud : (31)

A proof of Theorem 1 is given in Appendix A. The proof makes use of four additional deﬁnitions, namely Deﬁnition 26 (diagnosis set resulting from the join of a sequence of sets of diagnoses), Deﬁnition 27 (path of a constrained unit space U and relevant diagnosis set, along with the diagnosis set of U ), Deﬁnition 28 (path of an interface Int.U / and relevant diagnosis set, along with the diagnosis set of Int.U /), and Deﬁnition 29 (projection of a diagnosis problem on a subtree of the DDES). Besides, two ancillary propositions are introduced, namely Proposition 4 and Proposition 5. Proposition 4 claims that the projection NT of a trajectory T in X on the subtree NU of X rooted on an active unit U, with O being the temporal observation relevant to T , is such that NT 2 NU and

Figure 22: Dependency graph of the proof of Theorem 1 (cf. Appendix A).

LAMPERTI, ZANELLA, & ZHAO

the temporal observation relevant to NT equals the projection of O on NU. Proposition 5 claims that the diagnosis set of a unit space U equals the diagnosis set of Int.U /. In other words, the set of diagnoses associated with the paths in the respective graphs are the same. The actual proof of Theorem 1 is based on four lemmas, namely Lemma 1.1, Lemma 1.2, Lemma 1.3, and Lemma 1.4. The dependencies between the theorem, the relevant lemmas, and the ancillary propositions are depicted in Figure 22. Lemma 1.1 claims that, given a diagnosis problem }.X/, a relevant projection }. NU/, and a constraint for U involving the parameters of }. NU/, if ı 2 .}. NU//, with T being a trajectory generating ı, then .1/ U contains a path p whose diagnosis set equals ı, and .2/ the sequence of component transitions in U within the triples marking p equals the subsequence of T involving the transitions of components in U only. Roughly, this means that each diagnosis within the solution to }. NU/ is included in the diagnosis set of the constrained space U (completeness of .U /). As such, this lemma supports the proof of Lemma 1.2, which states the completeness of .Ud /, that is, .Ud / .}.X//. In an analogous way, Lemma 1.3 claims that, given a diagnosis problem }.X/, a relevant projection }. NU/, and a constraint for U involving the parameters of }. NU/, if ı 2 .U /, with ı

being a diagnosis relevant to a path p in U , then .1/ ı 2 .}. NU//, with T being the trajectory

in NU generating ı, and .2/ the sequence of component transitions in U within the triples marking p equals the subsequence of T involving the transitions of components in U only. Roughly, this means that each diagnosis within the diagnosis set of the constrained space U is included in the

solution to }. NU/ (soundness of .U /). As such, this lemma supports the proof of Lemma 1.4, which states the soundness of .Ud /, that is, .Ud / .}.X//.

Eventually, soundness (Lemma 1.3) and completeness (Lemma 1.1) of .Ud / prove the correctness of Theorem 1.

Example 29 Consider the interface of the constrained space of the AU M, namely Int.M M/, displayed in Figure 21. Based on this interface, we can determine the constrained space of the AU L, the line (cf. Figure 11), along with its decoration. An interface constraint for L is L D .l0; VL; OL; R; IL/, where l0 D .normal/, VL D ;, OL is empty, R is the ruler deﬁned in Example 19, and IL D .Int.M M//. The space of L constrained by L, namely L L, is shown on

State S H I = 0 .normal/ ."; "/ .0/ 0 1 .normal/ .nr; "/ .1/ 0 2 .normal/ .nr; "/ .2/ 0 3 .normal/ .nr; "/ .3/ 0 4 .isolated/ ."; "/ .1/ 0 5 .isolated/ ."; "/ .2/ 0 6 .isolated/ ."; "/ .3/ 0

Figure 23: Constrained space of the AU L (left), details of states where the empty ﬁelds E and M are omitted (center), and corresponding decorated constrained space where labels associated with transitions are omitted (right).

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

the left side of Figure 23. The decorated space Ld L is depicted on the right side. According to eqn. (30), the relevant diagnosis set is .Ld L/ D . .4/ r.4//[. .5/ r.5//[. .6/ r.6//, where, based on the state details in Figure 23, r.4/ D .1/, r.5/ D .2/, and r.6/ D .3/, where 1, 2, and 3 are the ﬁnal states of Int.M M/ (cf. Figure 21). Speciﬁcally, .1/ is . .19/ r.19//[. .19/ r.19//[. .19/ r.19// D . .19/ r.19// D f;g f;g D f;g. Likewise, .2/ D .3/ D f;g. Hence, .Ld L/ D fffbo; fm; ﬂigg f;g [ fffbo; fm; ﬂig; ffso; fm; ﬂigg f;g [ fffso; fm; ﬂigg f;g D fffbo; fm; ﬂig; ffso; fm; ﬂigg. Based on Theorem 1 in Appendix A, .Ld L/ is the solution to the diagnosis problem }.X/ deﬁned in Example 21, embodying two candidate diagnoses. Since the subset ffm; ﬂig is included in both candidates, it follows that we know for sure that the monitor m failed to alert the monitor m0 and the line l was isolated. Instead, as to the cause of the malfunction in P , we are uncertain: either the breaker b failed to open (fbo) or the sensor s sent the wrong command to the breaker b (fso).

6.7 Experimental Results

In Section 2, the usual technique adopted to solve a diagnosis problem relevant to an AS (which is a net of interconnected ACs) has been described. This technique reconstructs the overall AS behavior as constrained by the given observation, then it decorates the states in the FA representing this behavior with the relevant sets of faults: the collection of all the sets of faults relevant to the ﬁnal states is the global diagnosis result. In Section 3, the notion of an AU has been introduced, this basically being an AS that can both receive and generate emerging events. Section 4 has deﬁned the notion of a DDES, this being a hierarchy of AUs, which means that each AU in a DDES can receive emerging events only from its child AUs and can send emerging events only to its parent AU. An emergent event is generated by an AU whenever the ACs contained in it have followed a pattern of state transitions; a DFA, called a matcher, is able to detect whether a pattern has been matched (Section 5). A technique similar to that adopted for ASs can be applied to solve diagnosis problems relevant to DDESs. Basically, the behavior of each AU as constrained by the given observation is reconstructed, where each state includes also the states of the external links exiting the AU itself. Then, the constrained behaviors of all the AUs is combined into a global behavior, which is later decorated. Finally, the sets of faults relevant to the ﬁnal states are extracted in the global diagnosis result. Here, this technique is referred to as greedy. However, a new technique, which is able to ﬁnd a sound and complete set of candidates relevant to a DDES, has been described in the current Section 6. This technique is here referred to as lazy, as it does not compute the global trajectories of the DDES, these being unnecessary in order to ﬁnd the global candidates. Both the greedy and the lazy techniques encompass the same preprocessing step in order to build the matchers, each relevant to a distinct pattern (regular expression) given as input. Both techniques perform the reconstruction of the behavior of each AU, as constrained by the given local observation. As brieﬂy mentioned in Section 4.5, the time needed for this reconstruction has an upper bound that is exponential in the number of ACs and (internal) links of the considered AU. The other steps are different in the two techniques, however. An activity was carried out in order to experimentally show that the lazy technique outperforms the greedy one. It is well known that the task of model-based diagnosis, even in the form deﬁned by Reiter (1987) for static systems, suffers from two potential combinatorial problems: computing a diagnosis is NP-hard, and the number of diagnoses can be exponential in the number of distinct faults. Lamperti and Zanella (2013) proved that, for distributed DESs, checking the existence of a trajec-

LAMPERTI, ZANELLA, & ZHAO

0 5 10 15 20 0

Greedy Lazy

0 5 10 15 20 0

Memory [MB]

Processing time Memory allocation

Figure 24: Comparison between greedy diagnosis and lazy diagnosis (CPU time and memory).

tory that produces the given observation is NP-hard. The experimental results recorded by solving a number of diagnosis problems relevant to DDESs by adopting the lazy technique may look somewhat surprising, since the computation time is linear in the number of ACs included in each considered DDES. An interpretation of these results is given in Section 9.

Diagnosis of DDESs has been prototyped in C++ under Linux Ubuntu 15.10, on a notebook with an Intel Core i5 CPU (2.40GHz) and 4GB of RAM, using a single thread. The diagnosis framework includes a compiler for ofﬂine preprocessing and an online diagnosis engine. A language was designed to specify DDESs in terms of ACs, AUs, and emerging events, as well as diagnosis problems in terms of viewer, observation, and ruler. The simulated systems have been generated semi-automatically based on a given template. The diagnosis engine can run in either greedy or lazy mode, thereby enabling the comparison of the performances of the two techniques. As already explained, the greedy mode requires the reconstruction of the overall DDES behavior as constrained by the given observation, exactly like in diagnosis of ASs (Lamperti, Zanella, & Zhao, 2018b), whereas the lazy mode embodies the diagnosis method speciﬁc to DDESs described in the (previous subsections of the) current section of the paper. The implementation and experimentation have been conducted in a master thesis work at the University of Brescia.

Each DDES adopted for the experiments represents a power transmission system consisting of several contiguous protected lines. The schema of a protected line is a variant of that outlined in Figure 10; in this variant, the protection apparatus at either end of the line includes two breakers and (only) one sensor, the same as in the paper by Lamperti and Zhao (2013a). Each leaf AU in the DDES hierarchy represents a protection apparatus, hence it includes three ACs. A leaf AU sends the emergent events di, co, nc, and nc to its parent AU. Each pair of leaf AUs are the children of a distinct AU, positioned in the next upper level; this AU represents a kind of monitoring process inherent to a single protected line. Each monitoring AU sends the emergent events ni, nr, and ps to its parent AU, which includes either two or three ACs, each representing a line. Hence, altogether, each parent AU represents either two or three contiguous lines. Each pair of these AUs are the children of a higher level AU (if any), which thus cumulatively represents either four or six contiguous lines. An agglomerate of several lines is called a superline. For each of the next higher levels of the hierarchy up to the root, each AU (if any) represents the union of the pair of its child superlines. Speciﬁc rulers have been deﬁned for each superline, whose faults are based on the emergent events coming from the child AUs (be they lines or superlines).

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

0 100 200 300 400 500 600 700 0

0 100 200 300 400 500 600 700 0

Memory [MB]

Processing time Memory allocation

Figure 25: Experimental results with lazy diagnosis only (CPU time and memory).

The above modeling choices allowed for a modular construction of DDESs representing power transmission systems of increasing size. As already remarked, in the third layer from the bottom, AUs aggregating either two or three lines can be adopted. If in this layer only aggregates of two lines are built, the overall system represents a number of lines which is a power of two, e.g. n D 2; 4; 8; : : : ; 64. For instance, with 64 lines, the resulting DDES is composed of 255 AUs and 638 components (i.e. ACs), which are accommodated within a balanced binary tree having 8 layers. Every AU in the bottom layer has three ACs, while every AU in the other layers has two ACs. If instead, in the third layer from the bottom, agglomerates of three lines are created, despite the DDES hierarchy being a binary tree, the overall system represents a number of protected lines that is not a power of two. All the DDES hierarchies in the experiments has a binary tree structure, however the tree is not necessarily a balanced one. Comparison results are shown in Figure 24, both in CPU processing time (left) and in memory allocation (right). The horizontal axis indicates DDESs of increasing size, up to 20 components (ACs). The size of the DDES is limited because, as indicated by the ﬁgure, at a certain point (around 15 components), both the processing time and the memory allocation in greedy mode explode. For instance, in the last (and largest) DDES, the processing time in greedy mode is 270 seconds, while in lazy mode it is 0.032 seconds. Similarly, in the last DDES, the allocated memory in greedy mode is 3300 MB, while in lazy mode it is 10.5 MB. In order to test the experimental complexity of lazy diagnosis only, another set of experiments was done, as shown in Figure 25. Nine DDESs have been considered, from 9 to 638 components. The number of AUs in each DDES ranges from 4 to 255. As shown in the graphs, both processing time and memory allocation are practically linear in the number of components. For instance, with 318 components (127 AUs), the processing time is 1.61 seconds and the memory requires 36.18 MB; with 638 components (255 AUs), the processing time is 3.20 seconds and the required memory is 68.87 MB. It is worth highlighting that the comparison of the outputs produced by greedy diagnosis and lazy diagnosis in the experiments have also indicated that both diagnosis engines invariably generate the same set of candidates, which is in fact the solution to the diagnosis problem. This outcome was expected and reinforces in empirical terms the theoretical claim of Theorem 1, which proves the soundness and completeness of lazy diagnosis. Evidence from the experiments points out that diagnosing a DDES of signiﬁcant size would be impossible adopting the classical abduction-based technique requiring the generation of the O-

LAMPERTI, ZANELLA, & ZHAO

constrained space. Whether an application for real systems might be actually developed using the lazy technique is still an open question. Yet, given the reported results, the feeling is that lazy diagnosis of DDESs may be a viable solution.

7. Discussion

In the 1990s, a new class of DESs was introduced, coined active systems, as they are meant to represent systems that act in order to affect the external world and to react to events coming from it. Although conceived independently, when ASs appeared in the literature (Baroni et al., 1998), a major contribution about diagnosability and diagnosis of DESs, namely the diagnoser approach (Sampath, Sengupta, Lafortune, Sinnamohideen, & Teneketzis, 1995; Sampath et al., 1996), had already been delivered. The diagnoser approach proposed to model a distributed DES as a network of synchronous FAs, where each FA represents the behavior of a component, this being a monolithic DES. In other words, according to the diagnoser approach, a component can inﬂuence the behavior of other components since some state transitions occur at the same time in distinct components. ASs, instead, are asynchronous by nature, that is, in a distributed AS, each component (a monolithic DES whose behavior is modeled by an FA, the same as in the diagnoser approach) can inﬂuence the behavior of other components by communicating asynchronously with them: this is achieved by making the components exchange (internal) events through ﬁnite directed buffers, called (internal) links. Hence, the notion of an AS relies on the notion of a link: a speciﬁc modeling primitive is used for representing a link, and a diagnostic engine relevant to ASs has to be able to process it correctly. However, including links in a DES model is a matter of expressive power, not of computational power. A link, whichever its capacity and its policy (FIFO, LIFO, etc.)27, could be represented as a (synchronous) component itself (Lamperti & Zanella, 2013), that is, as an FA. The class of DESs described by using links, that is, the class of ASs, is a subset of the class of DESs described as interacting synchronously28, since an asynchronous communication can be modeled through the primitive for synchronous communication (i.e. the synchronous transition). Adopting speciﬁc primitives for asynchronous automata communication comes with several advantages. First, the link primitive is generic (it speciﬁes just the capacity and the policy), that is, independent of the number and types of exchanged events, while the component model of a link depends on them; second, the component model of a link includes a (possibly large) number of states that equals Pn i D0 d i, where d is the cardinality of the set of communication events and n is the capacity of the link; third, the link primitive is processed more efﬁciently (by ad hoc algorithms) than the component model of a link. These advantages are not the reason for ASs were proposed. This paper has introduced the class of DDESs, which adopts additional links, the external ones, to convey a new kind of events, the emergent events. Hence, new primitives have been added to the ones already available to model ASs. Speciﬁcally, in order to represent an emergent event, we need to specify regular expressions since an emergent event is generated whenever a subtrajectory matches a given regular expression. Hence, the notion of a DDES relies on the notions of AS and regular expression. Once again, including ad hoc primitives for such notions in a DES model is a

27. In the previous sections, it has been assumed that every link can store a single event (so its capacity is one) and that no event can be sent to the link when the link is full (this policy is called WAIT). However, more generically, other ﬁnite capacities and different policies can be adopted for links in the AS approach. 28. The class of DESs interacting synchronously does not equal the class of DESs deﬁned in the diagnoser approach, instead it is a superset of it. In fact, the diagnoser approach assumes the liveliness of both the language of transitions and the observational language. Such assumptions are relaxed in the AS approach.

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

matter of expressive power, not of computational power. All the ASs included in a DDES can be represented as distributed synchronous DESs; external links could be represented as synchronous DES components; each regular expression could be represented by its matcher, an FA that could be dealt with in the same way as all the behavioral descriptions of synchronous DES components. Hence, the class of DDESs is a subset of the class of synchronous DESs (and the class of DDESs includes the class of ASs since each AS can be seen as DDES trivially consisting in just one AU). Modeling an existing AS as a DDES with multiple layers29 comes with advantages, ﬁrst of all a more efﬁcient diagnosis method. Still, these advantages are not the reason for DDESs were proposed.

So, what is the rationale behind ASs and DDESs? It is, ﬁrst of all, the simplicity, intuitiveness, readability, and understandability of the models. If you have to model a DES whose components interact asynchronously, describing it as an AS is much more natural and easier than representing it as a distributed DES, where components interact synchronously and some components are really active whereas other are indeed passive as they are a trick to model buffers. If you have to model the hierarchical abstractions of a DES, specifying it as a DDES is more natural and easier than describing it as a ﬂat DES consisting of synchronous components or even as a ﬂat AS.

In order to substantiate this allegation, take the DES (power transmission line) described in Example 15. If it were represented as an AS, then P would not be an AU that generates emergent events di, co, nd, nc directed to monitor m, instead it would be a pair of components (b and s) sending internal events to component m. Each emergent event communicates a distinct circumstance the target component has to take care of, where such a circumstance may be the result of an evolution involving several components (as it is possibly the case with emergent events nd and nc). The circumstances m is interested in are disconnection (emergent event di), connection (co), failure in disconnecting (nd), and failure in connecting (nc). If the DES is represented as an AS, such circumstances are not communicated to the monitor as emergent events, hence the monitor has to be able to intercept them based on the internal events coming separately from the breaker and the sensor. This means that the model of the monitor would not be that displayed on the right of Figure 12, instead it would be more complex and less readable as it should represent also the behavior needed to discriminate between the four different circumstances of the protection apparatus instead of just the behavior to react to them. Analogously, if the DES were described as an AS, the four components m, m0, r and r0 would not be regarded as a unit (AU M) that sends to line l the emergent events specifying that a side of the line cannot be reconnected (nr) or isolated (ni) or that it is affected by a persisting short circuit (ps). Instead, line l would receive internal events coming separately from components m, m0, r and r0; therefore, the model of l would not be that depicted on the right of Figure 14, instead it should include also the behavior needed to discriminate what is going on on either side of the line. The behavior (displayed in Figure 14) of l when the system is represented as a DDES is quite simple to design and understand: it includes just four states, that clarify the real situation of the line (which can be normal, isolated, or shorted since a breaker has not opened, or even persistently shorted after a breaker has been closed). If the DES were modeled as an AS, the model of the line l would be quite larger (compactness of representation is an asset of DDESs), and its states would be less understandable since there would be intermediate states just

29. An AS can easily be represented as a DDES if the set of its components can be partitioned such that each part is a node in a hierarchy where the components in each node communicate, through links, only with the components in a single node in the next upper level and the communication is unidirectional and each link can store just one kind of events.

LAMPERTI, ZANELLA, & ZHAO

inherent to the process of discriminating the actual situation of the line and link states representing the actual situation that has been found out. The diagnosis of a ﬂat AS is provided at the component level (e.g. breakers and protection devices): the whole system is faulty only if it includes some faulty component(s). Since no functionbased interpretation of what has happened is given, it may be difﬁcult for an operator to decide the correct actions to carry out. By contrast, the context-sensitive diagnosis provided for a DDES is bound to result in a clearer understanding of the risks associated with the actions. For instance, the faults relevant to the line in the DDESs described in Example 15 are not actually faults in the traditional sense that something in the line has broken. In fact, nothing in the line can break; the faults associated with the AU including just the line component, which is the root of the hierarchy, provide an interpretation of what has happened at system level (e.g. fault ﬂi denotes that the line keeps being isolated since a breaker on the left side remains open). This considerably enhances the explainability of the diagnosis results. In addition, modeling complex systems as DDESs provides a support for integration. If we have several DESs, each one devoted to a speciﬁc task, and we want to integrate them into a new DES in order to control all DESs at a higher abstraction level, then the new DES can be conveniently modeled as a DDES, which is sensitive to speciﬁc behavioral patterns of the integrated DESs (emergent events). This way, monitoring and diagnosing the DDES is far more natural than interpreting (possibly overwhelming) streams of low-level events generated by individual DESs, such as the alarms detected in a control room. The key point is that the DESs are integrated in a new system not just by connecting them with one another by means of new (internal) links between components belonging to different DESs. Instead, besides this physical integration, a semantic integration is achieved too, so that the new DDES is not just the union of the DESs: it is a higher-level system with its proper behavior. Semantic patterns speciﬁed as regular expressions were ﬁrst introduced in the AS approach by Lamperti and Zanella (2010). The work, in order to assign a different status to diagnosis candidates that cause a (sub)system to misbehave with respect to candidates that do not cause any misbehavior, deﬁnes the concept of pattern rule. A pattern rule is a regular expression over the alphabet of the transitions of the components contained in the considered (sub)system, where distinct subsystems may overlap. Any sequence of transitions matching the same expression denotes a speciﬁc malfunction. There are distinct rules for distinct malfunctions. In this respect, a pattern rule resembles the regular expression for the generation of an emergent event: a detected malfunction is indeed an example of emergent event, that can propagate higher in the hierarchy since a misbehaving subsystem can cause the misbehavior of another. In fact, in the paper by Lamperti and Zanella (2010) a DAG, called dependency graph, is adopted in order to mimic this malfunction propagation. Still, the generation of emergent events in DDESs can represent further phenomena in addition to malfunction propagation; for instance, it can represent causal chains of faults. The next step in the research leading to DDESs is related to the work by Lamperti and Zanella (2011), which remarks that the topology of a complex DES, as deﬁned in another work of the same authors (2010), is organized in a hierarchy, where the root corresponds to the whole system, leaves to components, and intermediate nodes to subsystems. This topology, which is called context hierarchy by Lamperti and Zhao (2014), suggests to organize the diagnosis rules within a hierarchy that parallels the structure of the DES: each subsystem has its proper set of diagnosis rules, which may or may not depend on the rules of inner subsystems (nodes in the next lower layer of the hierarchy). Candidate diagnoses can be generated at the different levels of the hierarchy. This

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

approach, called context-sensitive diagnosis, provides the example of a possible DDES: the above complex topology can be accommodated in the hierarchical structure of a DDES. However, the hierarchical structure of a DDES can be exploited to represent several abstractions other than a containment hierarchy. The awareness that a hierarchical structure can represent any abstraction that is proﬁtable for a given purpose is gained in the works by Lamperti and Zhao (2013a, 2013b), where the notion of behavior stratiﬁcation, which is adopted in DDESs, was introduced. Hence a context is not necessarily a (sub)system in a containment hierarchy, instead, it is a node in an abstraction hierarchy. Behavior stratiﬁcation means that the behavior of each context, placed in a layer of the hierarchy, possibly depends on the behaviors of its child contexts, placed in the adjacent lower layer. This is a signiﬁcant change w.r.t. to the work by Lamperti and Zanella (2011), where it is the diagnosis rules of a (sub)system that can be affected by the diagnosis rules of lower layer (sub)systems, whereas the behavior of a (sub)system is invariably implicitly given by the composition of the behaviors of its components. In the works by Lamperti and Zhao (2013a, 2013b), instead, each node in the hierarchy has its own behavioral model, which does not coincide with the composition of the behavioral models of its components, as two distinct nodes consisting of the same components can be affected by the behavior of their lower level nodes in different ways. The communication between subsystems at different levels relies on complex events, occurring when speciﬁc patterns of transitions are matched. These patterns are deﬁned based on the transitions of contained subsystems, where each subsystem has its own modeled behavior. The current notion of DDESs can support any hierarchical abstraction. When a context is made up of components only, a regular expression deﬁnes a pattern of transitions for such components. In the general case, when a context is made up of subcontexts, the regular expression deﬁnes a pattern of interface symbols associated with its subcontexts, with each interface symbol being associated with a regular expression in the subcontexts. Basically, its strength consists in providing the modeler with the capabilities for .i/ representing the behavior of a subsystem/context concisely and effectively, as the reaction (also) to complex phenomena that have taken place in other parts/contexts of the system, and .ii/ separating the model of this behavior from the representation of such phenomena. The former model can include (the representation of) faults that cannot be simply inferred from the faults of lower-level contexts, while the latter models are free of faults. A DDES highlights that each subsystem has a combined behavior, partly depending on its components and partly on the function this subsystem is assigned within the system.

8. Related Work

In this work, each event emerging from a layer in a DDES hierarchy, directed to the adjacent upper layer, corresponds to the occurrence of a string of component transitions in a regular language. In other words, an emergent event is generated when a behavioral pattern is recognized. Superﬁcially, a behavioral pattern looks like a fault supervision pattern, deﬁned by J eron et al. (2006). However, the two categories of patterns are orthogonal: supervision patterns are meant to generalize the concept of a fault for both diagnosis and diagnosability of ﬂat DESs, while patterns for the generation of emergent events aim to support behavior stratiﬁcation in DDESs. In the work by Console, Picardi, and Theseider Dupr e (2003), temporal patterns about observables are represented by so-called temporal decision trees. These trees are knowledge compilation schemes that can be used for both qualitative and quantitative temporal constraints relevant to the

LAMPERTI, ZANELLA, & ZHAO

history of observables once a fault has been detected without being isolated. The values of the observables are assumed to be acquired at discrete times. The compiled knowledge is exploited to perform fault isolation so as to carry out a recovery action before a given hard deadline, which has been set by keeping safety and integrity of the physical system into account. Although a temporal decision tree is a means to represent a temporal pattern, the same as a matcher in the current approach, its alphabet, semantics, and purpose are quite different. The alphabet of a temporal decision tree is the set of values of an observable, whereas the alphabet of a matcher is a set of transitions. A temporal decision tree is based on the assumption that observations are performed at regular times, whereas the current approach assumes to intercept each value change whenever it occurs. The temporal decision tree represents a ﬁnite temporal horizon (the deadline within which the recovery action has to be carried out), whereas a matcher is not constrained by any time limit. A temporal decision tree is the result of a knowledge compilation process, whereas a matcher is not. Finally, the purpose of a temporal decision tree is to discriminate a fault, whereas the purpose of a matcher is to detect the occurrence of an emergent event. DDESs are endowed with a tree-shaped hierarchical structure similar to that of hierarchical ﬁnite state machines (HFSMs), which are inspired by state-charts (Harel, 1987). Diagnosis of HFSMs is considered by Idghamishi and Zad (2004) and by Paoli and Lafortune (2008). However, in contrast with DDESs, the complexity of HFSMs is conﬁned to the structure, without emergent events or behavior stratiﬁcation. A jointree structure that is similar to the hierarchical structure of DDESs is mentioned by Darwiche (1998). Jointrees, also called junction trees, cluster trees, clique trees, or trees of belief universes in the literature (Huang & Darwiche, 1996), are adopted in various AI ﬁelds, including probabilistic reasoning (Shenoy & Shafer, 1986; Huang & Darwiche, 1996) and constraint processing (Dechter, 2003). Darwiche (1998) proposes a symbolic logic characterization of consistency-based diagnosis of static systems that is alternative to the classical one (Reiter, 1987; de Kleer & Williams, 1987; de Kleer, Mackworth, & Reiter, 1992). The traditional behavioral system description is augmented with a system structure (a DAG explicating the interconnections between components): this pair of representations is altogether called a structured system description. By exploiting the novel characterization, the paper proposes a new diagnostic method and tries to minimize the computational complexity of such a method by graphically transforming the system structure into a jointree. The contribution includes a number of guidelines for creating models that can be processed by diagnostic algorithms efﬁciently, and provides computational guarantees based on the topology of the system structure. However, the addressed systems are static, the diagnosis method is consistencybased, and no deep behavior is conceived, as the jointree structure is solely meant to reduce the computational effort. Darwiche and Provan (1996) apply the notion of a structured system description (Darwiche, 1998) to continuous dynamic systems, each governed by a discrete controller, a device that issues control commands at discrete time points. While for static systems the structure is a DAG with nodes representing the inputs and outputs of the system components, and arcs depicting their interconnections, for dynamic systems the structure has been extended with directed cycles (satisfying speciﬁc conditions). The behavior of each system component is speciﬁed by a propositional temporal logic with quantiﬁcation over discrete time (temporal sentences have to fulﬁll some conditions), and component descriptions are accommodated in a symbolic causal network, which represents the overall system model. The pair (system model, system structure), called dynamic system description, is then turned into the system description deﬁned by Darwiche (1998) in linear time. This

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

phase, called expansion, can be carried out ofﬂine and consists in creating a causal network for each time point in the time-step cycle of the system and connecting each network with the next time-point network. After that, the diagnosis approach for static systems described by Darwiche (1998) is exploited. The most computationally intensive phase depends on the topology of the system structure. Like in the work by Darwiche (1998), in order to enhance the efﬁciency of the diagnosis process one can ﬁrst convert the system structure into a jointree. The notion of a dynamic system adopted by Darwiche and Provan (1996) is far from that of a DES of the current paper, let alone from that of a DDES. Once again, the jointree is not regarded as an abstraction hierarchy, instead it is exploited to reduce the diagnosis computation time. Likewise, no deep behavior is conceived by Stumptner and Wotawa (2001), where an algorithm for computing minimal diagnoses of tree-structured systems is presented. The goal is to improve the efﬁciency of the diagnosis task by exploiting the structure of the system. Subdiagnoses, which are generated by traversing the tree top-down, are eventually combined to yield the candidate diagnoses of the whole system. The considered systems are static while DDESs are dynamic, and the diagnosis method is consistency-based, whereas the method described in this paper for DDES diagnosis is abductive and processes the tree structure bottom-up. Jointrees are exploited also in DES diagnosability analysis. In contrast with the technique for diagnosability-checking of DESs proposed by Sampath et al. (1995), which suffers from exponential complexity, the twin plant method (Jiang, Huang, Chandra, & Kumar, 2001; Yoo & Lafortune, 2002) exhibits a polynomial complexity. However, the construction of a global twin plant, which corresponds to the synchronization based on (all) observable events of two identical instances of the automaton representing the whole DES behavior, is often impractical. The scalability of the approach is increased by Schumann and Huang (2008) by taking advantage of the distribution of a DES to build a local twin plant for each component. Then, the DES components (and their relevant local twin plants) are organized into a jointree. Both the method by Schumann and Huang (2008) and that presented in this paper are distributed. However, the tasks accomplished by the two methods are profoundly different, as the transformation of the DES into a jointree by Schumann and Huang (2008) is an artiﬁce for reducing the complexity of the diagnosability analysis task, whereas the tree-shaped structure is an integral part of the topological and behavioral abstraction in DDES modeling. A decentralized/distributed approach to diagnosis of DESs was introduced by Kan John and Grastien (2008), with the aim of computing local diagnoses that are globally consistent. By deﬁnition, a diagnosis is a trajectory that complies with the given observation. The observation is a set of sequences of observable events, each sequence being inherent to a distinct component. The paper enhances the proposal by Su and Wonham (2005) in order to achieve global consistency in local diagnoses of distributed DESs without generating either any global diagnosis or the global system model. It is well known that local (pairwise) consistency does not ensure global consistency, and that an algorithm that iteratively reﬁnes local diagnoses pairwisely until stability is reached (that is, no local diagnosis changes anymore) may not terminate. However, local consistency ensures global consistency when the connections between components form a tree. Thus, the proposal by Kan John and Grastien (2008) is to convert the connections between the components of the distributed DES, which, in the general case, form a graph, into a jointree. Each node in the tree is a cluster of components (a subsystem) of the DES, where all such components are interconnected in the system, that is, each pair of them share at least one event. Although clusters differ from one another, nonetheless distinct clusters may partially overlay and their union gives the set of all system components. Two

LAMPERTI, ZANELLA, & ZHAO

subsystems (nodes of the jointree) that share an event are connected through an edge of the jointree, or through a chain of edges, where intermediate subsystems also share this event. Building an optimal jointree is NP-complete but, by exploiting heuristics (Huang & Darwiche, 1996), the algorithm that transforms a graph into a jointree achieves polynomial-time while still producing a high quality tree (the fewest nodes, associated with the smallest clusters). Diagnosis (the construction of all the trajectories) is performed locally on each cluster by the classical synchronous composition of component models and observations. After a cluster has been picked to be the root of the jointree, the consistency of each local diagnosis with the local diagnoses inherent to neighbor nodes in the tree is achieved according to a strategy, called global propagation (Huang & Darwiche, 1996), which consists of two phases. In the former, called gather phase, local consistency starts from leaf nodes and is performed up to the root. In the latter, called distribute phase, local consistency is performed in the opposite direction, from the root down to the leaves. The set of all globally-consistent localdiagnoses is the distributed diagnosis of the system. The aim of Kan John and Grastien (2008) is slightly different from that of the current paper: the former computes (globally consistent) local diagnoses whereas we compute (globally consistent) global diagnoses. The notion of diagnosis is different in the two papers: for Kan John and Grastien (2008), a diagnosis is (a possibly inﬁnite) set of trajectories whereas in our paper a diagnosis is a (ﬁnite) set of candidates, a candidate being a (ﬁnite) set of faults. Although the DESs dealt with in both papers are distributed, they differ as in the work by Kan John and Grastien (2008) they are plain, synchronous, with no deep behavior, and they are not explicitly modeled, that is, a DES (component) is a regular language; instead, in this paper, the systems are asynchronous, they feature behavior stratiﬁcation and a DES component is explicitly modeled as an FA. While for Kan John and Grastien (2008) any node of the tree (and then the root also) is a subsystem, possibly structurally overlapping with the other subsystems, in the current approach a node is the representation of a (sub)system at some abstraction level and there is no overlapping. Finally, the root of a DDES is the representation of the whole system at the highest abstraction level, whereas the root of a jointree is chosen arbitrarily. An approach to consistency-based diagnosis supported by structural abstraction (which aggregates components to represent a static system at different levels of structural detail) is described by Chittaro and Ranon (2004) as a remedy for the high computational complexity of model-based diagnosis. Evidence from experimental evaluation indicates that, on average, the technique performs favorably with the algorithm of Mozetiˇc (1992). Still, differently from the topic of this paper, the approach is consistency-based, the considered systems are static, and no emergent behavior is conceived. Siddiqi and Huang (2011) exploit structural abstraction in order to reduce the cost of sequential diagnosis, this being a model-based diagnosis task where, once the candidates relevant to a given observation have been computed, faults are isolated by exploiting the evidence provided by a sequence of measurements. The diagnostic cost is the number of the measurements that are needed until all the actual faults are identiﬁed. The measurements and the order in which they have to be taken are selected heuristically. The structural abstraction dealt with in the paper is based on hierarchical diagnosis (Siddiqi & Huang, 2007), which can decompose the system into self-contained subsystems, each of which is regarded as a single component at a higher abstraction level. This means that a single health variable and failure probability is adopted for the entire subsystem, thus scaling the approach to handle larger systems. If a subsystem is identiﬁed as faulty in the top abstraction level, it can then be processed separately in a recursive fashion. In fact, a subsystem may contain further subsystems, leading to a hierarchy of subsystems. A system can be abstracted by

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

treating all its maximal subsystems as black boxes. In addition, Siddiqi and Huang (2011) proposed a method that systematically modiﬁes the structure of a system to reduce the size of its abstraction. The attention of such a method is focused on the components that are not part of any subsystem and hence cannot be abstracted away in hierarchical diagnosis. The idea is to create a sufﬁcient number of clones of each of such components so that the original component and each of its clones become part of some subsystems and hence can participate in the abstraction. The abstraction dealt with by Siddiqi and Huang (2007, 2011), unlike the one proposed in the current approach, is purely structural and is meant to scale diagnosis to large systems. Moreover, the examples of systems taken into account by Siddiqi and Huang (2007, 2011) are combinational circuits, hence static systems, although the authors claim that their sequential diagnosis framework applies as well to other types of systems as long as the system behavior is described by a probabilistic model.

9. Conclusion

The shift from ASs to DDESs, which is motivated by ergonomics in the modeling task, does not come with any additional cost in the diagnosis task, which is not only sound and complete, but also viable. Since a state of the AS includes the states of all components and the states of all links, the complexity of the abduction of the whole AS in diagnosis of ASs is exponential both in the number of components and in the number of links. This theoretical expectation is conﬁrmed by the experimental results presented in Section 6.7. Two diagnosis engines have been implemented in order to diagnose DDESs. The former engine makes use of the same technique adopted in diagnosis of ASs (Lamperti et al., 2018b), while the latter engine operates according to this paper. The results clearly show that the processing time of the latter engine increases almost linearly with the size of the system, in contrast with the processing time of the former engine, which grows exponentially. We believe that there are two reasons for this surprising difference in the performances of the two implementations: .a/ the new technique is able to distill from each AS the essential constraints to be propagated upward in the hierarchy in order to guarantee that the trajectory reconstruction relevant to an AS complies with the global observation as projected on the AS itself and all its descendant ASs, without any need for performing the asynchronous product of the reconstructed behaviors of distinct ASs, and .b/ the new method, being speciﬁc for DDESs, is able to take advantage of their hierarchical structure, while the previous method, being general, handles all systems the same way, independently of their structure. The latter point possibly corroborates several ﬁndings in the literature (Darwiche & Provan, 1996; Darwiche, 1998; Schumann & Huang, 2008; Kan John & Grastien, 2008), according to which the computation time of diagnosis and diagnosability analysis can be reduced by transforming the system structure into a tree structure. In turn, this suggests that the performance of existing methods for DES diagnosis can be enhanced by modeling the DES as a DDES. Moreover, we expect that the technique proposed in this paper can still save more computation time by performing a powerful knowledge compilation, as suggested in previous works (Lamperti, Zanella, & Zhao, 2018a, 2018c), and by processing online independent AUs in parallel. These remarks are the spurs to future investigation on DDESs. Further research paths can be envisaged. First, the tree-based topology of the DDES can be relaxed to a directed acyclic graph (DAG), where an AU can have several parent units. Second, the diagnosis task, which in this paper is assumed to be a posteriori, that is, carried out once a complete temporal observation has been gathered, can be made reactive, where diagnosis is performed as soon as a piece of observation is received. Third, knowledge compilation can be adopted

LAMPERTI, ZANELLA, & ZHAO

in order to generate a fast diagnoser, that is, a DFA whose language includes all possible temporal observations of the DDES. Fourth, the patterns deﬁning emergent events can be extended beyond regular languages, based on more powerful grammars, possibly enriched by semantic rules. Finally, in order to avoid the generation of the whole set of candidate diagnoses, the search space might be pruned based on domain-speciﬁc criteria.

Acknowledgments

The authors would like to acknowledge the anonymous reviewers for their constructive comments and inspiring suggestions, which resulted in a considerable improvement of the quality of the ﬁnal manuscript. Gianfranco Lamperti also expresses his gratitude to Giulio Quarenghi, who implemented the compiler of the DDES speciﬁcations and the diagnosis engine in C++, thereby providing the experimental results in his master thesis. This work was supported in part by Regione Lombardia (Smart4CPPS, Linea Accordi per Ricerca, Sviluppo e Innovazione, POR-FESR 2014-2020 Asse I) and by the National Natural Science Foundation of China (grant number 61972360).

Appendix A. Proof of Theorem 1

In this appendix, a proof of soundness and completeness of the technique presented in Section 6 is provided (Theorem 1). This guarantees that the diagnosis set based on eqn. (30) equals the solution to the diagnosis problem of a DDES, as deﬁned in eqn. (19). In so doing, four deﬁnitions are given (Deﬁnition 26, Deﬁnition 27, Deﬁnition 28, and Deﬁnition 29), along with two ancillary propositions (Proposition 4 and Proposition 5).

Deﬁnition 26 Let D Œ 1; : : : ; n be a (possibly empty) sequence of sets of diagnoses. The diagnosis set of is a set of diagnoses deﬁned as follows:

f;g if D Œ 1 if D Œ 1 1 2 : : : n otherwise. (32)

Deﬁnition 27 Let p be a path within a constrained unit space U D . ; W; ; w0; Wf/, namely

p D hw0; 1; w1i; hw1; 2; w2i; : : : ; wq 1; q; wq (33)

and the sequence of diagnosis sets i involved in i, where either i D .Ei; i/ or i D .t.c/; Ei; i/, i 2 Œ1 :: q . The diagnosis set of p, denoted .p/, is deﬁned as30

.p/ D . / r.wq/: (34)

The diagnosis set of U is deﬁned as

p2k U k .p/: (35)

30. . / and r.w/ are deﬁned in eqn. (32) and eqn. (28), respectively.

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

Deﬁnition 28 Let p be a path within an interface Int.U /,

p D hi0; .E1; 1/; i1i; hi1; .E2; 2/; i2i; : : : ; iq 1; .Eq; q/; iq (36)

and D Œ 1; : : : ; q . The diagnosis set of p, denoted .p/, is deﬁned as31

.p/ D . / r.iq/: (37)

The diagnosis set of Int.U / is deﬁned as

p2k Int.U /k .p/: (38)

Deﬁnition 29 Let }.X/ D .x0; V; O; R/ be a diagnosis problem for a DDES X D .U; L/, U 2 U, x0 D .U0; E0/, and let NU D . NU; NL/ be the DDES corresponding to the subtree of X rooted in U. The projection of }.X/ on NU is the diagnosis problem }. NU/ D . Nu0; NV; NO; NR/, where Nu0 D . NU0; NE0/, NU0 is the restriction of U0 on the states of AUs in NU, NE0 is the restriction of E0 on the events within the links between AUs in NU, NV is the restriction of V on the viewers of the AUs in NU, NO is the restriction of O on the temporal observations of the AUs in NU, and NR is the restriction of R on the rulers of the AUs in NU.

Proposition 4 Let }.X/ D .x0; V; O; R/ be a diagnosis problem for the DDES X, U an AU within X, NU the DDES rooted in U, }. NU/ D . Nu0; NV; NO; NR/ the projection of }.X/ on NU, T 2 k X k such that Obs.T; V/ D O, and NT the subsequence of T relevant to transitions of components in NU. We have NT 2 k NU k; Obs. NT ; NV/ D NO.

Proof. Based on the deﬁnitions of the space of X in Section 4.1 and the temporal observation of T in Section 4.2, the component transitions in T are constrained by the conﬁgurations of the links in X and by the array of the temporal observations in O. Since NT is the projection of T on NU, in particular, NT is constrained by the conﬁgurations of the links in NU and by the array of the temporal observations in NO, where NO is the array obtained by removing from O the temporal observation relevant to the root AU of X. That is, NT 2 k NU k and Obs. NT ; NV/ D NO, where NV is the array obtained by removing from V the viewer relevant to the root AU of X.

Proposition 5 Let U be a constrained unit space, where D . Nu0; NV; NO: NR; I/. Then,

.U / D Int U : (39)

Proof. Grounded on Lemma 5.1 and Lemma 5.2.

Lemma 5.1 If ı 2 .U / then ı 2 Int U .

Proof. According to Deﬁnition 27, there is a path p 2 k U k such that ı 2 .p/,

p D hw0; 1; w1i; hw1; 2; w2i; : : : ; wq 1; q; wq (40)

31. r.i/ is deﬁned in eqn. (29).

LAMPERTI, ZANELLA, & ZHAO

where, according to eqn. (34), .p/ D . / r.wq/, with being the sequence of the diagnosis sets relevant to the elements in .p/ D Œ 1; : : : ; q , and r.wq/ is the hidden set of wq deﬁned in eqn. (28). Let

.p/ D 1 [ Œ 0 1 [ 2 [ Œ 0 2 [ : : : [ q0 [ Œ 0 q0 [ q0C1 (41)

such that Œ 0 1; : : : ; 0 q0 is Œ j 2 .p/; D .t.c/; E; /; E ; D Œ .t1.c1/; E1; 1/, : : : ; .tq0.cq0/; Eq0; q0/ . Hence, based on the deﬁnitions of a fragment (Section 6.3) and an interface (Section 6.4), there is a path p0 2 k Int.U /k,

p0 D h i0; .E 0 1; 0 1/; i1 ; i1; .E 0 2; 0 2/; i2 ; : : : D iq0 1; .E 0 q0; 0 q0/; iq0 Ei (42)

such that 8j 2 Œ1 :: q0 , E 0 j D Ej , where Ej is the (nonempty) set of emergent events involved in 0 j . Moreover, since each state ij of p0, j 2 Œ1 :: q0 , includes (at least) one fragment (Section 6.3) ' of U in which each state is marked with the set of diagnoses relevant to all the subpaths of p starting in the initial state of ', we also have

8j 2 Œ1 :: q0 0 j . j / j (43)

where j D Œ j is involved in ; 2 j , while j is relevant to 0 j D .tj .cj /; Ej ; j /. Finally, we have r.iq0/ . q0C1/ r.wq/: (44)

In fact, on the one hand, q0C1 is relevant to a subpath in a fragment in iq0, up to the state .wq; q/. On the other, based to eqn. (29), r.iq0/ q r.wq/. Hence, based to Deﬁnition 28,

eqn. (43), and eqn. (44), we have ı 2 .p0/ and, hence, based on eqn. (38), ı 2 Int U .

Lemma 5.2 If ı 2 Int U , then ı 2 .U /.

Proof. Based on Deﬁnition 28, there is a path p 2 k Int.U /k such that ı 2 .p/,

p D hi0; .E1; 1/; i1i; hi1; .E2; 2/; i2i; : : : ; iq 1; .Eq; q/; iq (45)

where, according to eqn. (37), .p/ D . / r.iq/, with D Œ 1; : : : ; q , while r.iq/ is the hidden set of iq deﬁned in eqn. (29). Based on the deﬁnitions of a fragment (Section 6.3) and an interface (Section 6.4), there is a path p0 2 k U k,

p0 D hw0; 1; w1i; hw1; 2; w2i; : : : wq0 1; q0; wq0 (46)

such that .p0/ D 1 [ Œ 0 1 [ 2 [ Œ 0 2 [ : : : [ q [ Œ 0 q [ q C1, where Œ 0 1; : : : ; 0 q is Œ 0 j 0 2 .p0/; 0 D .t0.c/; E 0; 0/; E 0 ; D Œ .t0 1.c1/; E 0 1; 0 1/, : : : ; .t0 q.cq/; E 0 q; 0 q/ such that 8j 2 Œ1 :: q , E 0 j D Ej , with Ej being the (nonempty) set of the emergent events involved in the j-th transition of the interface path p in eqn. (45). Moreover, since each state ij of the interface path p, j 2 Œ1 :: q , includes (at least) one fragment ' of U in which each state is marked with the set of diagnoses relevant to all the subpaths of constrained unit-space path p0 starting in the initial state of ', we also have 8j 2 Œ1 :: q j . j / 0 j (47)

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

where j D Œ j is involved in ; 2 j , while 0 j is relevant to 0 j D .t0 j .cj /; E 0 j ; 0 j /. Finally, we have r.iq/ . q C1/ r.wq0/: (48)

In fact, on the one hand, q C1 is relevant to a subpath within a fragment in iq, up to the state .wq0; q0/. On the other, according to eqn. (29), r.iq/ q0 r.wq0/. In conclusion, according to Deﬁnition 28 and based on eqn. (47) and eqn. (48), we have ı 2 .p0/ and, hence, based on eqn. (35), ı 2 .U /.

Theorem 1 Let }.X/ D .x0; V; O; R/ be a diagnosis problem for the DDES X, U the root node in X, and Ud the decorated constrained space of U (deﬁned in Section 6.6). We have

.}.X// D Ud : (49)

Proof. Grounded on Lemma 1.1, Lemma 1.2, Lemma 1.3, and Lemma 1.4.

Lemma 1.1 Let }.X/ D .x0; V; O; R/ be a diagnosis problem, U an AU in X, NU the DDES rooted in U, }. NU/ D . Nu0; NV; NO; NR/ the projection of }.X/ on NU, and D . Nu0; NV; NO; NR; I/ an interface constraint for U. If ı 2 .}. NU//, with ı D Dgn.T; NR/, then there is a path p 2 k U k such that: (1) ı 2 .p/, and (2) the sequence Œ t.c/ j .t.c/; E; / 2 .p/ equals the subsequence of T involving only transitions of components in U.

Proof. By induction on the tree of AUs in X. (Basis) If U is a leaf node in X then U is such that D . Nu0; NV; NO; NR; I/ where I is empty

(no interface constraints). Hence, U is constrained by NO only, in other words, U D NU NO. Thus,

if ı 2 .}. NU//, where ı D Dgn.T; NR/, T D Œ t1.c1/; : : : ; tq.cq/ , then there will be a path p 2 k NU NOk,

p D hw0; .t1.c1/; E1; 1/; w1i; hw1; .t2.c2/; E2; 2/; w2i; : : : ; wq 1; .tq.cq/; Eq; q/; wq

(50) such that

8i 2 Œ1 :: q i D fffigg if .ti.ci/; fi/ 2 NR f;g otherwise

According to eqn. (34) and eqn. (28), .p/ is . / r.wq/ D 1 2 : : : q f;g D fıg. In other words, ı 2 .p/ (condition 1 of the lemma). Condition 2 of the lemma is grounded on eqn. (50), namely Œ t.c/ j .t.c/; E; / 2 .p/ D Œ t1.c1/; : : : ; tq.cq/ . (Induction) Assume that U is an internal node of X with children U1; : : : ; Uk, such that, 8j 2 Œ1 :: k , if ıj 2 .}. NUj //, ıj D Dgn.Tj ; NRj /, then pj 2 k U j j k such that: (1) ıj 2 .pj /, and

(2) the sequence t.c/ j .t.c/; E; / 2 .pj / equals the subsequence of trajectory Tj involving only transitions of components in AU Uj . Assume that ı 2 .}. NU//, where ı D Dgn.T; NR/, with T being a trajectory within the space NU . Let Tj , j 2 Œ1 :: k , denote the subsequence of T including the transitions relevant to the components within the DDES NUj . Based on Proposition 4, Tj is a trajectory in NU j such that Obs.Tj ; NVj / D NOj , where NOj is the temporal observation relevant to }. NUj /. Consequently, according to eqn. (19), Tj is also a trajectory involved in the solution to }. NUj /, in other words,

LAMPERTI, ZANELLA, & ZHAO

ıj 2 .}. NUj //, where ıj D Dgn.Tj ; NRj /, with NRj being the ruler relevant to }. NUj /. Hence, by the induction hypothesis, there is a path pj 2 k U j j k such that: (1) ıj 2 .pj /, and (2)

Tj Uj D t.c/ j .t.c/; E; / 2 .pj / equals the subsequence of trajectory Tj involving transitions of components in Uj only. Based on Proposition 5, there is a path p0 j 2 k Int.U j j /k such

that ıj 2 .p0 j /, where

p0 j D h i0; .E1j ; 1j /; i1 ; i1; .E2j ; 2j /; i2 ; : : : ; D q0 j 1; .Eq0 j ; q0 j /; iq0 j

and, according to eqn. (34), .p0 j / equals

. / r.iq0 j / D 1j 2j : : : q0 j r.iq0 j /: (53)

Moreover, 8j 0 2 Œ1 :: q0 , we have Ej 0 j ;, where Ej 0 j is the set of emergent events generated by a corresponding transition in Tj Uj . Let T e j D Œ te 1j .c1j /: : : : ; te q0 j .cq0 j / denote the subsequence

of Tj Uj involving the transitions generating emergent events. Since all transitions in Tj are included in T , j 2 Œ1 :: k , T includes all transitions in T e j as well. Let T e denote the subsequence of T involving the transitions in all T e j , j 2 Œ1 :: k . As such, the transitions in T e are constrained by the temporal observations in NO relevant to the AUs U1; : : : ; Uk, respectively, and by the load conﬁguration of the links entering the input terminals of U. Since the generation of U too is based on these two constraints, there is a path p 2 k U k involving all the diagnosis sets marking the transitions in all p0 j , j 2 Œ1 :: k , namely 11; : : : ; q0 1; 12; : : : ; q0 2; : : : ; 1k; : : : ; q0 k,

p D hw0; 1; w1i; hw1; 2; w2i; : : : ; wq 1; q; wq : (54)

Let TU denote the subsequence of T composed of the transitions relevant to the components in U only. As such, the transitions in TU are constrained by the temporal observation in NO relevant to the AU U, and by the load conﬁguration of the links entering the input terminals of U. Since the generation of U too is based on these two constraints, the path p 2 k U k in eqn. (54) involves all transitions in TU. Finally, according to eqn. (34),

.p/ D . / r.iq/ D 1 : : : q r.wq/ (55)

where 1; : : : ; q are the diagnosis sets involved in 1; : : : ; q, respectively. Still, comparing eqn. (55) to eqn. (53), with j 2 Œ1 :: k , in order for ı 2 .p/, we need to show that r.wq/ D r.iq0 1/ r.iq0 2/ : : : r.iq0 k/: Based on eqn. (28), as U is assumed not to be a leaf node, we have

i2I r.i/ (56)

where, according to Section 6.2, wq D .S; E; M; H ; I; =/, with I D .i1; : : : ; ik/ being the array of ﬁnal states in the interfaces Int.U 1 1/; : : : ; Int.U k k/, respectively. The conclusion of the proof of the induction step, as well as of Lemma 1.1, lies in that each state ij 2 I, j 2 Œ1 :: k , is in fact the ﬁnal state iq0 j of the path p0 j in eqn. (52).

Lemma 1.2 (Completeness) Let U be the root node of X. If ı 2 .}.X//, then ı 2 Ud .

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

Proof. According to eqn. (30), the diagnosis set of the decorated constrained space Ud is

8 : .wf/ r.wf/ 9 ; (57)

where Wf is the set of ﬁnal states of U , .wf/ the diagnosis set (decoration) of wf, and r.wf/ the hidden set of wf deﬁned in eqn. (28). Speciﬁcally, each state w in U is decorated based on the following two rules: (1) if w0 is the initial state, then ; 2 .w0/, and (2) if hw; ; w0i is a transition in U , with N being the diagnosis set involved in , then .w0/ 8 : .w/ N 9 ;. From Lemma 1.1, if ı 2 .}.X//, then there is p 2 k U k such that ı 2 .p/, where

.p/ D . / r.wq/ (58)

where D Œ 1; : : : ; q is the sequence of diagnosis sets marking the transitions in p and wq is the ﬁnal state of p. By induction on p we show that, for each preﬁx Op of p ending at state Ow, if Oı 2 . O /, then Oı 2 . Ow/, where O is the sequence of diagnosis sets marking the transitions in Op. (Basis) If Ow D w0 then, according to eqn. (32), . O / D f;g, where O D Œ . On the other hand, based on the ﬁrst decoration rule, ; 2 .w0/. (Induction) Assume that, for a preﬁx Op of p, with Op ending at the state Ow, if Oı 2 . O /, then Oı 2 . Ow/. Let Op0 be the preﬁx of p obtained by extending Op with the transition exiting Ow in p, namely h Ow; 0; Ow0i, with 0 being the diagnosis set involved in 0. Let Oı0 be a diagnosis in . O 0/, where O 0 D O [ Œ 0 . As such, Oı0 is obtained by extending Oı by a diagnosis ı0 2 0. On the other hand, according to the second decoration rule, the same applies for . Ow0/, based on that . Ow0/ 8 : . Ow/ 09 ;. Considering the ﬁnal state wq of p, based on eqn. (58), ı is obtained by

joining a diagnosis Oıq 2 . / with a diagnosis in the hidden set r.wq/, which is exactly the way a diagnosis in .U / is obtained based on eqn. (57).

Lemma 1.3 Let }.X/ D .x0; V; O; R/ be a diagnosis problem, U an AU in X, NU the DDES rooted in U, }. NU/ D . Nu0; NV; NO; NR/ the projection of }.X/ on NU, and D . Nu0; NV; NO; NR; I/ an interface constraint for U. If ı 2 .U /, where ı 2 .p/, p 2 k U k, then: (1) ı 2 .}. NU//,

where ı D Dgn.T; NR/, and (2) the sequence Œ t.c/ j .t.c/; E; / 2 .p/ equals the subsequence of T involving only transitions of components in U.

Proof. By induction on the tree of AUs in X. (Basis) If U is a leaf node in X then U is such that D . Nu0; NV; NO; NR; I/ where I is empty (no

interface constraints). Hence, U is constrained by NO only, in other words, U D NU NO. Thus, path p 2 k U k relevant to ı is such that

p D hw0; .t1.c1/; E1; 1/; w1i; hw1; .t2.c2/; E2; 2/; w2i; : : : ; wq 1; .tq.cq/; Eq; q/; wq

8i 2 Œ1 :: q i D fffigg if .ti.ci/; fi/ 2 NR f;g otherwise

LAMPERTI, ZANELLA, & ZHAO

According to eqn. (34) and eqn. (28), .p/ is . / r.wq/ D 1 2 : : : q f;g D fıg. On the other hand, this also means that there is a trajectory T 2 k NU k such that Obs.T; NV/ D NO and Dgn.T; NR/ D ı. In other words, based on eqn. (19), ı 2 .}. NU//. (Induction) Assume that U is an internal node of X with children U1; : : : ; Uk, such that, 8j 2 Œ1 :: k , if ıj 2 .U j j /, where ıj 2 .pj /, pj 2 k U j j k, then: (1) ıj 2 .}. NUj //, where ıj D

Dgn.Tj ; NRj /, with NRj being the ruler of }. NUj /, and (2) the sequence t.c/ j .t.c/; E; / 2 .pj /

equals the subsequence of Tj involving only transitions of components in AU Uj . Assuming ı 2 .U /, speciﬁcally ı 2 .p/, p 2 k U k, we have

p D hw0; 1; w1i; hw1; 2; w2i; : : : ; wq 1; q; wq (61)

such that, based on eqn. (34), .p/ D . / r.wq/, where D Œ 1; : : : ; q is the sequence of the diagnosis sets involved in 1; : : : ; q, respectively, while, based on eqn. (28), the hidden set of wq D .S; E; M; H ; I; =/, where I D .i1; : : : ; ik/, is r.wq/ D r.i1/ r.i2/ : : : r.ik/: In summary, ı 2 .p/, where .p/ D 1 : : : q r.i1/ r.i2/ : : : r.ik/. So, .p/ can be expressed as the join of k C1 join expressions .p/ D 0 0 1 0 2 : : : 0 k, where 0 D fı0g D O

.t.c/;E; /2 .p/ (62)

and, 8j 2 Œ1 :: k , we have

2 .p/; D.E; /; relevant to Int U j j

CCCA r.ij /: (63)

Hence, ı can be expressed as the union of k C 1 sets of faults, ı D ı0 [ ı0 1 [ ı0 2 [ : : : [ ı0 k, where ı0 2 0 D fı0g, while ı0 j 2 0 j , j 2 Œ1 :: k . Moreover, based on the deﬁnition of constrained unit space (Section 6.2), 8j 2 Œ1 :: k , there is a path p0 j 2 k Int.U j j /k such that ı0 j 2 .p0 j /.

According to Proposition 5, there is a path pj 2 k U j j k such that ı0 j 2 .pj /, in other words,

ı0 j 2 .U j j /. Hence, by point 1 of the induction step, ı0 j 2 .}. NUj //. According to eqn. (19), ı0 j is the diagnosis of a trajectory Tj 2 k NU j k based on the ruler NRj , such that Obs.Tj ; NVj / D NOj , with NOj being the temporal observation and NVj the viewer in }. NUj /. In order for Tj to be a subsequence of a trajectory T 2 k NU NOk, the constraints on load conﬁguration of links entering the input terminals of U should be respected.32 Since these constraints are in fact respected in the generation of U too, all the transitions of the trajectory Tj are interspersed (with same relative order) within T . Besides, based on point 2 of the induction step, the elements .E; / in .p/ are relevant to the transitions of the components in Uj , where E ; is the set of emergent events in Uj , j 2 Œ1 :: k . Consequently, the mode in which emergent events are generated in Uj and consumed in the construction of U is the same as in T . In other words, the sequence of transitions t.c/ involved in the triples of eqn. (62) is also the projection of T on the transitions of the components in U. In summary, we have

Dgn.T; NR/ D ı0 [ ı0 1 [ ı0 2 [ : : : [ ı0 k D ı: (64)

32. Speciﬁcally, no transition in Uj generating an emergent event on a nonempty terminal can be triggered.

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

Hence, the ﬁrst condition of Lemma 1.3 holds. Finally, the second condition of Lemma 1.3 is grounded on eqn. (62).

Lemma 1.4 (Soundness) Let U be the root node of X. If ı 2 Ud , then ı 2 .}.X//.

Proof. According to Section 6.6 and eqn. (30), we have

8 : .wf/ r.wf/ 9 ; (65)

where Wf is the set of ﬁnal states of U , .wf/ the diagnosis set of wf, and r.wf/ the hidden set of wf deﬁned in eqn. (28). Speciﬁcally, each state w in U is decorated based on the following two rules: (1) if w0 is the initial states of U then ; 2 .w0/, and (2) if hw; ; w0i is a transition

in U , with N being the diagnosis set involved in , then .w0/ 8 : .w/ N 9 ;. Based on these

rules, if ı 2 .Ud /, then there is a path p 2 k U k, namely

p D hw0; 1; w1i; hw1; 2; w2i; : : : ; wq 1; q; wq (66)

where wq is one of ﬁnal states wf in eqn. (65), such that ı 2 f;g 1 2 : : : q r.wq/, where, 8i 2 Œ1 :: q , i is involved in i, that is ı 2 . / r.wq/, where D Œ 1; : : : ; q . Hence, according to eqn. (34), ı 2 .p/. Also, based on Lemma 1.3, ı 2 .}. NU//. Since U is the root node of X, we have NU D X and, therefore, ı 2 .}.X//.

Eventually, the proof of Theorem 1 comes from Lemma 1.2 and Lemma 1.4.

Atay, F., & Jost, J. (2004). On the emergence of complex systems on the basis of the coordination of complex behaviors of their elements: synchronization and complexity. Complexity, 10(1), 17 22.

Baroni, P., Lamperti, G., Pogliano, P., & Zanella, M. (1998). Diagnosis of active systems. In Thirteenth European Conference on Artiﬁcial Intelligence (ECAI 1998), pp. 274 278, Brighton, United Kingdom.

Baroni, P., Lamperti, G., Pogliano, P., & Zanella, M. (1999). Diagnosis of large active systems. Artiﬁcial Intelligence, 110(1), 135 183.

Baroni, P., Lamperti, G., Pogliano, P., & Zanella, M. (2000). Diagnosis of a class of distributed discrete-event systems. IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans, 30(6), 731 752.

Bossomaier, T., & Green, D. (2007). Complex Systems. Cambridge University Press, Cambridge.

Brand, D., & Zaﬁropulo, P. (1983). On communicating ﬁnite-state machines. Journal of the ACM, 30(2), 323 342.

Cassandras, C., & Lafortune, S. (2008). Introduction to Discrete Event Systems (second edition). Springer, New York.

LAMPERTI, ZANELLA, & ZHAO

Chittaro, L., & Ranon, R. (2004). Hierarchical model-based diagnosis based on structural abstraction. Artiﬁcial Intelligence, 155(1 2), 147 182.

Console, L., Picardi, C., & Dupr e, D. T. (2003). Temporal decision trees: Model-based diagnosis of dynamic systems on-board. Journal of Artiﬁcial Intelligence Research, 19, 469 512.

Darwiche, A. (1998). Model-based diagnosis using structured system descriptions. Journal of Artiﬁcial Intelligence Research, 8, 165 222.

Darwiche, A., & Provan, G. (1996). Exploiting system structure in model-based diagnosis of discrete-event systems. In 7th International Workshop on Principles of Diagnosis (DX 1996), pp. 95 105, Montreal, CDN.

de Kleer, J., Mackworth, A. K., & Reiter, R. (1992). Characterizing diagnoses and systems. Artiﬁcial Intelligence, 56(2-3), 197 222.

de Kleer, J., & Williams, B. (1987). Diagnosing multiple faults. Artiﬁcial Intelligence, 32(1), 97 130.

Dechter, R. (2003). Constraint Processing. The Morgan Kaufmann Series in Artiﬁcial Intelligence. Morgan Kaufmann Publishers Inc., San Francisco, CA.

Goles, E., & Martinez, S. (Eds.). (2001). Complex Systems. Springer, Dordrecht, The Netherlands.

Hamscher, W., Console, L., & de Kleer, J. (Eds.). (1992). Readings in Model-Based Diagnosis. Morgan Kaufmann, San Mateo, CA.

Harel, D. (1987). Statecharts: a visual formalism for complex systems. Science of Computer Programming, 8(3), 231 274.

Huang, C., & Darwiche, A. (1996). Inference in belief networks: A procedural guide. International Journal of Approximate Reasoning, 15(3), 225 263.

Idghamishi, A., & Zad, S. (2004). Fault diagnosis in hierarchical discrete-event systems. In 43rd IEEE Conference on Decision and Control, pp. 63 68, Paradise Island, Bahamas.

J eron, T., Marchand, H., Pinchinat, S., & Cordier, M. (2006). Supervision patterns in discrete event systems diagnosis. In Seventeenth International Workshop on Principles of Diagnosis (DX 2006), pp. 117 124, Pe naranda de Duero, Spain.

Jiang, S., Huang, Z., Chandra, V., & Kumar, R. (2001). A polynomial algorithm for testing diagnosability of discrete event systems. IEEE Transactions on Automatic Control, 46(8), 1318 1321.

Kan John, P., & Grastien, A. (2008). Local consistency and junction tree for diagnosis of discreteevent systems. In Eighteenth European Conference on Artiﬁcial Intelligence (ECAI 2008), pp. 209 213, Patras, Greece. IOS Press, Amsterdam.

Khalastchi, E., & Kalech, M. (2018). On fault detection and diagnosis in robotic systems. ACM Comput. Surv., 51(1).

Lamperti, G., & Quarenghi, G. (2016). Intelligent monitoring of complex discrete-event systems. In Czarnowski, I., Caballero, A., Howlett, R., & Jain, L. (Eds.), Intelligent Decision Technologies 2016, Vol. 56 of Smart Innovation, Systems and Technologies, pp. 215 229. Springer International Publishing Switzerland.

DIAGNOSIS OF DEEP DISCRETE-EVENT SYSTEMS

Lamperti, G., & Zanella, M. (2010). Injecting semantics into diagnosis of discrete-event systems. In 21st International Workshop on Principles of Diagnosis (DX 2010), pp. 233 240, Portland, OR.

Lamperti, G., & Zanella, M. (2011). Context-sensitive diagnosis of discrete-event systems. In Walsh, T. (Ed.), Twenty-Second International Joint Conference on Artiﬁcial Intelligence (IJCAI 2011), Vol. 2, pp. 969 975, Barcelona, Spain. AAAI Press.

Lamperti, G., & Zanella, M. (2013). Preliminaries on complexity of diagnosis of discrete-event systems. In 24th International Workshop on Principles of Diagnosis (DX 2013), pp. 192 197, Jerusalem, Israel.

Lamperti, G., Zanella, M., & Zhao, X. (2018a). Abductive diagnosis of complex active systems with compiled knowledge. In Thielscher, M., Toni, F., & Wolter, F. (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference (KR 2018), pp. 464 473, Tempe, Arizona. AAAI Press.

Lamperti, G., Zanella, M., & Zhao, X. (2018b). Introduction to Diagnosis of Active Systems. Springer, Cham.

Lamperti, G., Zanella, M., & Zhao, X. (2018c). Knowledge compilation techniques for modelbased diagnosis of complex active systems. In Holzinger, A., Kieseberg, P., Tjoa, A. M., & Weippl, E. (Eds.), Machine Learning and Knowledge Extraction, Vol. 11015 of Lecture Notes in Computer Science, pp. 43 64. Springer, Cham.

Lamperti, G., & Zhao, X. (2013a). Diagnosis of higher-order discrete-event systems. In Cuzzocrea, A., Kittl, C., Simos, D., Weippl, E., & Xu, L. (Eds.), Availability, Reliability, and Security in Information Systems and HCI, Vol. 8127 of Lecture Notes in Computer Science, pp. 162 177. Springer, Berlin, Heidelberg.

Lamperti, G., & Zhao, X. (2013b). Speciﬁcation and model-based diagnosis of higher-order discrete-event systems. In IEEE International Conference on Systems, Man, and Cybernetics (SMC 2013), pp. 2342 2347, Manchester, United Kingdom.

Lamperti, G., & Zhao, X. (2014). Diagnosis of active systems by semantic patterns. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 44(8), 1028 1043.

Lamperti, G., & Zhao, X. (2016a). Diagnosis of complex active systems with uncertain temporal observations. In Buccafurri, F., Holzinger, A., Tjoa, A. M., & Weippl, E. (Eds.), Availability, Reliability, and Security in Information Systems, Vol. 9817 of Lecture Notes in Computer Science, pp. 45 62. Springer International Publishing AG Switzerland.

Lamperti, G., & Zhao, X. (2016b). Viable diagnosis of complex active systems. In IEEE International Conference on Systems, Man, and Cybernetics (SMC 2016), pp. 457 462, Budapest.

Licata, I., & Sakaji, A. (2008). Physics of Emergence and Organization. World Scientiﬁc.

Mozetiˇc, I. (1992). Hierarchical diagnosis. In Hamscher, W., Console, L., & de Kleer, J. (Eds.), Readings in Model-Based Diagnosis. Morgan Kaufmann.

Paoli, A., & Lafortune, S. (2008). Diagnosability analysis of a class of hierarchical state machines. Journal of Discrete Event Dynamic Systems: Theory and Applications, 18(3), 385 413.

Pencol e, Y., Steinbauer, G., M uhlbacher, C., & Trav e-Massuy es, L. (2018). Diagnosing discrete event systems using nominal models only. In Zanella, M., Pill, I., & Cimatti, A. (Eds.),

LAMPERTI, ZANELLA, & ZHAO

28th International Workshop on Principles of Diagnosis (DX 17), Vol. 4, pp. 169 183. Kalpa Publications in Computing.

Pill, I., & Quaritsch, T. (2013). Behavioral diagnosis of LTL speciﬁcations at operator level. In Twenty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI 2013), pp. 1053 1059. AAAI Press.

Pnueli, A. (1977). The temporal logic of programs. In 8th Annual Symposium on Foundations of Computer Science, SFCS 77, pp. 46 57, Washington, DC, USA. IEEE Computer Society.

Reiter, R. (1987). A theory of diagnosis from ﬁrst principles. Artiﬁcial Intelligence, 32(1), 57 95.

Sampath, M., Sengupta, R., Lafortune, S., Sinnamohideen, K., & Teneketzis, D. (1995). Diagnosability of discrete-event systems. IEEE Transactions on Automatic Control, 40(9), 1555 1575.

Sampath, M., Sengupta, R., Lafortune, S., Sinnamohideen, K., & Teneketzis, D. (1996). Failure diagnosis using discrete-event models. IEEE Transactions on Control Systems Technology, 4(2), 105 124.

Schumann, A., & Huang, J. (2008). A scalable jointree algorithm for diagnosability. In Twenty Third National Conference on Artiﬁcial Intelligence (AAAI 2008), pp. 535 540, Chicago, IL.

Schuppan, V. (2012). Towards a notion of unsatisﬁable and unrealizable cores for LTL. Sci. Comput. Program., 77(7 8), 908 939.

Shenoy, P., & Shafer, G. (1986). Propagating belief functions with local computations. IEEE Expert, 1(3), 43 52.

Siddiqi, S., & Huang, J. (2007). Hierarchical diagnosis of multiple faults. In 20th International Joint Conference on Artiﬁcial Intelligence (IJCAI 2007), pp. 581 586, Hyderabad, India.

Siddiqi, S., & Huang, J. (2011). Sequential diagnosis by abstraction. Journal of Artiﬁcial Intelligence Research, 41, 329 365.

Stumptner, M., & Wotawa, F. (2001). Diagnosing tree-structured systems. Artiﬁcial Intelligence, 127(1), 1 29.

Su, R., & Wonham, W. (2005). Global and local consistencies in distributed fault diagnosis for discrete-event systems. IEEE Transactions on Automatic Control, 50(12), 1923 1935.

Yoo, T., & Lafortune, S. (2002). Polynomial-time veriﬁcation of diagnosability of partially observed discrete-event systems. IEEE Transactions on Automatic Control, 47(9), 1491 1495.