E López-Mellado

J-J Lesage

Keywords: Discrete Event Systems, Black-box Identification, Interpreted Petri Nets

This paper deals with the identification of discrete event manufacturing systems that are automated using a programmable logic controller (PLC). The behavior of the closed loop system (PLC and Plant) is observed during its operation and is represented by a single long sequence of observed input/output (I/O) signals vectors. The proposed method follows a black-box and passive identification approach that allows addressing large and complex industrial DES and yields compact and expressive interpreted Petri net (IPN) models. It consists of two complementary stages; the first one obtains, from the I/O sequence, the reactive part of the model composed by observable places and transitions. The I/O sequence is also mapped into a sequence of the created transitions, from which the second stage builds the non observable part of the model including places that ensure the reproduction of the observed input output sequence. This method, based on polynomial-time algorithms on the size of the input data, has been implemented as a software tool that generates and draws the IPN model; it has been tested with input/output sequences obtained from real systems in operation. The tool is described and its application is illustrated through a case study.

Note to practitioners-Automated modeling of controlled discrete manufacturing systems can be achieved by efficient identification algorithms that cope with large and complex plants performing concurrent and repetitive tasks a priori unknown. The black-box identification procedure processes an input/output sequence recorded during the system functioning for a long period of time, and then yields a comprehensive model of the closed-loop controlled system; this model approximates closely the actual behavior of the compound system controllerplant. A tool based on identification algorithms constitutes an excellent resource for computer-aided reverse engineering of controlled manufacturing systems. The method proposed herein allows processing sequences composed by thousands of I/O vectors in few seconds.

I. INTRODUCTION

DENTIFICATION of discrete event systems (DES) allows building systematically a mathematical model (Petri nets, automata) that describes the behavior of an unknown or illknown system based on the observation of its evolution. Observations consist of data revealing the system activity: sequences of operations, events, messages, signals etc., and the models allow reproducing the observed behavior.

A. Related works

DES identification has been first addressed as a problem of grammatical inference [START_REF] Gold | Language Identification in the Limit[END_REF], [START_REF] Angluin | Queries and Concept Learning[END_REF] for obtaining finite automata (FA) that represents a given language. Afterwards, Petri net (PN) models have been proposed for coping with more complex systems exhibiting concurrent behavior; in [START_REF] Hiraishi | Construction of Safe Petri Nets by Presenting Firing Sequences[END_REF] an algorithm for constructing PN models is presented.

Several approaches for identification of DES have been proposed in literature in various formulations and from diverse approaches. Below there is an overview of the main approaches; other works can be found in detailed surveys on identification methods [START_REF] Estrada-Vargas | A Comparative Analysis of Recent Identification Approaches for Discrete-Event Systems[END_REF] and [START_REF] Cabasino | Model identification and synthesis of discrete-event systems[END_REF].

In [START_REF] Cabasino | Identification of Petri Nets from Knowledge of Their Language[END_REF], [START_REF] Cabasino | Linear Programming Techniques for the Identification of Place/Transition Nets[END_REF] methods based on Integer Linear Programming (ILP) are proposed; they allow obtaining accurate Petri nets from a set of transition sequences that can be fired from the initial marking. These methods require the a priori knowledge of the set of transitions and of the number of places, what makes difficult their application to identify real DES as black boxes, since the only available information after observation is the evolution of input and outputs signals exchanged between the control system and the plant.

In [START_REF] Meda-Campaña | Identification of Concurrent Discrete Event Systems Using Petri Nets[END_REF], [START_REF] Meda | Asymptotic Identification for DES[END_REF] it is described an efficient method to incrementally construct an IPN model from a single output vectors sequence. The considered DESs to identify must be event-detectable by the outputs. Applying this method to an I/O sequence would lead to models in which same output changes caused by different input evolutions would not be distinguished, and then incorrect behavior could be introduced.

The method presented in [START_REF] Klein | Fault detection of Discrete Event Systems using an identification approach[END_REF] is dedicated to fault detection and isolation (FDI). It allows obtaining a finite automaton representing precisely a set of cyclic I/O sequences. An extension to distributed identification and distributed FDI has been presented in [START_REF] Roth | Black-box identification of discrete event systems with optimal partitioning of concurrent subsystems[END_REF]. However, due to the usage of finite automata, structural information such as parallelism cannot be explicitly expressed into the models, what makes this approach inefficient for applications such reverse engineering. Other proposals related with FDI in the PN framework are presented in [START_REF] Cabasino | Fault Model Identification and Synthesis in Petri Nets[END_REF] and [START_REF] El Medhi | Petri nets design and identification for the diagnosis of discrete event systems[END_REF].

A Black-box Identification Method for Automated Discrete Event Systems Ana Paula Estrada-Vargas, Ernesto López-Mellado, and Jean-Jacques Lesage, Members, IEEE I In [START_REF] Dotoli | Real time identification of discrete event systems using Petri nets[END_REF], [START_REF] Dotoli | Identification of the unobservable behaviour of industrial automation systems by Petri nets[END_REF] an event sequence is observed, as well as the corresponding output symbols of a DES to produce an IPN model, in which the sequence and the observed output vectors are reproducible. This method requires the definition of an event list, which is not available a priori in the context of black-box identification problem addressed in this work. An alternative to this lack of events list could be the consideration of all the observed input changes. In this case, models with several paths describing input changes would be constructed, in which some input/output relations would not be explicitly observed. This work has been extended in [START_REF] El Mehdi | Design and Identification of Stochastic and Deterministic Stochastic Petri Nets[END_REF] towards the determination of stochastic transitions for FDI purposes.

In [START_REF] Cook | Discovering models of behavior for concurrent workflows[END_REF] a technique for constructing a Petri net-like model that describes the relationship between tasks from a sequence of workflow events is presented. This technique allows the discovering of events belonging to certain threads and synchronization points (forks and joins of tasks) through a probabilistic analysis of metrics such as the entropy, number and regularity of task occurrences. It is assumed that all the workflow operations are observable.

In [START_REF] Van Der Aalst | Workflow Mining: Discovering Process Models from Event Logs[END_REF] the modeling of a workflow is also considered. The input of the algorithm is a workflow log of several workflow instances composed by several tasks. Workflow instances are recorded sequentially, even if tasks may be executed in parallel. Based on the information in the workflow log and by making some assumptions about completeness of the log, a process model in the form of a workflow net is deduced.

B. Black-box approach

Beyond the theoretical interest of defining model synthesis methods from event sequences, the challenges of applying identification methods to actual industrial automated systems are related to the scalability of the algorithms and technological issues: the techniques must be efficient to cope with large and complex systems that handle actual signals.

In our approach we deal with Programmable Logic Controller (PLC) based automated systems. The aim is to discover, from observations of the system behavior expressed as a single sequence of PLC input and output signals how components of the system are interrelated, and to construct a concise model which can explicitly show the discovered behavior, in particular, concurrency, synchronization, resource sharing, etc. Identification of systems in operation involves two important aspects to consider: the system operation and the observation process. Technological issues of both aspects must be considered in the proposed algorithms to construct suitable abstractions.

In previous works [START_REF] Estrada-Vargas | A Stepwise Method for Identification of Controlled Discrete Manufacturing Systems[END_REF], [START_REF] Estrada-Vargas | Input-Output Identification of Controlled Discrete Manufacturing Systems[END_REF] an I/O sequence is considered to compute an IPN including cyclic behavior. Although the proposed methodology is scalable due to the algorithms efficiency, the obtained models are close to finite automata and can be huge, due to the explicit representation of observed input changes that could not be relevant to define the output evolution.

C. Contribution

In this paper we address these problems by analyzing the observed sequence to establish a clearer relation between inputs and outputs of the controller. The proposed method allows building a reduced representation of the observable part of the model which yields consequently, a reduced complete IPN. It consists of two complementary stages; the first one obtains, from the I/O sequence, the reactive part of the model composed by observable places and transitions. A first version of this stage has been presented in [START_REF] Estrada-Vargas | Identification of Industrial Automation Systems: Building Compact and Expressive Petri Net Models from Observable Behavior[END_REF]. The I/O sequence is mapped into a sequence of the created transitions, from which the second stage builds the non-observable part of the model including places that ensure the reproduction of the observed input output sequence. This method, based on polynomial-time algorithms on the size of the input data, has been implemented as a software tool that generates and draws the IPN model [START_REF] Estrada-Vargas | Identification of Partially Observable Discrete Event Manufacturing Systems[END_REF]. None of the black-box identification approaches in related works allows obtaining such well structured models. The present article gathers both stages of the method; it includes a detailed presentation of the revised results, additional illustrative examples, all the proofs omitted in the conference papers, and a case study regarding the identification of a real process.

