Ana Paula Estrada-Vargas

Ernesto López-Mellado

Jean-Jacques Lesage

INPUT-OUTPUT IDENTIFICATION OF CONTROLLED DISCRETE MANUFACTURING SYSTEMS

Keywords: Automated Modelling, Controlled DES, I-O Identification, Interpreted Petri Nets

The automated construction of discrete event models from observations of external system's behaviour is addressed. This problem, often referred to as system identification, allows obtaining models of ill-known (or even unknown) systems. In this article an identification method for Discrete Event Systems (DESs) controlled by a Programmable Logic Controller is presented. The method allows processing a large quantity of observed long sequences of input/output signals generated by the controller and yields an interpreted Petri net model describing the closed-loop behaviour of the automated DESs. The proposed technique allows the identification of actual complex systems because it is sufficiently efficient and well adapted to cope with both the technological characteristics of industrial controllers and data collection requirements. Based on polynomial-time algorithms, the method is implemented as an efficient software tool which constructs and draws the model automatically; an overview of this tool is given through a case study dealing with an automated manufacturing system.

Introduction

Industrial systems identification

In automation engineering, the first step of the development life cycle of new systems is generally devoted to the modelling of the system's behaviour. In most cases these models are used for functional or performance evaluation by analytical approaches or simulation techniques. In this paper, the problem we address is the model discovery of systems whose models are not updated or are not available at all. We will see later that this situation occurs frequently in industry. Nevertheless, despite the lack of a "reliable" model, performance evaluation or redesign is often required.

Modelling existing systems (natural or manmade) for performance assessment has been done in several fields:

• Natural systems: in [Chang and Hanna, 2004] a model for evaluating the quality of air is proposed, • Organizations: Hospital activity management is analysed through workflow models [Du, 2009],

• Energy production [START_REF] Connolly | Modelling the existing Irish energy system to identify future energy costs and the maximum wind penetration feasible[END_REF] and industrial systems [START_REF] Mottershead | [END_REF] may require more detailed and complete models for simulation.

In industrial systems under intensive workload, initial models are not always updated. In [START_REF] Lanubile | Iterative Re-engineering to compensate for Quick-Fix Maintenance[END_REF], the authors explain that a typical approach to software maintenance is analysing just the source code, applying some patches, releasing the new version, and then updating the documentation. This quick-fix approach usually leads to documentation that is not aligned with the current system and degrades the original system structure, thus rendering the evolution of the system costly and error-prone. This last case is representative of automated discrete production systems in which Programmable Logic Controller (PLC) code maintenance is often performed without updating the documentation nor the control algorithm or model. For such systems, identification from observations of external system's behaviour could be more appropriate, since the system is operating most of the time. In this case the main advantage of identification is that the obtained model approximates closely the actual system functioning. An identified model can be afterwards completed by applying well known modelling techniques using the knowledge about the process, for analysis or redesign purposes.

Identification methods

Languages inference techniques

Pioneer works on identification have been developed in computer science, where the problem of obtaining a language representation from sets of accepted words has been dealt since a long time. Such methods are generally referred as languages inference techniques or learning techniques.

Gold´s method [Gold, 1967] processes positive samples: an infinite sequence of examples such that the sequences contain all and only all the strings of the language to learn.

The Probably Approximately Correct (PAC) learning technique proposed in [Valiant, 1984] learns from random examples and studies the effect of noise on learning from queries.

The query learning model proposed in [Angluin, 1988] considers a learning protocol based on a "minimally adequate teacher"; this teacher can answer two types of queries: membership query and equivalence query.

Several works that have adopted state machines as representation model, allow describing the observed behaviour. In [Booth, 1967] a method to model a language as Moore or Mealy machines is presented. The system under investigation is placed within a test bed and connected to a so called experimenter, which generates the input signals and records the output signals of the system. The identification can be started considering a very few number of states. If, at some point of the experiment, it is impossible to find a correct machine with the assumed number of states, the identification is started again considering a machine with one more state.

The method proposed in [Kella, 1971] allows obtaining models representing Mealy machines from a single observed input-output sequence. The algorithm lists all reduced machines which may produce the given sequence. The construction principle is the merging of equivalent states.

In [Biermann and Feldman, 1972] a method for the identification of non deterministic Moore machines based on a set of input output sequences is presented. All the sequences start in the same initial state. The identification principle is the reduction of an initial machine represented as a tree.

The method presented in [Veelenturf, 1978] processes simultaneously a sample of sequences to produce stepwise convergent series of Mealy machines, such that the behaviour of every new machine includes the behaviour of the previous one. At each step, the last obtained machine is analysed and completed by adding transitions and possibly new states.

Later, in [Veelenturf, 1981] an algorithm to identify a unique Moore machine generating the behaviour observed during m sequences starting at the same initial state is proposed. The learning procedure operates in three steps: induction, contradiction, and discrimination. A state can never be deleted and only transitions between states can be modified. This method is improved in [Richetin, 1984], which proposes two algorithms to identify multiple systems as well as systems that may not be initialized between two records.

The identification problem for context free grammars (CFGs) needs, beside given examples, some additional structural information for the inference algorithm [START_REF] Levy | [END_REF]. [Ishizaka, 1990] has investigated a subclass of CFGs called simple deterministic grammars. A polynomial time algorithm that allows an exact identification of a simple deterministic language is given.

In [Takada, 1998] it has been shown that the grammatical inference problem for even linear languages can be reduced in polynomial time to the inference of regular languages.

Other works use as description formalism Petri net models. In [Hiraishi, 1992] an algorithm for synthesising Petri net models is presented. The proposed algorithm has two phases. In the first phase, the language of the target system is identified under the form of a DFA. In the second phase, a Petri net that accepts the same language as the DFA is built.

Recent DESs identification methods

In recent years, the scientific community has proposed identification approaches (based on Petri net or automata) for obtaining approximated models of DESs whose behaviour is unknown or ill-known. In the context of automated DESs, identification methods can be complementary to established modelling techniques; identification builds a closed-loop controller-plant model, which is more classically obtained by a composition of models of controller and plant. Three main approaches for identifying DESs have been proposed in literature [Estrada, 2010a].

The incremental synthesis approach, proposed in [START_REF][END_REF], [START_REF][END_REF], [START_REF][END_REF], deals with unknown partially measurable concurrent DESs exhibiting cyclic behaviour. Several algorithms have been proposed allowing the on-line building of interpreted Petri net (PN) models from the DES outputs. Although the techniques are efficient, the obtained models may represent more sequences than those observed.

In [START_REF] Giua | [END_REF] a method to build a free labelled PN from a finite set of transitions strings is presented. This method is based on the resolution of an Integer Linear Programming (ILP) problem; the obtained PN generates exactly the observed language. Both the ILP statement and its solution are computational demanding. This approach has been extended to other PN classes [START_REF] Cabasino | Identification of Petri Nets from Knowledge of Their Language[END_REF], [Dotoli, 2008], [START_REF] Fanti | [END_REF]] [Dotoli, 2011]; however, issues regarding applications to actual industrial DESs have not yet been addressed in these works.

