A Philippot

P Marangé

V Carré-Ménétrier

B Riera

Implementation of diagnosis approach for Discrete Event Systems

Keywords: Discrete Events Systems, Modeling, Diagnosis, Manufacturing systems

This paper presents an approach of diagnosis for manufacturing system considered as Discrete Event Systems. It uses plant decomposition and a decentralized diagnosis structure to reduce the combinatory explosion found in centralized structures. The local behavior is extracted using decentralized plant modeling. It is from this behavior that possible faults are identified to construct abnormal behavior models. The approach is illustrated around a manufacturing benchmark.

INTRODUCTION

Manufacturing systems have become more and more complex owing to technological evolution. Moreover, each maintenance intervention has an important cost, as false removal for example in case of uncertainty. This complexity and the desire for improved availability, reliability and dependability require the development of systematic approaches of diagnosis to detect and isolate a fault.

In literature, many approaches are developed and are based on the observability of the system [START_REF] Sampath | A Discrete Event Systems Approach to Failure Diagnosis[END_REF], [START_REF] Qiu | Decentralized/distributed failure diagnosis and supervisory control of discrete event systems[END_REF], [START_REF] Cordier | Distributed Chronicles for On-line Diagnosis of Web Services[END_REF]. However, manufacturing systems are often described as dynamic systems with discrete states which change only by discrete events. They are considered as Discrete Event Systems (DES) (Cassandras and Lafortune, 1999). Consequently, the observable information present is poor because of the discrete state space. Its observation alone does not often allow to detect a fault occurrence and to isolate the responsible element. Several approaches have been developed to solve the Fault Detection and Isolation (FDI) problem [START_REF] Sampath | A Discrete Event Systems Approach to Failure Diagnosis[END_REF], [START_REF] Su | Decentralized fault diagnosis for discrete-event systems[END_REF], [START_REF] Cordier | Distributed Chronicles for On-line Diagnosis of Web Services[END_REF]. Most of them are based on the use of a model in order to specify the normal and/or faulty behaviors of the system. This model defines how system states change due to event occurrences. The goal is to compare the system model state with the real one, based on the system observations. A failure is detected when the two states do not match.

Three structures of diagnosis decision are presented in literature. In centralized structure, the global diagnosis decision is taken by one centralized diagnoser based on one system model [START_REF] Sampath | A Discrete Event Systems Approach to Failure Diagnosis[END_REF]. Decentralized structure comprises one system model associated with several local diagnosers [START_REF] Wang | Decentralized diagnosis of discrete event systems using conditional and unconditional decisions[END_REF]. A very limited communication is permitted through a coordinator to solve the ambiguity or indecision problem between local diagnosers' decisions. Distributed structure uses several local models associated with several local diagnosers. A pure concurrent communication among local diagnosers is necessary to realize a global diagnosis decision [START_REF] Qiu | Decentralized/distributed failure diagnosis and supervisory control of discrete event systems[END_REF], [START_REF] Cordier | Distributed Chronicles for On-line Diagnosis of Web Services[END_REF].

The main disadvantage of centralized approaches for DES is the state explosion. The approaches with decentralized structure constitute a solution to this drawback. But so far, designing a decentralized diagnoser requires the existence of centralized model which entails again the state explosion problem [START_REF] Su | Decentralized fault diagnosis for discrete-event systems[END_REF]. In [START_REF] Cordier | Distributed Chronicles for On-line Diagnosis of Web Services[END_REF], the authors propose an approach to realize the decentralized diagnosis without using a global model. This approach is based on the use of a merging procedure which exploits the independence property between sub-models. The major advantage of distributed diagnosis approaches is that there is no need for a centralized plant model. The communication between local diagnosers is used to solve the indecision problem. However, their main disadvantage is the need to establish a performing protocol of communication, which scales well with the system complexity.