D. Contents

The paper is organized as follows. In Section II IPN basic notions are overviewed. Section III states the problem of industrial automated systems identification and overviews the two steps method. Such steps are explained in Section IV and Section V. Finally, the implementation details and a case study are presented in Section VI.

II. INTERPRETED PETRI NETS

This section contains the basic concepts and notation of PN and IPN used in this paper.

Definition 1: An ordinary Petri Net structure G is a bipartite digraph represented by the 4-tuple G = (P, T, Pre, Post) where: P = {p1, p2, ..., p|P|} and T = {t1, t2, ..., t|T|} are finite sets of vertices named places and transitions respectively; Pre(Post) : P × T → {0,1} is a function representing the arcs going from places to transitions (from transitions to places).

The incidence matrix of G is W = W + -W -, where W -= [wij -]; wij -= Pre(pi, tj); and W + = [wij + ]; wij + = Post(pi, tj) are the pre-incidence and post-incidence matrices respectively.

A marking function M : P→ Z + represents the number of tokens residing inside each place; it is usually expressed as a |P|-entry vector. Z + is the set of nonnegative integers. In particular, in this paper M : P→ {0,1}; the PN is referred as 1bounded or safe.

Definition 2: A Petri Net system or Petri Net (PN) is the pair N = (G,M0), where G is a PN structure and M0 is an initial marking.

In a PN system, a transition tj is enabled at marking Mk if ∀pi ∈ P, Mk(pi) ≥ Pre(pi, tj); an enabled transition tj can be fired reaching a new marking Mk+1. This behavior is represented as Mk →  j t Mk+1. The new marking can be computed as Mk+1 = Mk + Wuk, where uk(i) = 0, i≠j, uk(j) = 1; this equation is called the PN state equation. The reachability set of a PN is the set of all possible reachable markings from M0 firing only enabled transitions; this set is denoted by R(G,M0). Definition 3. A Petri net circuit is a path of vertices linked by arcs starting and ending in the same node. A circuit is said to be simple if it does not use the same transition more than once, and elementary if it does not use the same place more than once. Now it is defined IPN, an extension to PN that allows associating input and output signals to PN models. This definition is adapted from [START_REF] David | Petri Nets for Modeling of Dynamic Systems-A Survey[END_REF]. every Ci is a Boolean function on Σ; when a Ci is always true it is denoted as "=1", and -E={E1, E2,…} is the set of input events conditions; every Ei is a Boolean function of input events, build on Σ; events are denoted as Ii_0 and Ii_1 for representing that the input value changes from 1 to 0, or from 0 to 1 respectively. A condition Ei may not exist; this is denoted as "ε". In an IPN, a transition tj will be fired if a) tj is enabled, and b) condition C(tj) is true, and c) the event in E(tj) occurs.

Definition 4 : An interpreted Petri net (IPN) (Q, M0) is a labeled net structure Q = (G, Σ, Φ, λ, ϕ)
-ϕ : R(Q,M0)→(Z + ) q is an output function, that associates with each marking in R(G,M0) a q-entry output vector, where q=|Φ| is the number of outputs. ϕ is represented by a q×|P| matrix, such that if the output symbol Oi is present (turned on) every time that M(pj) ≥ 1, thenϕ (i,

j) = 1, otherwise ϕ(i, j) = 0.
The state equation of PN is completed with the marking projection Yk = ϕMk, where Yk ∈ (Z + ) q is the k-th output vector of the IPN.

Definition 5: A place pi∈P is said to be observable if the i-

th column vector of ϕ (denoted as ϕ(•,i)) is not null.
Otherwise it is non-observable. P = P obs ∪ P nobs , and P obs ∩ P nobs =∅; where P obs is the set of observable places and P nobs the set of non-observable places.

III. IDENTIFICATION OF INDUSTRIAL AUTOMATED SYSTEMS

A. The process PLC+Plant

In this work we consider systems composed by a Controller (a PLC) and a Plant denoted as {PLC + Plant} working on a closed loop. The input signals of the PLC (outputs of the Plant) are generated by the sensors of the Plant. The output signals of the PLC (inputs of the Plant) control the actuators of the Plant. The identification is made with respect to the inputs-outputs of the PLC (Fig. 1). A PLC cyclically performs three main steps: i) Input reading, where signals are read from the sensors; ii) Program execution, to determine the new outputs values for the actuators; and iii) Output writing, where the control signals to the actuators are set. At each end of the Program execution phase, the current value of all r inputs and q outputs, called I/O vector, is captured and recorded in a data base.

Regarding the implementation of the data link between PLC and identification data base, we use the UDP (User Datagram Protocol) connection presented in [START_REF] Roth | Identification of Discrete Event Systems, implementation issues and model completeness[END_REF]. Tests performed using a Siemens PLC (CPU 315-2 DP) equipped with a program leading to a PLC-cycle time of 25 to 30ms have shown that this connection is reliable and efficient: no data packets got lost during the transmission and the execution of the PLC program is not delayed by the capture of data.

The only available data for the identification procedure is therefore a single sequence of I/O vectors whose length depends on the observation duration:

,... ) ( ) ( ,..., ) 3 ( ) 3 ( , ) 2 ( ) 2 ( , ) 1 ( ) 1 (                         = k O k I O I O I O I w

B. Event types

In order to analyze signals evolution, we compute event vectors, i.e., the difference between two consecutive I/O vectors. Each event vector can be decomposed into input and output event vectors:

      -       + + =       = ) ( ) ( ) 1 ( ) 1 ( ) ( ) ( ) ( k O k I k O k I k OE k IE k E , where             = ) ( ) ( ) ( ) ( 2 1 k IE k IE k IE k IE r  and               = ) ( ) ( ) ( ) ( 1 1 k OE k OE k OE k OE q  (2)
Regarding input and output event vectors and the PLC cycle described in the previous subsection, there only exist four All of these situations should be taken into account to represent the system dynamics. Our aim in this work is to express the system's behavior extractible from the I/O vector sequence as an IPN.

C. Input-Output identification approach C.1 Overview of the method

The purpose in this research is not only to compute an IPN model in which the observed sequence is reproducible, but also to achieve expressivity and compactness in the identified model allowing representing causal relationship and concurrency of the involved operations.

The method processes off-line the I/O-sequence w captured during the process operation and delivers an IPN model that reproduces the observed behavior (w).

The method is outlined here with the help of a simple example. It regards a controller handling 3 inputs (s, x, y) and 3 outputs (A, B, C), from which the following I/O sequence is obtained: The method consists of two main steps which are outlined below.

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    =
Step1. Discovering the reactive input/output behavior. In this step is determined the observable part of the IPN consisting of subnets, named fragments, composed by observable places labeled with output symbols, and transitions labeled with algebraic expressions of input symbols (Fig. 2).

From the sequence w, a corresponding sequence of transitions S=t1 t2 t3 t4 t1 t2 t5 t6 t1 t2 t3 t4 t1 t2 t5 is obtained. Step2. Determining the non-observable part of the IPN and the initial marking M0. The sequence S is processed for obtaining causal and concurrency relationships useful for determining the non-observable places that relate the fragments such that S (thus w) can be executed from M0 (Fig. 3).

C.2 Dealing with event types

Since situations Type 1 and Type 2 (cf. section III.B) are directly observable by an output change, they can be straightforwardly modeled in an IPN. Such a modeling is performed by the first step of our method. The Type 1 situation represents a direct input/output reactive behavior, and thus the modeling is quite easy: the input change is associated with the label of a transition and the output change is represented as arcs relating such a transition with the observable places representing outputs involved. In the Type 2 situation the input values which lead to the output evolution are not observed at the same PLC cycle (i.e. at the same event vector). In order to represent such a behavior, the context (the values of the inputs) in which the output changes occur is analyzed; in this case, the output change is modeled such as in the Type 1 situation, but the label of the corresponding transition contains only a condition on inputs levels (the input change is ε).

The Type 3 situation is divided in two, depending on whether or not there is an internal state evolution of the controller. Situation Type 3.a is the case of the input events which provoke internal state evolutions and eventually lead to an output event of Type 2. Such internal evolutions cannot be directly computed, but can be inferred. By looking in the sequence built in Step 1, the order in which transitions appear can be determined. Such internal state inference will be performed by the second step of our method and will be modeled by the addition of non observable places assuring the order of the transition firings, such as in Fig. 3.

In the situation Type 3.b there is no internal state evolution, and thus there is nothing to be inferred, as well as the situation Type 4, where there are neither input nor output events occurring in a PLC cycle. Consequently, the sequence stored in the database will be built by adding a new I/O vector only when it is different to the last one. Notice that in this work we can only infer internal state evolutions by means of transition firing order. Other type of internal evolutions, such as timers or counters, is out of the scope of this work. We can now make the description of the two identification steps.

IV. IDENTIFICATION OF THE OBSERVABLE BEHAVIOR

In this section the first step of the method is presented. The introduced concepts and algorithms are illustrated through a simple case study inspired from a manufacturing example.

A. Overview and case study description

Algorithm 1 summarizes the steps of the procedure to identify the {PLC + Plant} observable behavior; the steps will be described in detail in the next sub-sections. The purpose of this system (Fig. 4) is to sort parcels according to their size. It has 9 signal sensors from the system: a0, a1, a2, b0, b1, c0, c1, k1, k2, and 4 signals to the actuators: A+, A-, B, C. This example has been used in other publications [START_REF] Estrada-Vargas | A Stepwise Method for Identification of Controlled Discrete Manufacturing Systems[END_REF], [START_REF] Estrada-Vargas | Input-Output Identification of Controlled Discrete Manufacturing Systems[END_REF] and we describe it to confront this work against previous results.

Algorithm 1.Computing the observable IPN components

B. Events vector sequence

In Fig. 5 the beginning of an I/O vector sequence is shown for illustrative purposes; however, recall that treated sequences are usually very much longer (thousands of vectors). We have included in the sequence the result of first sub-step of the algorithm, i.e., the computed event vectors (below the arrows) between each two consecutive I/O vectors.

                                                                                -    →                                                                                  -    →                                                                                  -   →                                                                                  -    →                                                                                 -   →                                                                                  -    →                                                                                    →                                     

C. Elementary events

In order to analyze the system behavior in a deeper way, event vectors can be decomposed into a set of elementary events (simply called events):

0 ) ( ) 1 ( s.t. } ,..., , { ) ( 1 2 1 ≠ - + = = = = k I k I IE IE IE IE k IE i i r i i ki kr k k  (3) 0 ) ( ) 1 ( s.t. } ,..., , { ) ( 1 2 1 ≠ - + = = = = k O k O OE OE OE OE k OE i i q i i ki kq k k  (4)
If no elementary input (output) event occurs in E(k), we denote it as IE(j)={ε} (OE(j)={ε}). The rising edge event of input Ii (output Oi) is denoted as Ii_1 (Oi_1). The falling edge event of input Ii (output Oi) is denoted as Ii_0 (Oi_0). Table 1 shows the elementary events computed for the example sequence.

D. Direct and Indirect Causality Matrices

As stated in Section III, the influence of some input signals over the outputs setting is observed at the same PLC cycle. In order to discover such an input/output direct relationship, we analyze the relative frequency of the occurrence of both input events IEi and output events OEk, with respect to the occurrence of OEk along the whole sequence of events. This relationship can be naturally expressed as the conditional probability of the occurrence of an output event OEk, given 5) E( 6) E( 7)

