Gianfranco Lamperti

Xiangfu Zhao

Diagnosis of Higher-Order Discrete-Event Systems

Preventing major events, like the India blackout in 2012 or the Fukushima nuclear disaster in 2011, is vital for the safety of society. Automated diagnosis may play an important role in this prevention. However, a gap still exists between the complexity of systems such these and the effectiveness of state-of-the-art diagnosis techniques. The contribution of this paper is twofold: the definition of a novel class of discrete-event systems (DESs), called higherorder DESs (HDESs), and the formalization of a relevant diagnosis technique. HDESs are structured hierarchically in several cohabiting subsystems, accommodated at different abstraction levels, each one living its own life, as happens in living beings. The communication between subsystems at different levels relies on complex events, occurring when specific patterns of transitions are matched. Diagnosis of HDESs is scalable, context-sensitive, and in a way intelligent.

Introduction

In the last decades, automated diagnosis of complex systems has become increasingly important for the safety of society. It suffices to consider two recent fateful events: the 2012 India blackout, and the 2011 Fukushima Daiichi nuclear disaster.

On July 2012, India suffered from a major blackout, the largest power outage in history, occurring as two separate events (on 30 and 31 July), which affected over 620 million people (half of India's population), and spread across 22 states, with an estimated 32 gigawatts of generating capacity being taken offline.

Among other consequences, the outage caused chaos in rush hours, as passenger trains were shut down and traffic signals were non-operational. Several hospitals reported interruptions in health services. Hundreds of miners were trapped underground due to failures in lifts. Water treatment points were shut down for hours and millions of people were not able to draw water from wells powered by electric pumps.

On August 2012, the investigation committee concluded that among other factors responsible for the blackout was the loss of a 400V transmission line caused by misbehavior of the protection system [1]. The committee also provided several recommendations to prevent further blackouts, including an audit of the protection system. Also some technology sources and the United States Agency for International Development (USAID) proposed that another widespread outage could be prevented by an integrated network of microgrids and distributed generation connected seamlessly with the main grid via a superior smart grid technology which includes automated fault detection, islanding and self-healing of the network.

On March 2011, following the Tohoku earthquake and tsunami, Japan was struck by a nuclear disaster caused by a series of equipment failures, nuclear meltdowns, and releases of radioactive materials at the Fukushima I Nuclear Power Plant. It was the largest nuclear disaster since Chernobyl in 1986.

Immediately after the earthquake, the three reactors that were operating in the power plant shut down automatically, and emergency generators were started for controlling electronic devices and coolant systems. However, the tsunami following by the earthquake quickly flooded the underground rooms housing the emergency generators, causing the latter to fail, thereby interrupting the power to the pumps aimed at continuously circulating coolant water to prevent the nuclear reactor from melting down. As a consequence, the reactors overheated owing to the high radioactive decay heat that continued for hours (even days) after the shutdown of the nuclear reactor.

In that situation, what could have prevented the meltdown was prompt flooding of the reactors with sea water. However, since salt in water was bound to ruin the (costly) reactors permanently, this action was delayed and taken only after an explicit order of the government. But it was too late. In the following hours and days all three reactors experienced full meltdown.

Subsequent explosions and the atmospheric venting of radioactive gases led to a 20 Km-radius evacuation around the plant. Sea water exposed to melting rods was returned to the sea heated and radioactive in large volumes for several months. The accident was eventually assessed at Level 7 (the maximum scale value).

Conclusions based on the analysis of the accident procedure manuals used for Fukushima Daiichi nuclear power plant published by the japanese Nuclear and Industry Safety Agency (NISA), include that after the batteries and power supply boards were flooded, almost all electricity sources were lost, and this event was not envisioned. Besides, a number of nuclear energy specialists remarked that plants should be able to maintain electricity during an earthquake (and other emergency situations).

The investigation report released by a government-appointed panel held on June 2012 asserts that the failure in preventing the nuclear disaster was not caused by the fact that a large tsunami was unanticipated, but because of the reluctance in investing time, effort, and money in protecting against a natural disaster considered unlikely [START_REF] Yamaguchi | Fukushima Nuclear Disaster Report: Plant Operators Tokyo Electric And Government Still Stumbling[END_REF].

The two disasters in India and Japan share two common properties:

-Complexity of the monitored system: in both cases, the system is composed of several interconnected subsystems, possibly at different abstraction levels; -Dependency on electricity: in both cases, the failure in supplying electricity plays a major role in provoking the disaster.

A complex system is not necessarily large (even though a large system is likely to be complex). In our meaning, complexity refers to the mode in which the system is organized, at different levels of abstraction, with each level being characterized by its proper behavior, which depends on the behaviors of lower-level layers, yet differs from just the composition of them. We call it behavior stratification.

A large system that is composed of many interacting components at the same level of abstraction is not complex per se. The human brain is complex not merely because it is composed of billions of neurons but because this huge biological neural network is organized in a hierarchy of different layered brains: 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.).

In this paper, we apply behavior stratification to discrete-event systems (DESs) [START_REF] Cassandras | Introduction to Discrete Event Systems[END_REF], in particular, to a class of asynchronous DESs called active systems [START_REF] Lamperti | Diagnosis of Active Systems -Principles and Techniques[END_REF]. DESs are typically modeled as networks of interacting components, where the behavior of each component is described by a communicating automaton [START_REF] Brand | On communicating finite-state machines[END_REF]. However, complexity of the DES has become a research issue only recently. Previous research has mainly focused on relevant yet different aspects, including incrementality [START_REF] Baroni | Diagnosis of large active systems[END_REF][START_REF] Grastien | Incremental diagnosis of discrete-event systems[END_REF], distribution / decentralization [START_REF] Pencolé | Decentralized diagnoser approach: application to telecommunication networks[END_REF][START_REF] Debouk | Coordinated decentralized protocols for failure diagnosis of discrete-event systems[END_REF][START_REF] Pencolé | Incremental decentralized diagnosis approach for the supervision of a telecommunication network[END_REF][START_REF] Debouk | On the effect of communication delays in failure diagnosis of decentralized discrete event systems[END_REF][START_REF] Grastien | Extending decentralized discrete-event modelling to diagnose reconfigurable systems[END_REF][START_REF] Pencolé | A formal framework for the decentralized diagnosis of large scale discrete event systems and its application to telecommunication networks[END_REF][START_REF] Qiu | Decentralized failure diagnosis of discrete event systems[END_REF], and uncertainty / incompleteness [START_REF] Lamperti | Diagnosis of discrete-event systems from uncertain temporal observations[END_REF][START_REF] Zhao | Model-based diagnosis of discrete event systems with an incomplete system model[END_REF][START_REF] Lamperti | Monitoring of active systems with stratified uncertain observations[END_REF][START_REF] Kwong | Fault diagnosis in discrete-event systems: incomplete models and learning[END_REF][START_REF] Zhao | Reasoning on partially-ordered observations in online diagnosis of DESs[END_REF].