In this paper a decentralized diagnosis approach is proposed to realize the diagnosis of DES, specifically manufacturing systems with discrete sensors and actuators. Manufacturing systems can be represented by several models of components called "Plant Elements" (PEs) which describe all possible evolutions. From each local component, an analysis is made to construct local models of abnormal behavior called diagnosers. Each local diagnoser returns a label to the user and the global decision is all local decisions merged.

The paper is organized as follow. In section 2, the proposed approach is presented with the different steps of modeling. Section 3 illustrates the approach in several aspects. Conclusion and prospects close the paper in section 4.

DECENTRALIZED DIAGNOSIS

In industrial processes, a manufacturing system is a functional chain composed of a controller which sends commands to a plant and receives sensor values (Fig. 1). Plant represents the mechanical part whereas controller is the logical part which describes the desired behavior. This exchange between controller and plant represents the only observable information available on line. As a diagnoser is defined as an observer of the system, it is necessary to use this information to rebuild behaviors through models.

Controller Plant

Observer

Sensor values Commands Fig. 1. Functional chain.

From the introduction, a centralized approach appears as unthinkable for complex systems. However, the difficulty of a decentralized approach is to determine the level of modular decomposition in a generic way. A manufacturing system is composed of mechanical components, called Plant Elements (PEs), which are actuators with associated sensors. Consequently, the proposed approach builds local diagnosers from each PE. Figure 2 shows the different steps to obtain local diagnosers. Firstly, from the real plant, PEs are defined from a library of models. Secondly, an expert analysis is made to identify the possible abnormal situations, and then to obtain local diagnosers.

PLANT

(2) Expert Analysis

Plant Element PE 1 Plant Element PE k Diagnoser D 1 Diagnoser D k (1) Modeling Fig. 2.
Steps of the proposed approach.

Plant Elements

Plant is divided into several components (actuator with associated sensors) which can be modeled in Plant Element.

Each model G i and corresponding language L i describes the logical and untimed behavior of the monitored system. It is a

Moore automaton: M = (Σ, X, Y, δ, h) where Σ is the set of finite events, X is the set of states, Y is the output space, δ: Σ

x X → X is the state transition function. δ(α, x) gives the set of possible next states if α occurs at x. h: Σ x X → Y is the output function. H(α, x) is the observed output when α occurs at x.

In [START_REF] Balemi | Supervisory control of a rapid thermal multiprocessor[END_REF], authors define controllable events Σ c ⊆ Σ as the control outputs (actuators) and uncontrollable events Σ u ⊆ Σ are defined as the control inputs (sensors). Σ o ⊆ Σ is the set of observable events where Σ c ⊆ Σ o . An automaton is used for each model. This automaton takes into account all the observable events. The detailed explanation of the construction of this model can be found in [START_REF] Philippot | On-line synthesis approach based on a structured plant modeling[END_REF]).

This paper is not focused on the PE modeling method. PE models have been validated in previous works and a library of common PE used in manufacturing systems has been established [START_REF] Philippot | Unconditional Decentralized Structure for the fault diagnosis of Discrete Event Systems[END_REF]. An example is given in section 3.

Temporal information

The majority of sensors and actuators in manufacturing systems produce constrained events since state changes are usually effected by a predictable flow of materials [START_REF] Boufaïed | Contribution à la Surveillance Distribuée Des Systèmes à Evénements Discrets Complexes[END_REF], [START_REF] Holloway | Time templates for discrete event fault monitoring in manufacturing systems[END_REF]. To enrich Boolean models, a timed model centred on the notion of expected event sequencing and timing relationships can be used. The temporal information about events minimal and maximal durations is represented by the actuator's minimal and maximal response times.

For each state of PE a temporal relationship between input and output events is obtained thanks to the learning phase which returns a Gaussian distribution. Each prediction is constructed for observable correlated events and it describes the next events that should occur and the relative time periods in which they are expected. These pre-defined time periods are determined by experts according to system dynamic and to the desired behavior. An extrapolation of the Gaussian distribution is made to choose minimal and maximal times. Consequently, when an event α 1 occurs at the state x 1 , the event α 2 should happen at the state x 2 and within the interval [t min , t max ] (Fig. 3). The use of the Gaussian distribution instead of intervals will be a prospect.