IE(1) = {k1_1} OE(1) = {A+_1} E(2) IE(2) = {a0_0} OE(2) = {ε } E(3) IE(3) = {k1_0} OE(3) = {ε} E(4) IE(4) = {a1_1} OE(4) = {A+_0, A-_1, B_1} E(
IE(5) = {b0_0} IE(6) = {a1_0} IE(7) = {b1_1} IE(6) = a1_0 OE(5) = {ε } OE(6) = {ε } OE(7) = {B_0 }
that a certain input event IEi has occurred at the same PLC cycle:

) ( ) , ( ) | ( k Obs i k Obs i k OE N IE OE N IE OE Prob = (5)
where NObs(.) denotes the number of observed occurrences. Using all values Prob(OEk|IEi), a matrix can be filled. We call such a matrix the Direct Causality Matrix (DM), in which every DMik = Prob(OEk|IEi). Fig. 6 presents the computed DM matrix for the Example 1, considering a sequence much longer than the presented one. Similarly, conditional probability has been used in [START_REF] Cook | Discovering models of behavior for concurrent workflows[END_REF] for determining the relationship between workflow operations.

With the DM matrix, we can find Evolution Type 1 simply by looking at each column the values that add up to 1, since this represents the total number of occurrences of event OEk. For example, from Fig. 6 we can discover that the output event A+_0 is always provoked by event a1_1 (in 44.4% of the observed cases) or by event a2_1 (in 55.6% of the observed cases). The general case where several input events can provoke an output event is formalized on the next section.

Similarly, to discover input/output non direct relationship, we look at the input values when a certain output event occurs. We compute the occurrence probability of an output event OEk, given that certain input has a given value ILi at the same PLC cycle:

) ( ) , ( ) | ( k Obs i k Obs i k OE N IL OE N IL OE Prob = (6)
We construct the Indirect Context Matrix (IM) in which every IMik = Prob(OEk|ILi). The IM matrix for Example 1 is shown in Fig. 7.

Using the IM matrix we can discover evolution Type 2 by inspecting in every column the values that add up to 1 which are not zero in the DM matrix. In the Example 1, k1=1 and k2=1 are input values which can provoke A+_1 output event, even if they were not always observed at the same PLC cycle. Now we will present how these relations can be automatically discovered from the DM and IM matrices.

E. Computing Firing Functions of Output Events

It can be noticed that the occurrence of every output event OEk is caused by one or several input events occurring at the same PLC cycle and by a condition on the input values. In order to represent such conditions, a firing function χ(OEk) has to be defined for every OEk. It is called the Output Event Firing Function (OEFF):

) ( ) ( ) ( k k k OE F OE G OE • = χ
where G(OEk) is a function of input events and F(OEk) is a function of inputs levels which allow the triggering of the output event OEk.

We compute G(OEk) as a conjunction of disjunctions of input events Ej:

j k DisjE OE G Π = ) ( ( 8
)
where Similarly, F(OEk) is computed as a conjunction of disjunctions of input levels Lj:

j k DisjL OE F Π = ) ( (11)
with DisjLj = (ILx ⊕…⊕ILz) such that 0 ,...

0 , 0 ≠ ≠ ≠ yj yj xj IM IM IM (12) 1 ... = + + + zj yj xj IM IM IM (13) 0 ,... 0 , 0 ≠ ≠ ≠ yj yj xj DM DM DM ( 14
)
At the end of the computing, for every output signal Oi, we will have the input events and input conditions to produce its rising and falling edges Oi_1 and Oi_0 respectively. This can be easily translated into IPN fragments, as shown in Fig. 8.

F. Input events with differed influence on the outputs

Notice that condition DMxj ≠ 0, DMyj ≠ 0,…, DMzj ≠ 0 requires that the inputs related to the output change were observed at least once changing its value at the same PLC cycle that the considered output. This condition may be restrictive if the input-output reaction is not observed in the same event vector. For example, in order to avoid component damages, in the absence of an input sensor to indicate that a pusher has been retracted, there may be some security temporizations which do not allow another actuator reacting at the moment an input condition has been satisfied.

In such cases, the input-output reaction would not be found and thus there may be an output event with empty conditions on its firing function. In order to find the correct OEFF, we can relax the condition to consider input events which have been observed in previous event vectors instead of the same event vector. Formally, we can compute:

) ( ) , ( ) | ( vector) previous ( k Obs i k Obs i k OE N IE OE N IE OE Prob = (15)
But this time, the computation is done by considering IEi occurred at the previous event vector than OEk. A new OEFF can be computed using new values instead of those of the DM matrix. If the computed OEFF has still empty conditions, we can take the previous to the previous event vector and successively while empty conditions are computed. In the Example 1, such relaxing condition is not necessary, since, as it can be noticed, no empty conditions have been computed. However, in the experimental case study of Section VI.B, such a technique is applied.

For the Example 1, D = ∅; the computed PN fragments are shown in Fig. 9.

G. Fusion of IPN fragments

As stated below, at each PLC cycle, several input and state conditions could lead to the simultaneous occurrence of several output events. This behavior is reproduced by merging such conditions into a unique transition, which is labeled by a firing function computed from individual firing functions of each output event. This is captured in the model as a fusion of IPN fragments as shown in Fig. 10.

The construction of the observable IPN can be systematically done with the next procedure: 10. IPN representation of several output events at the same cycle Complexity of Algorithm 2. Let r'<r and q'<q be respectively the maximum number of input and output elementary events appearing simultaneously in an event vector, and |E| be the length of the events sequence. The Algorithm 2 processes each one of the events in E. When a transition should be added to represent one of such events, an appropriate firing function should be computed. If only inputs changed, it is only necessary to include in the firing function the elementary input events with differed influence. This is achieved in O(r'). If there is at least an output change, for each one of the output elementary events which have occurred, we need search for each individual firing function the input events and input conditions that produced the evolution. This is performed in O(q'(r'log r')). Thus, the complexity of the procedure for building the transition sequence and fragments is O((q'r' log r')|E|). Consequently, the Algorithm 2 can be executed in polynomial time on the size of the input data.

ε • ∧ ∧ ∧ ⊕ ) 0 0 0 ) 2 1 (( c b a k k + A ) 1 _ 2 1 _ 1 ( 1 a a ⊕ • = C 1 _ 2 1 a • = 1 _ 1 1 c • = - A ) 1 _ 2 1 _ 1 ( 1 a a ⊕ • = 1 _ 0 1 a • = B 1 _ 1 1 a • = 1 _ 1 1 b • = Fig. 9. IPN fragments for Example 1       + +   →        ) 1 ( ) 1 ( ) ( ) ( ) ( j O j I j E j O j I )) ( ( )) ( ( ) ( j OE G j OE F T j • = λ j T jp OE jq OE jr OE jr jq jp OE OE OE j OE • • = ) ( Fig.
F(OE j )• G(OE j ) O i OE j = O i _1 O i OE j = O i _0 F(OE j )• G(OE j ) Fig. 8.
Property 1. The transitions sequence S is a translation of the I/O sequence w into transition firings of the PN-fragments built by Algorithm 2.

Proof. It is easy to see that at the steps 3.1.2 and 3.2.4 of Algorithm 2, S is formed by concatenating the computed transitions from the event sequence produced by w. This allows that the reactive behavior can be reproduced in the created IPN model. ▄ Fig. 11 shows how events E(1) and E(4) are treated by the algorithm. For E(1) the elementary output event A+_1 in OE( 1) is analyzed and function λ(t1) = (k1

• a0 • b0 • c0) • (ε)
is extracted considering that k1=1, a0=1, b0=1, and c0=1 are the input values which have satisfied χ(A+_1). For E(4) all elementary output events A+_0, A-_1 and B_1 in OE( 4) are considered and their Firing Functions χ(A+_0) = (=1)•(a1_1⊕ a2_1), χ(A-_1)=(=1)•(a1_1 ⊕ a2_1) and χ(B_1)=(=1)•(a1_1) are combined into λ(t2) = (=1)•(a1_1).

Notice that interesting labeling functions have been computed. For example, the output event A+_1 is provoked by the presence of a piece (k1=1 or k2=1) and it occurs only when the three components corresponding to outputs A+, B, and C are on its initial position (a0=1, b0=1 and c0=1).

At the end of the procedure, the following observable incidence matrix ϕW and labeling functions are obtained, as well as the transition sequence S, which is the projection of w over T: S = t1 t2 t3 t4 t1 t2 t4 t3 t5 t6 t7 t4 t1 t2 t3 t4 t5 t6 t7 t4 t1 t2 t3 t4 t1 t2 t3 t4 t5 t6 t7 t4 t5 t6 t7 t4 t1 t2 t3 t4 t5 t6 t7 t4 t5 t6 t7 t4 t5 t6 t7 t4 t5 t6 t7 t4 t5 t6 t7 t4 t1 t2 t4 t3 t1 t2 t3 t4 t1 t2 t3 t4 t1 t2 t4 t3 t1 t2 t3 t4 t1.

            - - - - - - + 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 1 7 6 5 4 3 2 1 C B A A t t t t t t t ) 1 _ 1 ( ) 1 ( ) ( ) 1 _ 2 ( ) 1 ( ) ( ) ( ) 0 0 0 2 ( ) ( ) 1 _ 0 ( ) 1 ( ) ( ) 1 _ 1 ( ) 1 ( ) ( ) 1 _ 1 ( ) 1 ( ) ( ) ( ) 0 0 0 1 ( ) ( 7 6 5 4 3 2 1 c t a t c b a k t a t b t a t c b a k t • = = • = = • ∧ ∧ ∧ = • = = • = = • = = • ∧ ∧ ∧ = λ λ ε λ λ λ λ ε λ
The corresponding partial model is shown in Fig. 12. The inferring procedure which allows discovering the nonobservable behavior is described in next section.

V. IDENTIFICATION OF THE NON-OBSERVABLE BEHAVIOR

A. Problem (re)statement

The previously described procedures allow obtaining an observable structure which represents the reactive behavior of the system. Given that events and transitions of the net are completely defined, we need to add non-observable places to translate an aggregation of the non-observable dynamics of the process in such a way that the global PN will reproduce the whole behavior of the system. By adding non-observable places (depicted as grey circles), we make the inference of situation Type 3.a described in Section III.B, which is the case of input events provoking internal state evolutions. The problem of determining the non-observable part of the IPN model complementary to that describing the observable (reactive) behavior can be stated as follows.

+ A ) 1 _ 2 1 _ 1 ( 1 a a ⊕ • = - A ) 1 _ 2 1 _ 1 ( 1 a a ⊕ • = B 1 _ 1 1 a • = - A B + A (=1) • (a1_1) ε • ∧ ∧ ∧ ⊕ ) 0 0 0 ) 2 1 (( c b a k k + A + A (k1 • a0 • b0 • c0) • (ε) t 2 λ(t 2 ) = (=1)•(a1_1) λ(t 1 ) = (k1 • a0 • b0 • c0) • (ε) IE(1) = {k1_1} OE(1) = {A+_1} I(2) = k1 • a0 • b0 •c0 IE(4) = {a1_1} OE(4) = {A+_0, A-_1, B_1} I(5) = a1 • b0 •c0
Given an observable IPN model whose structure is G obs =(P obs , T, Pre obs , Post obs ) and a transitions sequence S = t1 t2 … tj … ∈ T* reproducing the I/O sequence w, an ordinary PN structure G nobs =(P nobs , T, Pre nobs , Post nobs ) that reproduces S and an initial marking M0 enabling S must be found; (G obs , M0) must be safe.

Thus, the PN structure of the complete identified model is G=(P, T, Pre, Post) with P= P obs ∪ P nobs , Pre= Pre obs ∪ Pre nobs , Post= Post obs ∪ Post nobs .

Observe that in S there are not consecutive apparitions of the same transition, due to the nature of the considered events (rising and falling edges of binary signals).

In the literature there are many approaches which tackle the identification problem as stated above. However, our problem exceeds the hypothesis held in such works or they are not enough efficient to cope with long sequences. In particular, a) the system cycles are not know a priori, b) the whole language of the system is not known, c) the size of S is very large; thus finding efficient algorithms is required, d) the aim is building IPNs that shows structural parallelism.