The notion of context-sensitive diagnosis was introduced for DESs that are organized within abstraction hierarchies, so that candidate diagnoses can be generated at different abstraction levels [START_REF] Lamperti | Context-sensitive diagnosis of discrete-event systems[END_REF]. Even in that work, albeit the diagnosis depends on the context, the DES is assumed to be a network of components without behavior stratification. When behavior stratification occurs, we have a higher-order DES (HDES).

Higher-Order Discrete-Event Systems

A higher-order DES, namely H , is a tree where nodes are components. Leaf nodes are basic components, while internal nodes are complex components. The set of child components of a complex component X is indicated by C .X /. Each (either basic or complex) component in H is defined in terms of a topological model and a behavioral model. The topological model consists of a set of input terminals and a set of output terminals. Components in C .X / are connected to one another through links, with each link exiting the output terminal of one component and entering the input terminal of another component. These connections form a network N .X /.

Let I and O denote the input and output terminals of a component C . The behavioral model of C is a communicating automaton .S ; I; O; T /, where S is the set of states, I the set of input events, O the set of output events, and T W S .I I/ 2 .O O/ 7 ! 2 S the (nondeterministic) transition function. A transition is triggered by an input event and generates a (possibly empty) set of output events. The latters are thus made available as input events at the corresponding input terminals of connected components, while the input (triggering) event is consumed. A transition can be triggered only if all links, towards which output events are generated, are empty (no event is in the link).

Each complex component X is endowed with a Cot additional input terminal, which is sensitive to complex events. A complex event is a set of pattern events. A pattern event occurs when the network N .X / undergoes a string of transitions matching a given regular expression. The alphabet of such a regular expression is the whole set of transitions of components in C.X /.

In general, for each complex component X, a set P .X / of patterns is defined, with each pattern being a pair .p; r/, where p is the name of a pattern event and r a regular expression on transitions of C .X /. Several pattern events may occur simultaneously. In fact, given a string T of transitions of components in C .X /, each suffix of T matching a regular expression in P .X / gives rise to a pattern event. The whole set of these pattern events forms a complex event. Example 1 Shown in Fig. 1 is a HDES representing a power transmission line L. On both sides, the line is protected from short circuits by a protection hardware, namely W and W 0 . Each of them is composed of a protection device, p and p 0 , respectively, and two breakers, l and r, and l 0 and r 0 , respectively. Boxes denote complex components L, W , and W 0 . We assume that the output terminal of the protection device is exited by two links directed to the input terminals of the two breakers. The protection device is sensitive to short circuits on the line, detected as lowering of voltage, in which case it commands the breakers to open in order to isolate the line (just one open breaker on both sides is sufficient for isolation). Once the line is isolated, the short circuit is expected to die. If so, the protection device commands both breakers to close in order to reconnect the line (all breakers need to be closed). However, faulty behavior may occur, specifically:

-The protection device sends the wrong command; -The breaker does not react to the command of protection device (thereby remaining in its state); -The protection hardware fails to either disconnect or connect the line (if just one breaker does not open, the protection hardware is normal, as disconnection occurs; instead, for the connection, both breakers must close); -The line is not isolated, or once the short circuit is dead, the line is not reconnected, or after reconnection the short circuit is still alive (e.g. a tree fallen on the line).

Outlined in Fig. 2 are the behavioral models. Details on component transitions are provided in Table 1. Patterns relevant to complex events in Table 1 are defined in Table 2, where '‹' means optionality, ' ' means repetition zero or more times, 'C' means repetition one or more times, and ':' (negation) means any transition different from its argument. For instance, consider pattern event ps (persistent short circuit) and the corresponding regular expression, which occurs when either W or W 0 repeats one or more times the following sequence of transitions: it closes (w 5 ) and then, after zero or more occurrences of w 1 , it opens again (w 2 ), followed by zero or more transitions other than w 5 . Notice that ps is a single pattern event, while ps is the singleton fpsg (complex event). Incidentally, in our example all complex events are singletons. Þ

Pattern Space

In order to detect complex events, the state of the matching of patterns is to be maintained somewhere. To this end: Consumes op event w 1 Consumes nd (not disconnected) complex event w 2 ; w 3 Consumes di (disconnected) complex event w 4 ; w 5 Consumes co (connected) complex event w 6 ; w 7 Consumes nc (not connected) complex event

l 1 Consumes ni (not isolated) complex event l 2
Consumes nr (not reconnected) complex event l 3

Consumes ps (persistent short) complex event -For each pattern .p; r/, a deterministic pattern automaton A equivalent to regular expression r is generated, where final states are marked by pattern event p. -For each complex component X for which the set fA 1 ; : : : ; A k g of pattern automata were generated, a pattern space, written Pts.X /, is created as follows:

1. A nondeterministic automaton N is created by generating its initial state S 0 and one empty transition from S 0 to each initial state of A i , i 2 OE1 :: k; 2. In each A i , i 2 OE1 :: k, an empty transition from each non-initial state to S 0 is inserted;3 3. N is determinized into Pts.X /, where each final state S is marked by the union p of the pattern events that are associated with the states in S that are final in the corresponding pattern automaton.4 Following the steps specified above, Pts.W / is generated as detailed in Table 3. The main part of the table represents the transition function, where for each component transition T 2 fp 1 .p/; : : : ; b 5 .r/g (listed in the first column), and for each state P i , i 2 OE0 :: 10 (listed in the first row), the reached state is indicated in the cell .T; P i /. Moreover, highlighted states are final, namely P 1 , P 4 , P 7 , and P 8 . Complex events associated with final states are listed in the last row, namely di, co, nc, and nd (details are in Table 1). These are singletons of the homonymous pattern event.