t min 0 ↑α 1 ↑α 2 t max t

Fig. 3. Temporal information.

Diagnosers

In industrial processes, a manufacturing system is a functional chain composed of a controller which sends commands to a plant and receives sensor values. Plant represents the mechanical part whereas controller is the logical part which describes the desired behavior. This exchange between controller and plant represents the only observable information available on line. As a diagnoser is defined as an observer of the system, it is necessary to use this information to rebuild behaviors through models.

From the introduction, a centralized approach appears as unthinkable for complex systems. However, the difficulty of a decentralized approach is to determine the level of modular decomposition in a generic way. A manufacturing system is composed of mechanical components, called Plant Elements (PEs), which are actuators with associated sensors. Consequently, the proposed approach builds local diagnosers from each PE by an expert analysis to identify the possible abnormal situations from each normal state.

Consequently, a diagnoser is defined as

D i = (X i ∪ XDF i , Σ io , δ i , x i0 , V i , h i , PF i , l i ) with:
• X i is the set of normal states of NBMi,

• XDF i is the set of abnormal states,

• Σ io is the set of observables events by the PEi,

• δ i : X i × Σ i * → X i ∪ XDF i is the transition function, • x i0 is the initial state,
• V i is an input/output vector with V i (x) the vector of the state x, • h i : X i ∪ XDF i → Σ io is the output function where h i (x) is the observable event at the output of the state x, • PF ix = {PFx, ∀x ∈ X i } represents the set of prediction functions of the state x, • l x is the decision functions of the state x which can be the label N to indicate a Normal functioning or/and one fault label {Fj} or more.

If l x = {N}, then the diagnoser can decide with certainty the non-presence of faults. If l x = {Fj}, then the diagnoser indicates with certainty the occurrence of a fault of the type Fj. If l x = {N, Fj}, then the diagnoser cannot decide whether a fault has occurred or not and the system is in ambiguity or indecision case. Labels are defined in subsets called partition Π Fj . The knowledge of all faults comes from an expert analysis and/or documentation such as Failure Mode and Effects Analysis (FMEA), a tool used in safety, dependability and quality management [START_REF] Ashley | Failure analysis beats Murphy's law[END_REF].

For an input/output vector of 3 variables (e1 e2 e3) with labels {N, F1, F2, F3} for a normal or an abnormal behavior respectively on e1, e2 or e3:

From a normal state x0, h(x0) = ↑e1 is the only one normal evolution possible to attempt normal state x1 with label N. Consequently, possible faults which can be detected and isolated from x0 are:

• h(x0) = ↑e2: observable fault on e2 associated to label F1 (state x2), • h(x0) = ↑e3: observable fault on e3 associated to label F2 (state x3), • PFx0 = 1: non observable fault on e1 corresponding to a non-satisfaction of the temporal constraint. Diagnoser goes to state x4 with a label F3 by an internal event ePFx0. Remarks: non observable faults on e2 and e3 (stuck to 0) cannot be detected from x0 and need new events. Normal behavior on x0 cannot be guaranteed Label on this state is not only {N} but must be {N, F2, F3}.

Consequently, for a diagnoser with p variables, it is possible from each normal state to detect p-1 observable faults and 1 non observable faults.

ILLUSTRATION ON A BENCHMATK

Presentation

All of the proposed methodology will be illustrated by means of a virtual system from the ITS PLC collection, proposed by the Portuguese company Real Games. ITS PLC collection is a set of simulation software dedicated to automation training [START_REF] Riera | Complementary usage of real and virtual manufacturing systems for safe PLC training[END_REF]. Demos and technical descriptions of the five virtual industrial systems are available and freely downloadable at web address www.realgames.pt. As part of the work presented in this paper, the "sorting system" is used. The objective of this system is to bring boxes of entry conveyor to exit conveyor by sorting them according to for instance their height (Fig. 5). The specification used is as follows: after pressing the "start" button, the boxes are sent successively one to the left elevator and one to the right elevator. After pressing the "stop" button, boxes in transit are evacuated. In order to not overload the paper, the output conveyors are always on (A5 = A6 = 1) and the management of the buttons "start" and "stop" is not presented.

