Introduction

Automated modelling of discrete event processes from external behaviour is nowadays studied by numerous research groups along the two last decades. The main motivation is to discover the current behaviour of unknown or ill known systems, because the documentation is not updated or missing. The aim is to obtain models that express clearly causal and concurrency relationships between the events generated by the process. Petri nets have been mostly used to represent such models.

Variations on this problem have been named differently in the research community. Earlier methods were called language learning techniques, which aimed to build finite automata, or grammars of languages from samples of accepted words [1,2]. In discrete manufacturing systems the problem is referred as process identification, in which the purpose is to build finite automata or Petri nets from sequences of inputoutput signals. In this field several approaches and methods have been proposed: the incremental approach [3,4], and the integer programming based approach [5,6].

Input-output identification of automated production process is addressed in [7]; an interpreted PN is obtained from a long single observation of input-output vectors. Overviews of these methods are presented in [8] and [9].

In the field of workflow management systems (WMS) the problem is named process mining: discovery. Most of the proposals obtain Petri nets from a set of event traces representing the system behaviour as process cases. A complete review of recent works can be found in [10].

The work presented herein concerns to identification of discrete event processes, in which the available data is a set of sequences of input-output vectors, which represent the exchanged signals between a controller and a plant from the controller point of view. The events, the number of places, and the number of transitions are not known a priori. The proposed method yields a Petri net model including input functions and outputs. The method is based on a two-phase strategy presented in a recent previous work [7], in which the observable components of the labelled PN are first obtained, and then the non-observable part is inferred.

This paper focuses on the second phase in which a PN is obtained from a sequence S of events (transitions) from a given alphabet T. More precisely, a method based on the computation of the t-invariants [11] is extended; the proposed technique refines the obtained PN by determining a sequencing pattern, given also as a PN', that schedules the execution of t-components in the initial PN.

The paper contains a) an overview of the t-invariant based discovery method and b) the repetitive component scheduling technique.

Context and background

Input-Output identification

The present paper follows the approach presented in [7,11] for dealing with inputoutput identification. The method processes off-line the I/O-sequence w captured during the process operation and builds an interpreted PN (IPN) model that reproduces w.

Example 1. Consider a process handling 3 inputs (s, x, y) and 3 outputs (A, B, C), from which the following I/O sequence is captured:

The construction of an interpreted Petri net (IPN) model from w is performed in two stages. The first stage processes the sequence w and obtains the observable part of the model consisting of components using observable places and transitions labelled with output symbols and expressions of input symbols respectively (Fig. 1). This determines the set of transitions T. A transition sequence S that corresponds to the observed event sequence is also delivered. In the example S 1 =t 1 t 2 t 3 t 4 t 1 t 2 t 5 t 6 t 1 t 2 t 3 t 4 t 1 t 2 t 5 t 6 t 1 is obtained. A simpler technique for this stage is proposed later in [12].

The second stage builds a PN model that is able to reproduce S with a reduced excessive behaviour; furthermore, the number of nodes is small since only the necessary places to represent the discovered structural constrains are added. The resulting PN corresponds to the process' internal behaviour represented by non observable places. In the example the obtained PN showed in figure 2 reproduces S 1 (thus w). Merging A technique that allows determining more complex behaviours, in particular implicit dependencies, is proposed in [11]; besides discovering the non observable PN the technique delivers the t-invariant supports. In this example, the supports are <Y 1 >={t 1 , t 2 , t 3 , t 4 } and <Y 2 >={t 1 , t 2 , t 5 , t 6 }; the t-components ||Y i || can be clearly distinguished in this example.

⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ =

In the present paper we are extending the method in [11] for obtaining a more precise non observable IPN with respect to the observed sequence S.

In Example 1, notice that the execution of S exhibit always the occurrence of tcomponents in alternate way: S Y =τ 1 τ 2 τ 1 τ 2 τ 1 τ 2 ..., where τ i is a sub-sequence of S including transitions in <Y i >. However, in the model sub-sequences of repeated components (τ 1 τ 1 τ 1 ... τ 2 τ 2 ) may occur, which is a kind of exceeding behaviour.