Þ Proposition 1 The set p marking a final state S f of Pts.X / is composed of the pattern events p such that .p; r/ 2 P .X /, T is a string in the language of Pts.X / ending at S f , T 0 is a string matching regular expression r, and T 0 is a suffix of T .

Proof. (Sketch) In creating Pts.X /, if we omit step 2 then the language of Pts.X / will be the union of the languages of regular expressions involved in P .X /, where each string ending at S f matches the regular expression associated with a pattern event in p.

Consequently, the statement of the theorem should be restricted in the last condition by T 0 D T . The more relaxed condition, namely T 0 being a suffix of T , comes from step 2 of the construction: generally speaking, because of additional empty transitions, each string T ending at S f matches regular expressions only in its suffixes. .a/ E 0 .I / D (event e is consumed); .b/ 8.o; O/ 2 E out , E.I 0 / D , E 0 .I 0 / D o, where I 0 is the terminal entered by the link exiting O; .c/ If P 0 .P i / ¤ P .P i /, i 2 OE1 :: k, P 0 .P i / is final in Pts.X i / and marked by complex event p, then E.Cot/ D , E 0 .Cot/ D p.

b 3 .l/ --P 5 - --P 8 - --- b 3 .r/ --P 6 - -P 8 -- --- b 4 .l/ ---P 7 ---- --P 7 b 4 .r/ ---P 7 ---- -P 7 - b 5 .l/ ---P 9 ---- --- b 5 .r/ ---P 10 ---- --- di co
As such, transitions in Bsp.H ; H 0 / are marked by transitions of components in H . The new state not only reflects the consumption of input event e of the component transition T and the generation of the output events in E out : it also accounts for the possible occurrence of a complex event p.

A string in the language of Bsp.H ; H 0 / is a history of H . The behavior space is defined for formal reasons only, as its actual materialization is impractical in real HDESs.

Problem Formulation

Diagnosing a HDES means finding the faults in its history. A history can be observed only in its observable transitions, as a sequence of observation labels, called the trace of the history, with each label being associated with an observable transition. The diagnosis process is complicated by two facts. First, several histories may generate the same trace. Second, because of noise and distribution of the channels conveying labels from the HDES, rather than a sequence of labels, the trace is perceived as a DAG, called temporal observation, where each node contains a set of observation labels and each arc represents partial (rather than total) temporal ordering between observation labels. Consequently, several candidate traces are observed, each one being made up by choosing a label in each node of the DAG without violating the temporal constraints imposed by arcs. Furthermore, since several (even infinite) histories may be consistent with the same trace, the diagnosis output is a set of candidate diagnoses, with each candidate corresponding to a subset of the possible histories. However, despite the possible infinite set of histories consistent with the temporal observation, the set of candidate diagnoses is always finite (being it upper-bounded by the powerset of component transitions).

A diagnosis problem for a HDES H is a quadruple }.H / D .H 0 ; V ; O; R/; where:

-H 0 is the initial state of H ; -V is the viewer of H , a set of pairs .T; `/, where T is a transition and `an observation label, with h OEV denoting the trace of history h based on V; -O is the temporal observation of H , with kOk denoting the set of candidate traces; -R is the ruler of H , a set of pairs .T; f /, where T is a transition and f a fault label, with h OER denoting the diagnosis of history h based on R, defined as:

h OER D ff j T 2 h; .T; f / 2 Rg: If a transition T is involved in V , then it is observable, otherwise it is unobservable. If T is involved in R, then it is faulty, otherwise it is normal.
The solution of }.H / is the set of candidate diagnoses:

.}.H // D ˚ı j h 2 Bsp.H ; H 0 /; h OEV 2 kOk; ı D h OER « :

Each candidate diagnosis is the set of faulty transitions of a history that is consistent with the temporal observation. For practical reasons, instead of processing the temporal observation O, the index space of O is generated, namely Isp.O/. This is a deterministic automaton whose language equals kOk (the set of candidate traces). -In W 0 both breakers are closed, protection device is idle, and protection hardware is con (see states in Fig. 2); -V D f.b 1 .l/; opl/; .b 1 .r/; opr/; .b 2 .l/; cll/; .b 2 .r/; clr/; .p 1 ; awk/; .p 2 ; ide/, .p 3 ; awk/; .p 4 ; ide/g; -O is the temporal observation displayed in Fig. 3 (left); -R D f.b 3 .l/; nol/; .b 3 .r/; nor/; .b 4 .l/; ncl/; .b 4 .r/; ncr/; .p 3 ; fop/; .p 4 ; fcp/, .w 1 ; fdw/; .w 6 ; fcw/; .w 7 ; fcw/; .l 1 ; fil/; .l 2 ; frl/; .l 3 ; psl/g, with fault labels having the following meaning: Temporal observation O (Fig. 3, left) includes four nodes, with ! 1 and ! 4 containing two observation labels ( is the empty label). Because of this uncertainty and partial temporal ordering, O embodies six candidate traces, which are the strings of the language of Isp.O/ displayed on the right of Fig. 3 (where = 3 and = 5 are final). Þ

The definition of diagnosis-problem solution is not operational in nature: it refers to the behavior space, which is assumed not to be available in practice. The diagnosis engine is expected to be sound and complete in generating the solution of the problem, without the availability of the behavior space. To this end, it reconstructs only the subpart of the behavior space that is consistent with the temporal observation. In doing so, the reconstruction needs keeping four sorts of information: the state of components, the state of input terminals, the state of the matching of pattern events, and the state of the matching of the temporal observation. Specifically, the solution of a diagnostic problem }.H / D .H 0 ; V ; O; R/ is computed in three steps:

- Bhv.}.H // D .S ; T ; S 0 ; S f /; where -S Â S E P = is the set of states; -S 0 D .H 0 ; E 0 ; P 0 ; = 0 / is the initial state, where E 0 D . ; : : : ; /, P 0 D .P 10 ; : : : ; P k0 / the tuple of the initial states of pattern spaces Pts.X 1 /; : : : ; Pts.X k /, respectively, and = 0 the initial state of Isp.O/; -S f D f.S; E; P ; =/ j E D . ; : : : ; /, = is final g is the set of final states; -T is the transition function, where .S; E; P ; =/ T ! .S 0 ; E 0 ; P 0 ; = 0 / 2 T if and only if:

Generating
1. Conditions 1-4 on S 0 , E 0 , and P 0 , in the specification of the transition function of Bsp.H ; H 0 /, hold;

2. = 0 D ( N = if .T; o/ 2 V; = o ! N = 2 Isp.O/ = otherwise.
The actual algorithm that builds Bhv.}.H // starts from the initial state S 0 and generates all possible transitions based on the conditions above. Eventually, it removes all spurious states and transitions that are not in a path from the initial state to a final state. Example 4 With reference to }.W / defined in Example 3, shown in Fig. 4 is Bhv.}.W //, including states ˇ0; : : : ; ˇ15 , with ˇ15 final. Each state .S; E; P ; =/ is such that S is the quadruple of states for l, p, r, and W , where closed, open, idle, awaken, con, and dis1 are written c, o, i, a, c, and 1, respectively, E is the triple of events at input terminals of l, r, and W , respectively, where op, cl, di, and nc are written o, c, d, and n, respectively, while P and = are the indices of states in Pts.w/ and Isp.O/, respectively. For instance, ˇ2 D .oacc; od; 1; 2/ stands for S D .open, awaken, closed, con/, E D . ; op; di/, P D P 1 , and = D = 2 . Þ Once generated the behavior, each state S of Bhv.}.H // is decorated by a set of candidate diagnoses .S / based on the following two inductive rules:

.1/ For the initial state: .S 0 / D f;g.

.2/ For each transition S T ! S 0 in Bhv.}.H //: -If T is normal then ı 2 .S / ) ı 2 .S 0 /; -If .T; f / 2 R then ı 2 .S / ) .ı [ ff g/ 2 .S 0 /.
The algorithm that decorates Bhv.}.H // starts by applying the first rule, marking the initial state with the singleton of the empty diagnosis. Then, based on the decoration of the initial state, it continuously applies the second rule for each transition exiting a state S whose decoration has changed. If .T; f / 2 R then T is faulty, with f being the relevant fault. If so, each candidate diagnosis in .S / extended by fault f is also a candidate diagnosis in .S 0 /. Instead, if T is normal, all candidate diagnoses in .S / are candidate diagnoses in .S 0 / too. As such, .S / is constructed as the set of diagnoses relevant to histories ending at state S . The algorithm terminates when the application of the second rule does not cause any change in any decoration. Based on the decoration rules for B v , ı is incrementally generated starting from the empty diagnosis initially associated with S 0 , by inserting each faulty label associated with each faulty transition encountered in a path from S 0 to S f . This path is a history provided that it is finite. In fact, cycles in B v allow for an infinite number of applications of the second decoration rule. However, since ı is a set, once a cycle has been covered, all associated fault labels are inserted in ı. Successive iterations of the cycle do not extend ı because of duplicate removals. Thus, ı can always be generated by a finite history h, in other words, ı D h OER .

To prove Theorem 1, we show ı 2 .B v / , ı 2 .}.H //. On the one hand, if ı 2 .B v / then, based on Lemmas 1, 2, and 5, there exists a history h 2 B s such that h OEV 2 kOk and h OER D ı, that is, ı 2 .}.H //. On the other, if ı 2 .}.H // then, based on Lemmas 3 and 4, there exists a history h 2 B v ending at final state S f such that ı D h OER and ı 2 .S f /, that is, ı 2 .B v /.

Discussion

HDESs are a means of modeling complex DESs, where behavior is stratified and events can be generated by patterns of transitions. In spite of being influenced by other components, each internal node X of the hierarchy is a complex component living its own life. This means that X has its own behavioral model, which does not coincide with the composition of the behavioral models of its components. This results in a hierarchical system (HDES) made up of several cohabiting subsystems accommodated at different abstraction levels.

The diagnosis technique defined for HDESs is model-based in nature: diagnosis is output based on the model of the system and the temporal observation. Only the portion of the behavior space consistent with the observation is reconstructed and eventually decorated by candidate diagnoses. Not only does separation of concerns apply to the modeling, it also applies to the diagnosis task. Since each (complex) component is provided with its own behavioral model, diagnosis is context-sensitive [START_REF] Lamperti | Context-sensitive diagnosis of discrete-event systems[END_REF].

Moreover, depending on the degree of constraints on computational resources and time response of the diagnosis engine, model-based reasoning can be scaled to a convenient level of abstraction. This means restricting the HDES H to a portion H 0 (for instance, a complex component along with its children) and projecting observation O on O 0 , resulting from the removal of irrelevant labels, nodes, and arcs. This way, within the context of H 0 , the diagnosis output is complete, even if not sound (due to the removal of the behavioral constraints imposed by H H 0 and the observation constraint imposed by O O 0 ). To refine diagnosis, both H 0 and O 0 may be then enlarged to a suitable extent. Ideally, several restrictions H 0 1 ; : : : ; H 0 n of H can be considered and diagnosed in parallel, with eventual combination of the reconstructed behaviors.

An additional benefit in modeling complex systems as HDESs is support to integration. If we have several DESs, each one devoted to a specific task, and we want to integrate them into a new DES in order to have control on all DESs at a higher abstraction level, then the new DES can be conveniently modeled as an HDES, which is sensitive to specific behavioral patterns of the DESs (complex events). This way, monitoring and diagnosing the HDES is far more natural than interpreting (possibly overwhelming) streams of low-level events generated by DESs, such as alarms detected in a control room. The key point is that the DESs are integrated in a new system not just by connecting them to one another by means of new links between components belonging to different DESs. Instead, besides this physical integration, logical integration is achieved too, so that the new HDES is not just the union of the DESs: it is an higher-level system with its proper behavior and, as such, living its own life.

Related Work