New places and arcs must be determined such that they join the IPN fragments found in the first part of the method. Since the tasks in different processes can occur simultaneously or at some predefined order, each two fragments can be related in two manners only: sequentially or concurrently. Thus, several connecting forms are possible. Some of them are illustrated in Fig. 13, where "clouds" represent the fragments.

In this section, we present a procedure to build a nonobservable PN structure that is able to reproduce the sequence S of transitions firings. This construction principle is based on the precedence and concurrency relations among transitions, which will determine the final structure of the identified model. Algorithm 3 given below provides an overview of the procedure. The steps of Algorithm 3 are detailed in the following subsections. First some properties derived from the sequence S are introduced. Afterwards, based on such properties, an analysis technique allowing determining causal and concurrency relationships among the transitions in S is proposed. Then, the steps for building a PN structure observing the causal and concurrency relationships are presented.

B. Dynamical properties

Since the construction method is based on the analysis of causal and concurrency relationships, some notions must be defined before introducing the non-observable behavior construction procedure. Definition 6. The relationship between transitions in S that are observed consecutively is expressed in a relation Seq ⊆ T × T which is defined as Seq ={(tj, tj+1)| 1 ≤ j < |S| }. If (ta, tb) ∈ Seq, this is denoted by ta<tb.

Example 2. Let us reuse the sequence S of example 1, which is the projection of the observed I/O sequence w over the set of observable transitions T: S = t1 t2 t3 t4 t1 t2 t4 t3 t5 t6 t7 t4 t1 t2 t3 t4 t5 t6 t7 t4 t1 t2 t3 t4 t1 t2 t3 t4 t5 t6 t7 t4 t5 t6 t7 t4 t1 t2 t3 t4 t5 t6 t7 t4 t5 t6 t7 t4 t5 t6 t7 t4 t5 t6 t7 t4 t5 t6 t7 t4 t1 t2 t4 t3 t1 t2 t3 t4 t1 t2 t3 t4 t1 t2 t4 t3 t1 t2 t3 t4 t1