Another recent off-line method [Klein, 2005] allows building a non-deterministic finite automaton (FA) from a set of input/output (I/O) sequences, experimentally measured from the DES to be identified. Under several hypotheses, the constructed FA generates exactly the same I/O sequences of given length than observed ones. The method was conceived for fault detection in a model-based approach [START_REF] Roth | [END_REF]. Extensions to this work propose an identification method performing optimal partitioning of concurrent subsystems for distributed fault detection purposes [START_REF] Roth | [END_REF].

Other works on the matter, based on different approaches have been proposed. The techniques for workflow mining, published by van der Aalst and co-workers [Cook, 2004][van der Aalst, 2004], allows building Petri net models of workflow processes in which all the activities are observable. Other works pursue the construction of a stochastic PN from recorded event sequences [Ould El Medhi, 2006[START_REF] El | [END_REF] for reliability analysis.

Approach

Our approach is oriented towards the identification of actual industrial automated DESs, such as discrete manufacturing systems in which concurrent repetitive tasks are performed. We focus on closed loop controlled systems whose only available knowledge is the observed behaviour in the form of many long cyclic sequences of input-output vectors measured from a PLC. The aim of this research is to define an efficient identification method, able to build a comprehensible IPN model that describes closely the actual behaviour of the system.

In a first paper we proposed a method for synthesizing interpreted PN (IPN) for coping with concurrent partially observable DESs [START_REF] Estrada | [END_REF]; it processes a set of cyclic sequences of binary output signals yielding models including silent transitions and nonlabelled places. Afterwards the method has been extended for dealing with sequences of I/O signals captured during the closed-loop operation of PLC-based controlled DESs [Estrada, 2010b]. Fundamental technological characteristics of industrial controllers are taken into account in data collection and processing. The obtained model is a safe (1-bounded) IPN describing the controller-plant concurrent behaviour, including that non observable directly from the PLC. The present paper gathers and details the results of these papers; it presents a global and coherent view of these results, includes a wider literature review, and extends them with important application issues. For that, we describe an operational software tool which implements the proposed identification method, which builds and draws by building and drawing the IPN model automatically.

The paper is organized as follows. In section 2 the background on Petri nets and languages is summarised. Based on these definitions the problem of DESs identification is stated in section 3 in terms of language associated to an IPN. Several constraints inherent to real controlled DESs are analysed in section 4. The identification algorithm is given in section 5. Then, a software tool implementing the proposed method is outlined and a case study is included in section 6.

Basics on Petri nets and languages

This section presents the basic concepts and notation of PN and IPN used in this paper. The symbol • t j (t j • ) denotes the set of all places p i such that I(p i , t j ) ≠ 0 (O(p i , t j ) ≠ 0). Such places are called input (output) places of t j . Analogously, • p i (p i • ) denotes the set of input (output) transitions of p i .

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 post-incidence 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 + Cv k , where v k (i) = 0, i≠j, v 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 ). A PN is called safe (or 1bounded) if∀M k ∈ R(G, M 0 ), ∀p i ∈ P, M k (p i ) ≤ 1. Now it is defined IPN, an extension to PN that allows associating input and output signals to PN models.

Definition 3 : An IPN (Q, M 0 ) is a net structure Q = (G, Σ, Φ, λ, ϕ) with an initial marking M 0 where:
G is a PN structure, Σ = {α 1 , α 2 , ..., α r } is the input alphabet, and Φ = {φ 1 , φ 2 ,..., φ q } is the output alphabet.

λ : T→ g(Σ)∪{ε} is a labeling function of transitions, where g(Σ) is a conjunction of input changes (rising and falling edges), ε represents a system internal event externally uncontrollable.

ϕ : R(Q,M 0 )→( Z + ) q is an output function, that associates to each marking in R(Q, M 0 ) a q-entry output vector; q=|Φ| is the number of outputs. ϕ is represented by a q×|P| matrix, such that if the output symbol φ i is present (turned on) every time that M(p j ) ≥ 1, thenϕ (i, j) = 1, otherwise ϕ(i, j) = 0.

When an enabled transition t j is fired in a marking M k , then a new marking M k+1 is reached. This behaviour is represented as

1 + →  k j t k M M
; the state equation is completed with the marking projection y k = ϕ M k , where y k ∈ (ℤ + ) q is the k-th output vector of the IPN.

According to functions λ and ϕ, transitions and places of an IPN (Q,M 0 ) can be classified as follows.

Definition 4: If λ(t i ) ≠ ε the transition t i is said to be controllable (t i can be fired when the associated input symbol is presented). Otherwise it is uncontrollable (t i is autonomously fired). A place p i ∈P is said to be measurable if the i-th column vector of ϕ is not null, i.e. ϕ(•,i) ≠ 0. Otherwise it is non-measurable. P = P m ∪ P u where P m is the set of measurable places and P u is the set of non-measurable places.

Definition 5: The l-length I/O language L l (Q, M 0 ) of an IPN (Q, M 0 ) contains words of length l formed by pairs (λ(t k ), y k ), where

y k = ϕ M k . L l (Q, M 0 ) ={(λ(t i+1 ),ϕ(M i+1 ))(λ(t i+2 ),ϕ(M i+2 ))…(λ(t i+l ),ϕ(M i+l )) | 1 1 + →  + i t i M M i and ) , ( 0 M Q R M i ∈ }

Controlled discrete event systems

The systems considered in this work are closed loop controlled DESs (Figure 1); they consist of a plant and its industrial controller (in many cases a Programmable Logic Controller: PLC). The behaviour of such systems (i.e. the PLC-plant compound system behaviour) can be observed by collecting the signals exchanged between controller and plant.

Figure 1. Closed loop controller-plant DES Several phenomena, due to the interaction between plant and controller, increase the complexity of the identification process; they must be taken into account when real controlled DESs have to be identified:

• An input evolution (signal emitted by the plant through a sensor) does not always provoke an output evolution (signal emitted by the PLC to an actuator). In practice, few input changes provoke output evolutions; • Non simultaneous I/O events are often simultaneously observed;

• When output changes are provoked by input changes, this causal relationship is not necessarily captured simultaneously. Now, we are going to explain these phenomena.

Plant Controller I (j) O(j) I/O(j)

PLC treatment cycle

A PLC cyclically performs three main steps: "input reading" (I) where it reads the signals from the sensors, "program execution" (PEX) to determine the new outputs values for the actuators, and "output writing" (O) where the newly determined commands are sent to the plant actuators [Bel Mokadem, 2010].

Figure 2. PLC cycle and data collection

At the end of the PEX phase the current values of inputs and outputs (I/O) are sent from the PLC to a computer and stored for a later treatment by the identification algorithm. In this paper we consider that the PLC operates cycle driven, i.e. the cycle is executed periodically [START_REF] Lohmann | Comparison of Event-Triggered and Cycle-Driven Models for Verifying SFC Programs[END_REF].

Experimental constraints