Turntable diagnoser

All PEs models are not shown in the paper. In this paragraph, only turntable is described, from PE model to diagnoser model.

The turntable PE is a monostable actuator and then is driven by only one output (Fig. 6). At the initial state x 0 , the turntable is at the loading position c4. When output A4 is activated by the controller, then the turntable is in movement and sensor c4 is deactivated (state x 1 to x 2 ). From here, if the command is always activated, the turntable goes to unloading position c5 (state x 3 ) and awaits the deactivation of A4 to go back at the initial position (states x 4 , x 5 and x 0 ). From state x 2 , during the movement, if controller sends the deactivation of A4 (state x 5 ), then the turntable comes back to state x 0 without having achieved sensor c5. And from state x 5 , then during the movement back, it is possible to reactivate A4. This automaton with 6 states and 10 transitions represents all possible evolutions of the turntable PE. The others PEs have been modeled in the same way and are present in a library [START_REF] Philippot | Contribution au Diagnostic Décentralisé des Systèmes à Evénements Discrets : Application aux Systèmes Manufacturiers[END_REF]. Turntable diagnoser is obtained after identification of all possible faults on the PE. It is an expert analysis which allows to define the following faults associated to a label:

• F1: Sensor c4 stuck-off to 0 • F2: Sensor c4 stuck-on to 1 • F3: Sensor c5 stuck-off to 0 • F4: Sensor c5 stuck-on to 1 • F5: Cylinder stuck to c4 position • F6: Cylinder stuck to c5 position • F7: Unexpected c4 from 0 to 1 • F8: Unexpected c4 from 1 to 0 • F9: Unexpected c5 from 0 to 1 • F10: Unexpected c5 from 1 to 0 • F11: Unexpected movement from c4 to c5 • F12: Unexpected movement from c5 to c4 • F13: Cylinder blocked from c4 to c5 • F14: Cylinder blocked from c5 to c4
Three fault partitions can be defined:

• To sensor c4 : Πc4 = {F1, F2, F7, F8} • To sensor c5 : Πc5 = {F3, F4, F9, F10} • To actuator A4 : ΠA4 = {F5, F6, F11, F12, F13, F14}
The assumption that only one fault can occur at the same time in a PE is kept. For each state of PE, an expert must analyse the possibility of fault occurrence and especially the possibility to detect and isolate a fault. It returns a model with faulty states labelled (Fig. 7). « ? » symbol corresponds to a floating time which depends to previous state. The diagnoser is initialized from a normal state according to the input/output vector.

From the analysis, a first conclusion is that one fault can occur from any normal state without being directly detected. Consequently, all normal states (from x 0 to x 5 ) cannot be considered as dependable with certainty and then cannot have only label {N}. These states must have multi labels {N, F1, F2, …}. These labels are not marked to improve legibility. From state x 1 , if ↓c4 does not appear in the defined interval ]0, 1], an event is generated (e PFx1 = 1). The turntable is then considered in an abnormal situation and a fault is detected.

↑A4 ↓c4 ∈]0, 1] ↑c5 ∈]?, 4] ↑c4 ∈]?, 4] ↓c5 ∈]0, 1] ↓A4 F4, F6 F5
From the expert analysis, 2 candidates can be responsible for this fault, F2 or F5. To isolate the fault, diagnoser waits for a new observation or not to help it in its decision. If sensor c5 is activated in an interval ]t min↓c4 + t min↑c5 , t max↓c4 + t max↑c5 ], consequently ]0, 5], then a movement has been realized by the turntable and the faulty event is F2, sensor c4 stuck-on to 1. By contrast, if ↑c5 does not appear after (t max↓c4 + t max↑c5 ), consequently 5 units of time, the turntable is considered as stuck on the position c4 and the label is F5. This deduction can be realized thanks to the single fault assumption. All abnormal states are defined in the same way and finally the turntable diagnoser is composed of 6 normal states and 12 final abnormal states (8 intermediate states). All turntable faults can be detected but it is not possible to isolate with certainty states {F1, F14} and {F3, F13}.