We can compute Seq = {(t1, t2), (t2, t3), (t3, t4), (t4, t1), (t2, t4), (t4, t3), (t3, t5), (t5, t6), (t6, t7), (t7, t4), (t4, t5), (t3, t1)}, which can be expressed also as {t1<t2, t2<t3, t3<t4, t4<t1, t2<t4, t4<t3, t3<t5, t5<t6, t6<t7, t7<t4, t4<t5, t3<t1}.

In a PN model every pair in Seq may in fact be represented differently. If ta, tb were observed consecutively in S, this behavior could be issued from one of two situations in G nobs described in the following definition.

Definition 7. Every couple of consecutive transitions ta, tb in Seq can be classified in one of the following situations:

Causal relationship. If the occurrence of ta enables tb. In a PN structure, this implies that there must be at least one place from ta to tb (Fig. 14a).

Concurrent relationship. If both ta and tb are simultaneously enabled, but ta occurs first and its firing does not disable tb. In an ordinary PN structure, this implies that it is impossible the existence of a place from ta to tb. In this case, ta and tb are said to be concurrent, denoted as ta||tb. (Fig. 14b). In order to find which is the situation occurring between every pair of transitions in Seq, some other definitions are now introduced. The following notion is the systematical precedence of a transition tj with respect to another transition tk; it establishes a necessary condition for tj to occur repeatedly. Definition 8. A transition tj is preceded systematically by tk, denoted as tk∠tj iff tk is always observed between two apparitions of tj in S. By convention, we say that tj∠tj if tj was observed at least twice in S. Then the Systematical Precedence Set of a transition tj is given by the function SP: T→2 T , that indicates which transitions must be fired to re-enable the firing of tj, i.e. SP(tj)={tk |tk∠tj}. If tj was observed only once in S, then SP(tj) = ∅.

In the sequence S from Example 2, one may compute that t1∠t1, t2∠t1, t3∠t1, and t4∠t1, thus SP(t1)={t1, t2, t3, t4}. Notice that SP(tj) is the set of transitions that must invariantly occur to fire tj repeatedly. The rest of the SP sets are : SP(t2)={t1, t2, t3, t4}, SP(t3)={t1, t2, t3}, SP(t4)={t4}, SP(t5)={t4, t5, t6, t7}, SP(t6)={t4, t5, t6, t7}, SP(t7)={t4, t5, t6, t7}. From the sequence S in Example 2, we observe that the set of transitions in a two-cycle is TC= ∅.

Remark. Computing Seq, SP and TC can be executed in polynomial time on the size of S.

We will now extract some structural properties regarding N from S. The previously defined terms will be used to determine which situation between causality and concurrence is the most appropriated for every pair of consecutively observed transitions in S.

C. Causal and concurrency relationships 1) Causal relationship

In order to determine that two transitions are causally related as shown in Figure 14.a, several conditions stated below must be fulfilled.

Proposition 1. If ta∠tb (ta∈SP(tb)) then, there must exist in N a simple elementary circuit (SE circuit) to which both ta and tb belong.

Proof. Suppose that there is not a SE circuit containing ta and tb. Thus, right after the firing of tb, all the tokens in tb • (the output places of tb) could be displaced by transition firings through some path to • tb (the input places of tb), enabling tb without needing to fire ta, which implies that ta∉SP(tb).▄ Proposition 2. If ta < tb and ta∠tb, then there must exist in N a place from ta to tb.

Proof. Suppose that there is not a place from ta to tb. In order to allow the observation ta < tb, both ta and tb should be enabled simultaneously. By Proposition 1, there is at least one SE circuit containing ta and tb and thus, at least one path from ta to tb. Thus, if ta and tb are enabled simultaneously and ta is fired, all paths from ta to tb contain two tokens. If all transitions in a path from ta to tb are fired, then there will be two tokens in one of the input places of tb, resulting in a non-safe net. Then, at least one of the transitions ti in each path from ta to tb must be conditioned to the previous firing of tb. But if tb is fired, all the transitions in paths from ta to tb can be fired and all the transitions in paths from tb to tb which do not include ta can be fired; thus tb will be enabled before ta fires and as a consequence ta∉SP(tb). ▄ Proposition 3. If ta < tb and tb∠ta, then there must exist in N a place from ta to tb.

Proof. Suppose that there is not a place from ta to tb. Then, before the observation of ta < tb, both ta and tb must be enabled, and thus the occurrence of tb<ta is possible. Furthermore, together with tb∠ta and by Proposition 2 implies that there should be a place from tb to ta. However, at the firing of tb there are two tokens in such a place, and thus the net is not safe.▄ Proposition 4. If (ta,tb) ∈TC, then there must exist in N a place from ta to tb and a place from tb to ta.

Proof. The sequence tatbta must be reproducible in N. Right after the firing of ta there is a token on its output places, and thus tb must be at the output of such places; otherwise, there would be two tokens in such places after the second firing of ta. Similarly, right after the first firing of ta, there are no tokens on its input places, and thus tb must be at the input of such places; otherwise, ta could not be fired again. The same reasoning can be applied to reproduce the sequence tbtatb.▄ Notice that when two transitions are observed consecutively and one is systematically preceded by the other, a causal relationship is found. Also, when two transitions are involved in a two-cycle relation, they are in a causal relationship each other. Observe that all of these relationships are structural, and thus they do not depend of the initial marking of the net. From the Seq set in Example 2 (see Definition 6), the SP sets (see Definition 8) and the TC set (see Definition 9) we compute CausalR={(t1,t2), (t2,t3), (t4,t1), (t2,t4), (t5,t6), (t6,t7), (t7,t4), (t4,t5), (t3,t1)}.

If a couple of transitions (ta,tb) in the Seq set, belongs also to CausalR, then there must be a place from ta to tb in order to constrain the observed firing order. For the rest of the transition couples in Seq, we must decide if a place should exist to relate them. Next, we will discuss some cases where the existence of a place can be discarded.

2) Concurrency relationship

If two transitions ta and tb are concurrent, there must not exist a place neither from ta to tb nor from tb to ta; otherwise, the firing of one would constrain the firing of the other one.

Definition 11. The set of all pairs of concurrent transitions is called ConcR={(ta,tb)| ta||tb}.

If the sequence w is complete, (consequently, S) i.e., if it exhibits all of the possible behavior of the observed system, we can find concurrence between transitions that are not in a causal relation, as shown in the next proposition.

Proposition 5. Let ta, tb be two transitions which have been observed consecutively in a complete sequence S in both orders, i.e. (ta, tb)∈Seq, (tb, ta)∈Seq. Then (ta, tb)∉CausalR and (tb, ta)∉CausalR if and only if ta||tb.

Proof. Suppose that (ta,tb)∉ConcR. Without loss of generality, we suppose there is a place pab from ta to tb. Since (tb, ta)∈Seq, there must also be a place pba from tb to ta; otherwise, ta could be enabled simultaneously with tb to allow tb<ta and ta may be fired, yielding to the presence of two tokens in the place pab and breaking the safeness condition. Since (ta,tb)∉CausalR, tb∉SP(ta) and thus there must be at least one path from pab to pba which does not contain tb. Similarly, there must be at least one path from pba to pab which does not contain ta. Since (ta,tb)∉TC, tatbta should not be enabled and thus, there must be at least one SE circuit to which ta belongs, but tb does not belong. The resulting net violates the freechoice conditions (observe Fig. 15). Suppose now that (ta,tb)∈ConcR. That means that they can be both enabled simultaneously and one can be fired without needing the firing of the other one, and thus ta∉SP(tb) and tb∉SP(ta). Also, since there cannot be any place from ta to tb nor from tb to ta, neither the subsequence tatbta, nor the subsequence tbtatb can be enabled, and thus (ta,tb)∉CausalR and (tb, ta)∉CausalR. ▄ Notice that our methodology allows computing also non free-choice nets. Only in the case where the system includes a behavior like the one shown in Fig. 15, the transitions ta and tb would be wrongly considered as concurrent and the existence of links from ta to pab and from tb to pba would be missed.

However, the obtained model would be still capable to reproduce the sequence S.