This paper substantially extends the idea of context-sensitive diagnosis [START_REF] Lamperti | Context-sensitive diagnosis of discrete-event systems[END_REF] in three directions. First, in [START_REF] Lamperti | Context-sensitive diagnosis of discrete-event systems[END_REF] pattern stratification is only apparent, as, after macro-substitution, the regular expression is invariably defined on (basic) component transitions. In this paper, pattern stratification is real, since regular expressions are defined on the transitions of possibly complex components. Second, in [START_REF] Lamperti | Context-sensitive diagnosis of discrete-event systems[END_REF] faults are associated with pattern matching. In this paper, faults are associated with transitions of components: pattern matching generates pattern events and, by union, complex events, to which complex components are sensitive. More importantly, in [START_REF] Lamperti | Context-sensitive diagnosis of discrete-event systems[END_REF] context-sensitivity is defined on active systems, while this paper deals with HDESs, which provide behavioral stratification: separation of concerns holds not only for diagnosis but also for behavior.

This paper also differs from [START_REF] Jéron | Supervision patterns in discrete event systems diagnosis[END_REF], where the notion of supervision pattern is introduced, mainly because neither a hierarchical structure for the system is conceived nor behavioral stratification is applicable.

HDESs are not HFSMs (Hierarchical Finite State Machines). The notion of an HFSM was inspired by statecharts [START_REF] Harel | Statecharts: a visual formalism for complex systems[END_REF][START_REF] Harel | STATEMATE: a working environment for the development of complex reactive systems[END_REF], a visual formalism for complex systems. The most important feature of an HFSM is hierarchical state-nesting: if a system is in a nested state (substate), it is also in all its surrounding states (superstates). Moreover, transitions are defined at each level of the hierarchy. This resembles the idea of class inheritance in object-orientation and, in fact, it provides relevant advantages, including factorization and reuse. A simplified version of statechart, namely HFSM, was considered for solving a class of control problems in [START_REF] Brave | Control of discrete event sysytems modeled as hierarchical state machines[END_REF]. Recently, diagnosis of HFSMs has been considered in [START_REF] Idghamishi | Fault diagnosis in hierarchical discrete-event systems[END_REF][START_REF] Paoli | Diagnosability analysis of a class of hierarchical state machines[END_REF]. However, no patterns are involved, events are simple, and diagnosis is context-free.

Conclusion

HDESs are a means to formalize complex DESs with behavior stratification. This allows for the modeling of a hierarchy wherein different, yet integrated, subsystems coexist, each one living its own life. Benefits include context-sensitivity and scalability of diagnosis, as well as support to logical system-integration. It is our belief that monitoring and diagnosing complex systems, such as a nuclear plant or a large power network, requires some sort of abstraction and separation of concerns. The ideas presented in this paper may be a step in the right direction.

Fig. 1 .

 1 Fig. 1. HDES: protected power transmission line.

Fig. 2 .

 2 Fig. 2. Behavioral models.

Fig. 3 .

 3 Fig. 3. Temporal observation O (left) and relevant index space Isp.O/ (right).

Example 3

 3 With reference to Example 1, we define the diagnostic problem for the left-hand side protection-hardware as }.W / D .W 0 ; V; O; R/, where:

  nol : l fails to open; nor : r fails to open; ncl : l fails to close; ncr : r fails to close; fop : p fails to trip breakers to close; fcp : p fails to trip breakers to open; fdw : W fails to disconnect the line; fcw : W fails to connect the line; fil : L fails to be isolated; frl : L fails to be reconnected; psl : L is struck by a persistent short circuit.

Fig. 4 .

 4 Fig. 4. Behavior Bhv.}.W //.

Table 1 .

 1 Details for transitions of behavioral models in Fig.2.

T Action performed by component transition T p 1 Detects low voltage and outputs op (open) event p 2 Detects normal voltage and outputs cl (close) event p 3 Detects low voltage, yet outputs cl event p 4 Detects normal voltage, yet outputs op event b 1 Consumes op event and opens b 2 Consumes cl event and closes b 3 Consumes op event, yet keeps closed b 4 Consumes cl event, yet keeps open b 5 Consumes cl event b 6

Table 2 .

 2 Specification of patterns by regular expressions.

	Pattern event	Meaning	Regular expression
	di	Disconnected	b 1 .l/ j b 1 .r/
	co	Connected	b 2 .l/ j b 2 .r/
	nd	Not disconnected p

3 .p/ j p 1 .p/..b 3 .l/b 3 .r// j .b 3 .r/b 3 .l/// nc Not connected p 4 .p/ j p 2 .p/.b 5 .r/‹ b 4 .l/ j b 5 .l/‹ b 4 .r// ni Not isolated w 1 .W / j w 1 .W 0 / nr Not reconnected w 6 .W / j w 7 .W / j w 6 .W 0 / j w 7 .W 0 / ps Persistent short .w 5 .W /w 1 .W / w 2 .W /.:w 5 .W // / C j .w 5 .W 0 /w 1 .W 0 / w 2 .W 0 /.:w 5 .W 0 // / C Example 2 With reference to Example 1, consider complex component W , whose patterns are defined on top of Table 2.