A possible refining of the PN N of figure 3 to reduce this behaviour can be done by adding a component that ensures the occurrence of the t-components. Being ρ(τ 1 )=t 3 and ρ(τ 1 )=t 5 the representative transitions of each component, it is easy to determine that a circuit N' including such transitions and new places can be added to the PN to ensure the order of occurrence, as shown in figure 4. Next section describes this metaanalysis technique. (y, x))=1}, and

x • = {y | O((x, y)=1}. The incidence matrix of G is C = C + − C − , where C − = [c ij − ]; c ij − = I(p i , t j ); and C + = [c ij + ]; c ij + = O(p i , t j

) are the pre-incidence and postincidence matrices respectively.

A marking function M : P→ Z + represents the number of tokens residing inside each place; it is usually expressed as an |P|-entry vector. Z + is the set of nonnegative integers. Definition 2. A Petri Net system or Petri Net (PN) is the pair N = (G,M 0 ), where G is a PN structure and M 0 is an initial marking.

In a PN system, a transition t j is enabled at marking M k if ∀p i ∈ P, M k (p i ) ≥ I(p i , t j ); an enabled transition t j can be fired reaching a new marking M k+1 , which can be computed as M k+1 = M k + Cu k , where u k (i) = 0, i≠j, u k (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 M 0 firing only enabled transitions; this set is denoted by R(G,M 0 ). Definition 3. A PN system is 1-bounded or safe iff for any M i ∈ R(G,M 0 ) and any p ∈ P, M i (p) ≤ 1. A PN system is live iff for every reachable marking M i ∈ R(G,M 0 ) and ∀t ∈ T there is a reachable marking

M k ∈ R(G, M i ) such that t is enabled in M k .

Definition 4. A t-invariant Y i of a PN is an integer solution to the equation CY i =0

such that Y i ≥0 and Y i ≠0. The support of Y i denoted as <Y i > is the set of transitions whose corresponding entries in Y i are strictly positive. Y is minimal if its support is not included in the support of other t-invariant.

A t-component G(Y i ) is a subnet of PN induced by a <Y i >: G(Y i )=(P i , T i , I i , O i ), where P i = • <Y i >∪<Y i > • , T i =<Y i >, I i = P i ×T i ∩I, and O i =P i ×T i ∩O. G(Y i ) is usually denoted as ||Y i ||.

In a t-invariant Y i , if we have initial marking (M 0 ) that enables a t i ∈ <Y i >, when t i is fired, then M 0 can be reached again by firing only transitions in <Y i >.

Sequencing repetitive components

Problem statement

Consider the t-invariant based discovery method, which treats a single sequence S∈T* and delivers a safe PN N and a set of minimal t-invariant supports <Y>={<Y i >} such that PN executes all the t-invariants Y [11]. The refining technique has to find a PN N' using a set of transitions T'⊆ T and new places, such that the composed PN N''= N||N' by merging transitions in T' in both nets executes the t-components ||Y i || in the order they appear in S. This statement has been briefly introduced through Example 1, where N and N'' are illustrated in figures 2 and 4 respectively.

Sequence of t-components

A sequence S Y of t-components execution can be determined by parsing S from the first transition. Every component ||Y i || can be identified when a given transition that distinguishes the component is found or, in the worst case, the whole set <Y i > is found during the tracking of S.

Representative transitions

Definition. The distinguishable transitions of a t-component ι(||Y i ||)⊆<Y i > are the transitions that only belong to this support. When such transitions are fired, we are sure that a t-component is executed. ι(||Y i ||)=<Y i >∩(⊗ j <Y j >∀j). Notice that ι(||Y i ||)=∅ when every t j ∈ <Y i > belongs also to other t-invariant supports. Eventually, all the ι(||Y i ||)=∅.

Definition. The representative transition ρ i of <Y i > is a t j ∈<Y i > such that it determines precisely the t-component is being executed is S. If ι(||Y i ||)≠∅ then ρ i is the first transition in ι(||Y i ||) that occurs in S; else, ρ i is the last transition in <Y i > found in the current subsequence tracked in S, then τ i is determined.

In Example 1, ι(||Y 1 ||)={t 3 , t 4 } and ι(||Y 2 ||)={t 5 , t 6 }; ρ 1 = t 3 and ρ 2 =t 5 .

Property 1. In a firing sequence S all the transitions of a t-component are fired consecutively as a subsequence τ i if there is no other nested t-components (τ j , τ k ...) sharing transitions with τ i . In case of nested t-components, part of τ i is fired, then one or several occurrences of τ j may appear; afterwards some other transitions of τ i are fired, then other nested τ k may occur and so on; finally, the remainder transitions of τ i are fired.

Proof. In a repetitive execution of a PN if a t-invariant is executed, all the transitions of the support must be fired. When a nested t-component is executed, then this component will be executed (one or several times), and then the remaining transitions of the first t-component will be fired.

It is clear from S of Example 1 that all the transitions of <Y 1 > are fired first and then those of <Y 2 >. Thus, it can be expressed as S Y =τ 1 τ 2 τ 1 τ 2 τ 1 τ 2 ... Example 2. The PN in Figure 5 When some ι(||Y i ||)=∅, the transitions in <Y 1 > must be tracked during the parsing of S until the last transition or the support is found; then τ k is determined.

Obtaining the Y-Sequence

The sequence of t-components S Y , thus S ρ can be obtained from S by considering the representative transitions and the cardinality of the t-invariant support. A procedure that parses S and delivers S ρ is decidable and yields always the same S ρ ; the outline of a simple procedure for the case in which all ι(||Y i ||)≠∅, and there are not nested t-invariants is given below. The procedure for determining ρ must deal with the case in which some ι(||Y i ||)=∅; in the worst all the transitions in <Y i > must be tracked in S to determine uniquely the t-component that is being executed. Furthermore, when there are nested tcomponents, a stack can be used to parse the components execution, in particular when there is nesting at several levels; in this case, regarding the t-component at higher level ρ r , several representative transitions ρ r1 , ρ r2 , ... could be determined to go ahead the execution of the "interrupted" t-component. The structure of the discovered PN can be also exploited.

In

Repetitive patterns

Now, the next stage is to determine from S ρ the repetitive pattern that schedules the execution of the t-components. The problem is similar to that of process discovery but some other facts must be considered.

Simple patterns

It is easy to see in Example 1 that the S ρ =t 3 t 5 t 3 t 5 corresponds to a pattern that can be represented by a PN N' that is a cycle p 6 t 3 p 7 t 5 p 6 with p 6 initially marked. Similarly, in Example 2, the pattern N' derived from S ρ =t 1 t 4 t 3 t 1 is a cycle including the representative transitions; the merging of N' with N is shown in Figure 6; when the implicit place (marked) is removed, the simplified PN is shown in Figure 7. Notice that in previous examples, the refined PNs have one t-component. 2 and the same tinvariants. Thus, the representative transitions are the same; however, the sequence of representative transitions is not the same: S ρ =t 3 t 5 t 5 t 3 t 5 t 3 ...; in the pattern the tcomponent ||Y 1 || is executed once, whilst ||Y 2 || twice. This cyclic pattern, which establishes a production rate 1-2 for the jobs, is designed as a 2-bounded PN N' that is shown in Figure 8. For patterns that handle k jobs given by S Y =(τ 1 ) n (τ 2 ) m ...(τ k ) r (τ 1 ) n ... with regular executions (fixed n, m, ..., r) of jobs, the PN can be designed similarly. Now, consider the discovered PN, which describes the behaviour of a process involving three jobs. The t-invariant supports are: <Y 1 >= {t 1 , t 2 , t 3 }, <Y 2 >= {t 1 , t 4 , t 5 }, and <Y 1 >= {t 1 , t 6 , t 7 }; the representative transitions are: ρ 1 = t 2 , ρ 2 = t 4 , and ρ 3 = t 6 . Be- .., that is, τ 1 is executed between the alternation of τ 2 and τ 3 . The PN N' that describes this pattern is shown in Figure 10. Notice that N' has two invariants; thus, in a recursive manner, being t 4 and t 6 the representative transitions of these t-components, N'' can be obtained (Figure 11). The refined PN is obtained by merging N with N''; such a PN, shown in Figure 12 has only a tinvariant.

p