It is well known that in practice, the sequence w is not complete, since in the general case, the observed systems do not show all their possible behavior during a finite time of data collection. In fact, it is not possible to assure that the whole behavior of a system has been observed. The consideration of Proposition 5 is then very restrictive, since it demands the observation of all possible behavior; it could lead to the construction of incorrect models in case of incomplete sequences. Then, some less constraining rules to find concurrence must be considered. Next, we present several properties which allow us to identify couples of transitions which must be concurrent in the identified net N.

First, we will introduce the notion of Sequential Independence, which is a characteristic of concurrent transitions. Later, the propositions to find concurrency will be introduced.

Definition 12. Two transitions ta and tb are Sequentially Independent if ta∉SP(tb) and tb∉SP(ta).

From the SP sets of Example 2 (see Definition 8) we compute the set of Sequentially Independent transitions: {(t1,t5), (t1,t6), (t1,t7), (t2,t5), (t2,t6), (t2,t7), (t3,t4), (t3,t5), (t3,t6)}.

Observe the net in Fig. 16 which is composed by two independent t-components X1 and X2 with supports <X1>= {ta, ti} and <X2>= {tb, tk} respectively. In a sequence belonging to the language of such a net, transitions belonging to different tcomponents are sequentially independent. In fact, SP sets of this net correspond exactly to t-components of the net. Proposition 6. Let ta and tb be two transitions in S which have been observed consecutively in both orders (ta<tb and tb<ta). If: a) (ta,tb) ∉ CausalR and (tb,ta) ∉ CausalR, b) and |SP(ta)| >1 and |SP(tb)| >1, then ta||tb. Proof. Suppose that ta and tb are not concurrent. Without loss of generality, we suppose there is a place pab from ta to tb. Since tb<ta has been observed, there must be also a place pba from tb to ta (and as consequence N contains a two-transition cycle); otherwise, ta could be enabled simultaneously with tb to allow tb<ta and ta may be fired, yielding to the presence of two tokens in the place pab and breaking the safeness condition. Since tb∉SP(ta), there must be at least one path leading from pab to pba not including tb. Since |SP(ta)| >1, there must be at least one circuit including ta and not including pab, pba nor tb. Since ta∉SP(tb), there must be at least one path leading from When SP(tj) is a singleton, it means that it belongs to several elementary circuits and then Proposition 6 does not allow to find concurrent transitions to tj. But if tj is included in the SP of other transitions, we may find some concurrence relations, as shown in the next proposition. Proposition 7. Let ta and tb be two transitions in S that have been observed consecutively in both orders (ta < tb and tb < ta).

If ta and tb a) are Sequentially Independent and b) there exists a transition tk such that ta∠tk (ta∈SP(tk)) and tb∠tk (tb∈SP(tk)) then ta||tb. Proof. Suppose that it does not hold that ta||tb. Without loss of generality, we suppose that there is a place from ta to tb. Since ta ∈SP(tk) and tb ∈SP(tk), after the firing of tk, both ta and tb must be fired before the next firing of tk. Since tb < ta may happen, the place from ta to tb must be marked. However ta < tb may occur too, leading to the presence of two tokens in the same place after the firing of ta, and making the net not safe.▄ Fig. 17 shows an example of the case characterized by Proposition 7. It is the general case of transitions belonging to concurrent threads (ta, tc and tb, td, te, tf respectively), which are eventually synchronized by one transition (tk). If we make several firings to build a transition sequence, eventually the SP sets would become: SP(tk) = {tk, ta, tc, tb, td, tf}, SP(ta) = SP(tc) = {tk, ta, tc}, SP(tb) = SP(tf) = {tk, tb, td, tf}, SP(te) = {te, td}, SP(td) = {td}. Even if SP(td) is a singleton, the synchronization point tk help us to find by Proposition 7 several concurrent relationships: ta||tb, ta||td, ta||tf, tc||tb, tc||td, and tc||tf.

In If concurrent transitions do not belong to synchronized threads, conditions of the next propositions help us to find a subset of concurrent transitions which do not depend from another transition tk. Proposition 8. Let be two transitions ta and tb which have been observed consecutively in both orders (ta < tb and tb < ta). If ta and tb are: a) Sequentially Independent, and b) ∃ tk such that tk∈SP(tb), tk∉SP(ta), and c) (ta,tk)∈Seq then ta||tb. Proof. Suppose there is a place pab from ta to tb. Since tb<ta has also been observed, there must be also a place pba from tb to ta; otherwise, ta should be enabled simultaneously with tb to allow tb<ta and ta may be fired, yielding to the presence of two tokens in pab. Since there exists tk such that tk∈SP(tb), then there must be a SE circuit containing both tb and tk. If such a circuit contains places pba or pba, it is not possible to fire ta<tk and thus such a circuit must contain another input place pkb of tb and another output place pbk of tb. Now, to accomplish that tb∉SP(ta), there must be at least one path leading from pab to some input place of ta not including tb. Consider the first transition tx of this path. In order to respect the free-choice conditions, pkb should be an input place of tx, making the occurrence of ta<tk impossible. ▄ Definition 13. The Inverse Systematical Precedence set of a transition SP -1 : T→ 2 T contains the transitions which are dependent of a common transition to re-enable their firing:

)} ( | { ) ( 1 k j j k k j t PS t and t t t t PS ∈ ≠ = - (13)
Proposition 9. Let ta and tb be two transitions which have been observed consecutively in both orders (ta < tb and tb < ta). If ta and tb are: Sequentially Independent, and SP -1 (ta) ≠ ∅, ∀tj∈SP -1 (ta), tj || tb, then ta||tb.

Proof. Suppose there is a place pab from ta to tb. Since tb<ta has also been observed, there must be also a place pba from tb to ta; otherwise, ta should be enabled simultaneously with tb to allow tb<ta and thus ta may be fired, yielding to the presence of two tokens in the place from ta to tb. Since tb∉SP(ta), there must be at least one path leading from pab to pba not including tb. Similarly, there must be at least one path leading from pba to pab not including ta. Since SP -1 (ta) ≠ ∅, there is at least one transition tj concurrent to tb such that tj∠ta and there must be a SE circuit including ta and tj. Such a circuit cannot contain pab nor pba otherwise tj may be able to fire without need of firing ta. Consider the input place px of ta in this path. The freechoice conditions are not satisfied between px and pba: they share ta as output transition, but pba has at least another output transition. ▄ An example where Proposition 9 can be used is shown in Fig. 18. SP -1 (ta) ={tj1, tj2} and tj1||tb, tj2||tb are determined by Proposition 6. Consequently, ta || tb.

Remark. Computing CasualR and ConcR can be executed in polynomial time on the size of S.

D. Building the non-observable PN

We will use now the computed data from sequence S to infer internal evolutions of the system. We will make an analysis of causal and concurrency relations that have been found between consecutive transitions in order to compute non-observable places of the net. Definition 14. The set Seq'= (Seq -CausalR) -ConcR contains the set of transition pairs (ta,tb) which have been observed consecutively, but are not in a causal relation or in a concurrency relation.

Until now, we have computed for Example 2 that Seq = {(t1, t2), (t2, t3), (t3, t4), (t4, t1), (t2, t4), (t4, t3), (t3, t5), (t5, t6), (t6, t7), (t7, t4), (t4, t5), (t3, t1)}, CausalR={(t1, t2), (t2, t3), (t4, t1), (t4, t5), (t5, t6), (t6, t7), (t7, t4), (t2, t4), (t3, t1)} and ConcR = {(t3,t4)(t4,t3)}. Thus, Seq' = {(t3, t5)}. This means that there is a relationship which has not been explained.

If Seq' ≠ ∅, then there are two possibilities for the remaining transition pairs (ta,tb) in Seq': b) They are both input and output transitions of a place with several input and output transitions c) They are concurrent, but w (thus, S) is not complete enough to find such a relationship Since our goal is to approximate as much as possible the language generated by identified IPN, to the observed sequence S, we assume that if we have observed two transitions consecutively (ta<tb) but by none of the previous propositions we have determined that they are concurrent, thus the firing of ta has enabled tb. This is made in order to preserve in the PN the firing order observed in S. Then, a place will be added from ta to tb; this denoted by [ta, tb].

When it is found that [ta, tc] and [tb, tc], and the involved transitions are related by a single place, this is represented as [tatb, tc]. In general, a place p can be denoted as [ta1 ta2… tal, tb1 tb2… tbh], where tai are the input transitions of p and tbi are the output transitions of p, and l=| • p|, h=|p • |, as illustrated in Fig. 19.