In the identification problem we are addressing, the PLC program is assumed to be unknown. Sequential Function Charts (SFC) are used in this paper only for describing the diverse situations addressed by the proposed method.

SFC is a graphical programming language used for PLCs. It is one of the five languages defined by IEC 61131-3 standard. Main components of SFC are: Steps with associated actions, Transitions with associated logic conditions, Directed links between steps and transitions. Steps in an SFC diagram can be active or inactive. Steps are activated when all steps above it are active and the connecting transition is validated (i.e. its associated condition is true). When a transition is fired, all steps above are deactivated and simultaneously all steps below are activated. Actions associated with steps can be of several types, the most relevant ones being Continuous (N), Set (S) and Reset (R). Apart from the obvious meaning of Set and Reset, an N action ensures that its target variable is set to 1 as long as the step is active.

Due to the PLC cycle, some situations between inputs and outputs could arise. Consider a situation described in Figure 3 These three specific scenarios, among numerous possible others, show that the implementation of a controller and its interaction with the plant introduces phenomena that must be taken into account by the identification algorithm.

.} , { ) ( 2 1 w w S = Γ , such that                   = ) ( ) ( ,..., ) 2 ( ) 2 ( ) 1 ( ) 1 ( i i i i i i i i i w O w I O I O I w
, where

      ) ( ) ( j O j I i i
is the j-th observed I/O vector of size r + q in sequence w i and i w is the length of the I/O word w i .

Definition 7:

The observed k-length I/O language of a DES S is defined as

L κ { } k l w l j S w l j w j w j w S i i i i i ≤ ≤ + Γ ∈ + + + = , ), ( | ) ( )... 2 ( ) 1 ( ) ( .
Now the identification problem can be defined as follows: given a set of observed I/O words Γ(S) generated by a real DES during its operation, the aim of our identification approach is to construct a safe (or

1-bounded) IPN model (Q, M 0 ) such that L κ (Q, M 0 ) = ℒ κ (S).
Since Γ(S) does not provide any information related to the state evolution of the observed DES, these states will be inferred in the identified IPN from ℒ κ (S), where each word of length κ is part of the history (of length κ) of the system. The I/O language generated by the identified IPN is therefore inevitably an approximation of the actual behaviour of the DES. In our approach, the parameter κ is used to adjust the accuracy of the identified model, similarly as proposed in [Klein, 2005].

Identification algorithm

The identification method consists of several steps (Algorithm 1) that build systematically a safe IPN representing exactly the sampled output language of length κ+1 of the DES from the observed I/O vectors sequence Γ(S).

Algorithm 1. Global identification procedure

Inputs: Γ(S) and the parameter κ Output: (Q,M 0 ): an IPN model 1. Compute event vector sequences τ i and symbolic input events λ' from the observed vectors Γ(S). 2. For every sequence of event vectors τ i , create event vector traces τ i κ of length κ.

3. Create the non-observable behaviour of the IPN and simplify it. 4. Complete the IPN adding the observed behaviour and deleting implicit places.

The steps of this procedure are described below.

Sample processing 4.1.1 Event sequences

As stated before, the data obtained by observing the system to be identified is a set of sequences of I/O vectors w 1 , w 2 ,… such that w i = w i (1)w i (2)… where w i (j) refers to the j-th observed vector in sequence w i . Such sequences may have different length. From these sequences, strings of observed event vectors are first computed. Definition 8: An observed event vector τ i (j) is the variation between two consecutive I/O vectors w i (j), w i (j + 1); it is computed as

) ( ) 1 ( ) ( j w j w j i i i - + = τ
. An input event vector λ(τ i (j)) is the variation between two consecutive input vectors I i (j), I i (j + 1); it is computed as

) ( ) 1 ( )) ( ( j I j I j i i i - + = τ λ .
An input event vector can be represented in a compact way by specifying only the input symbols that changed in the event. I i _1 denotes the change from 0 to 1 of the input I i ; similarly I i _0 denotes the change from 1 to 0 of the input I i . Then the symbolic input event λ'(τ i (j)) is a string composed by the representation of the inputs changed in the event vector.

∏ = = m i i i x I j 1 _ )) ( ( ' τ λ where      = - + - = - + = - + = 0 ) ( ) 1 ( 1 ) ( ) 1 ( 0 _ 1 ) ( ) 1 ( 1 _ _ j I j I if j I j I if I j I j I if I x I i i i i i i i i i ε
Then for every sequence w i , a sequence of observed event vectors

τ i = τ i (1) τ i (2)… τ i ( i w -1
) is obtained. The maximum number of possible event vectors is 3 (r + q) -1. However, in practice, only a small subset of them is observed.

                                                                  = 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 w                                                                                                                                     = 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 2 w                                                                                                                                     = 0
τ i = τ i (1) τ i (2)… τ i ( i w -1) is computed.
During the process, if the difference has not been observed before, a new event vector e j is created and stored (τ i (j) = e j ).

For the Example 1, sequences τ i of the detected event vectors e j associated to I/O changes are obtained:

                                            →                                              - →                        =
= = ) ( ' , 1 _ ) ( ' 2 1 e a e                                             - - →                                              - - →                                              - →                                              →                                              - →                        =
) ( ' , 0 _ ) ( ' , 0 _ ) ( ' , 1 _ 1 _ ) ( ' 6 5 4 3 a e c e b e c b e = = = = λ λ λ λ                                             - - →                                              - →                                              - - →                                              →                                              - →                        =

Sequences of κ-length event vector traces

In order to distinguish sub-sequences including the same events, event traces of length κ are used. From every sequence τ i = τ i (1) τ i (2)… τ i ( i w -1) we compute sequences of event vector traces

τ i κ = τ i κ (1)τ i κ (2)… τ i κ ( i w -1) such that every τ i κ (j)
is the κ-length substring of τ i that finishes with τ i κ (j). For the first κ -1 elements of the trace sequence the event vector ε (zero vector) is used. Such traces are used to determine equivalent states, according to the following equivalence notion.

Definition 9: Two states of the identified system are κ-equivalent if their I/O vectors are the same and if the κ last observed event vectors that lead to these states are the same.

Following with the Example 1, the sequences of traces using κ = 2 are:

4.2

Building the basic structure

Representing event traces

Once the sequences of event vector traces have been obtained, every trace τ i κ (j) is related to a transition in the IPN through a function γ:T→{τ i κ (j)}; the firing of a transition implies that κ consecutive event vectors related to such a transition have been observed.

In order to preserve the firing order between transitions, dependencies are created between them and associated with an observed marking through the function

)} , ( | { : 0 M G R M M P i i u ∈ → ϕ µ
, which relates every non-measurable place with an observed marking, such that every transition has only one input place and one output place ( )

1 , = = ∈ ∀ • • r r r t t T t
. Notice that the number of non-measurable places is not predefined.

When an event vector trace τ i κ (j) is found again in a τ i κ , the associated dependency must be used if it leads to the same observed marking.

Let e j be the last event vector in the trace τ i κ (j); the associated transition will be denoted as j e r t (more than one transition may have associated the same e j ). This strategy can be systematically performed following the next procedure.

Algorithm 2. Building the basic IPN structure

Input: The set Then merge(current, p ini );

Γ κ = {τ i κ } Output: A PN structure G composed by p∈P u 1. T ←∅; ET ←∅; P←{p ini }; M 0 (p ini )←1;µ(p ini )←τ i (1); //

Properties of Algorithm 2

• Characteristics of G. The obtained model is a PN state machine (PNSM). After processing the first sequence, the PN graph yield is a circuit; afterwards, when previously created transitions whose associated traces have been found, such a transition and its input place are merged (step 2.2.2); thus the fusion preserves the structural nature of a PNSM. Since M 0 (p ini )=1, (G, M 0 ) is 1-bounded. • Complexity. Since search operation has linear-time complexity and the algorithm performs the addition of a transition for every computed trace that has not been yet observed, Algorithm 2 is executed in polynomial-time on the number of observed input/output sequences and their maximum length. • Completeness. The IPN G built through Algorithm 2 represents all and only all the trace sequences (sub-sequences) in Γ κ . In fact, by construction, every sequence τ i κ is represented in G by a circuit starting from p ini including the sequence of t r ej ; this circuit represents also the sequence τ i of events. Furthermore, the reuse of computed transitions having associated the same event traces, during the processing of subsequent τ i κ , is done only when common paths of length κ are built, that does not introduce other sequences.

Using the previous algorithm, the obtained PN corresponding to the three sequences of event vector traces of the Example 1 is showed in Figure 6. Notice that one of the sequences is not cyclic.

Figure 6. Basic model with sequences of event vector traces

Simplifying the basic structure

Additional node merging operations can be performed on the basic structure in order to obtain a simpler equivalent trace model. Now we can take into account the event vector e j associated to transitions. Consider the following transformation rules. Input: G Output: G', an equivalent IPN Apply the following rules on the initial place and iteratively on the merged places Rule 1:

∀ t a ej , t b ej ∈ p ini • | a ≠ b //
) • , p b = (t b ej ) • ; t i ∈ p ini • |t i ≠ t a ej , t i ≠ t b ej , p i = (t i ) • . After applying Rule 1, Lfp ini = e j (Lp a ∪ Lp b ) ∪ (∪λ(t i )Lp i )
; thus the language of G is not changed by the application of Rule 1. A similar reasoning can be done for Rule 2.

In the example, the application of the rules leads to the model of Figure 7a. Since the initial place has two input transitions associated to e 6 , they can merge and their input places can too.

Concurrent transitions

Other transformations may be performed when some events associated to transitions appear in different order in different sequences, describing their interleaved firing; this behaviour is exhibited by concurrent transitions in parallel paths in the model. The analysis can be performed on a model component comprised between two transitions t f and t j , which have respectively a single output place t f

• and t j • , which are relied by several paths containing the concurrent transitions. If there are m! paths, we can explore if there exists m different transitions in each path and the events sequence in every path appear as a permutation from each other. When it is verified, the subnet can be transformed into a component formed by m concurrent paths from t f and t j containing each one a transition related to one of the concurrent events. This transformation of G' preserves the same behaviour.

In Figure 7a, notice that between the transition associated to e 3 and the new transition associated to e 6 there are paths with all possible permutations of 4 and e 5 ; then, we can transform this into a concurrent component and we obtain the net showed in Figure 7b. Notice that this model preserves the same event vector sequences of the previous one. The equivalent fork-join structure obtained by this transformation is composed by m elementary paths composed by two places and one transition between the fork an join transitions. Each path will contain one token in one of its places; this substructure is 1bounded, the transformed PN is also 1-bounded.

The simplification by analysis of concurrency is not strictly necessary for representing the event vector sequences; however the equivalent model with concurrent transitions may be simpler. Although the analysis could be inefficient when the number of paths in the subnet is large, usually this number is reduced.

The aim of the simplification strategies given above is obtaining fairly reduced models useful for analyzing the DES behaviour, rather than minimizing the number of nodes in the obtained models.

Adding interpretation to the PN model 4.3.1 Representing outputs changes

Once the event vector sequences are represented in the basic model, it must be completed by adding the output and input changes. Recall that event vectors are computed from the difference of consecutive I/O vectors; thus an e j relates measurable places representing the outputs changes. This procedure is detailed in Algorithm 4.

Algorithm 4. Representing outputs changes

Input: G', {e i (j)} Output: H, the IPN including measurable places

Step 1. P ← P ∪ {p 1 , p 2 ,...,p q }.

Step 2.∀t r ej ∈ T: If e j (i) = -1 Then I(p i , t r ej ) = 1 and O(p i , t r ej ) = 0; If e j (i) = 1 Then I(p i , t r ej ) = 0 and O(p i , t r ej ) = 1; If e j (i) = 0 Then I(p i , t r ej ) = 0 and O(p i , t r ej ) = 0; Step 3. If component i of vector w j (1) is 1 Then M 0 (p i ) = 1 Else M 0 (p i ) = 0 The number of measurable places is then equal to the number of outputs. The net with measurable places for the example is showed in Figure 7c.

Model simplifying

Implicit non-measurable places can be removed; if there is a non-measurable place p k whose input and output transitions are exactly the same than any measurable place, then p k is deleted and its input and output arcs.

Representing input changes

Once the output adding and implicit places deleting has been performed, it only remains to add input information to complete the IPN model. Input information is associated with labels for transitions in a natural way given by the symbolic event input function.

Algorithm 5 describes a systematic way to do it.

Algorithm 5. Representing input changes

Input: H, λ'(e j ) Output: (Q,M 0 ) the final model of the identification process

Step 1.∀t r ej ∈ T, λ(t r ej ) ← λ'(e j )

The final model for the illustrative example is showed in Figure 8. The associated inputs for transitions are given by: λ(t 1 )=a_1, λ(t 2 )= ε, λ(t 3 )=b_1 c_1, λ(t 4 )=b_0, λ(t 5 )=c_0, λ(t 6 )=a_0.

Figure 8. Simplified IPN model

Completeness of the identified model

Since every one of the transitions in the net actually represents a sub-sequence of event vectors of length κ, the input-output language of length κ + 1 of the net is equal to the observed I/O language. Even, for the above example, the I/O language of the IPN is equal to the observed I/O language, i.e. only the observed cyclic I/O sequences are represented by the evolution of the net.

Proposition 1. For a DES S and an identification parameter κ, Algorithm 1 yields an IPN model (Q, M 0 ) which represents exactly L κ+1 (S).

1 _ a 1 _ , 1 _ c b ε 0 _ b 0 _ c 0 _ a A B C D Proof.
Since the deletion of implicit places does not change L κ+1 (Q,M 0 ), the proof is made with the model obtained before this procedure. The firing of a transition t in the system is not affected by the addition of arcs to and from t, since these arcs have been computed from output events (differences of output vectors) in Γ(S). Then, also in this model, every event vector sequence σ of length less or equal than κ belongs to the language of the net if and only if it has been observed.

The sequences of transitions of length less or equal than κ that can be fired, lead to markings in the measurable places that also belong to Γ(S) (since the marking change provoked in the measurable places was obtained from the difference of observed vectors).

Then, we have that sequences of observed output vectors of length less or equal than κ + 1 correspond to sequences of marking vectors in the net and L κ + 1 (Q) =L κ + 1 (S). ■

Further simplifications

The identification procedure takes into account any change in the inputs or outputs and represents it in the identified model; in such a model we often find consecutive input events that do not provoke output changes. This situation is due to variations in some inputs, during the system operation, which are not directly related with the outputs changes.

In systems where the number of inputs/outputs and the length of the sequences are large, the identified model size may grow because of this reason. Thus further reductions to the model can be done about the above mentioned sub-sequences of input events, allowing a more compact representation of the system's behaviour. For instance, consider the following I/O vector sequence w involving one input x and two outputs A, B:

                        =         1 0 1 0 1 1 0 1 0 w B A x
In this sequence the event x_1 appears first, and later an output change is produced; it can be represented as:

A →  1 _ x A →  ε B.
j i k j i    →  ≅ →  →  →  ... ...
This transformation is applied to paths in the PN model that do not include decision places. This is going to be illustrated on the case study included in Section 6.

Method implementation and application

This section presents a software tool for DESs identification and its application to a case study.

An operational identification tool

Based on the algorithms presented above, a software tool has been developed using Java (JDK 6 Update 11 for compiling and JRE 6 Update 26 for executing) to automate the IPN model synthesis. The architecture of the tool is showed in Figure 9.

The user interface allows capturing the input-output sequences and shows the obtained model graphically. Several data is provided to the tool in text files: the sequences, the parameter κ, the names of the input and output signals, and the output file name. Additionally it is specified the order in which inputs and outputs appear in the txt files and the index numbers of the signals to take into account if a mask is going to be applied. Figure 9. Software architecture Later, an input reader component processes these input files and transforms every input-output sequence into a vector. These vectors will be delivered to a component called Algorithm in which the identification algorithm is implemented. The output of this component is a dot file that can be treat by Graphviz (an open source graph visualization software: http://www.graphviz.org/) to generate an image file jpg.

The presented identification tool has been tested on many examples of diverse size and complexity, which have been previously solved following the identification procedures. For better understanding, we develop below a small size case of study.

Case study

We illustrate the use of the software tool through the identification of a small size manufacturing system obtained from [Roth, 2009] described on Figure 10. The purpose of such a system is to sort parcels according to their size. It has 9 PLC inputs, that are signals generated by the sensors of the plant for detecting positions (a0, a1, a2, b0, b1, c0, c1) and presence of parcels detection (k1, k2), and 4 PLC outputs, that are signals controlling the actuators of the plant (A+, A-, B, C).

Tuning the parameter κ

The parameter κ helps to distinguish sequences of events that look similar during the construction of the basic internal model; its value indicates the history of past events that have to be considered for deciding the state equivalence. On the one hand, high values of κ imply distinguishing more sequences avoiding path fusion during the model construction; thus the obtained models are more accurate but less compact. On the other hand low values of κ allow more state fusions; the obtained model are more compact but more paths can be created yielding an overrepresentation of the observed behaviour. In general it is not possible to establish a priori the value of κ, since it is assumed that the system is unknown. However, in practice the identification procedure can be applied using several values of κ (because it is not time consuming). Compact models allow a first approximation to the understanding of the system functioning, whilst larger models provide a more precise description. For small examples, such as that included in this section, κ=1 or κ=2 allows distinguishing event sequences whilst compact models are built.

In actual industrial systems the difference can be more drastic. Results in testing the algorithm on an industrial flexible manufacturing line called "Fischertechnik" [Roth, 2009] showed a more remarkable difference between the obtained models for several values of κ. The manufacturing line consists of three machines and three conveyors connecting them. The plant has 30 binary I/Os. During one production cycle, three work pieces are treated. The test has been performed using a Siemens PLC (CPU 315-2 DP); a database has been built using a reliable and efficient UDP (User Datagram Protocol) connection.

The database containing 100 input-output sequences whose length varies from 178 to 186, has been processed by the identification procedure using different values of κ from 1 to 6. Since the obtained models are huge, they are not showed herein; instead, the size of the identified models are summarised in table 1. The execution time of the identification procedure is also included to provide an idea of the performance of the algorithm. The tests have been performed in a Laptop computer based on an Intel Core 2 Duo T7300 processor at 2.00 GHz with 2.00 GB of RAM under Windows XP Professional 2002 Service Pack 3. The time has been measured excluding the execution of the Graphviz visualisation software.

Concluding remarks

Identification of automated concurrent Discrete Event Systems (DESs) has been addressed. The method herein proposed allows dealing with complex actual automated DESs because it takes into account technological characteristics of actual industrial 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.

Although in [START_REF][END_REF] and subsequent works the proposed algorithms are efficient, the identified models represent also non observed behaviour, due to the fact that the state equivalence is based on the observation of the same observed outputs vector, which is not very often the case for real systems; besides system's inputs are not taken into account. The Techniques based on ILP derived from [START_REF] Giua | [END_REF]] yield models representing exactly the event sequences regardless how the events are obtained from I/O data; however, they are limited to deal with few short event sequences. In [Klein 2005] and subsequent papers, both inputs and outputs are considered, however obtained FA models do not describe explicitly the input-output reactive behaviour nor output concurrent evolutions.

The black-box approach proposed herein allows obtaining IPN models from cyclic input/output vector sequences that represent the closed loop behaviour of PLC-based controlled plants. The proposed technique builds the IPN that is a close approximation of the compound controller-plant behaviour, which can be detailed later for controller redesign or model-based diagnosis purposes.

Current research deals with inference of cyclic sequences from a single long sequence and with the reduction of the obtained model by the analysis of the ulterior influence of inputs that apparently do not provoke changes in the outputs. Also, the inference of nonbehaviour regarding concurrent sub-processes is an issue to deal with.

Definition 1 :

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

  (current active step is #10; a and b are two input signals to the PLC; A and B are two output signals).

Figure 3 .

 3 Figure 3. A single input is the condition for state evolution

Figure 4 .

 4 Figure 4. Apparent simultaneous evolution of several inputs Let us now consider the specification described in Figure 5(a) in which the effect of input b is considered when the step 11 is active. Now consider the situation shown in the time diagram in Figure 5(b) in which input b changes its value from 0 to 1 before the change in a and then in A; after that b is taken into account to produce B.In this case the relationship cause-effect specified to activate step 11 cannot be captured simultaneously; however it will be detected only if we observe a sequence of 4 consecutive events.

  Consider the following language definitions used in the statement and solution of the identification problem. Definition 6: The set of observed input/output (I/O) words of a DES S with r inputs and q outputs is ,..

Example 1 .

 1 Consider a DES with q = 4 output signals, Φ = {A, B, C, D}, and r = 3 input signals Σ = {a, b, c}. Three I/O sequences have been observed; vector entries correspond to distribution [a b c | A B C D] T

w

  According to Definition 8, for every sequence w i , a sequence of observed event vectors

  Simplifying the basic structure.

Figure 7 .

 7 Figure 7. (a) Model after merging (b) Simplified basic model (c) IPN model including measurable places

FigureFigure 12 .

 12 Figure 10. Case study layout

  //Create an arc from current place to the new transitionIf j = |τ i κ | and µ(current) + e j = µ(p ini ) //The trace is the last one Then If ∃p in | p in = • (t r ej ), t r ej ∈ T, γ(t r ej ) = τ i κ (j) and µ(p in ) = µ(current) //Ifthere is a place with the same observed marking preceding a transition with the same label Then merge(current, p in ); current ← (t r ej ) • ; //Merge such a place with current Else Go to step 2.2.1 // τ i κ (j) ∈ ET is not considered If j = |τ i κ | and µ(current) + = µ(p ini ) //The trace is the last one

	Initialise the net (j); //Create a new transition labelled with the trace 2.1. current ← p ini ; //Keep track of the current place 2. ∀τ i κ ∈ Γ κ 2.2. ∀τ i κ (j) ∈τ i κ , 1 ≤ j ≤ |τ i κ | //Analyse every event trace 2.2.1. If τ i κ (j) ∉ ET //The trace is new Then ET ← ET ∪ {τ i κ (j) }; //Create a new transition label T ← T ∪ {t r ej }; γ(t r κ ej ) ←τ i ∀p a ∈ P I(p a , t r ej )←0; ej )←0; O(p a , t r I(current, t r ej ) ← 1; Then O(p ini , t r ej ) ← 1; //Create an arc from the transition to the initial place
	Else
	P ← P ∪ {p out }; //Create a new place ∀t b ∈ T
	I(p out , t b )←0; O(p out , t b )←0; µ(p out ) = µ(current) + e j ; O(p out , t r ej )←1; //Relate such a place with observed marking and add an arc from the transition to such a place

current ← p out //Take such a place as current 2.2.2. If τ i κ (j) ∈ ET //The trace is not new

preserves the trace sequences in G.

  Let us analyse the effect of Rule 1; let Lf pi = {λ(t 1 )λ(t 2 )...λ(t r )|t 1 ∈ p i • , t i+1 ∈ (t i • ) • }be the set of observable sequences from place p i . Consider t a ej , t b ej ∈ p ini • |a ≠ b; before applying Rule 1, Lfp ini = e j Lp a ∪ e j Lp

	Common prefixes ej ); merge((t a ej ,t b ej ) • , (t b ej ) • ) //Merging of transitions and their output places ej ∈ • p ini | a ≠ b // Common suffixes merge(t a Rule 2: ∀t a ej , t b merge(t a ej , t b ej ); merge( • (t a ej ), • (t b ej )) //Merging of transitions and their input places
	Properties of Algorithm 3
	• G' is a safe PNSM. The node fusions are performed similarly as in Algorithm 2, thus the structure remains as a PNSM.
	• G'

b ∪ (∪λ(t i )Lp i ), with p a = (t a ej

  This behaviour can be represented in a more

	compact way:	A x →  1 _	B	. In general, this transformation including several input events
	can be represented as:
		A		e	A	e	A	e	B	A	e	e	e k	B

Table 1 .

 1 Size of identified models for different values of κ.

	κ	Transitions	Places	Total of nodes	∆	Processing time
	1	541	375	916		516 ms
	2	748	580	1328	412	547 ms
	3	958	783	1741	413	547 ms
	4	1175	996	2171	430	562 ms
	5	1399	1212	2611	440	578 ms
	6	1623	1443	3066	455	609 ms

For space considerations we show the processing by the identification tool of nine cyclic I/O sequences; the text files including these sequences are showed in Figure 11. The vector entries correspond to the following distribution: [A+ A-B C k 1 k 2 a 0 a 1 a 2 b 0 b 1 c 0 c 1 ].

Figure 11. Input-output cyclic sequences of the case study After the execution of the identification process using κ=1, and before concurrence transformations, the model showed in Figure 12 is obtained; the identified model using κ=2 is showed in Figure 13. After some transformations of the model in figure 12 considering the phenomena described in section 6, the net in Figure 14 is obtained.

From the obtained model, we can infer the following behaviour:

-When a large parcel arrives (k1 and k2 rise), cylinder A is extended (A+ rise). After cylinder A pushes the parcel to the conveyor 3 (a0 falls, k1 falls, k2 falls, a1 rises, a1 falls and a2 rises), cylinder C extends (C rises) and cylinder A retracts to its initial position (Afalls). When parcel is completely pushed, cylinders retract to their initial position.

-When a short parcel arrives (only k1 rise), cylinder A is extended (A+ rise) until conveyor 2 is reached (a0 falls, k1 falls and a1 rises). Then, cylinder B extends (B rises) and cylinder A retracts (A-falls). When parcel is completely pushed, cylinder B retracts until its initial position. This interpretation is valid only for the observed behaviour. If the data collection has been made for a long time, we can state that the model is almost exact.

Notes on contributors


P Van Isacker

Partial and Quasi Dynamical Symmetries in Nuclei

Keywords: numbers: 03.65.Fd, 21.60.Fw, 24.60.Lz

One of the interesting aspects in the study of atomic nuclei is the strikingly regular behaviour many display in spite of being complex quantum-mechanical systems, prompting the universal question of how regularity emerges out of complexity. It is often conjectured that symmetries play a pivotal role in our understanding of this emerging simplicity. But most symmetries are likely to be broken, partial or both. Under such more realistic conditions, does the concept of symmetry still provide a basis for our understanding of regularity? I suggest that this requires the enlarged concepts of partial and quasi dynamical symmetry.

DYNAMICAL SYMMETRY

Symmetries are of central importance to physics. Classically they determine constants of motion and conserved quantities. In quantum mechanics they provide quantum numbers to label eigenstates, determine degeneracies and lead to selection rules that govern transition processes. A derived notion is that of dynamical symmetry concerning which, unfortunately, considerable semantic confusion exists and which is defined here following Iachello [START_REF] Iachello | Lie Algebras and Applications[END_REF]. While a hamiltonian with a given symmetry commutes with all transformations associated with that symmetry, this is no longer the case for a hamiltonian with a dynamical symmetry which only commutes with certain combinations of those transformations (called Casimir operators) which commute among themselves. As a result, eigenstates of a hamiltonian with a dynamical symmetry, as compared to those of one with a symmetry, are characterized by the same labels and obey the same selection rules but the feature of spectral degeneracy is relaxed. The symmetry breaking occurs for the hamiltonian but not for its eigenstates.

While dynamical symmetry might be unfamiliar as a term, the concept is used extensively in diverse areas of physics, and in particular in nuclear physics. Notable examples are Racah's pairing model [START_REF] Racah | [END_REF] and Elliott's rotation model [3], and their many extensions that can be formulated in terms of dynamical symmetries [START_REF] Frank | Symmetries in Atomic Nuclei[END_REF]. Lesser known are two further generalizations which have been developed over the last two decades, namely partial dynamical symmetry (PDS) [START_REF] Leviatan | [END_REF] and quasi dynamical symmetry (QDS) [6], and which are the subject matter of the present article. I will illustrate the basic ideas behind these extensions in the context of a simplified version of a nuclear model, while emphasizing that they are of generic applicability to any many-body problem as long as it can be formulated in an algebraic language.

THE INTERACTING BOSON MODEL AS A SYMMETRY LABORATORY

The interacting boson model (IBM) proposed by Arima and Iachello [7] is ideally suited to illustrate the notion of dynamical symmetry and its above-mentioned generalizations. The model in its simplest version assumes a system of N interacting bosons that have either spin 0 (s) or spin 2 (d). The bosons can be thought of as pairs of nucleons (neutrons or protons) in the valence shell of the nucleus [8]. Alternatively, the d bosons can be associated with quadrupole oscillations of the nuclear surface [9]. Over the years the IBM has revealed a rich algebraic structure, allowing a simple yet detailed description of many collective properties of nuclei. Numerical techniques exist to solve the secular equation associated with a general IBM hamiltonian. An additional characteristic feature of the model is that, for particular choices of the boson energies and the boson-boson interactions, this equation admits analytic solutions. This happens when the hamiltonian can be written as a combination of commuting Casimir operators of U(6), the algebra formed by the s and d bosons, and its subalgebras. The analysis of Arima and Iachello shows [10] that three such cases (that is, three dynamical symmetries) exist, corresponding to nuclear spectra with a vibrational [U(5)], a rotational [SU(3)] or a γ-soft [SO (6)] character. The essential symmetry properties of the IBM are captured by the hamiltonian of the so-called extended consistent-Q formalism (ECQF) [11], where nd is an operator that counts the number of d bosons and Qχ is the quadrupole operator of the model containing a parameter χ. The structural properties of the ECQF depend on the two parameters ξ and χ since ω is but an overall scale parameter. The conventional ranges of the two structural parameters are 0 ≤ ξ ≤ 1 and -√ 7/2 ≤ χ ≤ 0, and their extreme values (ξ, χ) = (0, anything), (1, -√ 7/2) and (1, 0) correspond to the U(5), SU(3) and SO(6) dynamical symmetries (or 'limits' for short), respectively. The entire physical parameter space can therefore be represented on a so-called Casten triangle [START_REF] Casten | Interacting Bose-Fermi Systems in Nuclei[END_REF], each point of which corresponds to a specific choice of the parameters in the ECQF hamiltonian. (It is possible to extend this triangle to include the region 0 ≤ χ ≤ + √ 7/2; this extension is important as regards the quantum phase transitions of the ECQF hamiltonian [START_REF] Jolie | [END_REF] but is not considered here in the discussion of its symmetry properties.)

ĤECQF = ω (1 -ξ)n d - ξ 4N Qχ • Qχ , (1)
One way to determine the symmetry properties of a given hamiltonian is with the help of its 'wave-function entropy' (WFE) [14]. For one of its eigenstates this quantity is defined asi α 2 i ln α 2 i where α i are the states amplitudes in a given basis which in the IBM are usually taken to be U(5), SU(3) or SO (6). A vanishing WFE therefore implies an exact U(5), SU(3) or SO(6) dynamical symmetry. For example, any eigenstate of an SU(3) hamiltonian has zero WFE in the SU( 3) basis (since one amplitude α i equals 1 and all others 0) but a large one in U(5). Figure 1 shows the averaged WFE for all eigenstates of the ECQF hamiltonian with angular momentum L = 0 in the three different bases. As expected, a blue region (low WFE) is found around the vertex that corresponds to the basis used. It is tempting to conclude from this figure that the interior region of the triangle is not amenable to any symmetry treatment. That conclusion would be wrong.

The results of figure 1 are found if one considers the WFE of all eigenstates (with L = 0) with respect to all quantum numbers in a given basis. But in most applications one's interest is confined to a few low-energy eigenstates. In addition, interesting symmetry properties may arise if some symmetries are broken while others are conserved. To uncover the existence of such cases, one considers the WFE of a subset of eigenstates of the ECQF hamiltonian and/or the decomposition of these eigenstates onto subspaces characterized by a single label of a particular subalgebra. There are many combinations of this kind and figure 2 shows the WFE for three choices of eigenstates and/or labels in an SO(6) basis (again for L = 0 but similar results are obtained for other L). From left to right the figure illustrates the three types of partialities as defined in Ref. [START_REF] Leviatan | [END_REF]: (PDS1) some eigenstates carry all the labels proper to a particular dynamical symmetry, (PDS2) all eigenstates carry some of its labels and (PDS3) some eigenstates carry some labels. A surprising result of figure 2, only recently recognized [15], is shown in the plot PDS3 SO(6) which quantifies the conservation of the SO(6) label in the ground state and uncovers an entire band of ECQF hamiltonians with approximate ground-state SO(6) symmetry.

Figure 3 provides another illustration of the baffling multitude of symmetry features of the Casten triangle. The plot PDS2 SO [START_REF] Leviatan | [END_REF] indicates to what extent the label of the SO(5) subalgebra-associated with d-boson seniority-is conserved for all eigenstates of the ECQF hamiltonian, and it turns out that the conservation of this label is exact for the entire U(5)-SO(6) transitional hamiltonian. This feature was noted a long time ago [16] and it can be shown, more generally, that the U(5)-SO(6) transitional hamiltonian is in fact integrable [17]. Another noteworthy result is shown in the plot PDS3 SO(5) of figure 3 which proves that a large area in the Casten triangle corresponds to ECQF hamiltonians with approximate SO(5) symmetry in the ground state. One may therefore expect selection rules associated with this symmetry to have a wide validity in nuclei.

One can similarly investigate the persistence of quasi-dynamical symmetry (QDS) in the ECQF hamiltonian. While QDS can be defined mathematically in terms of embedded representations [18], its physical meaning is that several observables associated with a particular subset of eigenstates may be consistent with a certain symmetry, which in fact is broken in the hamiltonian and its eigenstates. This typically occurs for a hamiltonian transitional between two dynamical symmetries which retains, for a certain range of its parameters, the characteristics of one of those limits [19]. This 'apparent' symmetry is due to a coherent mixing of representations in selected eigenstates. The criterion for the validity of QDS is not the WFE of individual eigenstates in a certain basis but rather the similarity of the decomposition in that basis for a subset of eigenstates. Figure 4 shows a quantitative measure of this similarity for yrast eigenstates of the ECQF hamiltonian with L = 0, 2, . . . , 10. It is defined as √ 1 -Θ where Θ is the average of Θ LL ′ = i α L i α L ′ i for all pairs L = L ′ , where α L i are the amplitudes of the yrast eigenstates with angular momentum L in a U(5), SU(3) or SO(6) basis. It is seen that large areas of the Casten triangle are blue (i.e., display QDS).

There are obvious connections between the symmetry concepts of PDS and QDS, as illustrated by comparing the plots PDS3 SO(6) in figure 2 and QDS3 SO (6) in figure 4 which have a similar structure. Even more surprising is the fact that areas of the Casten triangle exist where the partial conservation of one symmetry [SO( 6) PDS] is consistent with a coherent mixing of another, incompatible symmetry [SU(3) QDS]. The contrast of the results shown in figures 2 to 4 with those of figure 1 is startling. While dynamical symmetries are restricted to small regions in the parameter space (the blue areas in figure 1) and therefore can be expected to have only marginal applicability in nuclei, this is not the case for the extended concepts of PDS and QDS-see figures 2 to 4 where large bands of blue abound in the triangles. It is in fact difficult to find a spot in the Casten triangle that is not amenable to some symmetry treatment!

The ECQF is used here only to illustrate with figures the notions of PDS and QDS, and in no way do these results represent the complete symmetry analysis of the IBM. A general IBM hamiltonian with up to two-body interactions allows the occurrence of exact dynamical symmetries of various partialities [20], some of which are not or only approximately present in the ECQF. In addition, dynamical symmetries exist corresponding to different phase conventions [21], and these should be taken into account in a full symmetry study. Finally, three-body interactions between the bosons, which are to be expected given their composite nature, further enrich the symmetry features of the IBM [22]. It is remarkable that close to forty years after the proposal by Arima and Iachello, the full symmetry content of the IBM still remains to be uncovered.

AN EXAMPLE FROM THE SHELL MODEL: SENIORITY ISOMERS

Although most applications of PDS and QDS have been considered in the context of the IBM, they are by no means restricted to this model. As an illustration of this statement, I present an example taken from the shell model. The starting point is the original analysis of Racah [START_REF] Racah | [END_REF] who proved that the pairing interaction between identical fermions in a j shell is characterized by the seniority quantum number (usually denoted by υ) which counts the number of nucleons not in pairs coupled to angular momentum zero. Subsequent studies showed that seniority has a much wider applicability in the sense that any two-body interaction between identical nucleons conserves this quantum number as long as the angular momentum j of the shell is smaller than or equal to 7/2 [START_REF] De-Shalit | Nuclear Shell Theory[END_REF].

There are clear observational consequences associated with the conservation of seniority, one of them being vanishing E2 matrix elements between levels with the same seniority when the j shell is half filled [START_REF] De-Shalit | Nuclear Shell Theory[END_REF]. These findings are at the basis of the existence of so-called seniority isomers [START_REF] Grawe | [END_REF], nuclear levels with a half-life typically in the micro-second range, whose decay is hindered by this seniority selection rule. In the left part of figure 5 is shown the spectrum of 94 Ru [25], which has an 8 + isomer at 2.644 MeV with a half-life of 71 µs. The isomeric character of this level is a consequence of the slow E2 decay and the small energy difference with the 6 + level below it. In a first approximation, 94 Ru can be treated as a semi-magic nucleus with four protons in the 1g 9/2 shell to which a seniority classification can be applied. The expected seniority spectrum is shown in the middle of figure 5 and it is seen that two 4 + and two 6 + levels occur close in energy, with seniority υ = 2 (blue) and υ = 4 (red), respectively. Since for a general interaction seniority is not a conserved quantum number in a shell with j = 9/2, one would expect the states with the same angular momentum to mix, which in turn would modify the E2 decay of the 8 + level. This is not the case however, since it can be shown [26] that the states indicated in red have exact seniority υ = 4 for any two-body interaction. This is an example of a PDS in a fermion system, in this case associated with seniority. As a result of PDS, no mixing occurs, the predictions of the seniority scheme hold true and the isomeric character of the 8 + level depends essentially on its position relative to the 6 + level with seniority υ = 4.

In the right part of figure 5 is shown the spectrum of 72 Ni where the 6 + level with seniority υ = 4 is below the 8 + level, opening up an alternative decay path, which explains why the latter level is no longer isomeric but has a half-life of less than 20 ns [27]. Similar simple analyses can be done for other semi-magic nuclei and explain why the 8 + level is isomeric in 212,214 Pb and in 128 Pd [28].

It therefore transpires that the occurrence of isomers in several semi-magic nuclei is a consequence of the partial conservation of seniority. The problem can be recast as one of interacting fermions with half-odd-integer spin j and it can be shown [29] that the partial conservation of seniority is a very peculiar geometric (i.e., interaction-independent) property valid only for j = 9/2. A similar analysis can be carried out for particles with integer spin and it turns out that for bosons partial conservation of seniority is a prevalent phenomenon [30], the consequences of which (e.g., for Bose-Einstein condensates of atoms with integer hyperfine spin) still remain to be investigated.

EMERGING SIMPLICITY

In summary, the concept of dynamical symmetry is arguably too restrictive to analyze systems governed by complex dynamics. From the IBM example presented here, it is tempting to conclude that a satisfactory explanation of the emergence of regularity in complex systems requires the enlarged concepts of partial and quasi dynamical symmetry.

FIG. 1 :

 1 FIG.1: Illustration of the concept of dynamical symmetry (DS) for the ECQF hamiltonian. The plots show the wave-function entropy, in the three different bases U(5), SU(3) and SO(6) (left, middle and right), averaged for all eigenstates with angular momentum L = 0 and boson number N = 15. This quantity is a measure of dynamical symmetry and vanishes when all quantum numbers of the basis are exactly conserved for all eigenstates.

FIG. 2 :FIG. 3 :

 23 FIG. 2: Illustration of the concept of partial dynamical symmetry (PDS) for the ECQF hamiltonian. The plots show the wave-function entropy (WFE), in the SO(6) basis, of eigenstates with angular momentum L = 0 and boson number N = 15.From left to right is shown: (PDS1) WFE of the yrast eigenstate with respect to all labels of the SO(6) limit, (PDS2) WFE of all eigenstates with respect to the SO(6) label and (PDS3) WFE of the yrast eigenstate with respect to the SO(6) label.

FIG. 4 :

 4 FIG.4: Illustration of the concept of quasi dynamical symmetry (QDS) for the yrast eigenstates of the ECQF hamiltonian in the three different bases U(5), SU(3) and SO(6) (left, middle and right). The plots show a quantitative measure (as defined in the text) of the similarity of the decomposition in the different bases for the yrast eigenstates with even angular momentum L = 0 to 10 and boson number N = 15.

FIG. 5 :

 5 FIG.5: Energy spectra of94 Ru and 72 Ni. The 8 + level is isomeric in the former but not in the latter nucleus. The thickness of the arrows is proportional to the B(E2) values expected on the basis of a seniority classification, and therefore indicates the likely decay path followed in both nuclei. In the middle is shown a schematic spectrum of low-energy states with seniority υ = 0 (black), υ = 2 (blue) and υ = 4 (red).

Acknowledgements

I wish to thank José-Enrique García-Ramos, Stefan Heinze, Christoph Kremer, Amiram Leviatan and Norbert Pietralla, my collaborators in this work, and Richard Casten for many helpful suggestions.