Table 3 .

 3 Tabular specification of pattern space Pts.W /. T n P i P 0 P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9 P 10 p 1 .p/ P 2 P 2 P 2 P 2 P 2 P 2 P 2 P 2 P 2 P 2 P 2 p 2 .p/ P 3 P 3 P 3 P 3 P 3 P 3 P 3 P 3 P 3 P 3 P 3 p 3 .p/ P 8 P 8 P 8 P 8 P 8 P 8 P 8 P 8 P 8 P 8 P 8 p 4 .p/ P 7 P 7 P 7 P 7 P 7 P 7 P 7 P 7 P 7 P 7 P 7 b 1 .l/ P 1 P 1 P 1 P 1 P 1 P 1 P 1 P 1 P 1 P 1 P 1 b 1 .r/ P 1 P 1 P 1 P 1 P 1 P 1 P 1 P 1 P 1 P 1 P 1 b 2 .l/ P 4 P 4 P 4 P 4 P 4 P 4 P 4 P 4 P 4 P 4 P 4 b 2 .r/ P 4 P 4 P 4 P 4 P 4 P 4 P 4 P 4 P 4 P 4 P 4

  (where e is the input event and E out the output events with relevant terminals) is a transition of a component C such that s equals one element of S, I is an input terminal of C , and E.I / D e; 2. S 0 differs from S only in s 0 replacing s; 3. If C 2 C .X i /, i 2 OE1 :: k, then P 0 differs from P only in the i -th element as follows:

	P 0 .P i / D	(	N P if P .P i / P i 0 otherwise; T ! N P 2 Pts.X i /
	4. E 0 differs from E based on these conditions:

nc nd

2.2 Behavior Space

Starting from its initial state H 0 , HDES H may perform a sequence of component transitions within its behavior space, written Bsp.H ; H 0 /, which is a finite automaton Bsp.H ; H 0 / D .S; T; S 0 /: S is the set of states .S; E; P /, with S D .s 1 ; : : : ; s n / being the tuple of states of components in H . E D .e 1 ; : : : ; e m / is the tuple of events at input terminals of components in H ( indicates no event), and P D .P 1 ; : : : ; P k / the tuple of pattern-space states. S 0 D .H 0 ; E 0 ; P 0 / is the initial state, where E 0 D . ; : : : ; / and P 0 D .P 10 ; : : : ; P k0 / the tuple of the initial states of pattern spaces Pts.X 1 /; : : : ; Pts.X k /, respectively. T is the transition function, where .S; E; P / T ! .S 0 ; E 0 ; P 0 / 2 T if and only if:

1. T D s .e;I / j E out ! s 0

  Decorating the states of behavior Bhv.}.H // by the associated set of candidate diagnoses. Let E be the domain of tuples .e 1 ; : : : ; e m / of events at input terminals (other than Ext) of components in C.H /. Let = be the domain of states in Isp.O/. Let P be the domain of tuples .P 1 ; : : : ; P k / of pattern-space states. The behavior of }.H / is a deterministic automaton:

the index space of temporal observation O; -Generating the subspace of Bsp.H ; H 0 / that is consistent with temporal observation O, based on viewer V , called the behavior of }.H /, written Bhv.}.H //; -The actual solution .}.H // is the union of the decorations associated with final states of Bhv.}.H // (see Theorem 1). Formally, Bhv.}.H // is defined as follows. Let S be the domain of tuples .s 1 ; : : : ; s n / of states of components in C .H /.

Table 4 .

 4 Decoration of Bhv.}.W //. Based on ruler R (Example 3), the behavior in Fig.4will be decorated as specified in Table4. Therefore, two candidate diagnoses are associated with final state ˇ15 , namely ı 1 D fnor; ncl; fcwg, and ı 2 D fnor; fcp; fcwg, corresponding to these two scenarios:ı 1 W Breaker rfails to open, breaker l fails to close, and protection hardware W fails to connect; ı 2 W Breaker r fails to open, protection device trips breakers to open rather than to close, and W fails to connect. Based on Theorem 1, fı 1 ; ı 2 g is the solution of }.W /. Albeit we have two candidates, since ı 1 \ ı 2 D fnor; fcwg, certainly r failed to open and W failed to connect. Þ Theorem 1 Let }.H / D .H 0 ; V ; O; R/, and .B v / denote the union of the sets of diagnoses decorating the final states of Bhv.}.H //. Then, .}.H // D .B v /. Proof. (Sketch) The proof is grounded on Lemmas 1-5, where B s and B v denote Bsp.H ; H 0 / and Bhv.}.H //, respectively. If history h 2 B v then h 2 B s . This derives from the fact B v differs from B s in the additional field =, which is irrelevant for conditions on S 0 , E 0 , and P 0 . By induction on h, starting from the initial state, each new transition applicable in B v is applicable in B s too. If history h 2 B v then h OEV 2 kOk. Recall that h OEV is the sequence of observable labels associated with visible transitions in viewer V . Based on the definition of B v , h OEV belongs to the language of Isp.O/, which equals kOk. Thus, h OEV 2 kOk. Lemma 3 If history h 2 B s and h OEV 2 kOk then h 2 B v . By induction on h, starting from the initial state, each new transition T applicable in B s is applicable in B v too. In fact, if T is invisible, no further condition is required. If T is visible, based on the assumption h OEV 2 kOk and that the language of Isp.O/ equals kOk, the label associated with T in viewer V matches a transition in Isp.O/. Lemma 4 If history h 2 B v ends at final state S f then .S f / includes a candidate diagnosis h OER . Based on the two rules for decoration of B v , by induction on h, starting from the initial state (h empty) and the empty diagnosis ı, the addition of a new transition T in h extends ı (within the decoration of the new state) by either nothing (T normal) or a fault label (T faulty). Upon the last transition of h, ı includes all fault labels associated with faulty transitions in ruler R, in other words, ı D h OER . Lemma 5 If S f is a final state in B v and ı 2 .S f / then there exists a history h 2 B v ending at S f such that h OER D ı.

	States	Decoration
	ˇ0; ˇ1; ˇ2; ˇ4	f;g
	ˇ3; ˇ5; ˇ6; ˇ7; ˇ10	ffnorgg
	ˇ9	ffnor; nclgg
	ˇ13	ffnor; ncl; fcwgg
	ˇ8; ˇ12 ; ˇ14	ffnor; fcpgg
	ˇ11	ffnor; fcp; fcwgg
	ˇ15	ffnor; ncl; fcwg; fnor; fcp; fcwgg
	Example 5

This allows for pattern-matching of overlapping strings.

Each state S of the deterministic automaton is identified by a subset of the states of the equivalent nondeterministic automaton.

Acknowledgment

This work was supported in part by NSFC under Grant No. 61003101, and Zhejiang Provincial Natural Science Foundation under Grant No. Y1100191.


Fleur Jeanquartier
email: f.jeanquartier@hci4all.at

Andreas Holzinger
email: a.holzinger@hci4all.at

On Visual Analytics And Evaluation In Cell Physiology: A Case Study

Keywords: visual analytics, evaluation of visualization, human computer interaction, biomedical science

In this paper we present a case study on a visual analytics (VA) process on the example of cell physiology. Following the model of Keim, we illustrate the steps required within an exploration and sensemaking process. Moreover, we demonstrate the applicability of this model and show several shortcomings in the analysis tools functionality and usability. The case study highlights the need for conducting evaluation and improvements in VA in the domain of biomedical science. The main issue is the absence of a complete toolset that supports all analysis tasks including the many steps of data preprocessing as well as end-user development. Another important issue is to enable collaboration by creating the possibility of evaluating and validating datasets, comparing it with data of other similar research groups.