The same place could be used to relate several consecutive transitions. If a transition tk has been observed followed by two transitions tai, taj in S (tk<tai and tk<taj), there are two cases to represent such observations into the PN model: the case of selection, where they are represented with the same place [tk, tai taj] (Fig. 20a) or the case of concurrence, where they are represented with different places [tk,tai] [tk, taj] (Fig. 20b).

In a generalized form, for every set tk<ta1,…, tk<taw of nonconcurrent consecutive transition pairs with the same first transition tk, we can thus merge all tk<ta1,…, tk<tax whose second transitions ta1…taw are non-concurrent nor consecutive and represent them into a single place [tk, ta1…taw], as illustrated in Fig. 21.

Once we have made the first merging, all places [tk1, ta1…taw], [tk2, ta1…taw],…, [tkz, ta1…taw] whose input transitions are non-concurrent nor consecutive and whose output transitions are the same, can be merged into a single place as illustrated in Fig. 22.

Remark. Building the non-observable PN can be executed in polynomial time on the size of Seq.

E. Initial marking

Once the structure of the net is built, the initial marking can be computed by allowing the firing of S. All transitions are processed, from the last transition till the first one. The processing of a transition is as follows:

• If its output places are unmarked, the tokens in such places are retired, • Tokens are added to its unmarked input places.

F. Token flow verification

As stated before, with the proposed mechanisms in last the sequence w may not have shown enough combinations which allow us to determine concurrence. If the sequence w were complete, all the concurrent and sequential behavior could be found and represented, according to Proposition 6. However, since we know that w could not be complete, in order to approximate the language of the identified IPN to S as much as we can, we have considered that if two transitions have not been declared as concurrent, they must be in a sequential relationship. But if the transitions are actually concurrent, the sequential consideration could lead us to links or places in the built model which restrict too much the behavior of the system and don't allow the firing of S. Now, we present some notions that will help us to verify if added places until now do not interfere in the correct reproduction of S.

Proposition 10. If the IPN model has been correctly build, every computed non-observable place p in N must fulfill the place input/output flow equation: [START_REF] El Mehdi | Design and Identification of Stochastic and Deterministic Stochastic Petri Nets[END_REF] where Occ(tk) is the number of occurrences of tk in S.

1 ) ( ) ( ± = ∑ ∑ • ∈ • ∈ p t i p t i i i t Occ t Occ
Proof. Equation follows straightforward from the IPN transition enabling and firing conditions and from the fact that (G nobs , M0) must be safe. ▄ Proposition 11. If there exists a place p such that | • p|=1, then ∀tj ∈ p • , tk ∈ SP(tj), SP(tj)≠∅ where tk is the input transition of p. Also, if there exists a place p such that |p • |=1, then ∀tj ∈ • p, tk ∈ SP(tj), SP(tj)≠∅ where tk is the output transition of p.

Proof. If | • p|=1, for the re-enabling of tj, p must be marked and the only way to do so is the firing of tk, and thus tk ∈ SP(tj). Similarly, if |p • |=1, for the re-enabling of tj, p must be unmarked and the only way to do so is the firing of tk, thus tk ∈ SP(tj).▄ Correction rule. If the input/output flow equation or the conditions in Proposition 11 are not satisfied by some place, the arcs relating transitions which are not in CausalR are removed. If there are not CausalR represented in such a place, it is deleted.

Example 2 (Cont.). In the model of Figure 23, we verify the input/output flow equation for each place. From Example 2, we can compute Occ(t1)=12, Occ(t2)=11, Occ(t3)=11, Occ(t4)=20, Occ(t5)=9, Occ(t6)=9, and Occ(t7)=9. We check also the condition of Proposition 11. p1: Occ(t1) = Occ(t2) (±1), t1∈SP(t2), t2∈SP(t1) p2: Occ(t2) = Occ(t3) (±1), t2∈SP(t3), t3∈SP(t2) p3: Occ(t3) ≠ Occ(t1) + Occ(t5) (±1), t3∈SP(t1), t3∈SP(t5) p4: Occ(t4) = Occ(t1) + Occ(t5) (±1), t4∈SP(t1), t4∈SP(t5) p5: Occ(t5) = Occ(t6) (±1), t5∈SP(t6), t6∈SP(t5) p6: Occ(t6) = Occ(t7) (±1), t6∈SP(t7), t7∈SP(t6) p7: Occ(t2) + Occ(t7) = Occ(t4) (±1), t4∈SP(t2), t4∈SP(t7) As can be observed, p3 is a wrong place, since Occ(t3)≠ Occ(t1)+ Occ(t5)±1. Since (t3, t5)∈Seq'; this means that the sequence is not complete, and thus the causal relationship we assumed between t3 and t5 is wrong. In order to fix this, we can delete the arc going from place p3 to transition t5. After this correction, all of the conditions from Proposition 10 and Proposition 11 are satisfied.

Finally, the identified IPN of the sorting system described in Example 1 is obtained by merging the observable model in Fig. 12 and the non-observable model from Fig. 23 after applying the places correction. We can also delete nonobservable implicit places. Then the IPN shown in Fig. 24, which reproduces w, is the final result of the model merging.

In the supplementary file [26] several additional examples regarding the method for identifying a non observable model from a sequence S are included. Proof. Regard that we have computed the following sets:

• Seq containing all the consecutive transition couples in S.

If we represent into a net all couples in Seq, the net will be able to reproduce S, • CausalR containing transition couples (ta, tb)∈Seq that must be related by a place,

• ConcR containing transition couples (ta, tb)∈Seq, that must not be related by any place. If the set Seq'= (Seq -CausalR) -ConcR = ∅, it means that all transition couples (ta,tb)∈Seq are correctly represented in N and thus the sequence S is reproducible. If Seq'≠∅, it means that there are still transition couples that cannot be distinguished as concurrent or sequential. Thus, by merging several couples in Seq, all couples in Seq' are considered as sequential by creating places with several input and output transitions. If they are actually sequential, all the verification rules are satisfied. Otherwise, they are actually concurrent and they are corrected using the described procedure. Once they are corrected, it only remains places relating sequential transitions and thus the sequence S is reproducible.▄

G.2 Performance

Given that all of the procedures of Algorithm 3 are executed in polynomial time on |S|, the construction of (G nobs , M0) is efficiently performed.

Note also that the application of Algorithm 3 to a sequence S yields always the same PN model, due to that all the constructive steps in the procedures are deterministically performed, i.e. there are not random selections on the input and intermediate data.

VI. METHOD IMPLEMENTATION AND APPLICATION

Based on the presented algorithms, a software tool has been developed to automate the IPN model synthesis. The architecture of the tool is shown in Fig. 25.

The user interface allows capturing the input/output sequence and shows the obtained model graphically. Following input data is provided to the tool: the name of a text file containing the I/O sequence (with one line per I/O vector), the names of the input and output signals, and the desired name for the output file. Additionally it is specified the order in which inputs and outputs appear in the txt file (since depending on data collection procedure, order could change) and the index numbers of the signals to take into account if a mask is going to be applied (some inputs or outputs could be ignored like indicator lights or push-buttons).

Later, an input reader component processes the input file and transforms the input/output sequence into a vector sequence. These vectors are delivered to a component called Algorithm in which the identification procedure is implemented. The output of this component is an XML file that can be opened with the Platform Independent Petri net Editor (PIPE [START_REF]Platform Independent Petri net Editor 2[END_REF]), which is an editor for visualization and analysis of Petri nets.

The presented identification tool has been tested on several examples of diverse size and complexity. A small size case study regarding an actual manufacturing system is described in the supplementary files to this article [26] in which the use of such a software tool is illustrated.

VII. CONCLUSION

The proposed identification method discovers the actual input-output relation of PLC controlled discrete event systems. The technique allows building a concise IPN model in which the transitions are labeled with sufficient conditions on the inputs which represent both the input changed and the inputs execution context. The obtained structure is remarkably more clear and expressive than that synthesized with a previous method.

The technique copes with complex automated DES because it takes into account technological characteristics of actual controlled systems, and because it is based on efficient algorithms. This feature is not still addressed in current literature on the matter, in which several features considered in the current stated problem have not been dealt.

The algorithms issued from the present method have been implemented as a software tool and tested on experimental case studies which are very close to actual industrial discrete event processes. The performed tests reveal the efficiency of the methods when data including thousands of input-output vectors are processed in few seconds.

Due to this is a black-box approach, the obtained models represent the observed behavior; consequently, when the observation has been made for a long time, the identified IPN approximates closely the actual behavior. Afterwards this model can be completed using available knowledge on the process.

( 1 )

 1 I(k) and O(k) are vectors whose entries are respectively the values of the r inputs I1, I2,… Ir and q outputs O1, O2,… Oq at the k-th PLC cycle. Furthermore we denote Ii(k) and Oi(k) the values of input Ii and output Oi respectively at the k-th cycle.

Fig. 1 .

 1 Fig. 1. {PLC + Plant} compound and identification procedure.

Fig 3 .

 3 Fig 3. Second step: assembled IPN fragments

1 )

 1 Input: I/O sequence w Output: Observable incidence matrix φW and labeling transition function λ Analyze sequence w in order to • Compute events vector sequence • Compute elementary events • Compute Direct and Indirect Causality Matrices • Construct Output Event Firing Functions • Find Input events with differed influence 2) Use computed data in the previous step to • Compute transitions of the IPN and their labeling λ • Compute observable incidence matrix φW Example 1.