Discussion

A first discussion from the turntable diagnoser can be quickly made. As each label is detected in a bounded delay and with certainty in one state, the turntable is then detectable according to the partition of faults defined. However, the turntable is not diagnosable because all faults cannot be isolated. Consequently, another rule must be present to guarantee diagnosability notion [START_REF] Lin | Diagnosability of Discrete Event Systems and its Applications[END_REF].

Concerning the delay of detection and isolation, it depends on the numbers of states of each local diagnoser. Here, delays are counted in terms of events due to the controller. For the turntable diagnoser, maximum delay to detect and isolate a fault is 3 events. For example, c5 can be stuck-off to 0 from state x 5 , as soon as it was deactivated, and it will be isolated from state x 2 , after events (↑c4, ↑A4, ↓c4).

Thanks to failures simulation mode of ITS PLC, it is interesting to see that if the diagnosis information is returned to the controller, it is possible to establish a fault tolerant controller and avoid mechanical and/or products failures (F2, F4, F7, F9). In contrast, some failures (F11 and F12) are unavoidable.

CONCLUSIONS

The paper presents an approach for diagnosis of discrete manufacturing systems based on the plant decomposition. A decentralized structure is used to diminish combinatory explosion found in centralized structure. From Plant Elements Models, all possible faults are identified to construct abnormal behavior models called diagnosers. The approach is illustrated using a benchmark.

However, only the faults related to components (actuators and sensors) are considered. To take into account the product faults, a product model is necessary. This model depends on the product nature and on the production objective. Thus, a future work is to extend this approach to include the faults related to product.

