Gwénolé Lecorvé
email: gwenole.lecorve@irisa.fr

Guillaume Gravier
email: guillaume.gravier@irisa.fr

Pascale Sébillot
email: pascale.sebillot@irisa.fr

Constraint selection for topic-based MDI adaptation of language models

Keywords: language model adaptation, topic terminology, minimum discrimination information, speech recognition

This paper presents an unsupervised topic-based language model adaptation method which specializes the standard minimum information discrimination approach by identifying and combining topic-specific features. By acquiring a topic terminology from a thematically coherent corpus, language model adaptation is restrained to the sole probability re-estimation of n-grams ending with some topic-specific words, keeping other probabilities untouched. Experiments are carried out on a large set of spoken documents about various topics. Results show significant perplexity and recognition improvements which outperform results of classical adaptation techniques.

Introduction

In large vocabulary automatic speech recognition (ASR) systems, unsupervised statistical language model (LM) adaptation is a key problem to face discourse variations in spoken documents of different task domains, e.g., shifts in style, epoch, topic, etc. Given a baseline LM trained on a large generalpurpose corpus, LM adaptation seeks to re-estimate n-gram probabilities so that they better represent a specific task domain, and hopefully lead to better transcriptions. Due to the LM training process, adaptation is commonly done by refering to a domain-specific corpus from which the n-gram probability distribution is re-estimated [START_REF] Bellegarda | Statistical language model adaptation: review and perspectives[END_REF]. However, in the field of topic LM adaptation, the corpus-based approaches mainly focus on the way to retrieve adaptation data for a given topic whereas they simply perform the n-gram re-estimation step through standard methods, without taking into consideration specificities of the topic adaptation task.

The work presented in this paper is in line with a completely unsupervised topic adaptation approach, detailed in [START_REF] Lecorvé | An unsupervised webbased topic language model adaptation method[END_REF], based on the retrieval of topic-specific corpora from the Internet, and which seeks both to avoid the use of a priori knowledge and to integrate Natural Language Processing (NLP) techniques. Hence, this paper does not study the adaptation data retrieval step but focuses on the LM re-estimating problem for the specific case of corpus-based topic adaptation, with the even constant will not to rely on a priori knowledge.

LM re-estimating techniques used in the topic adaptation field can be split into two main classes. First, n-gram probabilities or counts derived from a topic-specific LM or corpus can be directly interpolated with the ones of the baseline generalpurpose LM [START_REF] Chen | Using information retrieval methods for language model adaptation[END_REF]; this approach is not optimal since it attaches the same importance to any n-gram, disregarding its relevance to the topic. Second, the targeted adapted n-gram distribution can be seen as the solution of an optimization problem in which the baseline LM must maximize or minimize a given measure over a topic-specific corpus, leading to rescale independently the n-grams probabilities. Especially, the final distribution can be obtained using Minimum Discrimination Information (MDI) adaptation [START_REF] Della Pietra | Adaptive language modeling using minimum discriminant estimation[END_REF]. This latter approach is particularly interesting since it proposes a flexible adaptation scheme in which constraints on the targeted distribution can be almost freely set according to the adaptation task. In many topic adaptation works using MDI, constraints are derived from n-gram probabilities trained on topic-specific corpora. However, since these corpora are rather small to estimate reliable statistics, unigram probabilities are frequently used as the sole information source [START_REF] Federico | Efficient language model adaptation through mdi estimation[END_REF]. To circumvent this problem, [START_REF] Chueh | Reliable feature selection for language model adaptation[END_REF] proposes to also consider reliable higher order n-grams by computing confidence intervals from which inequality constraints are derived. Notwithstanding the good results of these works, they still do not take into consideration specifities of the topic adaptation task since n-grams are processed the same way, whatever their relevance w.r.t. the considered topic. Other works precisely seek to encapsulate more topic-specific information using MDI and various probabilistic latent semantic analysis techniques [START_REF] Tam | Unsupervised language model adaptation using latent semantic marginals[END_REF]. Probabilities to encounter a word in a given text are computed based on a worddocument co-occurrence matrix, a priori trained and decomposed into a static number of concepts. Finally, these unigrams are used to constraint the adapted LM. While these approaches propose a more adequate solution for the topic LM adaptation task, they rely on abstract concepts rather than directly on words which makes them difficult to combine with standard NLP techniques, as we are interested in. Furthermore, these techniques use pre-calculated topic knowledge which is excluded from our method, since we want it to be completely unsupervised.

In this paper, we aim at better understanding mechanisms that are useful for topic LM adaptation using the MDI framework. More precisely, this work adresses the problems of extracting and combining appropriate topic-specific features by using NLP techniques, which results in a new completely unsupervised LM adaptation method. While Section 2 recalls MDI main principles, Section 3 presents our topic-based feature selection and gathering method for LM adaptation. Finally, experiments and results are reported in Section 4.

Minimum discriminant information language model adaptation

The goal of MDI adaptation is to find out a new LM whose probability distribution satisfies some constraints derived from a specific task and whose relative entropy (minimum information) with the baseline LM is minimal. This section first introduces the general principles of MDI adaptation before discussing the way it is used in the frame of corpus-based topic LM adaptation.

Let us consider a baseline distribution PB over a set V n of n-grams, and k features of an information source, where fea-tures are observable characteristics of the source. The basic idea of MDI adaptation is to get the adapted distribution PA which solves a constraint system derived from the features, where each constraint i restrains a mass Ki to be spread over the n-grams recognized by the feature i [START_REF] Rosenfeld | A maximum entropy approach to adaptive statistical language modeling[END_REF]. Depending on the features chosen, the recognition criterion is also defined according to the adaptation task. This can be expressed by the constraints:

fi, PA = Ki, ∀i ∈ [1..k] (1)
where fi, PA = X

hw∈V n fi(hw)PA(hw), (2)
and fi is a feature function over n-grams hw, defined as:

fi(hw) = ( 1 if hw is recognized by feature i, 0 otherwise. (3)
Then, PA is defined as the solution of (1) which minimizes the Kullback-Leibler divergence with respect to PB:

PA = arg min P DKL(P ||PB). (4)
Considering the constraint system (1) to be consistent, PA can be computed using the Generalized Iterative Scaling (GIS) algorithm [START_REF] Darroch | Generalized iterative scaling for log-linear models[END_REF]. Due to computation complexity, GIS is often iterated only once, leading to the following rough PA(hw) estimate:

PA(hw) ≈ PB(hw) k Y i=1 " Ki fi, PB « f i (hw) N hw (5) = PB(hw) × α(hw) (6)
where N hw is the number of constraints recognized by the sequence hw, and α(hw) is called scaling factor. Finally, to fit LM structure, adapted conditionals can be written as:

PA(w|h) = PB(w|h) × α(hw) P ŵ PB( ŵ|h)α(h ŵ) . (7)
Since topic-specific adaptation corpora are usually small1 , the generic solution presented above is traditionally implemented in a manner that overcomes data sparseness and reliable probability estimating problems: n-grams hw ∈ V n sharing a same final token w are gathered into a same feature, and are rescaled according to the sole unigram probability P (w) trained on the topic-specific corpus and supposed as reliable [START_REF] Kneser | Language model adaptation using dynamic marginals[END_REF]. Given the topic-specific corpus Ca and its distribution Pa, the constraint system (1) can be written as:

f ŵ , PA = Pa( ŵ), ∀ ŵ ∈ V ( 8
)
where V is the ASR system vocabulary and f ŵ is defined as:

f ŵ (hw) = ( 1 if hw ends with ŵ, 0 otherwise. ( 9
)
According to [START_REF] Federico | Efficient language model adaptation through mdi estimation[END_REF], the scaling factor α(hw) reduces then to:

α(hw) = α(w) = Pa(w) PB(w) (10)
In many works [START_REF] Federico | Efficient language model adaptation through mdi estimation[END_REF][START_REF] Tam | Unsupervised language model adaptation using latent semantic marginals[END_REF][START_REF] Kneser | Language model adaptation using dynamic marginals[END_REF], α(w) is exponentially smoothed by a coefficient lower than 1, optimized on heldout data. However, in our experiments, we chose to use [START_REF] Kneser | Language model adaptation using dynamic marginals[END_REF] as it is, since this paper does not seek to perfectly tune a LM adaptation but rather aims at better understanding mechanisms that are useful for topic adaptation.

Topic-specific constraint building

Contrary to other MDI topic adaptation works, we consider that topic adaptation should not rely on all the ASR system vocabulary words, but rather only on the few ones which most contribute to the topic. These latter words constitute the topic terminology and are referred as terms. We also consider that, among these terms, some words have close meanings and, thus, play a same role within the topic adaptation. As a consequence, our goal is both to identify and to combine these terms in order to build topic-specific features. Based on these features, only a few n-gram probabilities will be re-estimated, keeping other probabilities untouched. After presenting a method to acquire a topic terminology from a topic-specific corpus, this section studies how the topic terminology can be integrated into the MDI framework through the questions of feature selection and of feature gathering. For illustration purposes, we report here results obtained on a development set of spoken documents for which topic-specific corpora have been automatically retrieved, as described in Section 4.

Topic terminology acquisition

Based on a topic-specific corpus, terminology acquisition seeks to highlight words which represent substantial notions of the topic. To do this, beyond methods coming from the terminology domain [START_REF] Drouin | Term extraction using non-technical corpora as a point of leverage[END_REF], our approach relies on Information Retrieval (IR) methods [START_REF] Kilgarriff | Comparing corpora[END_REF]. Given the topic-specific corpus Ca, each document d of Ca is projected into a high dimension space using the TF-IDF criterion leading to a normalized vector -→ v d :

- → v d = `σd (w1) • • • σ d (wN ) ´(11)
where σ d (wi) is a score depending on the frequency of the word wi in d and on the number of documents containing wi in a reference corpus 2 . In practice, when computing these scores, lemmas 3 are considered instead of words since the topic characterization task does not depend on the inflexion information.

Then, topic characterization -→ T of the whole corpus is computed as the average of all the normalized document vectors:

- → T = 1 |Ca| × P d∈Ca - → v d ( 12
)
in which words with highest scores are the most supposed to be related to the topic. Finally, a topic terminology is defined as the set of the n words with the highest scores in -→ T , noted as Tn. As an illustation of this method, Table 1 presents the set T30 obtained for a corpus dealing with atypical pneumonia4 .

Feature selection

Using such a terminology, one wish not to build constraints for all the n-grams but only for those recognized by a term. This brings the constraint set (8) to only consider unigrams of a terminology, as follows:

f ŵ , PA = Pa( ŵ), ∀ ŵ ∈ Tn ( 13
)
where n is an empirically set parameter. As it can be shown from [START_REF] Federico | Efficient language model adaptation through mdi estimation[END_REF] any topic-specific word reduces to 1, i.e., their probability is directly reported from the baseline LM except the normalization factor. Figure 1 presents word error rate (WER) and perplexity variations measured on our development set using either topic terminologies of different sizes or using the whole vocabulary. It appears that WER and perplexity gains obtained with topic terminologies are about the same as the one using classical unigram rescaling, even when considering only 500 words for the adaptation. One possible hypothesis to explain these results is that only topic-specific words contribute to perform the topic LM adaptation. Hence, other experiments have been carried out alternately using or excluding topic terminologies of 500 words (T500) and 5, 000 words (T5000). Perplexity, WER and lemma error rate 5 (LER) of Table 2 clearly show that adaptation has no effect when probabilities relating to topic-specific words are not adapted, which confirms our working hypothesis.

Feature gathering

In addition to selected features, the feature function used is also an important parameter in MDI adaptation since it splits n-grams in different classes, each corresponding to a target probability mass. In standard unigram rescaling method, n-grams are gathered according to their last word. However, semantic similarities shared by some words within the topic urge on gathering them into a same feature through the use of more appropriate feature functions. Hence, we tested two feature functions: a first one based on lemmas, defined by: and a second one which gathers all the words of a given terminology T in one same class:

f ℓ (hw) = ( 1 if
fT (hw) = ( 1 if w is in T , 0 otherwise. (15)
In practice, this latter feature function leads to consider only one constraint, meaning that all the topic-specific words have the same importance. Perplexity and WER measured using these two feature functions are compared to the ones obtained with the standard unigram method in Table 3. On the one hand, it appears that function fT is the worst function, probably because it is too rough. On the other hand, results show that gathering n-grams based on lemmas is nearly equivalent to the standard gathering based on words: while perplexity improvements are the same, WER is slightly worse when using lemmas. In the light of these preliminary results, we chose to discard the feature function fT for the backend experiments.

Experiments and results

Our ASR system is a multipass 65K words system based on two general-purpose LMs: a 3-gram LM to create word graphs from acoustic features and a 4-gram LM to score word graphs. Experiments are carried out on 172 thematically coherent segments from 6 hours of Broadcast News (BN) shows from the French radio BN corpus ESTER [START_REF] Galliano | The ESTER phase II evaluation campaign for the rich transcription of French broadcast news[END_REF]. These segments, coming from 3 different broadcasters and all dated from the same period of time, are spread over diversified topics (war in Iraq, national politics, sports, weather, etc.) and lengths (from 30 to 2,000 words). This collection is divided into a development set and a test set of respectively 91 and 81 segments. For each segment, a topic-specific corpus is automatically retrieved from the Internet, as detailed in [START_REF] Lecorvé | An unsupervised webbased topic language model adaptation method[END_REF], and transcription. In this section, results are presented for the test set using topic terminologies of 5, 000 words, which led to the best WER results on the development set, and of 500 words, which is an extreme case since it represents less than 1 % of the ASR system vocabulary. Adaptation is processed using a feature function either based on words (f ŵ ) or based on lemmas (f ℓ ). Perplexity, WER and LER are measured for each segment and compared to those obtained with our baseline LM, i.e., without topic adaptation, and using linear interpolation with an interpolation factor set to 0.8 after optimizing on the development set, and with MDI unigram rescaling (Table 4). First, one can notice that baseline results are much better than those obtained on the development set, especially the WER absolute difference is of 1.4. Then, it appears clearly that terminology-based unigram rescalings result in better improvements than linear interpolation and standard unigram rescaling, both being comparable. Especially, WER improvement obtained with T5000 and f ŵ is all the more interesting since it is very significant: p-values is of 2.556 × 10 -6 , with paired ttest, and of 4.251 × 10 -6 , with the paired Wilcoxon test. Even, results are better when using a small topic terminology (T500), which shows that only a few words contribute to establish the topic of a document and, as a consequence, that topic adaptation must not be performed for all the n-grams. This is all the more reasonable since adaptation data is sparse and not always reliable. Finally, as for the development set, recognition rates tend to be slighly worse when n-grams are gathered based on lemmas instead of words. This leads us to conclude that our assumption about the weak role of inflections for topic adaptation is probably too categorical. To bridge over the slight recognition differences, it could be interesting to integrate importance factors inside the n-gram classes, e.g., by considering non-binary feature functions.

Conclusion and future work

In this paper, we have presented a new LM adaptation method which specializes the general MDI adaptation framework for the specific case of topic adaptation using IR and NLP techniques. Especially, the standard unigram rescaling method has been refined, without relying on a priori knowledge, by automatically extracting topic terminologies from which different constraint building methods have been proposed. Experiments lead to significant perplexity and recognition gains which outperform gains of standard LM adaptation techniques. These results are all the more interesting since it appears that topic adaptation can be properly performed with very few topic-specific words whereas it cannot when these latter words are discarded.

Future work should explore three main directions. First, as discussed in Section 3.3, feature function used in MDI should better fit the topic adaptation task. Especially, relationships between n-grams should integrate more linguistic knowledge, e.g., lemmas, semantical similarities, etc., to adjust biases implied by adaptation data sparseness. Second, one should apply the feature selection scheme to higher order n-grams to characterize topic-specific phrases. However, this arises even more the sparseness problem. Finally, a topic-specific corpus may deal with different thematic aspects which should probably be treated separately. For example, when considering a document about a movie dealing with the conjugal duties, the topicspecific corpus may contain documents about cinema while others would get onto family life problems. For a better adaptation method, one should seek to identify the different thematic aspects of an adaptation corpus before processing them separately.

Figure 1 :

 1 Figure 1: Influence of the number of terms selected on WER and perplexity.

Table 1 :

 1 List of the 30 words with the highest scores obtained from a corpus of 200 documents about "atypical pneumonia".

	, scaling factor of n-grams which are not recognized by

Table 2 :

 2 Perplexity, WER and LER measured on the development set without topic LM adaptation (Baseline) and with different adaptation methods. In brackets, average perplexity relative variations and absolute WER/LER variations.

			T500	T5000
		No gathering	80.3 (-19%) 75.5 (-20%)
	PPL	Gathered by lemmas 77.0 (-19%) 74.2 (-20%)
		All gathered	89.2 (-7%)	94.0 (-3%)
		No gathering	21.3 (-0.8)	21.2 (-0.9)
	WER Gathered by lemmas	21.4 (-0.7)	21.4 (-0.7)
		All gathered	21.7 (-0.4)	21.92 (-0.2)

Table 3 :

 3 Perplexity and WER measured for different feature functions for two topic terminology sizes.

Table 4 :

 4 Perplexity, WER and LER measured on the test set without topic LM adaptation (Baseline) and with different LM adaptation methods. In brackets, average perplexity relative variations and absolute WER/LER variations.

In this paper, the average size of the topic-specific corpora is of about 700,000 words, which is very low w.r.t. the 400M words used to train the baseline LM.

800,000 articles from the French newspaper Le Monde, 1987-2003.

A lemma is a canonical form of a word. For example, plural nouns are reduced to their singular form, conjugated verbs are reduced to their infinitive form. . .

The words Toronto and Canada are listed here since the spoken document for which the topic-specific corpus has been retrieved is about a new screening method developed by Canadian researchers.

LER is the WER measured on lemmatized lexical words, i.e., nouns, adjectives and non-modal verbs reduced to their lemmatized form.


Laurent Miclet

Nelly Barbot

Baptiste Jeudy

Analogical proportions in a lattice of sets of alignments built on the common subwords in a finite language

Keywords: Locally maximal subwords, alignments, algebraic structure of sets of alignments

We define the locally maximal subwords and locally minimal superwords common to a finite set of words. We also define the corresponding sets of alignments. We give a partial order relation between such sets of alignments, as well as two operations between them. We show that the constructed family of sets of alignments has the lattice structure. The study of analogical proportion in lattices gives hints to use this structure as a machine learning basis, aiming at inducing a generalization of the set of words.

Introduction

Much has been done on finding maximal subwords and minimal superwords to a set of words, when the order relation is based on the length of words. We are interested in this paper in the same problem, but for the finer order relation based on the definition of a subword. Is there a manner to characterize the set of maximal subwords and that of minimal superwords, given a finite set U of words, according to this relation ? More than that, is there an algebraic relation between all these sets of subwords and superwords of U ? An answer to these questions would allow to give a precise definition to what the words of U share, and how this common core is organised.

The firsts parts of this paper gives a partial answer to these points. We define in section 2 a particular case of the notion of alignment, which will be useful for our construction. Actually, in section 3, we define two operations and an order relation on sets of alignments that leads to the construction of a lattice.

We are also interested in how this structure could be analysed in terms of analogical proportions, which could be used in machine learning. Since we start from a finite set of words, the convenient machine learning framework seems to be grammatical inference (from a positive set of positive samples, in our case). It seems that the lattice structure is particularly adapted to learning by analogy, since some natural analogical proportions can be observed in such a structure. We give in section 4 some hints on these points.

2 Maximal subword, minimal superword, alignment

Basics

Let Σ be an alphabet, i.e. a finite set of letters. A word u is a sequence u1 . . . un of letters in Σ. The length of u, denoted |u| is n. The empty word, of null length, is . A language is a set of words. A subword of a word u is a word obtained by deleting letters of u at some (non necessarily adjacent) positions4 in u. We denote u • v the shuffle of the two words u and v.

In Σ , the set of all words on Σ, we use the order relation ≤ defined by: (u ≤ v ⇔ u is a subword of v). When u is a subword of v, v is called a superword5 of u. For example: abc ≤ aabbcd.

A word w is a common subword to u and v when w ≤ u and w ≤ v. The word w is a maximal common subword to u and v if there does not exist any other common subword x to u and v such that w ≤ x. For example, ab and c are maximal common subwords to u = cadba and v = f agbhc, while a is a non maximal common subword. Defining a common maximal subword to a finite set of words is a straightforward extension.

A maximal common subword to two words and to a non empty finite set of words is defined in an analog way.

In a partially ordered set S, an antichain is a subset of S composed of pairwise incomparable elements. Any subset T of S can be reduced to a maximal antichain by removing from T every element of T lesser than another element of T .

Alignments

Definition

Definition 1 An alignment is a finite set of pairs (w, l) where w is a word and l a set of indices between 1 and |w|. The set l defines a subword of w denoted w[l]. Moreover, an alignment a must satisfy the following properties for all (w, l) ∈ a and (w , l ) ∈ a:

1. w[l] = w [l ] 2. (w = w ) ⇒ (l = l ) 3. (w ≤ w ) ⇒ (w = w )
The set of words on which the alignment is defined is called the support and is denoted word(a) = {w | ∃l ⊂ N with (w, l) ∈ a} .

According to our definition6 , the support is an antichain of words for ≤.

The set of indices l will be called the position of the indexed subword of w[l].

In the following, an alignment will be represented by a set of words in which some letters are boxed. For each element (w, l) of the alignment, the boxed letters represent the subword w[l] (also called the boxed subword of the alignment).

For legibility, the n words can be displayed in such a manner that the corresponding letters of w in the n words are in the same column. Some blanks can be added freely to help the reading. For example:

a =   a c b d e g a c e h g a h c d  
denotes the alignment a = {(acbdeg, {1, 2}), (aceh, {1, 2}), (gahcd, {2, 4})}.

We can write also without ambiguity: a = ( a c bdeg, a c eh, g a h c d).

Locally maximal alignments and locally maximal subwords

Generally speaking, two alignments on the same support W = {w1, . . . , wn} with the same boxed subword r can be different (having different set of indexes). We could define maximal alignments as those whose boxed letters are maximal subword of W . However, all interesting alignments would not be maximal with this definition. Consider for example the two words w1 = abcd and w2 = dabcab. The complete set of common subwords is { , a, b, c, ab, ac, bc, abc, d} and their set of maximal common subwords is {abc, d}.

But these two subwords are not sufficient to define the totality of the interesting alignments. Actually the alignment ( a b cd, dabc a b ) is somehow "maximal" since it is not comparable to the only alignment with the boxed subword abc, namely ( a b c d, d a b c ab).

This leads to define the following notion of locally maximal alignment and of locally maximal subword.

Definition 2 An alignment a = {(w1, l1), . . . , (wn, ln)} is locally maximal if there is no other alignment b = {(w1, l 1 ), . . . , (wn, l n )} on the same support such that for all i, li ⊂ l i .

Notice that the empty alignment ∅ is locally maximal.

Definition 3 The set of boxed subwords associated to all locally maximal alignments between a finite set of words W = {w1, . . . , wn} is called the set of locally maximal subwords to W and is denoted • (W ).

For some r ∈ • (W ), the set of locally maximal alignements associated to r is denoted Ar(W ).

We also define:

A(W ) = r∈ • (W )
Ar(W ).

For example, let us consider W = {ababc, cabd}, its sets of locally maximal alignments are given by A(W ) = A ab (W ) Ac(W ). Then, the set of locally maximal subwords of W is

• (W ) = {ab, c}

Language associated with an alignment

Definition 4 Let w = w1 • • • wp be a word, locally maximal subword of two words u and v at only one position (i.e. |Aw({u, v})| = 1). Then there exists an unique set of factors of u, denoted (u 1 , . . . , u p+1 ), and an unique set of factors of v, denoted (v 1 , . . . , v p+1 ), such that u = u 1 w1 . . . u p wpu p+1 and v = v 1 w1 . . . v p wpv p+1 . We define L(Aw({u, v})) as the following finite language:

L(Aw({u, v})) = (u 1 •v 1 )w1(u 2 •v 2 ), . . . , (u p •v p )wp(u p+1 •v p+1 )
The construction of L(Aw({u, v})) is shown in Figure 1, with straightforward graphic conventions.

u 1 v 1 w 1 u 2 v 2 w i u i+1 v i+1 w i w p-1 u p v p w p u p+1 v p+1 • • • • • Figure 1. The construction of L(Aw(u, v)) when |Aw({u}, {v})| = 1.
If |Aw({u, v})| > 1, L(Aw({u, v}) is defined as the union of all languages associated with all different positions of w as locally maximal subword of u and v. Finally, L(A({u, v})) is defined as the union of the languages L(Aw({u, v})), for all w locally maximal subwords of u and v.

Proposition 1 Let w be a locally maximal subword common to two words u and v and L(Aw({u, v})) constructed as above. We have:

1. All words in L(Aw({u, v})) are (non necessarily minimal) common superwords of u and v. 2. For any word W ∈ L(Aw({u, v})), we have

7 |W | + |w| = |u| + |v|.
Proof.

We firstly give an axample to show that a word of L(Aw({u, v})) can be a non-minimal superword of u and v.

We take the two words u = abcabb and v = aabbc. The associated alignment ( a b ca b b, a a b b c) is locally maximal. The language L(A abb ({u, v}) contains the language aabcab(b • c) and, in particular, the word w = abcabbc. The word w = abcabbc is another superword of u and v, and w ≤ w. Thus, w is not an locally maximal superword of u and v.

Then we demonstrate the proposition. Let us consider W ∈ L(Aw({u, v})). By definition of L(Aw({u, v})), there exists (u 1 , . . . , u p+1 ) and (v 1 , . . . , v p+1 ), respectively sets of factors of u and v, such that the word W can be written as W = x 1 w1 . . . x p wpx p+1 where, for every i ∈ {1, . . . p + 1},

x i ∈ (u i • v i ).
1. Therefore, for every i ∈ {1, . . . p + 1}, x i ≥ u i and x i ≥ v i .

We then have W ≥ u 1 w1 . . . u p wpu p+1 = u and W ≥ v 1 w1 . . . v p wpv p+1 = v.

2.

|W | = |x 1 | + |w1| + . . . + |x p | + |wp| + |x p+1 | = |w| + p+1 i=1 |x i | = |w| + p+1 i=1 |u i | + |v i | = |w| + (|u| -|w]) + (|v| -|w|) = |u| + |v| -|w| .

Constructive algorithms

We have devised an algorithm producing a finite automaton A • ({u,v}) which exactly recognizes the language • ({u, v}), the set of locally maximal subwords common to two words u and v, due to lack of space, we do not describe it here. It is based on the transformation of an 2-d array displaying which letters are common to two words into a finite automaton recognizing • (u, v) (see an example on figure 2(a)).

Starting from A • ({u,v}) , it is then simple to produce a finite automaton that we call A ({u,v}) which exactly recognizes the language L(A({u, v})) (also denoted ({u, v})). We display an example at figure 2(b).

Order relation and operations between alignments

In this section, we are interested in a particular family of alignments, since we want to describe what have in common the subwords and superwords of a finite set U of sentences. We will consider alignments on U , i.e. alignments with a support subset of U . Moreover, we will assume that U is an antichain according to the order relation ≤.

Order relation

Definition 5 (Order on alignments on U ) Given two alignments on U a = {(w1, l1), . . . , (wn, ln)} and b = {(w 1 , l 1 ), . . . , (w m , l m )}, we write a

b if for all i ∈ (1, n), it exists j ∈ (1, m) such that 1. wi = w j 2. l j ⊆ li Therefore, if a b, then word(a) ⊆ word(b).
It is easy to check that is a partial order relation on the set of alignments and that the empty alignment ∅ is smaller than every other alignment.

Definition 6 (Homogeneous sets of alignments) A set of alignments is homogeneous if it is non empty and all its elements have the same support. The family of homogeneous sets of locally maximal alignments is denoted AH .

In order to link this definition with definition 3, we can notice that, for any subset W of U , A(W ) ∈ AH .

Definition 7 (Order on homogeneous sets of alignments on U ) Let A and B be two homogeneous sets of alignements. We have Proposition 2 is a partial order on AH and the smallest element is {∅}.

A B if for all b ∈ B, there is a ∈ A such that a b.

Proof.

Reflexivity and transitivity are immediate. In order to check the antisymmetry, let us consider two homogeneous sets of locally maximal alignments, denoted A and B, such that: A B and B A. Since A and B are homogeneous, all alignments in A have the same support, denoted word(A), and the same holds for B, with the support denoted word(B). From the definition of , we easily check that word(A) = word(B). Let us consider b1 = {(w1, l 1 ), . . . , (wn, l n )} ∈ B: since A B and B A, it exists a ∈ A and b2 ∈ B such that a b1 and b2 a. By transitivity, we have b2 b1. At last, b1 and b2 having the same support and being locally maximal, it implies that b1 = b2 and then a ∈ B. Hence, A ⊆ B. Similarly, we can check that B ⊆ A.

Definition and properties of

(i, k), if (w k = ui) then (L k ⊆ li) 3. for all (j, k), if (w k = vj) then (L k ⊆ l j )
Secondly, we denote a b the set of minimal elements of a + b according to .

As consequence, if • ({r, s}) = ∅, then the boxed word in c ∈ a+b is a subword of r and s, else, no letter is boxed in c. In addition, if a and b contains an identical word ui = vj such that li ∩ l j = ∅, no letter is then boxed in c.

The operation is extended to homogeneous sets of alignments by the following definition. There is no equivalent relation between and inf for all homogeneous sets of alignments, we must restrict to sets of all alignments built on a given set of words.

Definition 12 If U is a finite collection of words, we define the collection of sets of alignments

A(U ) = {A(V ) | V ⊆ U }.
Proposition 6 Let A and B be sets of alignments in A(U ). Then, in A(U ), inf (A, B) exists and:

inf (A, B) = A B Proof. • First, we show that if A = A(V ) and B = A(W ) with V ⊆ U and W ⊆ U then A B = A(W ∩V ). Let c ∈ A B. c is a loc- cally maximal alignment on its support word(A) ∩ word(B) = W ∩ V , thus c ∈ A(W ∩ V ). Let c ∈ A(W ∩ V ).
Let a be an alignment on W such that c a, then c is obtained from a ∈ A using the definition of A B and c ∈ A B.

• Let C ∈ A(U ) be a set of alignments smaller than A and B. We show that C is smaller than A B. Some alignments of C are smaller than alignments of A and others are smaller than alignments of B. Since C is homogeneous, its support word(C) must be included in word(A) ∩ word(B) and since

C = A(T ) for some T ⊆ U , then T ⊆ V ∩ W . Therefore A(T ) A(V ∩ W ) which is exactly C A B.
Proposition 7 Let U = {u1, u2, • • • , un} be a finite set of words, the operations and are internal to A(U).

Proof. For it is a consequence of the previous definition. For , it is not difficult to see it from the definition of .

Proposition 8 Let U = {u1, u2, • • • , un} be a finite set of words, antichain for ≤. Then U = (A(U ), , ) is a lattice. This lattice is said to be built on the finite language U .

Proof. This is a direct consequence of the three previous propositions. These requirements are often called the axioms of analogical proportion (see [START_REF] Lepage | De l'analogie rendant compte de la commutation en linguistique[END_REF]).

Analogical proportions between words

A first definition using factorization. According to Yvon and Stroppa [START_REF] Stroppa | Analogical learning and formal proportions: Definitions and methodological issues[END_REF] a general definition of analogical proportion, conform to the axioms, can be given in many different cases thanks to the notion of factorization. We show here how it applies in Σ , and we will come back later to its use in general lattices.

Definition 14 (Analogical proportions between words.) (x, y, z, t) ∈ Σ are in analogical proportion, which is denoted x : y : z : t , if and only if there exists a positive integer n and two sets of words (αi) i∈[1,n] and (βi) i∈[1,n] ∈ Σ such that: The authors have shown that this definition is conform to the axioms.

Another definition using alignments. This second definition, with the associated algorithms, is given in [START_REF] Miclet | Analogical dissimilarity: Definition, algorithms and two experiments in machine learning[END_REF]. The axioms of analogical proportion are verified as well.

Definition 15 Let u, v, w and x four words in Σ . We assume that an analogical proportion is defined on Σ. We extend this relations to Σ = Σ ∪ { }, adding the proportions a : :: a : for all a ∈ Σ. Then u, v, w and x are in analogical proportion in Σ if there exists an alignment between the four words such that every column of the alignment is an analogical proportion in Σ . The following alignment shows that there is an analogical proportion in Σ between the four words CaCA, CcbBA,bAc and bCbb.

Example

    C C b b a c A C b b C B c b A A    
Note that there is no boxed letter in this alignment. It can happen anyway in the case of a column such that a : a :: a : a.

Links between the two definitions. The second definition using alignments is shown to imply the first one (not the reverse). However, a straightforward modification of the first one lead to a complete equivalence [START_REF] Hassena | Apprentissage par analogie de structures d'arbres[END_REF].

Analogical proportions in a lattice

Using the factorization technique, Stroppa and Yvon [START_REF] Stroppa | Analogical learning and formal proportions: Definitions and methodological issues[END_REF] have found that a general definition of an analogical proportion can be given in a lattice. Unfortunately, his definition was uncomplete. We give here the complete one.

Definition 16 For four elements (x, y, z, t) ∈ (L, ∨, ∧) 4 , the analogical proportion denoted (x : y :: z : t) is true if and only if:

x = (x ∧ y) ∨ (x ∧ z) and x = (x ∨ y) ∧ (x ∨ z) y = (x ∧ y) ∨ (t ∧ y) and y = (x ∨ y) ∧ (t ∨ y) z = (t ∧ z) ∨ (x ∧ z) and t = (t ∨ z) ∧ (t ∨ y) t = (t ∧ z) ∨ (t ∧ y) and z = (t ∨ z) ∧ (x ∨ z)
The geometry of this definition is displayed in figure 3.

A simple example of proportion in a lattice is given by the following property:

x ∧ z t ∧ z t ∧ y x ∧ y y t x z x ∨ z t ∨ z t ∨ y x ∨ y

Learning from U

After having given the basis in the previous sections, we give preliminary here remarks and hints concerning some possible extensions of this work to applications, via machine learning, in connexion with analogical proportions and lattice structure. Firstly, when investigating the connexions between locally maximal subwords, locally minimal superwords and analogical proportions, a first property is easy to show from definition 15 and proposition 1. However, what we are really interested in is to find how using the lattice U and its analogical properties to generalize U . As a second remark, we note that any homogeneous set of alignments A in U represents an intensional definition of the finite language (A), the set of locally minimal superwords common to all the words in the support8 of A. We can also construct, as indicated in section 2.4, a finite automaton as an intensional representation of this language, with the syntactic analysis facility. Therefore, we have potentially at our disposal a lattice of finite automata, in connection with the lattice of subsets of U : each automaton recognizes a finite language which is a particular generalization of the associated support, itself a subset of U .

We denote hereafter ≤ the order relation between finite set of words derived from the subword relation ≤, defined by: M ≤ N iff ∀m ∈ n, ∃ n ∈ N such that m ≤ n. For example, {ab, c} ≤ {abcd, e}. There is an partial inclusion relation between the languages recognized by this lattice of automata, compatible with that of the subsets, since the following property holds.

Proposition 11 For any subsets J and K of U , the three following relations are equivalent:

L(A(J)) ≤ L(A(K)), J ⊂ K and • (K) ⊂ • (J).
Note that the exploration of such a lattice of automata, constructed on a finite set of positive examples, is the basis of the efficient finite automata inference, see [dlH10]. This could be one basis for the use of our lattice in machine learning.

Another threads to follow could be the idea of analogical closure of a finite language, as described in [START_REF] Lepage | De l'analogie rendant compte de la commutation en linguistique[END_REF] and that of analogical generation, see [START_REF] Bayoudh | Learning a classifier with very few examples: analogy based and knowledge based generation of new examples for character recognition[END_REF]. In both, a triple of words is taken in the learning sample and a fouth sentence is generated, under the constraint that the four sentences are in analogical proportion. It is not yet clear to the authors how this technique can be combined with the lattice structure, but this could be a connection with the area of machine learning on the basis of formal concepts, as in [START_REF] Kuznetsov | Machine learning on the basis of formal concept analysis[END_REF].

Conclusion and related work

The problem of finding one longest common subsequence (subword) or one shortest common supersequence (superword) to two or more words has been well covered (see e.g. [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences[END_REF], pp 287-293 and 309, [START_REF] Irving | Two algorithms for the longest common subsequence of three (and more) strings[END_REF]). However, to the best of our knowledge, the problem of finding an intentional definition to the sets of maximal subwords and minimal superwords of a set of words has not been explored yet. In this, we have produced, via the construction of a lattice of alignement sets, an interesting subset of minimal superwords and maximal subwords to a set of words. We have not worked yet neither on the theoretical complexity of the construction of the lattice of alignments, nor on its practical complexity and applications. Hereafter we give some bibliographical hints to this problem.

A complexity result (sometimes misinterpreted) is given by Maier [START_REF] Maier | The complexity of some problems on subsequences and supersequences[END_REF] who has demonstrated that the "yes/no longest common subsequence problem" and the "yes/no shortest common supersequence problem" are NP-complete for alphabets of sufficient size. These problems are defined as follows: "Given an integer k and a set of sequences R, is |LCS(R)| ≤ k ? Is |SCS(R)| ≥ k ?" where |LCS(R)| and |SCS(R)| are the length of a longest common subsequence and the length of a shortest common supersequence of R.

It is also true that finding the length of a shortest (longest) super(sub)sequence common to a set of k sequences is in 9 O(m1 . . . m k ), with mi the size of the i-th of the k sequences, hence exponential in k.

The works of Fraser and Irving [START_REF] Fraser | Maximal common subsequences and minimal common supersequences[END_REF] have produced algorithms to find the longest minimal common supersequence (superword) and the shortest maximal common subsequence, according to the order relation ≤.

Yvon and Stroppa [START_REF] Stroppa | Analogical learning and formal proportions: Definitions and methodological issues[END_REF] give a definition of an analogical proportion between words and also within lattices. Our objective is to use the properties of the lattice structure on alignement sets to solve the associated analogical equations.

A

  ab (W ) = { ( a b abc, c a b d), ( a ba b c, c a b d), (ab a b c, c a b d) } Ac(W ) = {(abab c , c abd)} .

  Figure 2. Constructing the languages (r, s) and (r, s)

Definition 8

 8 Let a ∈ Ar({u1, • • • , un}) and b ∈ As({v1, • • • , vm}), where a = {(u1, l1), . . . , (un, ln)} and b = {(v1, l 1 ), . . . , (vm, l m )}. Firstly, we construct a + b, the finite set of alignments c = {(w1, L1), . . . , (wp, Lp)} such that 1. {w1, . . . , wp} = word(a) ∪ word(b) 2. for all

Definition 9

 9 Let A and B be two homogeneous sets of alignments. We define A B as the set of the minimal elements of A+B according to whereA + B = b∈B a∈A (a + b)Proposition 3 The operation is internal to AH , commutative and idempotent.Proof. Let us consider A ∈ AH and B ∈ AH .1. All the alignments in A B are locally maximal by definition and have the same support, namely word(A) ∪ word(B).2. The commutativity is straightforward. 3. Let a be an element of A, it is immediate that a ∈ (a + a) ⊆ A + A. Moreover, since A ∈ AH , a is a locally maximal alignment, and so a ∈ A A. Consequently, A ⊆ A A. Reciprocally, let c be an element of A A. Then it exists a couple (a, b) ∈ A 2 such that c ∈ a + b. Since A ∈ AH and word(c) = word(a) ∪ word(a), a, b and c have the same support. Moreover, from definitions 5 and 8, a c and b c. c being a minimal element of A + A according to , and a and b belonging to A + A, it turns out that a = b = c. At last, c ∈ A. Hence A A ⊆ A. is then idempotent on AH .

3. 3 Proposition 4

 34 Construction of Definition 10 Let a ∈ Ar({u1, • • • , un}) and b ∈ As({v1, • • • , vm}) where a = {(u1, l1), . . . , (un, ln)} and b = {(v1, l 1 ), . . . , (vm, l m )}. We construct a b, the finite set of alignments c = {(w1, L1), . . . , (wp, Lp)} such that 1. {w1, . . . , wp} = word(a) ∩ word(b) 2. Either, for all (i, k) such that w k = ui we have li ⊆ L k , or for all (j, k) such that w k = vj we have l j ⊆ L k . 3. c is a locally maximal alignment. An alignment in a b is thus based either on a restriction of a to the support word(a) ∩ word(b) or on a restriction of b to the same support. For instance, if a = {( a cd, ab a c, a ba)} and b = {(a c d, aba c , c a)}, then a b = {( a c d, a ba c ), ( a c d, ab a c )}. The operation is internal to AH , commutative and idempotent. Proof. The commutativity is straightforward (definition 10 is symetric wrt a and b). For idempotence, we use the fact (direct consequence of the definition) that if a and b are locally maximal alignements on the same support, then a b = {a, b}. Let us consider A ∈ AH : if a ∈ A then a ∈ (a a) ⊆ (A A) and therefore A ⊆ A A. If c ∈ A A, then there exists (a, b) ∈ A 2 such that c ∈ a b. Since a and b have the same support, either c = a or c = b, therefore c ∈ A and A A ⊆ A. 3.4 Structure of homogeneous sets of alignments on U We define sup (A, B) as the minimal set of alignments larger than A and B (if it exists) according to . Similarly, inf (A, B) is the maximal set of alignments smaller than A and B. Proposition 5 Let A and B be finite homogeneous sets of alignments. Then sup (A, B) exists and: sup (A, B) = A B Proof. • First, we show that A B is greater than A and B for . Let c ∈ A B. By construction, there exist a ∈ A and b ∈ B such that c ∈ a b ⊆ a + b. By the first item of definition 8, word(a) ⊆ word(c) and by the two other items, we can conclude that a c. Thus for every c ∈ C there is a ∈ A such that a c. Thus A A B and B A B. • Let C be a set of alignments greater than A and B, and let c ∈ C. There are a ∈ A and b ∈ B such that a c and b c. We need to find c ∈ A B such that c c. Remove from the support of c all words not in the support of a or b. The obtained alignment may not be locally maximal, so we add more boxed letters to make it locally maximal. The result alignment c satisfies all conditions of Definition 8, thus A B C and therefore sup (A, B) = A B.

4

  Analogical proportions in the lattice U 4.1 The axioms of analogical proportion Definition 13 (Analogical proportion) An analogical proportion on a set E is a relation in E 4 such that, for all 4-tuples A, B, C et D in relation in this order (denoted A : B :: C : D ): 1. A : B :: C : D ⇔ C : D :: A : B 2. A : B :: C : D ⇔ A : C :: B : D For every 2-tuple, one has : A : B :: A : B It is easy to show that five other proportions are equivalent: B : A :: D : C D : B :: C : A D : C :: B : A B : D :: A : C C : A :: D : B

x

  = α1. . .αn, t = β1. . .βn, y = α1β2α3. . .αn, z = β1α2β3. . .βn ou x = α1. . .αn, t = β1. . .βn, y = β1α2β3. . .αn , z = α1β2α3. . .βn and ∀i, αiβi = .Example. reception : refection :: deceptive : defective is an analogical proportion between sequences, with n = 3 and the factors : α1 = re, α2 = cept, α3 = ion, β1 = de, β2 = f ect, β3 = ive.

  Let Σ = {a, b, c, A, B, C} an alphabet with the analogical proportions a : b :: A : B , a : c :: A : C , c : b :: C : B .

Figure 3 .

 3 Figure 3. The general analogical proportion in a lattice.

Figure 4 .

 4 Figure 4. A canonical proportion in a lattice: (y : y ∨ z :: y ∧ z : z).

Proposition 10

 10 Let w = w1 • • • wp be a locally maximal subword of two words u and v. Then: ∀t ∈ L(Aw({u, v})), ∃w ∈ • (u, v) such that t : u :: v : w ∀w ∈ • (u, v), ∃t ∈ L(Aw({u, v})), such that t : u :: v : w Take u = abcabb and v = aabbc with the maximal subword y = abb. The alignment ( a b ca b b, a a b b c) is locally maximal. The language L(A abb ({u, v}) contains the word w = abcabbc. The facing figure displays the analogical proportion w : u :: v : y

IRISA-Dyliss, Rennes France. miclet@enssat.fr

IRISA-Cordial, Lannion France. barbot@enssat.fr

Université de Saint-Étienne, Laboratoire Hubert Curien. baptiste point jeudy at univ-st-etienne point fr

Other terms for subword are subsequence and partial word. A factor, or substring is a subword of u built by contiguous letters of u.

A superword of u, also called a supersequence must not be confused with a superstring of u, in which the letters of u are contiguous. In other words, u is a factor (a substring) of any superstring of u. See[START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences[END_REF], pages 4, 309 and 426.

An alignment (regardless of the third point of our definition), is called a trace by Wagner and Fisher[START_REF] Wagner | The string-to-string correction problem[END_REF] for two words and a threading scheme in Maier[START_REF] Maier | The complexity of some problems on subsequences and supersequences[END_REF].

A consequence of this assertion is : let LCS(u, v) be a longest common subword to u and v and SCS(u, v) be a shortest common superword to u and v. Then we have:|LCS(u, v)| + |SCS(u, v)| = |u| + |v|.

Remember that this support, that we have denoted word(A), is a subset of U .


Damien Foures
email: dfoures@laas.fr

Vincent Albert
email: valbert@laas.fr

Jean-Claude Pascal

ACTIVITYDIAGRAM2PETRINET : TRANSFORMATION-BASED MODEL IN ACCORDANCE WITH THE OMG SYSML SPECIFICATIONS

Keywords: MDE, ATL, TINA, transformation, verification, Petri Nets, SysML, OMG, VHDL-AMS, Ecore

This study aims to automate the transformation of activity diagrams (AD) to Petri nets (PN). Based on specifications given by the Object Management Group (OMG), we have established transformation rules in ATLAS Transformation Language (ATL) to obtain a model consistent with our Petri Net meta-model (model2model). The semantic of Activity Diagram was verified with PetriNet2Tina transformation (model2text) and has allowed us to verify that was the same in the corresponding PN. This verification is done with the "model-checker" TIme petri Net Analyzer (TINA) and Linear Temporal Logic (LTL) language. The user needs only to set up the Activity Diagram from the stakeholder requirements; the transformation and verification is automatic. PetriNet formalism could enable us to provide valuable information on a Activity Diagram, to execute and simulate it.

INTRODUCTION Context

The present work is based on the general context of systems engineering and integration of heterogeneous systems. These systems have software and hardware components, they generally hold high real-time constraints and disciplines (electrical, mechanical, information, hydraulic...). We seek to propose methods and tools for controlling the development cycle of such systems. The use of models and simulation is becoming dominant component in the development cycle, and we seek to improve (and eventually to automate) their use. The use of meta-modeling moves in this direction as it aims to make the modeling. Based on the instantiation of the meta-model, more clearer and less ambiguous.

Approach

Our approach uses the concepts advocated by the OMG through Model Driven Architecture (MDA), itself based on modeling and automatic transformation of models into other models. Presently we have the TINA formalism (LAAS 2011), TINA toolbox (LAAS 2011), and a transformation procedure from PN to VHDL-AMS (Albert et al. Octobre 2005). TINA formalism allows us to verify formally that Activity Diagram properties are preserved, using its model-checking tool (selt). The transformation to VHDL-AMS (IEEE 1999) allows us to propose a simulation phase, commonly called virtual prototyping. The addition of these two approaches allows us to validate the discrete and continuous part of the activity diagrams, and hence predict functional characteristics of the system. In this work, we begin with a method to create metamodels of AD and PN. We will see a suggestion of concept mapping and its verification, and finally a simple example of transformation. Till date transformation from State Machine to PetriNet were made [START_REF] Bernardi | From UML sequence diagrams and statecharts to analysable petri net models[END_REF], [START_REF] Campos | On the Integration of UML and Petri Nets in Software Development[END_REF], but Activity Diagrams (ADs) accentuate the internal control and data flow of systems. Further work on ADs were made [START_REF] Bonhomme | Methodology and Tools for the Design and Verification of a Smart Management System for Home Comfort[END_REF][START_REF] López-Grao | From UML activity diagrams to Stochastic Petri nets: application to software performance engineering[END_REF] or (Thierry-Mieg and LHillah 2008) but do not take into account many properties of ADs.

SYSML PRESENTATION

SysML is a graphical modeling language developed by OMG and INCOSE. SysML is a UML profile adapted to systems engineering emerged in the 2000s. It can model the behavior of systems (continuous and discrete), with a hierarchical approach. OMG SysML specifications appeared only in 2007. We extracted the meta-model from (OMG 2010c) and (OMG 2010b) .

Activity Diagram

The activity diagram is one of the four behavioral diagrams included in SysML. They are useful to describe a hierarchical behavior, delayed, or a mixed systems. The TOPCASED framework permits to describe graphically all AD in accordance with the AD meta-model, itself in accordance with the Ecore [START_REF] Budinsky | Eclipse Modeling Framework[END_REF] metameta-model. The Meta-Object Facility (MOF) is preconized by OMG, but Ecore is more or less aligned on Essential MOF (EMOF).

Activity Diagram Meta-model

The AD meta-model was extracted from OMG specification as described therein, without addition. Small part of it with ControlNode meta-class is shown in figure 1. We see that FlowFinalNode and ActivityFinalNode inherit FinalNode. The FinalNode inherits to Con-trolNode as InitialNode, similarly ForkNode, JoinNode and MergeNode. To create the AD meta-model, it is easier to begin with basic node of AD, directly afterwards all properties, all links with other meta-class were extracted. The biggest difficulty was to know where to stop the meta-model extraction. Indeed, in (OMG 2010c) and (OMG 2010b) all classes inherit from many other classes from SysML and UML metamodels. Subsequently it uses the AD meta-model from TOPCASED 1 framework. First, we have verified compliance with OMG specification for parts we have used.

PETRINET PRESENTATION

A PetriNet is a mathematical modeling language. There are currently a lot of Petri nets classes. Gradually basic, hierarchical and differential predicate transition Petri nets, will be transformed to, the control part, the hierarchy, and finally the continuous part of the activity diagram. A Petri net is composed of places, transitions, and arcs. Arcs connect a place to a transition or a transition to place, others possibilities are forbidden. This kind of constraint must appear in the meta-model of PN.

1 http://www.topcased.org/

PetriNet Meta-model

The PN meta-model established in (Albert et al. Octobre 2005) was adapted to this new work. Macroplace and macro-transition were removed because they are restrictive. For example, if an ActionNode of AD is transformed into macro-place it is impossible to put new value in this macroplace during execution. During execution macro-node becomes totally independant, so we decided to work flat. Flat PN, without hierarchy, are more easy to master communication links. TINA works also on only one abstraction level. Figure 2 shows a simplified version of PN meta-model. We can read on it: PetriNet is composed of Node and ArcClassic. A node can be a Transition or a Place and they are linked with ArcClassic. A node can have multiple incoming or outgoing ArcClassics. An ArcClassic can only have one Source Node and one Target Node. This interpretation includes a description of the previous paragraph. However, constraints do not appear, they must be expressed, for example in Object COnstraint Language (OCL)(OMG 2010a). Initially, our work was to be, totally in accordance with OMG. Tools for model transformation suggested by the OMG are still evolving, and to date we prefer to use EMF with Ecore meta meta-model and ATL language which seems to be the best choice, with a framework that has been already tried and tested. Our transformation choices are pointed out in figure 3.

Mapping of Concepts

The original contribution of our transformation is to match an activity diagram artefact to a PN block which will preserve the AD semantic, related to this artefact as defined by OMG. Such a PN block must also handle alternatives in AD modeling, e.g. an input pin may be stereotyped "optional" and becomes useless to start the activity. Table 4 illustrates the main mapping. Solutions: We can do with the property 1 that the first intuition is good, PetriNet arc carry tokens too. Property 2 and many others shows that the ControlFlow has behavior of token storage like a PetriNet place. The inability to know dynamically the number of token in a place to empty correctly ControlFlow brings us to the model as a buffer. Indeed, the presence of token is important but not the token multiplicity.

The same work was done with almost every ActivityDiagram node. Many stereotypes can be applied to nodes and was not considered to date.

The transition from one column to another in figure 4 is possible at M2 level (see figure 3 ) with ATL rules and Eclipse Modeling Framework. We'll see how we built a block PN during a small example.

Complex Petri Net

It was already seen how to build an atomic block. Building complex PN is relatively simple, in an activity diagram every or almost every node are connected to another by "ControlFlow" or "ObjectFlow". They will just have to connect each atomic block (can be viewed as:Transition-Place-Transition) to controlflow or objectflow block (can be viewed as:Arc-Place-Arc).We remind the reader that, analysis at model level should be higher than meta-model level to establish the rules in MDE context. Using the hierarchy can significantly reduce the amount of transformation rules. With AD2PN transformation, we could see that ATL cannot use easily the advantages of hierarchy. The language must be well controlled to limit significantly the coding rules.

VERIFICATION

After establishing the rules for "control flow" part, it is important to verify formally the transformation and, thus, verify that the PN had the same behavior as the activity diagram. In other words, it must check, through PN, to find the operational semantics of an AD. Subsequently, it is possible to imagine that users adds constraints (OCL) to the model, their validity in the PN can be proved with verification.

ResolveTemp Meta-model

Each PN block can be reduced to a sequence, Transition-Place-Transition. This meta-model defines each type of block to give essential features, but no behavior. It performs double transformation AD2PN and synchronized AD2ResolveTemp. This is to retrieve the name of input transitions (isStarted), output transitions (isFinished), running place (isRunning) and this incoming/outgoing (incomming/outgoing) (see figure 5). Sometimes attributes are added to define better LTL property (is-NotRunning, optionnalIncoming,...)

Incoming

Outgoing

AD node

Figure 5: PN block definition

LTL Properties and selt

Owing to lack of space, we will not present LTL language. Our approach has been to develop, properties in blocks with properties with inputs and outputs. In accordance with transitivity relationship A ⇒ B and B ⇒ C then A ⇒ C. If block satisfies this properties, and if properties with connected blocks are satisfied then entire PN is verified. This verifies formally correct construction of the Petri net. This technique shows limitations indeed to have the expected Petri net (no problem in the construction). But it does not involve checking of correct behavior of the Petri net. If the building blocks have a limited or incorrect behavior, the model will be wrong and yet the verification will be positive. The user must know the limits of model transformation used.

EXAMPLE: ACTIVITY DIAGRAM TO PETRI NET

We can see in figure 6, at left, a simple AD. When Ac-tivity1 is running, executes Action1, when this one is finished, starts parallel execution of both action (action 2 and 3 ). If action2 is finished, action 3 can run, but if action 3 is the first to finished, at this moment, Activ-ity1 is stoped, and all action in Activity1 are stopped. We can see figure 6, at right, the resulting petri net after AD2PN transformation. It is more complex in appearance, it takes the behavior of Activity Diagram, that part is not really readable but does not provide specific information aditional. To make this transformation, we must establish rules for each meta-class present through these instances in the model. For example: The ATL transformation rule for InitialNode meta-class. For each instance of InitialNode, a marked place is created, arc connects the latter to a transition. This transition is associated with meta-class instance after transformation, present in outgoing InitialNode argument ( Outputlink←a.outgoing). This graphical version under TINA is possible with a second transformation, from Petri Net to Tina (model2text). To make this transformation we have used "Query" [START_REF]ATL:Atlas Transformation Language ATL User Manual[END_REF] [](p2_CFlow_CF1_Activity1+p3_CFlow_CF1_Activity1= 1);

The OMG specification says:"If multiple control tokens are available on a single incoming control flow, they are all consumed."(OMG 2010c).To respect this semantic, controlflow is modelised as seen in concepts of mapping subsection (presence or exclusively absence of tokken in ControlFlow).

Figure 6: Simple AD2PN example

CONCLUSION AND FUTURE WORK

This work, has already set up a complex management of AD in accordance with the OMG specifications. OMG Specifications regularly contrain to refrain some shortcuts, which could simplify development. PN provides a mathematical formalism which is, at this step of the project not really exploited. It should eventually allow to highlight the invariant properties in AD, execute activity diagram in parallel with VHDL-AMS, to cover all the possibilities offered by the activity diagrams.

The future work will use differential predicate transition PN [START_REF] Genrich | Predicate/Transition Nets[END_REF] for dataflow management. Today this first step can say if data are presents or not, but it does not convey any information. With this new class of petri nets, the TINA formalism becomes unuseful and we'll go to validation by simulation (VHDL-AMS). During this work, it was also possible to show that management of interrupts areas is possible with basic PN.

We express concern about management of many changes which allows users (stereotype, optional attribute,...), to manage all of these cases seems to overload rules of transformation. ATL language has sometimes seemed a bit complex, it will be interesting to see the contribution of Query / View / Transformation (QVT) language. The development of the reverse chain; Petri nets to activity diagram in this work will be completed by providing the user with an AD modified or re-organized according to the invariant or error detected in PN. Verification should be transparent to the user, however, a good mastery of AD seems crucial to create a really exploitable PN for us.

Figure 1 :

 1 Figure 1: Part of Complete Activity Diagram in accordance with OMG specification.

Figure 2 :

 2 Figure 2: Petri Net model conforms to simple Petri Net meta-model.

Figure 3 :

 3 Figure 3: Meta-modelling Transformation.

Figure 4 :

 4 Figure 4: Basic Concepts Mapping: from AD to PN

  ). For example, a ControlFlow can be modelised as a single transition (Thierry-Mieg and LHillah 2008), it can be also included on nodes like in[START_REF] Bonhomme | Methodology and Tools for the Design and Verification of a Smart Management System for Home Comfort[END_REF]. In figure4the ultimate PN block acts as a buffer to respect ControlFlow properties written in OMG specification. They define ControlFlow like an edge that starts an activity node after the previous one is finished, with this simple definition an PetriNet arc is a correct model, but OMG add many specification on ControlFlow or which influences behavior. Finally, PetriNet arc is inadequate to meet all properties. Let's look at an excerpt of the properties and define possible solutions to respect them: Property 1 (from ControlFlow): Tokens offered by the source node are all offered to the target node.

Property 2 (from ActionNode): When an action accepts the offer for control and object tokens, the tokens are removed from the original sources that offered them. If multiple control tokens are available on a single incoming control flow, they are all consumed.