Fig. 4 .

 4 Fig. 4. Layout of the system case study.

Fig. 5 .

 5 Fig. 5. Beginning of I/O vector sequence.

Fig. 6 .

 6 Fig. 6. Direct Causality Matrix for the Example 1

Fig. 7 .

 7 Fig. 7. Indirect Context Matrix of the Example 1.

  each disjunction DisjEj = (IEx ⊕…⊕IEz) involves those variables corresponding to non-zero column values of the DM matrix, which add up to 1, i.e. those satisfying conditions: 0

Algorithm 2 . 1 . 3 . 1 . 1 .

 21311 Input: I/O sequence w, I/O events sequence E, Matrices DM and IM, Differed input set D Output: Observable incidence matrix φC, labeling transition function λ, and sequence of transitions S 1. P← {p1, p2,…, pq} //Create q observable places, one for every output of the system 2. S←ε //Initialize the sequence S 3. ∀E( j), j=1,…,|E| do //Consider all the computed I/O events in E 3.If OE(j) = 0 and ∃ IEs,…,IEu ∈ IE(j) ∩ D //There is not an output change in E(j), but IE(j) contains elementary input events IEs,…,IEu belonging to D then T← T∪{tj}; λ(tj) ← IEs•…•IEu; W(tj,pi) ← 0, ∀pi∈P //If it has not been created before, create a new zero transition tj (a zero column in the incidence matrix) representing input changes IEs,…,IEu 3.1.2. S← S⋅tj //Concatenate tj to S 3.2. else if OE(j) ≠ 0 //There is an output change in E(j) then 3.2.1. ∀OEjk ∈ OE(j) //Consider all the elementary output events in OE( j) in order to compute G(OE(j)) and F(OE(j)) 3.2.1.1. ∀DisjEi ∈ G(OEjk), do DisjEi' ← DisjEi ∩ IEjk // Look into IE(j) the input event IEjk which has satisfied DisjEi and assign it to DisjEi' 3.2.1.2. G'(OEjk) ← ΠDisjEi' //Combine into G'(OEjk) all the conditions DisjEi' which have satisfied G(OEjk) 3.2.1.3. G(OE(j)) ← ΠG'(OEjk) //Combine into G(OE(j)) all the input event conditions G'(OEjk) which have satisfied all the events OEjk 3.2.1.4. ∀DisjLi ∈ F(OEjk), do DisjLi' ← DisjLi ∩ I(j+1) // Looking the I(j+1) vector as a set of Boolean variables, save into DisjLi' the input value ILik which has satisfied DisjLi 3.2.1.5. F'(OEjk) ← ΠDisjLi' //Combine into F'(OEjk) all the conditions which have made true F(OEjk) 3.2.1.6. F(OE(j)) ← ΠF'(OEjk) //Combine into F(OE(j)) all the conditions which have produced all the OEjk

Fig. 11 .

 11 Fig. 11. Treatment of E(1) and E(4) by the Algorithm 2.

Algorithm 3 . 2 .

 32 Non-observable behavior construction Input: Transitions sequence S Output: Non-observable model representing S 1. Compute basic structures and relations (Seq, SP, and TC) from S From the information in Seq, SP and TC compute the causal relation between transitions CausalR 3. From Seq and CausalR, compute concurrency relation (ConcR) between transitions 4. Build a PN model representing CausalR and ConcR 5. Verify the tokens flow and correct part of the structure if needed

Fig. 13 .

 13 Fig. 13. Some different possibilities for fragments assembling

Fig. 14 .Definition 9 .

 149 Fig. 14. Structures that represent ta< tb. a) shows a causal relationship from ta to tb, whereas b) shows a concurrent relationship between ta and tb.

Definition 10 .

 10 The causal relationship set CausalR keeps track of all the causal relationships in S. CausalR = {(ta,tb) | (ta<tb) and (ta∠tb or tb∠ta or (ta,tb)∈TC)}.

Fig. 23 .

 23 Fig. 23. (G nobs , M0) the non-observable IPN of Example 1

Fig. 24 .

 24 Fig. 24. Final IPN model for the process in Example 1 G. Features of the method G.1 Reproducibility of S Proposition 12. The PN model (G nobs , M0) built with the previous procedures summarized in Algorithm 3 reproduces the sequence S.Proof. Regard that we have computed the following sets:• Seq containing all the consecutive transition couples in S.If we represent into a net all couples in Seq, the net will be able to reproduce S, • CausalR containing transition couples (ta, tb)∈Seq that must be related by a place,

  Rising and falling edges of output Oi 3.2.2. T← T ∪ {tj}, λ(tj) = F(OE(j))• G(OE(j)) //If it has not been created before, create a new transition tj and label it with the computed F(OE(j)) and G(OE(j))

	3.2.3. ∀pi∈P, do
	If Oq_1 ∈OE(j) then W(tj,pq) ←1,
	else If Oq_0∈OE(j) then W(tj,pq) ← -1,
	else W(tj,pjq) ← 0 //for all elementary output
	events in OE(j) = OEjp• OEjq•…• OEjr, put a 1 into the line
	corresponding to OEjk if it is a rising event, and a -1 if it is a
	falling event; for the rest of the lines, assign a 0.
	3.2.4. S← S⋅ tj //Concatenate tj to S

  Fig.[START_REF] Dotoli | Identification of the unobservable behaviour of industrial automation systems by Petri nets[END_REF]. Structure where (ta, tb)∈Seq and (tb, ta)∈Seq but (ta,tb)∉ConcR pba to pab not including ta. Consider the first transition tx of this path. The free-choice conditions are not satisfied, since tx and ta share pba as input place, but ta has at least one different input place. ▄ We may observe that for Example 2, (t3, t4) are sequentially independent (seeDefinition 12), however, |SP(t4)| =1 and thus we cannot infer any concurrence.

			p ab
						t a	t i	t b	t k
	. . .	t a	. .	t b	. . .	Fig. 16. A net with two t-components
			.
			p ba

  Example 2, (t3,t4) are Sequentially Independent (see Definition 12), and we have determined that t3∠t1 and t4∠t1 (see Definition 8), thus we can conclude that t3||t4.

	t k	t a	t c
		t d	t f
		t b	t e
	Fig. 17. Concurrent threads synchronized by a transition

Example 2 (Cont.).

  By considering the couples of consecutive non-concurrent transitions in Seq'(which in this example is only (t3, t5) -see Definition 14), the places: [t1, t2] Selection and parallelism representation. a)Shows the case where tai, taj are not concurrent and have not been observed consecutively whereas b) shows the case where tai, taj are concurrent or have been observed consecutively.

	[t2, t3] [t3, t1t5] [t4, t1t5] [t5, t6] [t6, t7] and [t2t7, t4] are computed.
	The PN structure and the computed initial marking is shown in
	Fig. 23.
	p 3	p 4
	1 t 1 t p 1	5 t 5 t p 5			t k		t k
	2 t 2 t	6 t 6 t
	p 2	p 7	p 6	t ai	t aj	t ai	t aj
	3 t 3 t	4 t 4 t	7 t 7 t		a)		b)
	t a1 t k1 Fig. 20. t b1 t b2 … t a1 t al t a2 … t bh	t k t b2 … Fig. 21. A PN place p = [ta1 ta2…tal, tb1 tb2… tbh] t aw t a2 … t b1 t bx t c1 … t a1 t aw t a2 … t kz t k2 … t k1 t k2 … t c2 … Fig. 22. Selection and concurrence between pre-transitions	t cy t kz
	Fig. 19. A PN place p = [ta1 ta2…tal, tb1 tb2… tbh]

by CONACYT (Mexico) under Grant No. 50312, and by Région Île-de-France.

User interface