Introduction

From the first data analysis attempts to exploratory data analysis, up to information visualization, today we are facing the possibilities of visual analytics (VA). With VA several analysis processes may be transformed and become more effective and efficient through integrating automated analysis results and reasoning [START_REF] Keim | Mastering The Information Age-Solving Problems with Visual Analytics[END_REF]. There is ongoing research in a variety of application areas ranging from document analysis over network security to molecular biology. Applying visual analysis techniques within these areas bring up certain limitations [START_REF] Kohlhammer | Solving Problems with Visual Analytics[END_REF]. Dealing with the complexity of biological data requires sophisticated visualization technologies. Prominent examples of visualization for exploration and analysis in the domain of biology come from systems biology and include, among many others, the visualization of biological networks and omics data [START_REF] Gehlenborg | Visualization of omics data for systems biology[END_REF] such as protein structures [START_REF] Doncheva | Topological analysis and interactive visualization of biological networks and protein structures[END_REF], visual analysis of gene expression data [START_REF] Lex | Caleydo: Design and evaluation of a visual analysis framework for gene expression data in its biological context[END_REF], but also visual analysis of cell signaling networks [START_REF] Berger | Avis: Ajax viewer of interactive signaling networks[END_REF]. For populating such databases for network analysis biologists also deal with basic research in cell physiology. In Fig. 1 we see a slightly modified version of the VA Process, first described by [START_REF] Keim | Visual Data Mining[END_REF]. According to Keim, humans have to be included early in the data analysis process. By using their background knowledge and being supported by processing, transformation and visualization tools the analysis process eventually brings up new insight. We illustrate the mapping of a VA process during one example cell physiological experiment. Life scientists especially in the domain of biomedical science may struggle with the fact, that the process starts with a first data analysis. As for the observed work process later described in the Section 2 the domain expert also started with describing the hypothesis and then choosing suitable materials and methods for data acquisition. According to [START_REF] Keim | Visual Data Mining[END_REF] input for the data sets used in the VA process are of heterogeneous nature and can be results from scientific experiments. Therefore we included the prior results as input for the feedback loop. The hypothesis may be formed by a preceding exploration. The domain expert makes use of knowledge gained by preceding work. Human computer interaction (HCI) and knowledge discovery (KDD) along with biomedical informatics are of increasing importance to effectively make sense out of data [START_REF] Holzinger | On Knowledge Discovery and interactive intelligent visualization of biomedical data: Challenges in Human-Computer Interaction & Biomedical Informatics[END_REF]. Biologists can benefit from a data deluge with the means of an integrated visualization approach, however, conducting evaluation and improving toolsets are still required to overcome certain hurdles on the way to new insights [START_REF] Donoghue | Visualizing biological data -now and in the future[END_REF]. A domain expert as analyst often works alone while analysing data sets facing many problems, some of that have been illustrated by [START_REF] Wong | Information Quality in e-Health[END_REF]. To foster sense-making and insights in VA systems it is essential to conduct studies and determine how people are using such systems [START_REF] Kang | How Can Visual Analytics Assist Investigative Analysis? Design Implications from an Evaluation[END_REF][START_REF] Wong | The Top 10 Challenges in Extreme-Scale Visual Analytics[END_REF]. Case studies as field studies are a common approach to evaluating VA systems [START_REF] Lam | Empirical Studies in Information Visualization: Seven Scenarios[END_REF]. Qualitative evaluation such as observational studies can be conducted in a more realistic setting and allow improved understanding of existing practices for analysis and environmental constraints [START_REF] Carpendale | Evaluating information visualizations[END_REF].

Consequently, we describe an observational study of a domain expert in cell physiology to present the current practice of VA in this domain.

Observation

The user, a domain expert within biomedical science, is part of the visual analysis and KDD process of a group of researchers dealing with cell physiology experiments. We accompanied the domain expert while investigating and analysing a set of experiments' results and observed the expert's analysis work. The analysis process includes visual analysis as part of the data processing, data analysis and KDD process as well as visual communication for dissemination. A fluorescent biosensor [START_REF] Morris | Fluorescent biosensors of intracellular targets from genetically encoded reporters to modular polypeptide probes[END_REF] measures the concentration of certain molecules within cellular compartments. Fluorescent biosensors can be used for monitoring various processes and analytes such as metabolites, ions, target localization, gene expression and physiological relevant changes within subcelluar regions [START_REF] Okumoto | Quantitative imaging with fluorescent biosensors[END_REF].

The biosensor allows to quantify variations in concentration or localization of the specific analyte within the cell by a change in fluorescence intensity. This quantification is further visualized as intensity signal over time in terms of kinetic curves. By that method, data in hundreds of columns and rows is recorded and has to be processed further. In summary, this method provides the measurement of biological signaling dynamics in vivo.

Experiments start with monitoring kinetics in signal transduction. The signal represents the fluorescence intensity [START_REF] Mehta | Reporting from the field: genetically encoded fluorescent reporters uncover signaling dynamics in living biological systems[END_REF]. First of all sequences of high-resolution fluorescent imaging of cells are acquired to capture dynamic changes. This action takes place in the lab's dark room. Fluorescence images are captured by a digital camera incorporating a CCD detector, connected to the fluorescence microscope. A commercial bioimaging software is used to communicate with the hardware, translating recorded signals to raw data. The software also provides some data/image processing functionality. Once the measurements are complete, the analysis process continues with data processing and image analysis. Noise (such as background lights within the dark room) reduction of images is supported by a ratio function. The domain expert marks specific regions of interest within the cell in order to monitor biological activites in healthy and pathological cells. Image segmentation is done manually insofar as the domain expert manually selects specific regions of interest on the image data for further comparison and analysis. Hence, regions of interest as polygon shapes are placed on every raw source to display the intensity value. The evaluation of whether the data and to what extent is accurate is done by manually comparing specific regions with a background region. The software allows the scientist to explore the data only in a very limited way. For not occupying the lab's dark room workplace for the time-consuming tasks of data processing and analysis, the expert moves to another workplace outside the dark room. Consequently, when the domain expert believes, that the data is sufficient, the raw data is exported to a commercial spreadsheet computation software via CSV for further processing and analysis.

