Proceedings of the 2009 IEEE International Conference on Systems, Man, and Cybernetics San Antonio, TX, USA - October 2009 Off-line Identification of Concurrent Discrete Event Systems Exhibiting Cyclic Behaviour Ana P. Estrada-Vargas, Jean-Jacques Lesage Member IEEE E. López-Mellado Member IEEE LURPA Ecole Normale Supérieure de Cachan CINVESTAV Unidad Guadalajara 61, av du Président Wilson Av. Científica 1145, Col. El Bajío 94235 Cachan Cedex, France 45015 Zapopan, Mexico
[email protected]{aestrada, elopez}@gdl.cinvestav.mx Abstract— This paper presents a method for the algorithms have been proposed allowing the on-line identification of concurrent Discrete Event Systems (DES) from identification of concurrent DES. Although the techniques are input-output sequences representing the observed behavior. The efficient, the obtained models may represent more sequences proposed off-line technique yields an input-output model than those observed. expressed as an Interpreted Petri net (IPN), which represents exactly the language than that generated by the observed system, Other technique oriented to fault diagnosis is presented in which may include cyclic sequences. First, a sample of input- [10]; it obtains non deterministic FA representing the same output vectors words are processed for obtaining sequences of observed behavior, which is represented as a set of output changes called events; then sequences of ț-length event input/output sequences. The algorithms operate off-line traces are built and represented by an IPN model composed by efficiently. non measurable places. Then measurable places are added; they are related to transitions representing pertinent output changes. The off-line techniques based on integer linear Finally inputs are associated to transitions and implicit non programming (ILP) approach lead to free-labeled PN models measurable places are removed. representing exactly the observed behavior [4]. However both the ILP problem statement from samples and their processing Keywords—Discrete event systems, Automated model have exponential complexity. This approach is being applied identification, Interpreted Petri nets to other PN classes in [2] [3]. I. INTRODUCTION In this paper a method for the identification of Petri net models from observed input-output sequences representing Automated building of discrete event models from external behavior of concurrent DES is presented. It gathers and observation of system behavior has been addressed as a extends some strategies form [13] and [10] and focuses on off- problem of system identification. The problem has interesting line case. Because of the inherent capacity of Interpreted Petri applications such as reverse engineering for (partially) Nets (IPN) models to represent inputs and outputs of DES unknown systems, fault diagnosis or system verification. systems, internal states, non-controllable transitions and Previous results on the matter have been proposed as a parallelism, the proposed method yields an IPN model which solution to the problem of grammatical inference. In [5] a represents exactly the same language of length N+1 than that finite automaton (FA) is built from positive samples of generated by the system without taking into account accepted words. Later several methods for obtaining Mealy [8] information a-priori about the system other than its input and [16] and Moore [1] [17] machines have been proposed. Also output signals. In the first stage, a sample of output vectors building of context free grammars has been studied [11], [15], words are processed for obtaining sequences of output changes [7]. called events; then sequences of ț-length event traces are considered allowing building an underlying IPN of non The identification of Petri net (PN) models has been measurable places. The IPN orders the events by relating the proposed for coping with more complex systems exhibiting measurable places according to pertinent output changes. concurrent behavior. In [6] an algorithm for constructing Petri Finally, the inputs are added and the model is simplified by net models is presented. First, the language of the target eliminating implicit non-measurable places. system is identified in the form of deterministic FA (DFA). Then, the algorithm obtains from the DFA the structure of a The remainder of this paper is organized as follows. PN that accepts the obtained language. Section 2 overviews basic definitions on PN and IPN. Section 3 presents the proposed identification technique. Finally Three different approaches have been adopted in recent concluding remarks are given. publications addressing the problem of identification of DES. The incremental synthesis approach proposed by Meda et al., II. PETRI NET MODELS deals with unknown partially measurable DES exhibiting This section presents the basic concepts and notation of PN cyclic behavior; in [12] an identification method based on the and IPN used in this paper. least square estimator is presented. Then in [13][14] several 181 978-1-4244-2794-9/09/$25.00 ©2009 IEEE Definition 1: An ordinary Petri Net structure G is a behaviour is represented as M k ot M k 1 ; Mk+1 can be j bipartite digraph represented by the 4-tuple G=(P,T,I,O) computed using the state equation: where: Mk+1 = Mk + Cvk x P = {p1,p2,...,pn} and T ={t1,t2,...,tm} are finite sets of yk = M Mk vertices named places and transitions respectively, where C and vk are defined as in PN and yk (Z +)q is the k-th x I (O) : P × T o {0, 1}is a function representing the arcs output vector (or marking projection) of the IPN. going from places to transitions (transitions to places). Pictorially, places are represented by circles, transitions are According to functions O and M, transitions and places of represented by rectangles, and arcs are depicted as arrows. The an IPN (Q,M0) can be classified as follows. symbol xtj (tjx) denotes the set of all places pi such that I(pi,tj)0 Definition 4: If O(ti)H the transition ti is said to be (O(pi,tj)0). Such places are called input (output) places of tj. controllable. Otherwise it is uncontrollable. A place piP is Analogously, xpi (pix) denotes the set of all transitions tj such said to be measurable if the i-th column vector of M is not null, that O(pi,tj)0 (I(pi,tj)0). Such transitions are called input i.e. M(x,i)0. Otherwise it is non-measurable. P = Pm Pu (output) transitions of pi. where Pm is the set of measurable places and Pu is the set of The incidence matrix of G is ܥൌ ܥା െ ି ܥ, where non-measurable places. ି ି ି ା ା ܥൌ ൣܿ ൧; ܿ ൌ ܫሺ ǡ ݐ ሻ; and ܥା ൌ ൣܿ ൧Ǣ ܿ ൌ ܱሺ ǡ ݐ ሻ are Definition 5: A firing transition sequence of an IPN (Q, ௧ the pre-incidence and post-incidence matrices respectively. M0) is a sequence ߪ = titj...tk such that ܯ ՜ ܯାଵ ௧ೕ ௧ೖ A marking function M: PoZ represents the number of ՜ ǥ ܯାȁఙȁିଵ ՜ ܯାȁఙȁ , where ȁߪȁ is the length of the tokens (depicted as dots) residing inside each place. The sequence ߪ . The set of all firing sequences is called the marking of a PN with n places is usually expressed as an n- language of (Q, M0) and it is denoted as ͉ሺܳǡ ܯ ሻ ൌ ሼߪȁߪ ൌ ௧ ௧ೕ ௧ೖ entry vector. Z + is the set of nonnegative integers. ݐ ݐ ǥ ݐ ܽ݊݀ܯ ՜ ܯାଵ ՜ ǥ ܯାȁఙȁିଵ ՜ ܯାȁఙȁ ሽ. Definition 2: A Petri Net system or Petri Net (PN) is the Definition 6: The input language of an IPN (Q, M0) is pair N = (G,M0), where G is a PN structure and M0 is an initial defined as: ͉ሺǡ Ͳሻ ൌ ሼ OሺሻOሺͳሻǤǤǤ OሺȁVȁǦͳሻOሺȁVȁሻȁ ௧ ௧ೕ ௧ೖ marking. ՜ͳ՜ǤǤǤ ȁVȁǦͳ՜ȁVȁǡ ǤǤǤ ͉ሺǡͲሻሽǤ The output In a PN system, a transition tj is enabled at marking Mk if language of an IPN (Q, M0) is defined as: ͉ሺǡ Ͳሻൌሼ Mሺሻ ௧ ௧ೕ ௧ೖ pi P, Mk(pi) I(pi,tj); an enabled transition tj can be fired MሺͳሻǤǤǤ MሺȁVȁǦͳሻMሺȁVȁሻȁ ՜ͳ ՜ǤǤǤ ȁVȁǦͳ ՜ȁVȁǡ reaching a new marking Mk+1 which can be computed as ǤǤǤ͉ሺǡͲሻሽǤ Mk+1 = Mk + Cvk, where vk(i)=0, ij, vk(j)=1, this equation is called the PN state equation. The reachability set of a PN is the Definition 7: The output language of length l of an set of all possible reachable marking from M0 firing only IPN (Q, M0) is defined as: enabled transitions; this set is denoted by R(G,M0). This work ͉௨௧ ሺܳǡ ܯ ሻ ൌ ሼݓȁ͉ א ݓ௨௧ ሺܳǡ ܯ ሻܽ݊݀ȁݓȁ ݈ሽ. uses IPN, an extension to PN that allows associating input and output signals to PN models. III. IDENTIFICATION METHOD Definition 3: An IPN (Q, M0) is a net structure A. Problem statement Q = (G,6,),O,M) with an initial marking M0. An identification procedure of a DES builds a mathematical model that represents its behaviour from the x G is a PN structure measured evolution of the DES’ inputs and outputs x 6 = {D1, D2, ..., Dr} is the alphabet of input symbols Di. [12][10][3]. Below the addressed identification problem is x ) = {I1, I2,..., Iq} is the alphabet of output symbols Ii. stated. x O : To 6{H} is a labelling function of transitions with the following constraint: tj,tk T, jk, if pi I(pi,tj) = I(pi,tk) Consider a DES S with binary outputs revealing part of its 0 and both O(tj) H, O (tk) H, then O(tj) O(tk); H internal states in which the outputs may evolve concurrently. represents a system internal event externally uncontrollable The input data to the identification procedure is a set of output x M : R(Q,M0)o( Z +)q is an output function, that associates words Ȟሺሻ describing behaviour and the sequences of input symbols in 6 that yield the output sequences. to each marking in R(Q,M0) a q-entry output vector; q is the number of outputs. M is represented by a q×n matrix, in Definition 8: The set of observed output words of a DES S which if the output symbol Ii is present (turned on) every is Ȟሺሻ ൌ ሼݓଵ ǡ ݓଶ ǡ ǥ ሽ such that ݓ ൌ ሺݓ ሺͳሻǡ ݓ ሺʹሻǡ ǥ time that M(pj)1, then M (i,j)=1, otherwise M(i,j)=0. ݓ ሺȁݓ ȁሻሻ, where ݓ ሺ݆ሻ is the j-th observed vector in sequence ݓ and ȁݓ ȁ is the length of the output word ݓ . If a transition tj T of an IPN is enabled at marking Mk, there are two possibilities: a) If O(tj) = Di H is provided to the Definition 9: The observed output language of a DES S is system then tj can be fired. b) If O(tj) = H and tj is enabled then defined as ࣦሺሻ ൌ ሼݓ ሺ݆ ͳሻݓ ሺ݆ ʹሻ ǥ ݓ ሺ݆ ݈ሻȁݓ א tj must be fired. When an enabled transition tj is fired in a Ȟሺሻ݆ ݈ ȁݓ ȁሽ. marking Mk, then a new marking Mk+1 is reached. This 182 భ మ య ఱ ర ల Definition 10: The output language of length l of a DES S Ͳ ՜ ͳ ՜ Ͳ ՜ Ͳ ՜ Ͳ ՜ Ͳ ՜ Ͳ is defined as ࣦ ሺܵሻ ൌ ሼݓȁࣦ א ݓሺܵሻȁݓȁ ݈ሽ. ېͲۍ ͳ ېͲۍെͳ ېͲۍ Ͳ ېͲۍ Ͳ ېͲۍ Ͳ ېͳۍ Ͳ ېͲۍ ۑ ێې ۍۑ ێې ۍۑ ێې ۍۑ ێې ۍۑ ێې ۍۑ ێې ۍۑ ێ ݓଶ ൌ ێ ۑͲێ ۑͳێ ۑͲێ ۑ Ͳ ێ ۑͲێ ۑͲێ ۑͲێെͳۑͲێ ۑ Ͳ ێ ۑͳێ ۑ Ͳ ێ ۑͲێ ۑ Given a set of output words Ȟሺܵሻ, the input signals 6 of a ێ ۑͲێ ۑ ͳ ێ ۑͳێ ۑ Ͳ ێ ۑͳێ ۑͲێ ۑͲێ ۑ Ͳ ێ ۑͲێ ۑͲێ ۑͲێെͳۑͲێ ۑ DES S, and an accuracy parameter ߢ , the aim of the ێ ےͳۏ ۑ Ͳ ێ ےͲۏ ۑͳێ ےͲۏ ۑ Ͳ ێ ےͲۏ ۑͲێ ےͲۏെͳےͲۏ ۑ Ͳ ێ ےͳۏ ۑ ےͲۏ ےͲۏ ےͲ ۏ ےͳۏ ےͲۏ ۏെͳے identification process is to obtain a safe IPN model (Q, M0) such that ͉௨௧ ሺܳǡ ܯ ሻ ൌ ࣦ ሺܵሻ. The parameter ߢ is used to ߬ଶ ൌ ݁ଵ ݁ଶ ݁ଷ ݁ହ ݁ସ ݁ adjust the accuracy of the identified model, similarly as Additionally consider that the input signals measured at the proposed in [9]. It is assumed that for every output vector output changes are: a, H, b, c, d, e, for e1, e2, e3, e4, e5, e6, change an input signal Di 6 is recorded; otherwise H is taken. respectively. B. General approach 2) Sequences of ț-length event traces The method for identification consists of several stages that build systematically a safe IPN which represents exactly the In order to introduce the accuracy parameter ߢ for sampled output language of length ț +1 of the DES. identification, from every sequence of events ߬ ൌ ߬ ሺͳሻ߬ ሺʹሻ ǥ ߬ ሺȁ߬ ȁሻ we compute sequences of event traces From the output vector words, the event sequences are ߬ ൌ ߬ ሺͳሻǡ ߬ ሺʹሻǡ ǥ ߬ ሺȁ߬ ȁሻ such that every ߬ ሺ݆ሻ is a computed and then sequences of event substrings of length ț substring of length ߢ of߬ that finishes with߬ ሺ݆ሻ. For the first are built. Then every substring is associated to a transition of a ߢ െ ͳ elements of the trace sequence the event ߝ is used. PN, which describes the causal relationship between event substrings through paths including non-measurable places. Following with the previous example, the sequences of Finally, the output changes provoked by events are described traces using ߢ ൌ ʹ are: by marking changes in measurable places and then related to ߬ଵଶ ൌ ߝ݁ଵ ǡ ݁ଵ ݁ଶ ǡ ݁ଶ ݁ଷ ǡ ݁ଷ ݁ସ ǡ ݁ସ ݁ହ ǡ ݁ହ ݁ for ߬ଵ pertinent transitions in the PN. Notice that the number of non- ߬ଶଶ ൌ ߝ݁ଵ ǡ ݁ଵ ݁ଶ ǡ ݁ଶ ݁ଷ ǡ ݁ଷ ݁ହ ǡ ݁ହ ݁ସ ǡ ݁ସ ݁ for ߬ଶ observable places is not predefined. D. Building the basic structure C. Sample processing 1) Representing event traces 1) Event sequences Once the sequences of event traces have been obtained, As stated before, the data obtained from the system to be every trace ߬ ሺ݆ሻis related to a transition in the IPN through a identified is a set of sequences of output vectors ݓଵ ǡ ݓଶ ǡ ǥ, function J:Toሼ߬ ሺ݆ሻሽ; the firing of a transition implies that ߢ such that ݓ ൌ ሺݓ ሺͳሻǡ ݓ ሺʹሻǡ ǥ ሻ, where ݓ ሺ݆ሻ refers to the j- consecutive events related to such a transition have been th observed vector in sequence ݓ . Sequences may have observed. In order to preserve firing order between transitions, different length. From these sequences, strings of observed dependencies are created between them and associated with an events are first computed. observed marking through the function ߤǣ ܲ௨ ՜ ሼMܯ ȁܯ א ܴሺܰǡ ܯ ሻሽ, which relates every non-measurable place with an Definition 11. An observed event ߬ ሺ݆ሻ is the variation observed marking, such that every transition has only one between two consecutive output vectors ݓ ሺ݆ሻ, ݓ ሺ݆ ͳሻ; it is input place and one output place ( ݐ ܶ אǡ xݐ ൌ ݐx ൌ ͳ ); computed as ߬ ሺ݆ሻ ൌ ݓ ሺ݆ ͳሻ െ ݓ ሺ݆ሻ. when an event trace ߬ ሺ݆ሻis found again in a ߬ the associated dependency must be used if it leads to the same observed Then for every sequence ݓ , a sequence of observed marking. Let ej be the last event in the trace ߬ ሺ݆ሻ ; the events ߬ ൌ ߬ ሺͳሻ߬ ሺʹሻ ǥ ߬ ሺȁ߬ ȁሻ is obtained. During the process, if the difference has not been observed before, a new associated transition will be denoted as ݐ ೕ (more than one transition may have associated the same ej). This strategy can event ݁݇ is created (߬ ሺ݇ሻ ൌ ݁ ሻ . be systematically performed following the next procedure. The following example illustrates that the method copes also with DES exhibiting cyclic behaviour. It has five output Algorithm 1. Building the basic IPN structure signals, ) = {A, B, C, D, E}, and five input signals 6 = {a, b, c, d, e}. Two output sequences have been observed: Input: The set Ȟ ൌ ሼ߬ ሽ Output: An IPN model G composed by non-measurable ܣ Ͳ ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ ͳ Ͳ Ͳ Ͳ Ͳ Ͳ places ې ܤۍ ېͲۍ ېͲۍ ېͳۍ ېͳۍ ېͲۍ ېͲۍ ېͲۍ ېͲۍ ېͲۍ ېͲۍ ېͳۍ ېͲۍ ېͲۍ ېͲۍ ۑ ێ ۑ ێۑ ێۑ ێۑ ێۑ ێۑ ێۑ ێ ۑ ێۑ ێۑ ێۑ ێۑ ێۑ ێۑ ێ Step1. ܶ ՚ Ǣ ܶܧ՚ Ǣ ܲ ՚ ሼ ሽǢ ܯ ሺ ሻ ՚ ͳǢ ݓۑ ܥ ێଵ ൌ ۑͲێ ۑͳێ ۑͳێ ۑͲێ ۑͲێ ۑͲێ ۑͲێ,ݓଶ ൌ ۑͲێ ۑͳێ ۑͲێ ۑͲێ ۑͲێ ۑͲێ ۑͲێ ۑ ܦێ ۑͲێ ۑͲێ ۑͲێ ۑͳێ ۑͲێ ۑͲێ ۑͲێ ۑͲێ ۑͲێ ۑͳێ ۑͳێ ۑͲێ ۑͲێ ۑͲێ ߤሺ ሻ ՚ ߬ ሺͳሻ. //Create an initial empty set of transitions, an ے ܧۏ ےͲۏ ےͳۏ ےͲۏ ےͲۏ ےͲۏ ےͲۏ ےͲۏ ےͲۏ ےͳۏ ےͳۏ ےͲۏ ےͲۏ ےͲۏ ےͲۏ initial empty event trace set, and an initial set of places with only a The sequences Wi of the detected events ej associated to marked place ݅݊݅associated with the first observed vector. output changes are obtained: Step 2. ߬ אȞ : భ మ య ర ఱ ల 2.1 ܿ ݐ݊݁ݎݎݑ՚ //Take as current. Ͳ ՜ ͳ ՜ Ͳ ՜ Ͳ ՜ Ͳ ՜ Ͳ ՜ Ͳ 2.2 ߬ ሺ݆ሻ߬ ǡ ͳ ݆ ȁ߬ ȁ . //For every event ېͲۍ ͳ ېͲۍെͳ ېͲۍ Ͳ ېͲۍ Ͳ ېͳۍ Ͳ ېͳۍ Ͳ ېͲۍ ۍ ۑ ێ ې Ͳ ۍ ۑ ێ ېͳۍ ۑ ێ ې Ͳ ۍ ۑ ێ ېͲۍ ۑ ێെͳۑ ێ ې Ͳ ۍ ۑ ێ ې trace: ݓଵ ൌ ۑͲێ ۑ ێ ۑͳێ ۑ ێ ۑͳێ ۑ ێ ۑͲێ ۑ ێ ۑͲێ ۑ ێ ۑͲێ ۑ ێ ۑͲێ ێ ۑͲێ ۑ Ͳ ێ ۑͲێ ۑ ͳ ێ ۑͳێ ۑͲێ ۑͲێ ۑ Ͳ ێ ۑͲێ ۑͲێ ۑͲێെͳۑͲێ ۑ 2.2.1 If ߬ ሺ݆ሻ ܶܧ ב//If it is new ێ ےͲۏ ۑͳێ ےͲۏ ۑ Ͳ ێ ےͲۏ ۑͲێ ےͲۏെͳےͲۏ ۑ Ͳ ێ ےͳۏ ۑ Ͳ ێ ےͲۏ ۑ ےͲ ۏ ےͲۏ ےͲۏ ےͲۏ ےͳۏ ۏെͳے ߬ଵ ൌ ݁ଵ ݁ଶ ݁ଷ ݁ସ ݁ହ ݁ 183 then ܶܧ՚ ܶܧሼ߬ ሺ݆ሻሽǢ ܶ ՚ ܶ ൛ݐ ೕ ൟǢ J൫ݐ ೕ ൯ ՚ ߬ ሺ݆ሻǢ t 4e4 t5e5 t6e6 ܲ אǡ ܫ൫ ǡ ݐ ೕ ൯ ՚ ͲǢ ܱ൫ ǡ ݐ ೕ ൯ ՚ Ͳ //create a ೕ t3e3 transition ݐ ೕ to represent the trace;ܫሺܿݐ݊݁ݎݎݑǡ ݐ ሻ ՚ ͳ t1e1 t 2e2 pini //create an arc from current to ݐ ೕ If ݆ ൌ ȁ߬ ȁ //If it is the last trace of the sequence, t7e5 t8e4 t9e6 then ܱ൫ ǡ ݐ ೕ ൯ ՚ ͳ //add an arc from its transition to ݅݊݅. Figure 1. Basic model describing the sequences of event traces else ܲ ՚ ܲ ሼ௨௧ ሽǢ ݐ ܶ אǡ ܫሺ௨௧ ǡ ݐ ሻ ՚ Ͳǡ ሺ௨௧ ǡ ݐ ሻ ՚ ͲǢ ߤሺ௨௧ ሻ ՚ ߤሺܿݐ݊݁ݎݎݑሻ ݁ //create 2) Simplifying the basic structure ೕ a new place pout;ܱ൫௨௧ ǡ ݐ ൯ ՚ ͳ //create an arc from Additional node merging operations can be performed on its transition to pout ; ܿ ݐ݊݁ݎݎݑ՚ ௨௧ //take such place the basic structure in order to obtain an equivalent trace as current. model. Now we can take into account the event ej associated 2.2.2 If ߬ ሺ݆ሻ ܶܧ א//If it is not new to transitions. Consider the following transformation rules. then find ݐ ೕ ܶ אȁJ൫ݐ ೕ ൯ ൌ ߬ ሺ݆ሻ //find the transitions which represent the sequence. For every one of those Algorithm 2. Simplifying basic structure. x ೕ Input: G transitions, let be pin = ݐ //take the input place of the transition as pin; Output: G’: an equivalent IPN If there is any pin such that ߤሺ ሻ ൌ ߤሺܿݐ݊݁ݎݎݑሻ Apply the following rule on the initial place then ǡ ሺǡ ሻm ሬሬሬറሺሺǡሻǡ ሺ ǡሻሻǢ Rule 1: ݐೕ ǡ ݐೕ א x ȁܽ ് ܾ //If ݅݊݅has several output ೕ ǡ ሺǡ ሻm ሬሬሬറ ሺሺǡሻǡ ሺ ǡሻሻǢ transitions with the same associated event, then merge ݐ and where ሬ ሬሬറ is a vector bitwise or operation Ǣ ܲ ՚ ݐೕ and their output places accordingly. This test is ̳ܲሼܿݐ݊݁ݎݎݑሽ //merge current place with such an input performed iteratively on the new obtained place, until ೕ place; ܿ ݐ݊݁ݎݎݑ՚ ሺݐ ሻx //take the output place of the there are no many output transitions of such a place transition as current. sharing the same event. else go to step 2.2.1, and take ߬ ሺ݆ሻ as new. Rule 2: ݐೕ ǡ ݐೕ אx ȁܽ ് ܾ //If ݅݊݅has more than one input If ݆ ൌ ȁ߬ ȁ //If it is the last trace of the sequence, transition with the same associated event, then merge ݐ and ೕ then ǡ ሺǡ ሻmሬ ሬሬറሺሺǡሻǡ ሺ ǡሻሻǢ ݐೕ and their respective input places accordingly. ሬ ሬሬറ ǡ ሺǡ ሻm ሺሺǡሻǡ ሺ ǡሻሻǢ ܲ ՚ ̳ܲሼܿݐ݊݁ݎݎݑሽ //merge current with the initial place. Since merging has linear order and rules cannot be applied ʹǤ͵ݐ ೕ ܶ א, OԢ൫ݐ ೕ ൯ ՚ ݁ //associate every transition ݐ to more times than the number of places in the net, Algorithm 2 the last symbol ej of the event trace it represents. is executed in polynomial time on the number of repeated transitions in the same place. Since search operation has linear complexity and the algorithm implies the addition of a transition for every Property 2. G’ preserves the sequences in G. computed trace that has not been yet observed, then Proof. Let ݂ܮ ൌ ሼߣԢሺݐଵ ሻߣԢሺݐଶ ሻ ǥ ߣԢሺݐ ሻȁݐଵ א x ǡ ݐାଵ א Algorithm1 is executed in polynomial time on the number and ሺݐ x ሻx ሽ be the set of observable sequences from place . maximum length of observed output sequences. Consider ݐೕ ǡ ݐೕ א x ȁܽ ് ܾ . Before applying rule 1, Property 1. The IPN G built through algorithm 1 represents x all and only all the sequences (sub-sequences) in Ȟ ݂ܮ ൌ ݁ ܮೌ ݁ ܮ್ ሺߣ ڂԢሺݐ ሻܮ ሻ , with ൌ ൫ݐೕ ൯ , ೕ x Proof. By construction, every sequence ߬ is represented ൌ ൫ݐ ൯ ; ݐ א x ȁݐ ് ݐೕ ǡ ݐ ് ݐೕ , ൌ ሺݐ ሻx . After in G by a circuit starting from including the sequence of applying rule 1, ݂ܮ ൌ ݁ ሺܮೌ ܮ ್ ሻ ሺߣ ڂԢሺݐ ሻܮ ሻ . ݐ ೕ ; this circuit represents also the sequence Wi of events. Thus݂ܮ ൌ ݂ܮ , and then language of G is not changed by Furthermore, the reuse of computed transitions having the application of rule 1. A similar reasoning can be done for associated the same event traces, during the processing of rule 2. ז subsequent߬ , is done only when common paths of length ߢ are built, which does not introduce other sequences. ז In the example the application of the rules lead to the model of figure 2. Since the initial place has two input Using the previous algorithm the obtained IPN transitions associated to e6, they can merge and their input corresponding to the two sequences of event traces of the places. example is showed in figure 1. 3) Concurrent transitions Other transformations may be performed when there are transitions that appear in the sequences in different order 184 describing their interleaved firing; this behaviour is exhibited Algorithm 3. Representing outputs changes by concurrent transitions. The analysis can be performed on a Input: G’, {ei(j)} model component comprised between two transitions relied Output; Q : the IPN including measurable places and inputs by several paths containing the concurrent transitions. If there Step 1. ܲ ՚ ܲ ൛ଵ ǡ ଶ ǡ ǥ ǡ ൟ. Create q measurable places are m! paths, we can explore if there exists m different for every one of the components in the output vectors. transitions in the paths and every sequence is a permutation from each other. When it is verified, the subnet can be Step 2. ݐ ೕ ܶ א: if ݁ ሺ݅ሻ ൌ െͳ then ܫ൫ ǡ ݐ ೕ ൯ ൌ ͳ and transformed into a concurrent component of G’ preserving the ܱ൫ ǡ ݐ ೕ ൯ ൌ Ͳ , if ݁ ሺ݅ሻ ൌ ͳ then ܫ൫ ǡ ݐ ೕ ൯ ൌ Ͳ and same behaviour. ܱ൫ ǡ ݐ ೕ ൯ ൌ ͳ , if ݁ ሺ݅ሻ ൌ Ͳ then ܫ൫ ǡ ݐ ೕ ൯ ൌ Ͳ and t4e4 t5e5 ܱ൫ ǡ ݐ ೕ ൯ ൌ Ͳ (add arcs to and from the measurable places according to its associated vector event ݁ ). t6e6 t1e1 t 2e2 t3e3 Step 3. If component ݅ of vector ݓ ሺͳሻ is 1 then ܯ ሺ ሻ ൌ ͳ, pini otherwise ܯ ሺ ሻ ൌ Ͳ (put tokens in the measurable places to t7e5 t8e4 represent the first output vector). Step 4. Associate to each ݐ ೕ the input symbol registered at the detection of ej. The net with measurable places and inputs for the example Figure 2. Model after merging is showed in figure 4. In figure 2 notice that between the transition associated to e3 and the new transition associated to e6 there are paths with B t 4e5 E all possible permutations of e4 and e5; then, we can transform d t6e6 this into a concurrent component and we obtain the net t1e1 A t 2e2 t3e3 pini showed in figure 3. Notice that this model preserves the same a H b event sequences of the previous one. D t5e4 C e c t 4e5 t6e6 Figure 4. IPN model including the measurable places t1e1 t2e2 t3e3 pini t5e4 2) Model simplifying Implicit non-measurable can be removed: if there is a non- measurable place whose input and output transitions are exactly the same than any measurable place, then delete such Figure 3. Simplified basic model a place and its input and output arcs. The final model for the illustrative example is showed in The simplification by analysis of concurrency is not figure 5; the incidence matrix, output function and initial strictly necessary for representing the event sequences; marking of this IPN are given below. The associated inputs however the equivalent model with concurrent transitions for transitions is given by the lambda function: O(t1)=a, O(t2)= may be simpler. Although the analysis could be inefficient H, O(t3)=b, O(t4)=d, O(t5)=c, O(t6)=e. when the number of paths in the subnet is large, usually this number is reduced. െͳ Ͳ Ͳ Ͳ Ͳ ͳ ͳ ۍ ͳ െͳ Ͳ Ͳ Ͳ Ͳې Ͳ ͳ Ͳ Ͳ Ͳ Ͳ Ͳ ې Ͳۍ ێ ۑ Ͳۍ ۑ ێ E. Adding outputs and inputs ێ Ͳ ͳ െͳ Ͳ Ͳ Ͳۑ Ͳ Ͳ ͳ Ͳ Ͳ Ͳې ۑ Ͳێ ێ ۑ ܥൌێ Ͳ Ͳ ͳ െͳ Ͳ Ͳ ۑ, ߮ ൌ Ͳێ Ͳ Ͳ Ͳ Ͳ Ͳ ͳۑ, ܯ ൌ ۑͲێ 1) Representing outputs changes ێ Ͳ Ͳ ͳ Ͳ െͳ Ͳۑ Ͳێ Ͳ Ͳ Ͳ ͳ Ͳ Ͳۑ ۑ Ͳێ ێ Ͳ Ͳ Ͳ ͳ Ͳ െͳۑ Ͳۏ Ͳ Ͳ Ͳ Ͳ ͳ Ͳے ۑ Ͳێ Once the event sequences are represented in the basic ۏ Ͳ Ͳ Ͳ Ͳ ͳ െͳے ے Ͳۏ model, it must be completed by adding the output changes represented by the events and their respective inputs. Recall B t4 E that events are vectors computed from the difference of p4 d p6 t6 A t3 consecutive output vectors; thus ej relates measurable places t1 t2 representing the outputs yielding the incidence matrix p1 a p2 H p3 b D t5 C e corresponding to measurable places. The inputs are straightforward included in the model. This procedure is p5 c p7 detailed below. Figure 5. Simplified IPN model 185 Since every one of the transitions in the net actually The proposed algorithms have polynomial complexity on represents a sequence of events of length ߢ , the output the input data size; they have been tested with numerous language of length ߢ + 1 of the net is equal to the observed examples of diverse complexity including an industrial output language. Even, for the illustrative example, the output experimental system; in general ߢ must be greater than one language of the IPN is equal to the observed output language, and the obtained model allows representing complex i.e. only the observed cyclic output sequences are represented behaviour such as concurrency and non determinism. by the evolution of the net. Current research deals with a depth study on the choice of F. Procedure the accuracy parameter ߢ and the definition of an efficient procedure for the analysis of concurrency in the basic non- Now, we can summarise the stages of the method for IPN measurable model. model identification. ACKNOWLEDGEMENT Algorithm 4. Building an IPN model Inputs: A DES and an accuracy parameter ߢ A.P Estrada-Vargas was sponsored by CONACYT Grant No. Output: (Q,M0): an IPN model 50312, and by ENS de Cachan International Scholarship. 1. Obtain the input symbols and the cyclic sequences of REFERENCES observed output vectors. [1] A.W. Biermann and J.A. Feldman, “On the Sysnthesis of Finite-State 2. Compute the event sequences from the observed vectors. Machines from Samples of Their Behavior”, IEEE Trans. on Computers, Vol. 21, pp. 592-597, 1972 3. For every sequence of events, create traces of lengthߢ. [2] M. P. Cabasino, A. Giua, C. Seatzu, “Identification of deterministic Petri nets”, Proc. of the 8th International Workshop on Discrete Event 4. Create the non-observable behaviour of the IPN (Algorithm Systems, Ann Arbor, Michigan, USA, July 10-12, 2006. 1) and simplify it (algorithm 2). [3] M. P. Fanti and C. Seatzu, “Fault diagnosis and identification of discrete event systems using Petri nets”, Proc. of the 9th International 5. Complete the Petri net adding the observed behaviour and Workshop on Discrete Event Systems, Göteborg, Sweden, pp. 432-435, delete implicit places (algorithm 3). May 28-30, 2008 [4] A. Giua and C. Seatzu, “Identification of free-labeled Petri nets via integer programming”, Proc. of the 44th IEEE Conference on Decision Proposition 1. For a DES S that holds the hypothesis given and Control, and the European Control Conference 2005, Seville, Spain, in section III.A and an identification parameter N, Algorithm 4 December 12-15, 2005 yields an IPN model (Q,M0) which represents exactly [5] E.M. Gold, “Language Identification in the Limit”, Information and ࣦ ାଵ ሺܵሻ. Control, Vol. 10, pp. 447-474, 1967 [6] K. Hiraishi, “Construction of Safe Petri Nets by Presenting Firing Proof. Since the deletion of implicit places does not Sequences”, LNCS, 616, pp. 244-262, 1992 alter͉௨௧ ሺܳǡ ܯ ሻ, we make the proof with the model obtained [7] H. Ishizaka, “Polynomial Time Learnability of Simple Deterministic before this procedure. The firing of a transition ݐin the system Languages”, Machine Learning, Vol. 5, pp. 151-164, 1990 is not affected by the addition of arcs to, and from ݐ, since [8] J. Kella, “Sequential Machine Identification”, IEEE Trans. on these arcs were computed from differences of vectors in Ȟሺܵሻ. Computers, Vol. 20, pp. 332-338, 1971 Then, also in this model, every event sequence ߪ of length less [9] S. Klein, L. Litz, J.-J. Lesage, “Fault detection of Discrete Event Systems using an identification approach”, 16th IFAC World Congress, or equal than ߢ belongs to the language of the net iff it was CDROM paper n°02643, 6 pages, Praha(CZ), July 4-8, 2005 observed. [10] S. Klein, “Identification of Discrete Event Systems for Fault Detection The sequences of transitions of length less or equal than ߢ Purposes”, Ph. D. Thesis, Ecole Normale Supérieure de Cachan, Oct 2005 that can be fired lead to markings in the measurable places that [11] L.S. Levy and A.K. Joshi, “Skeletal structural descriptions”, also belong to Ȟሺܵሻ (since the marking change provoked in the Information and Control, Vol. 39, pp. 192-211, 1978 measurable places was obtained from the difference of [12] M.E. Meda, “DES identification using Interpreted Petri nets”, observed vectors). Then, we have that sequences of observed International Symposium on Robotics and Automation, pp 353-357, output vectors of length less or equal than ߢ ͳ correspond to December 1998 sequences of marking vectors in the net and ͉ାଵ ௨௧ ሺܳሻ ൌ [13] M. E. Meda-Campaña, “On-line Identification of Discrete Event ࣦ ାଵ ሺܵሻ.ז Systems: Fundamentals and Algorithms for the Synthesis of Petri Net Models”, Ph. D. Thesis, CINVESTAV, Unidad Guadalajara, Nov 2002 IV. CONCLUSION [14] M.E. Meda-Campaña, E. Lopez-Mellado, “Identification of Concurrent Discrete Event Systems using Petri Nets”, 2005 IMACS Conference, In this paper we provided a method to create an IPN model Paris, France, Jul. 2005 for a given DES described by a set of input-output sequences [15] Y. Takada, “Grammatical Inference for Even Linear Languages Based that may contain cycles representing infinite length behaviour. on Control Sets”, Information Proc. Letters, Vol. 28, pp. 193-199, 1998 The proposed off-line procedure operates considering an [16] L.P.J. Veelenturf, “Inference of sequential machines from Sample accuracy parameter ߢ such that in the output language of the Computations”, IEEE Trans. on Computers, Vol. 27, pp. 167-170, 1978 obtained IPN only and all observed output sequences of length [17] L.P.J. Veelenturf, “An Automata theoretical approach to developing ߢ + 1 are represented. This approach avoids including in the learning neural networks”, Cybernetics and Systems, 12, pp. 179-202, model more sequences than that observed. 1981 186