Another prospect is to use diagnosers with filter approach to be dependable regardless the controller. This filter is a set of constraints which must be verify the safety and liveness properties of the system [START_REF] Marangé | Verification of functional constraints for safe product driven control[END_REF]. Finally, the approach must be implemented into a Programmable Logic Controller for a real, and not simulated, system such as the flexible manufacturing system platform Cellflex of university of Reims (http://meserp.free.fr/) or the CISPI installation of university of Nancy.

  Fig. 4. Construction of a Diagnoser.

Fig. 5 .

 5 Fig. 5. Sorting system. The system is instrumented using 11 sensors to determine the size of the boxes (small or large) and the entry or exit of a box in different conveyors (feeding, intermediate, evacuation) or turntable. The seven outputs of the Programmable Logic Controller (PLC) (IEC 61131-3, 1993) can activate the various conveyors and the turntable. Inputs (Sensors): c0: Feeder belt exit detector, c1: Lower case detector, c2: Higher case detector, c3 Exit detector of the entry conveyor, c4-c5: Detectors of the turntable position, c6: Turntable pallet detector, c7: Entry detector of the left exit conveyor, c9: Exit detector of the left exit conveyor, c8: Entry detector of the right exit conveyor, c10: Exit detector of the right exit conveyor Outputs (Actuators): A0: Feeder belt, A1: Entry conveyor, A2: Turntable rollers (loading), A3: Turntable rollers, A4: Turntable, A5: Left exit conveyor, A6: Right exit conveyor

Fig. 6 .

 6 Fig. 6. Turntable Plant Element Model.

  Fig. 7. Turntable Diagnoser.

ACKNOLEDGEMENT

These works are integrated in incentive action of university of Nancy. Authors wish say thanks all staff of this project.


Falk Howar
email: falk.howar@cs.tu-dortmund.de

Bernhard Steffen
email: steffen@cs.tu-dortmund.de

Maik Merten
email: maik.merten@cs.tu-dortmund.de

Finding Counterexamples Fast Lessons learned in the ZULU challenge

Introduction

The concept of query learning (due to Dana Angluin [START_REF] Angluin | Learning Regular Sets from Queries and Counterexamples[END_REF]) is used and developed in several different communities today. The TU Dortmund team originates in the area of program verification. Active learning in this community is used to produce exact and complete models of a system under test. Having in mind this application of learning, we entered the ZULU challenge with the goal to improve in [START_REF] Angluin | Learning Regular Sets from Queries and Counterexamples[END_REF] saving membership queries and (2) finding counterexamples, while still producing exact models. In both disciplines we proceeded in two steps: first finding good generic solutions and then customizing these to reflect the specific profile of the ZULU problems. Our main contribution is a highly configurable learning algorithm, which can mimic most of the known algorithms, and a new approach to steering the search for counterexamples using a monotone growing hypothesis annotated with coverage information.

A Configurable Inference Framework

The learning algorithm we used can best be described as an implementation of generalized Observation Packs [START_REF] José | Algorithms for Learning Finite Automata from Queries: A Unified View[END_REF]. It combines a discrimination tree [START_REF] Michael | An Introduction to Computational Learning Theory[END_REF] with a reduced observation table [START_REF] Rivest | Inference of finite automata using homing sequences[END_REF]. The realization as a general framework allows us to switch between different strategies for handling counterexamples easily as well as using a non-uniform observation table (i.e., a table with multiple sets of distinguishing suffixes). Additionally, these sets can be initialized arbitrarily (e.g., as {ε} for deterministic finite automata (DFA) or as Σ for Mealy machines).

For ZULU, we configured two versions of our learning algorithm, both using a strategy for analyzing counterexamples that is based on [START_REF] Rivest | Inference of finite automata using homing sequences[END_REF]. The strategy extracts from each counterexample (1) a new distinguishing suffix and (2) the word from the SA-set that will produce an unclosure subsequently. The registered algorithms differed as follows.

Initial set of distinguishing suffixes: In one configuration, the initial set of distinguishing suffixes was initialized as {ε} (as in the literature). In the other configuration, we used {ε}∪Σ in order to simulate the effect of changing from DFA to Mealy models. : We used uniform and non-uniform observation tables. In a non-uniform table, the sets of distinguishing suffixes are managed independently for each component (cf. [START_REF] José | Algorithms for Learning Finite Automata from Queries: A Unified View[END_REF]). This leads to using less membership queries but more equivalence queries than a uniform table does.

Continuous Equivalence Queries

Active learning algorithms proceed in rounds. Each round is opened by an equivalence query. A counterexample returned from such a query will be analyzed and exploited during the rest of the round. This general formulation suggests that equivalence queries in different rounds are independent, i.e., run on unrelated conjectures. But, using a reduced observation table (or more precisely: analyzing counterexamples as in [START_REF] Rivest | Inference of finite automata using homing sequences[END_REF]) will guarantee a monotone growing hypothesis: the S-set of access sequences will only be extended by elements from the SA-set. The prefix-closed set S can be understood as a successively produced spanning tree of the target automaton. This observation has two consequences:

1. finding counterexamples coincides with proving transitions (elements from the set SA) leading to yet undiscovered states, 2. different conjectures can be related using the S-set.

Relating the different conjectures results in using only one evolving hypothesis automaton. In this automaton, only the transitions that correspond to elements from the SA-set can change (and only in a monotone fashion). This allows the formulation of continuous equivalence tests: each transition in the hypothesis can be annotated with a measure, e.g., counting the number of tests that have been executed for this transition; the counter will be reset when the transition changes. This global coverage criterion can be used to steer the search for counterexamples. Fig. 1 shows schematically one round of such a continuous equivalence query: after updating the hypothesis, single transitions are selected and then tested with some future (i.e., suffix word) until either a counterexample is found or a termination criterion is met. For the ZULU challenge, we concretized this general scheme as follows.

Select transition & Book keeping: For the E.H.Blocking algorithm, transitions from the SA-set were chosen randomly. Once used, a transition was excluded from subsequent tests. When no transitions were left to choose from, all transitions were re-enabled. The E.H.Weighted algorithm uses weights on all transitions, which will be increased each time a transition is selected. The probability of choosing a transition is inversely proportional to the weight. Generate future: The suffixes were generated randomly with increasing length.

The length was initialized as some ratio of the number of states in the hypothesis automaton, and was increased after a certain number of unsuccessful tests. The exact adjustment of the suffix length was developed in a trial-anderror way to fit the properties of the problems in the ZULU challenge.

We did not use an explicit termination criterion. A query terminated as soon as the number of queries granted by ZULU was reached.

Results

For the actual competition, we registered six candidate algorithms: three using a non-uniform observation table with a DFA-style initial set of distinguishing suffixes and three using a uniform observation table with a (modified) Mealystyle initial set of distinguishing suffixes. Those two groups correspond to the decisions discussed above. Both groups were equipped with the same three equivalence algorithms: (1) E.H.Blocking, (2) E.H.Weighted, and (3) a plain random walks algorithm as reference. The random walks algorithm tested randomly generated words. Table 1 shows the configuration of the algorithms, their average scores during the training phase and the rankings from the competition phase.

On the training problems, we also ran algorithms for the other two possible configurations of the learning phase. There was, as can partly be seen in Table 1 and Table 2, a significant gap between algorithms using uniform tables and algorithms using non-uniform tables (about 10 to 15 points). For the algorithms using the same kind of table, there were gaps of 2 to 5 points between the versions with different initial sets of distinguishing suffixes; DFA-style initial sets leading to better results.

Compared to the big differences in the scores that were caused by the configuration of the learning phase, the differences between the three equivalence algorithms at first glance seem to be not significant. But, this is due to the ZULU rating mechanism as shown in Table 2 for the training problem 49763507. While the ratings do not differ significantly, the number of states does. The continuous equivalence algorithms produce conjectures with significantly more states using the same amount of queries (over all) as the random walks algorithm does.

Conclusion

We played the ZULU challenge following the same pattern for the learning phase and for the equivalence phase. We first built good general frameworks and then customized these to reflect the special requirements of the ZULU scenario: The problems were best learned as DFA and using a non-uniform observation table.

Both decisions aim at keeping the table as small as possible, i.e., saving membership queries. Counterexamples were found considerably faster (especially for bigger systems) using an evolving hypothesis. This allowed spending more queries on the learning part. Also, due to their structure, the analysis of the counterexamples from the continuous equivalence queries required less membership queries than analyzing randomly generated counterexamples. The configuration we used for the learning phase made us compete at eye level with the other players. Finally, the solution for finding counterexamples fast resulted in the small but deciding advance (89.39 vs. 88.93 in the training phase, but 1st vs. 6th in the competition phase).

Figure 1 .

 1 Figure 1. Continuous Equivalence Query

Table 1 .

 1 Algorithms: Configuration and Ranking

	Algorithm	Dist. Set	Equivalence Query	Training Rank
		Init. Uniform Continuous	Strategy	(Avg.)
	E.H.Blocking			yes	block transitions	89.38	1
	E.H.Weighted {ε}	no	yes	weight transitions	89.26	2
	Random			no	random walks	88.93	6
	run random			no	random walks	80.17	14
	run blocking1 {ε} ∪ Σ yes	yes	block transitions	79.89	15
	run weighted1			yes	weight transitions	79.65	16

Table 2 .

 2 Detailed Training Example: Problem 49763507

	Algorithm	New Membership Queries		Rounds States Score
		Close Obs. Analyze CEs Search CEs
	E.H.Blocking	6,744	358	999	259	352 94.11
	E.H.Weighted	6,717	349	1,035	262	351 94.61
	Random	6,586	519	996	228	332 93.28
	run random	8,080	14	7	5	312 74.89
	run blocking1	8,074	11	16	6	319 73.06
	run weighted1	8,077	9	15	6	319 74.39