Fig. 2. First visual analysis of intensity signal over time

The domain expert creates a first visualization (compare Fig. 2) of the data, describing the kinetic changes in specific groups of healthy and pathological cells. This task is done semi-automatically by end-user development [START_REF] Lieberman | End user development[END_REF]. The following visual analysis shows, that the data has to be further filtered, corrected and transformed and finally improved in terms of readability and to be visualizable for the task of dissemination. It is up to the domain expert and the implicit knowledge of models, developed by the group of researchers within the lab, which transformation and manipulations are considered to be appropriate. Some of the processing tasks are automatic and some are again manual. The domain expert uses several tools for the various tasks and switches between them while advancing in the analysis process. While the process itself is occasionally being discussed in group, several smaller but complex actions are double checked by colleagues. Both the experiments and the visual analysis process are repeated many times until certain "surprising" [START_REF] Beale | Supporting serendipity: Using ambient intelligence to augment user exploration for data mining and web browsing[END_REF] results get visible. This repetitive approach to gain new insights, also known as explorative data analysis (EDA), supports the process illustrated in Fig. 1 as it consists of a feedback loop. Finally, when the visual analysis results show surprising effects, the domain experts concludes with the dissemination (see Fig. 3) of the results, again with the means of visualization. The final visualizations are again being iteratively improved. By further discussing the case study's process and comparing it with the VA process, we try to outline certain issues when dealing with the evaluation of scientific visualizations.

Discussion

The case study shows, that there are analysis processes in biomedical science which embody VA as a lived approach. At the same time, the case study also shows the need for improvements regarding HCI and end-user development. Experts in this domain are using their domain knowledge in combination with both automatic and visual analysis together, but need to be guided by computer science experts to improve the choice of tools that are used. There are certain tasks still done manually that could be automated or at least semi-automated, using the right tool, such as image segmentation, noise reduction as well as postprocessing up to creating a set of fitting visualizations for dissemination. For instance, there already exist attempts to automatically estimate suitable background in fluorescence imaging [START_REF] Chen | In situ background estimation in quantitative fluorescence imaging[END_REF] and automatic localization of cell nuclei [START_REF] Song | Regionbased progressive localization of cell nuclei in microscopic images with data adaptive modeling[END_REF].

The case study supports the statement, proposed by VA, that automated analysis often speeds up analysis tasks. It also shows that communication through visual representations is used for the dissemination of research results (see Fig. 3). Therefore, the case study shows, that visual analysis plays an important role for gaining new insights and dissemination. However, the case study also highlights that certain evaluation tasks are missing. Lessons Learned include that there is a gap in free exploration of data and information due to the lacking usability and interaction possibilities of the tools used. The researchers within this field of study state, that they do not know about powerful VA solutions. At the same time, they are facing certain restrictions that hinder them to cooperate fully with computer science experts. During the observation the domain expert made complaints about shortcomings in the analysis tools' functionality and usability. Many tasks have to be repeated, not only due to data inconsistency, but also because most tools are hardly faulttolerant and lack in supporting the user in certain data preprocessing steps as well as in the post-processing such as choosing the right visualization technique and improving the visualization's readability.

There are several possibilities to improve the end-user development and to min-imize the interaction junk [START_REF] Endert | Interaction junk[END_REF] within the observed process, such as simplifying the creation of the effect curves for both visual analysis as well as dissemination. Furthermore, the visualizations in use are still limited to curve diagrams and bar charts. Alternative visualization metaphors such as multi-variate data visualizations [START_REF] Fuchs | Visualization of Multi-Variate Scientific Data[END_REF] allow scientists to explore the data and it's various dimensions in other ways and may highlight certain effects that are not visible within the current effect curves. The discussion after the observation further included improvements and suggestions to support the whole VA process. Due to the reason that both data as well as study results are confidential we are not allowed to go into detail in this respect. However, we already communicate general aspects of HCI and KDD and present general suggestions for improving VA within this domain. The domain expert agreed that there are several possibilities how evaluation could be integrated to support VA. Lam et al. already list some fitting evaluation goals and questions within the VDAR-and the CTV scenario [START_REF] Lam | Empirical Studies in Information Visualization: Seven Scenarios[END_REF]. However, the very idea of discussing the visual analysis process with a domain expert in HCI already brought up certain shortcomings within the visual analysis work. Suggestions include: Evaluating the dataset, comparing it to datasets of other similar groups of researchers, would help validating specific models as well as techniques and speed up the analysis work. Moreover, enabling and facilitating collaboration supports scientific problem solving [START_REF] Good | Games with a scientific purpose[END_REF]. The researchers in the group also agree on the fact, that evaluating software in use and furthermore, having the possibility to improve and extend the tools functionality would improve their daily research tasks. Incooperating the many steps of data examination and preprocessing into a single tool would be highly appreciated. The case study highlights the need for conducting evaluation and improvements in VA in the domain of biomedical science.

Conclusion

Every day scientists in many sub domains of life sciences such as biomedical science are facing the challenging task of VA with the goal of reaching new insights. Life scientists may benefit from a data deluge with the means of an integrated visualization approach. However, conducting evaluation and improving certain toolsets for exploratory data analysis and end-user development are prominent challenges on the way to new insights.

We described an observational study of VA in cell physiology. We compared the process to Keim's VA process. The case study shows, that there are analysis processes in biomedical science which embody VA. Further studies may include additional practice of VA related analysis work of various other approaches in biomedical science. The observation highlights the need for conducting evaluation and improvements in VA in the domain of biomedical science. We suggested evaluation possibilities and further noted challenges regarding its' application for visualization in life sciences. Among others, suggestions include incooperation and improvement of support for developing visualization in regard to analysis.

Fig. 1 .

 1 Fig. 1. Adapted Version of Keim's VA Process for the Application In Cell Physiology

Fig. 3 .

 3 Fig. 3. Visualization of the kinetic parameters measured within the groups of healthy control to pathological cells for dissemination