Nyoman Juniarta
email: nyoman.juniarta@loria.fr

Victor Codocedo
email: victor.codocedo@inf.utfsm.cl

Miguel Couceiro
email: miguel.couceiro@loria.fr

Mehdi Kaytoue
email: mehdi.kaytoue@insa-lyon.fr

Amedeo Napoli
email: amedeo.napoli@loria.fr

Pattern Structures for Identifying Biclusters with Coherent Sign Changes

Keywords: biclustering, FCA, gene expression, pattern structures

In this paper we are studying the task of nding coherentsign-changes biclusters in a binary matrix. This task can be applied to the interpretation of gene expression data, where such a bicluster represents a set of experiments that aect a set of genes in a consistent way. We start with a binary table and study biclustering methods based on FCA and partition pattern structures. Pattern concepts provide biclusters and their hierarchical relation, which can be used to analyze the prole of genes in the given expression data. Our approach is purely symbolic, so we can detect larger biclusters and work with rather complex data.

Introduction

Gene expression data can be represented as a matrix, where rows and columns represent genes and experiments respectively. Each cell contains the numeric expression level of a given gene under a given experiment. In such data, we can say that an experiment aect a gene by either lowering or raising its expression, according to the gene's normal level. One may be interested in nding a subset of genes and a subset of experiments, such that the experiments aect the genes in a consistent way. In other words, any two experiments in the subset have always either the same eect or the opposite eect on every gene in the subset. This task corresponds to the mining of coherent-sign-changes (CSC) biclusters.

Biclustering is an important technique aimed at discovering patterns in a matrix representing a dataset. It is related to standard clustering whose main objective is to group the rows based on their similarity. On the other hand, biclustering refers to the problem of discovering submatrices whose cells exhibit similar behavior. This problem is also called co-clustering [START_REF] Govaert | Co-clustering[END_REF], where rows and columns are clustered simultaneously.

In this paper, we present a method based on FCA and pattern structures for discovering a specic type of bicluster: coherent-sign-changes bicluster. An existing approach in [START_REF] Tanay | Discovering statistically signicant biclusters in gene expression data[END_REF] can mine this bicluster type, but it is statistical, since its discovery of CSC biclusters is based on the magnitude of the expression changes.

Our approach is more symbolic, by taking into account only the direction of the changes, with expectation of detecting larger biclusters. Our FCA-based method also gives us the hierarchical structure of all biclusters, allowing an easier interpretation of the results by experts. Furthermore, pattern structures and AddIntent algorithm allows us to dene a threshold of bicluster size, so that we can limit the amount of retrieved biclusters. This paper is organized as follows. First, we discuss some related work about the discovery of biclusters with coherent sign changes in Section 2. Then, some basic denitions of biclustering are presented in Section 3. We explain our approach in Section 4, and discuss the experiments in Section 5. Finally, we concludes our article and give some research perspectives in Section 6.

Related Work

The rowcolumn clustering was introduced in [START_REF] Hartigan | Direct clustering of a data matrix[END_REF], and Cheng and Church [START_REF] Cheng | Biclustering of expression data[END_REF] were the rsts to used the term biclustering while working on gene expression data. A bicluster in [START_REF] Cheng | Biclustering of expression data[END_REF] is a subset of genes and a subset of conditions with a high similarity score, statistically measured by calculating variances over all values in the submatrix.

Still in the domain of gene expression data, the algorithm called SAMBA was proposed in [START_REF] Tanay | Discovering statistically signicant biclusters in gene expression data[END_REF] to discover a submatrix where the expressions of a subset of genes signicantly changes across a subset of conditions. The rst model of SAMBA searches a submatrix where there is a joint change across all genes, without looking whether it is an increase or a decrease. The second model takes into account the direction of the change, such that any two conditions in the submatrix have either always the same eect or always the opposite eect. We call this type of submatrix a coherent-sign-changes bicluster, as denoted in [START_REF] Madeira | Biclustering algorithms for biological data analysis: a survey[END_REF].

Regarding bicluster discovery based on FCA, several methods were proposed.

In a binary matrix, dense approximate bicluster discovery was studied in [START_REF] Gnatyshak | Analysing online social network data with biclustering and triclustering[END_REF][START_REF] Ignatov | Concept-based biclustering for internet advertisement[END_REF] based on standard FCA. This is similar to mining formal concept, but instead of exact concepts, the authors relax the problem such that the approximate concepts (having a certain amount of empty cells) can also be detected. For biclustering with similar values in a numerical matrix, Kaytoue et al. in [START_REF] Kaytoue | Mining Gene Expression Data with Pattern Structures in Formal Concept Analysis[END_REF] proposed standard FCA with scaling and interval pattern structures. Triadic Concept Analysis was also studied in [START_REF] Kaytoue | Biclustering meets triadic concept analysis[END_REF] to extract this bicluster type. Furthermore, a partition pattern structure was presented in [START_REF] Codocedo | Lattice-based biclustering using partition pattern structures[END_REF][START_REF] Kaytoue | Traitement de données numériques pas analyse formelle de concepts et structures de patrons[END_REF] for mining bicluster with constant columns.

Biclustering

In this section, we recall the basic background and discuss illustrative examples of the dierent types of biclusters as described in [START_REF] Madeira | Biclustering algorithms for biological data analysis: a survey[END_REF]. We consider that a dataset is composed of a set of objects G, each of which has values over a set of attributes M . This dataset can be represented as a numerical matrix where each cell indicates the value of an object w.r.t. an attribute, and can be formally written in Def. 1.

Denition 1 (Dataset). A dataset is a numerical context (G, M, I) where G is a set of objects, M is a set of attributes, and I corresponds to m(g), which is the value of m ∈ M for object g ∈ G.

One may be interested in nding which subset of objects possesses the same values w.r.t. a subset of attributes. Regarding the matrix representation, this is equivalent to the problem of nding a submatrix that has a constant value over all of its elements (example in Table 1a). This task is called biclustering with constant values, which is a simultaneous clustering of the rows and columns of a matrix. In coherent-sign-changes (CSC) bicluster, the matrix is binary. In this bicluster, each row is correlated (either entirely identical or entirely opposite) to all other rows. In the example in Table 1c, the rst row is identical to the second and opposite to the third and fourth. We can also see this bicluster by comparing the columns. In the example, the rst column is identical to the second and opposite to the third. Before formalizing the denition of CSC bicluster, rst we introduce the notation of column submatrix and its similarity.

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 (a)
+ + - + + - - - + - - + (b)
Denition 2 (Column submatrix). In a binary dataset (G, M, I), given a set of objects A ⊆ G and an attribute m ∈ M , m(A) is the column submatrix formed by the attribute m over A.

The submatrix m j (A) is equal to m k (A), denoted as m j (A) m k (A), if all rows in m j (A) are either entirely identical or entirely opposite to the corresponding rows in m k (A). This can be formally written as:

m j (A) m k (A) ⇐⇒∀g ∈ A : m j (g) = m k (g) or ∀g ∈ A : m j (g) = ¬m k (g).
With the previous notation, the denition of a CSC bicluster is given as follows.

Denition 3 (Coherent-sign-changes bicluster). Given a binary dataset (G, M, I),

a pair (A, B) (where A ⊆ G, B ⊆ M ) is a coherent-sign-changes bicluster if ∀m j , m k ∈ B : m j (A) m k (A).
In the bicluster discovery, a bicluster can be found entirely within another larger bicluster. We then say that this small bicluster is not maximal. The notion of maximal bicluster is the same for any type of bicluster, and given in the following denition.

M m1 m2 m3 m4 g1 + + - - g2 + + - - g3 - - + - g4 + + + + g5 - - - -

Formalization

In the task of CSC bicluster discovery in a formal context (G, M, I), we propose an approach based on partition pattern structures. Instead of partition of objects in G as described in [START_REF] Baixeries | Characterizing functional dependencies in formal concept analysis with pattern structures[END_REF][START_REF] Codocedo | Lattice-based biclustering using partition pattern structures[END_REF], here we use partition of attributes in M . It is still similar to an object partition since an attribute partition covers every attribute in M and there is no overlapping between any two partition components.

To formally dene our signed partition, rst we dene the notion of signed attribute and signed partition component as follows.

Denition 5 (Signed attribute). Let M be a set of attributes, m ∈ M be an attribute, and * ∈ {-, +} be a sign. A signed attribute m * is an attribute m having a sign * .

Denition 6 (Signed partition component). A signed partition component (or

sp-component ) c is a subset of M , where each attribute in c is associated to their corresponding sign * . Therefore, c = {m * 1 , • • • , m * n }. For example, m +
1 is a signed attribute where the sign + is given to m 1 , and {m + 1 , m - 2 , m + 4 } is a signed partition component. Since an sp-component contains not only attributes but also their associated sign, we dene the equality of two sp-components according to these two aspects as follows.

Denition 7 (SP-component equality). Any two sp-components are equal i both contain the same set of attributes, and they have either entirely same sign or entirely opposite sign.

Therefore, if we have

c 1 = {m + 1 , m - 2 , m + 4 }, c 2 = {m + 1 , m - 2 , m + 4 }, and c 3 = {m - 1 , m + 2 , m - 4 }, then c 1 = c 2 = c 3 .
Denition 8 (Signed partition). A signed partition (or s-partition ) d is a collection of sp-components, written as

d = {c 1 , • • • , c n }, such that every attribute in M is present in exactly one sp-component. For example, given M = {m 1 , • • • , m 4 }, then {{m + 1 , m - 2 , m + 4 }, {m + 3 }} is a valid signed partition of M .
The set of all possible s-partitions is denoted as D. This allows us to create an s-partition mapping δ : G → D which assigns an object to an s-partition over M . For an object m, δ(m) is an s-partition containing only one sp-component. This sp-component contains all attributes in M with the corresponding sign according to the object g. Example from Table 2:

δ(g 1 ) = δ(g 2 ) = {{m + 1 , m + 2 , m - 3 , m - 4 }} δ(g 3 ) = {{m - 1 , m - 2 , m + 3 , m - 4 }} δ(g 4 ) = {{m + 1 , m + 2 , m + 3 , m + 4 }} δ(g 5 ) = {{m - 1 , m - 2 , m - 3 , m - 4 }}.
Notice that since the sp-components in δ(g 4 ) and δ(g 5 ) contain the same attributes with entirely opposite sign, according to Def. 7 we have δ(g 4 ) = δ(g 5 ).

This mapping is formulated as follows:

δ(g) = {{m * j j |m j ∈ M }} where * j = m j (g).

(1)

Signed Partition Space

For the task of CSC bicluster discovery, here we dene relations between any two s-partitions. The set of all possible s-partitions D is a meet-semilattice where we can dene the meet of any two s-partitions.

First, we dene the notation m(c) as the sign of an attribute m in an spcomponent c.

For example, if c = {m + 1 , m - 2 , m - 3 }, then m 1 (c) = +.
With this notation, we dene the similarity (∩ ± ) between any two sp-components as:

c 1 ∩ ± c 2 = {{m * j ∈ c 1 |m j (c 1 ) = m j (c 2 )}, {m * j ∈ c 1 |m j (c 1 ) = ¬m j (c 2 )}}, (2)
where * corresponds to the sign of m j in c 1 , i.e. m j (c 1 ).

In other words, the operator ∩ ± between c 1 and c 2 gives {c 12 , c 1|2 }. The c 12 represents all attributes who are present in c 1 and c 2 with the same sign, while c 1|2 represents all attributes who are present in c 1 and c 2 , but with opposite sign. The signs in the resulting sp-component are the same as those in the rst sp-component. Example:

if c x = {m + 1 , m - 2 , m - 3 , m - 4 } and c y = {m + 1 , m - 2 , m + 3 , m + 4 , m - 5 }, then c x ∩ ± c y = {{m + 1 , m - 2 }, {m - 3 , m - 4 }}.
Since the signs in c 1|2 follow the rst sp-component, the result of c 1 ∩ ± c 2 could be dierent to c 2 ∩ ± c 1 . This can be resolved by Def. 7 that ensures the commutativity of ∩ ± . For example:

c x ∩ ± c y = {{m + 1 , m - 2 }, {m - 3 , m - 4 }}, c y ∩ ± c x = {{m + 1 , m - 2 }, {m + 3 , m + 4 }}, c x ∩ ± c y = c y ∩ ± c x .
Having dened the similarity of any two sp-components, we can now dene the similarity of any two s-partitions. The similarity (or the meet) of two s-

partitions d 1 = {c 1 • • • c k } and d 2 = {c 1 • • • c n }, with k = |d 1 | and n = |d 2 |, is dened as: d 1 d 2 = {c i ∩ ± c j |∀c i ∈ d 1 , c j ∈ d 2 }, (3)
and the order between two s-partitions is given by:

d 1 d 2 ⇐⇒ d 1 d 2 = d 1 . (4)
Let C the set of all sp-components in M , and D is the set of all s-partitions in M . We have ∩ ± : C 2 → D and : D 2 → D. Example from Table 2:

δ(g 1 ) δ(g 3 ) = {{m + 1 , m + 2 , m - 3 , m - 4 }} {{m - 1 , m - 2 , m + 3 , m - 4 }} = {{m - 4 }, {m + 1 , m + 2 , m - 3 }}. Suppose that d 1 = {{m - 4 }, {m + 1 , m + 2 , m - 3 }}. Then d 1 δ(g 1 ), d 1 δ(g 2 )
, and d 1 δ(g 3 ).

In order to dene a partial order among d ∈ D, the operator has to be commutative, idempotent, and associative. These properties are shown in the following propositions.

Proposition 1. The operator is commutative, i.e.

d 1 d 2 = d 2 d 1 . Proof. Consider d 1 = {c 1 • • • c n } with n = |d 1 | and d 2 = {c 1 • • • c k } with k = |d 2 |. d 1 d 2 = d 2 d 1 {c i ∩ ± c j |∀c i ∈ d 1 , c j ∈ d 2 } = {c j ∩ ± c i |∀c i ∈ d 1 , c j ∈ d 2 }
It is previously stated that ∩ ± is also commutative. Therefore, both sides of the equation above are equal.

Proposition 2. The operator is idempotent, i.e.

d 1 d 1 = d 1 . Proof. Consider d 1 = {c 1 • • • c n } with n = |d 1 |. d 1 d 1 = {c i ∩ ± c j |∀c i ∈ d 1 , c j ∈ d 1 }
Since there is no overlap among c i ∈ d 1 , then c i ∩ ± c j is an empty set for i = j.

Therefore :

d 1 d 1 = {c i ∩ ± c j |∀c i , c j ∈ d 1 and i = j} = {c i ∩ ± c i |∀c i ∈ d 1 } = {c i |c i ∈ d 1 } = d 1 Proposition 3. The operator is associative, i.e. (d 1 d 2 ) d 3 = d 1 (d 2 d 3 ). Proof. Consider d 1 = {c 1 • • • c n } with n = |d 1 |, d 2 = {c 1 • • • c p } with p = |d 2 |, and d 3 = {c 1 • • • c q } with q = |d 3 |. (d 1 d 2 ) d 3 ={c i ∩ ± c j |∀c i ∈ d 1 , c j ∈ d 2 } d 3 ={c i ∩ ± c j ∩ ± c k |∀c i ∈ d 1 , c j ∈ d 2 , c k ∈ d 3 } =d 1 {c j ∩ ± c k |∀c j ∈ d 2 , c k ∈ d 3 } =d 1 (d 2 d 3 )
With the denition of similarity ( ) and the associated partial ordering ( ) between two s-partitions, we then dene the notion of signed partition pattern concept in the following subsection.

Signed Partition Pattern Structures

Let G a set of objects, M a set of attributes. The lattice of s-partitions of M is (D, ), where δ : G → D maps an object to an s-partition as dened in Eq. 1.

A signed partition pattern structure is determined by the triple (G, (D, ), δ), where the derivation operators for A ⊆ G and d ∈ D are dened as:

A = g∈A δ(g),
A = {g 1 , g 2 , g 3 }, we have m 1 (A) m 2 (A) m 3 (A) (recall the denition of in Section 3).
The order between any two spp-concepts is given by

(A 1 , d 1 ) ≤ (A 2 , d 2 ) ⇐⇒ A 1 ⊆ A 2 or d 2 d 1 .
Using this order, the lattice of all spp-concepts from Table 2 can be constructed and is shown in Figure 1. It should be noticed that the lattice is readable and interpretable only if its size is small. This lattice is useful not only for understanding the hierarchical structure among all biclusters, but also for detecting maximal biclusters. By Def. 4, the bicluster ({g 1 , g 2 , g 4 , g 5 }, {m 1 , m 2 }) from Table 2 is not maximal, since we can add g 3 that constructs another bicluster ({g 1 , g 2 , g 3 , g 4 , g 5 }, {m 1 , m 2 }). The non-maximal biclusters can be detected from the concept lattice [START_REF] Kaytoue | Biclustering numerical data in formal concept analysis[END_REF]. Consider two concepts (A 1 , d 1 ) and (A 2 , d 2 ) such that (A 1 , d 1 ) ≤ (A 2 , d 2 ), and an sp-component c. The bicluster

(A 1 , c) is maximal i c ∈ d 1 and c ∈ d 2 .
For example, consider the concept p 1 = ({g 1 , g 2 , g 4 , g 5 }, {{m + 1 , m + 2 }, {m + 3 , m + 4 }}) and p 2 = ({g 1 , g 2 , g 3 , g 4 , g 5 }, {{m + 1 , m + 2 }, {m + 3 }, {m + 4 }}), where p 1 ≤ p 2 . We see that the sp-component {m + 1 , m + 2 } is in the intent of both p 1 and p 2 . Therefore, the bicluster ({g 1 , g 2 , g 4 , g 5 }, {m 1 , m 2 }) from p 1 is not maximal.

Mining SPP Concepts

As described in Section 3, CSC bicluster is a submatrix in a binary matrix. Therefore, given a numerical matrix, it is required to transform it into binary matrix. This can be done by scaling, for example by introducing a threshold, and each numerical value can be transformed to + orbased on whether it is above or below the threshold. In a gene expression data for example, a threshold can be the normal expression level for each gene. An expression that is above (or below) this normal level should be transformed to + (orrespectively). In the task of formal concepts, the algorithm called AddIntent was proposed in [START_REF] Van Der Merwe | AddIntent: A new incremental algorithm for constructing concept lattices[END_REF]. This algorithm can be used for any pattern structures by dening the meet ( ) and the order ( ) between any two descriptions. Having dened the meet in Eq. 3 and the order in Eq. 4, we then use AddIntent to mine sppconcepts in a binary matrix. Furthermore, this algorithm is also eective for building a concept lattice, which is needed in our case to detect the maximality of any CSC bicluster.

∅ {g1, g2}

{{m + 1 , m + 2 , m - 3 , m - 4 }} {g3} {{m - 1 , m - 2 , m + 3 , m - 4 }} {g4, g5} {{m + 1 , m + 2 , m + 3 , m + 4 }} {g1, g2, g3} {{m + 1 , m + 2 , m - 3 },

Experiments

As previously explained in Section 4, CSC biclusters can be found in any sppconcept. Therefore, from a binary matrix, we should retrieve all spp-concepts.

To do that, we reuse the AddIntent source code in [START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF] by modifying the definition and operators. This algorithm also allows us to build the lattice of all concepts. We can reduce the lattice by choosing a threshold θ that applies to the intent of a concept. This threshold denes the minimal size of an sp-component that an intent should have. Since the lattice construction is performed by a bottom-up approach, this threshold allows to prune the lattice.

For example, with θ = 3, the lattice for We tested our method to lymphoma dataset provided in [START_REF] Alizadeh | Distinct types of diuse large b-cell lymphoma identied by gene expression proling[END_REF]. It contains the numerical expression levels of 4026 genes over 96 tissues. The objective of CSC bicluster discovery in this dataset is to nd a subset of genes that behave in a consistent way over a subset of tissues. For this task, we convert this numerical dataset to binary by assigningand + for the values < 0 and ≥ 0 respectively.

The number of concepts and runtime for dierent thresholds are listed in Table 4. We tested three thresholds: 70, 80, and 90. As shown here, higher θ can reduce the number of concepts, and consequently reduce the runtime.

For θ = 70, around 157K concepts are obtained. Among them, only 153K have extent size larger than 1. This means that there are 153K CSC biclusters having at least 70 columns and at least 2 rows. Furthermore, still with θ = 70, the largest extent size is 8, meaning that among the biclusters with ≥ 70 columns, there are no bicluster with > 8 rows.

Higher θ corresponds to higher number of columns in the biclusters and thus lower number of rows. With θ = 90, we see that among the biclusters with ≥ 90 rows, there are no bicluster with > 3 rows.

Conclusion

In this paper we have presented an approach to mine biclusters with coherent sign changes in a binary matrix. We formulated our method based on partition pattern structures. The generated lattice allows us to examine the maximality that denes a minimum number of columns of the biclusters. This is also useful to reduce the number of concepts and the computational time.

The computational time can be further reduced by taking into account the maximality of a bicluster. If the intent of a concept p contains an sp-component c that is present in the intent of p's superconcept, then this c indicates a nonmaximal bicluster. In this case, c should be removed from the intent of p. However, this may change the denition of .

Another aspect that should be studied is the possibility of a matrix that has another sign in addition to + and -. This new sign can represent a missing value, or in the case of threshold-based transformation, a value that is equal to the threshold. It can be resolved using tolerance relation introduced in [START_REF] Kaytoue | Embedding tolerance relations in formal concept analysis: an application in information fusion[END_REF], such that a value equal to the threshold should be regarded as similar to both + and -. In the case of missing value, it can be resolved by modifying the denition of attribute partition in Def. 8 which permits an attribute to be not present in any sp-component. This modication may consequently require modications on the denition of meet and order between s-partitions.

Eventually, the CSC bicluster discovery can be applied in a domain besides gene expression data. Frequent gradual itemset mining was studied in [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF] to extract gradual rules from a numerical table, e.g. a hotel price table with 3 attributes: m p for city population, m d for distance from city center, and m r for room price. We may nd an sp-component {m + p , m - d , m + r }. It is related to the rule saying the more/less m p , the less/more m d , then the more/less m r . Moreover, some studies ( [START_REF] Codocedo-Henríquez | Contributions à l'indexation et à la récupération d'information utilisant l'analyse formelle de concepts[END_REF][START_REF] Ignatov | Recommender system based on algorithm of bicluster analysis RecBi[END_REF]) show the benets of biclustering in the recommendation systems. In a usermovie rating matrix for example, a constantcolumn bicluster represents a set of users having the same interest across a set of movies. On the other hand, a CSC bicluster in this matrix represents a set of users having either the same or the opposite interest. This is useful for a new user u: we can recommend movies liked by users similar to u and movies disliked by users opposite to u.

Denition 4 .

 4 (Maximal bicluster) Given a dataset (G, M, I), a bicluster (A, B) is a maximal bicluster if adding an object g ∈ G\A to A or an attribute m ∈ M \B to B does not result in a bicluster.[START_REF] Codocedo | A proposition for sequence mining using pattern structures[END_REF] The Pattern Structures of Signed Partition

( 5 )

 5 d = {g ∈ G|d δ(g)}.

  d) is a signed partition pattern concept (or spp-concept ) when A = d and d = A. From an spp-concept (A, d), a CSC bicluster is any pair (A, c) where c ∈ d (we can ignore the attribute signs in c). All spp-concepts from

Table 1

 1

	. Examples of two bicluster types: (a) constant-values and (b) coherent-sign-
	changes (CSC).

Table 2 .

 2 Running example.

Table 2

 2 are listed in Table3. In the concept ({g 1 , g 2 , g 3 }, {{m +

	1 , m + 2 , m -3 }, {m -4 }}) for

Table 3 .

 3 All sign partition pattern concepts from Table2and their corresponding CSC

	biclusters.
		Concept	CSC bicluster
	Extent	Intent	Objects	Attributes
	{g1, g2} {g3} {g4, g5} {g1, g2, g3}	{{m + 1 , m + 2 , m -3 , m -4 }} {{m -1 , m -2 , m + 3 , m -4 }} {{m + 1 , m + 2 , m + 3 , m + 4 }} {{m + 1 , m + 2 , m -3 }, {m -4 }}	{g1, g2} {g3} {g4, g5} {g1, g2, g3}	{m1, m2, m3, m4} {m1, m2, m3, m4} {m1, m2, m3, m4} {m1, m2, m3}
			{g1, g2, g3}	{m4}
	{g1, g2, g4, g5}	{{m + 1 , m + 2 }, {m + 3 , m + 4 }}	{g1, g2, g4, g5}	{m1,
			{g1, g2, g4, g5}	{m3, m4}
	{g3, g4, g5}	{{m + 1 , m + 2 , m + 4 }, {m + 3 }}	{g3, g4, g5}	{m1, m2, m4}
			{g3, g4, g5}	{m3}
	{g1, g2, g3, g4, g5}	{{m + 1 , m + 2 }, {m + 3 }, {m + 4 }}	{g1, g2, g3, g4, g5}	{m1, m2}
			{g1, g2, g3, g4, g5}	{m3}
			{g1, g2, g3, g4, g5}	{m4}

example, we can nd the CSC bicluster ({g 1 , g 2 , g 3 }, {m 1 , m 2 , m 3 }). Looking back to the original table, this CSC bicluster means that in

Table 2

 2 Fig. 2. Sign partition pattern lattice for pattern structure in Table 2 with θ = 3.

	does not contain the con-

Table 4 .

 4 Experiments on lymphoma dataset.

	θ	Runtime	Number of concepts	Largest extent size
		(minutes)	All	Extent size > 1
	70	229.4	157K	153K	8
	80	62.9	7K	2K	7
	90	62.1	4K	83	3
	of discovered biclusters. Another advantage is that we can choose a threshold


Aclivc dcviccs such as MBSFETs arc iitlrwtivc sincc t h y can provide coiivcrsion gain iis wcll i i s niixing opcriiliun. 'l'liis allows 11ic ; i m y io sciid m p l i I i c d signals tow;uuls the sowcc Iocafioii wiilioiit includiiig iitldition;il ;unpliliers, wliicli will iiicreasc circuit size iiiicl cor[ [4]. 111 Illis Lcttcr wc iircwnt ii tncw phiisc coiijuplor tvitli aclivc dcviccs for rctroilircclivc iintciinw niwys, wliicli iilsn iiinkes i t possihle to use the same polarisiition for both truismittint( mid rccciviiig wlicn plticcd in ti rctiutlii+cct ivc iirl'iiy. 'I'liis wllows eitcli elcinciil to he inudc very siiiiill, which is vcry importaiit sincc tlic scanning raiigc of rctrotlircclivc To date, iiios~ active riiultilayer antciiiiiis Iiwe been rcdiscd by fabricxtitig the active coinponcnts tlirttlty 011 tIrc iintciiiiii substmtc [I], '1'0 tLvuid poor conncclioiis due to air gaps, ; i i d piuvide a n ;iaiiratc reeding position, the antenna is hilly rcaliscd by meails of phutolihgmphy prncesscs. In lhis Letter we report an integrakd piwitiiity-fed iiiitciina a m y , the contigur;~tiun o f which allows the optiinisation of both the ;~titcnn;r and active suhstr.;itc. 'l'lre active coinponcnt subsurate is galliiun arsenide irnd thc subsirate of thc antcnuii is a11 ultrathick polymci. dielectric, Amoco IJltradcl 7505 [2) (a pliotoscnsitisctl epoxy resin). To iiicrciw i hc bandwidth, tlic pit~chcs RIC strongly couplcd in Ilic H-plane [3]. microatrlpline A/iterrrtra JdnY~fiun: l h e faliricatioii proccss is sliowii in Fig. 2. Dn one side of thc CaAs substrate ii traiisinissioii liiicsis deposited by tlicriiial evaporation of 'li (200A) wild Ai1 (5OOOA) (l;ig, 2n). Pnlynicr 7505 i s tlwi applied by spiliqoilting to acliievc thc desired tliickncss of thc dielectric (Pig. 20). I:ollowing a pre-bnke at 100°C: 011 Iiotplatc, thc polynier is exposed to near irllluviolel light. ABcr prc-hkc in B 175°C: nitrogen wcii, wc thcii carry oul developtnciil using D510 devdopcr: illid finally a post-hakc on ii hotplatc at 100°C is carried out for -3min. "l'lie rcsonators arc lheiz deposited on thc dielectric by rl~crintil evaporation of Ti and Ail (liig. 21:). This final structulr can be seen in Fig. 3. '['lie climeusion of tlic srttwrc rcsoiintois is t;ikcn i o bc 1.86tnin aiid their resonant f r q i e i i c y is 2601-Iz. Ttic tlislaiice belweeii thc rcsonators is 0.51iim. 'l'lic parasitic patches cn;iblc the briiidwidrli d Troni hOOMHz for :I sin$ ~~a t c h to 1.2GHz for i~ ~Iircc-clcmerit h e a r iy. The dimelisions of tlic fccdcr i~re wljuslcd to inalch the input iinpcdaiicc or a 50Q load at thc rcsuiimt rrequency. We obtaincd R intixiiiium handwidth of 5% Tor ~lir: array antenna instcritl or 2.5% Tor ii single rcsonator.

G&

Expwirneritd r.c:sulrlr.s: The antenna inounicrl in

i i K-cell is stinwii in

  hriI01~: The antcnna dcsigri is sliown in Fig.I. 'ihc driving palch i s electro~niigncticlly coupled to a micrustrip line, wnd i s Inirdcd by psrasitic ptitclies wliich foriii the m a y of thc miteniia. Tticsc parasitic patches tire clcclroiiiagncticirl~y illfluelmcoupled togcthor and invnlvc an incrcc;isctl bmlwidth, The pittchcs arc Gibricwtctl on a low-loss diclcchic subswate with a thickness of h2 = 4 f l p and ii low rchtive permittivity of E,? = 2, which provides good Istdi;iiiiig cpfciaicy. Tlic transmission lines clre hlxicatcd on it high periiiitlivity suhstratc with Iliickness i l l .-4oopii and ii rcclalivc permittivity of &,I = 12.8. The CAD softW;ii-c Enscmble (noulder, CO) 1 4 1 hiis bccn used to design thc :intcniia.

Fig. 4 .

 4 Fig. 4. Thc iiicauured ~r i d simiilwd rcsulls arc ptesentcd in Fig. 5. The iiicasurcd and simulwted hequencies arc tlic siinx (20Gllz) ill the case of a singlc resonator; in the case of thc antcnna ; ~i i y , n slight discrepancy C B I ~ be nuictl (25.7 when mcas-

iiiiknixi arr;iy tlcpcntls 011 thc arl

  ;iy spilciny. Corichiurr: A iicw coinpad pliarc coiijiig;itor has bccn piuposed. I his new struclrire irllnivs liigli I<l-'/lF isolntiuii t h e to its hybrid striiclut'c, arid LISCS FET iiiixers tor co~~vci~sinii gairi. Thc circuit iiws oiic port for both input ;iiid oiitpur, ;itid shows high liti/lli isolalioii i i 3 wcll ;is coiiversinii gain. This comlxict ;rrcliilecliire caii he iiscd iis Ilic Ixiildjiig lilock thr i l wide niiige retrodircctivc antciitia aruiy duc to its compucriicss, which nieiins that it ciin bc casily incorporatccl into iiii array, as well as its cxcellcnt pcrformiincc. Currcnt cfhrls arc bcing rlircclcd (owiirtls dcvclopitig ii

	,	w F E T m l x e r s

rctrodircctivc ;irray hiscd on this ;ircIiitcctiirc. /

lultrioii?lr,t~/nrsrl: 'I'liis work is suppurlcd by (lie US AIIO MIJRT

  Dcwl h i , his tlelpliil advice.

	p i ~~g ~i n i iiiidcI conlracl DAAIJ04-'16-1-0005. 'I'Iic iiiitliors also thank W. r l

power CMOS current conveyor A.M. Isinail and A.M. Soliman

  Low-power analoguc dcsign, tlicrerow, rriiscs its own cliallcngc [l ~ 71. Owing l o cconomic constraints, the sland;ird CMOS tecliiiology is suit;iblc for use in inariy applicafioris. L<cccntly, nnalague CMOS currcntinodc circuits tiavc tcceived ii grciil tlciil of intercst bccnusc llicy can opcralc under low vnltage sripplics siiicc thc currciit-iiiude siibstilutcs crirrciit swings I'or voltuge swings in tlic signal propagalion [I -31. The srcoiici-gciicration curlriil conveyor (CCIr) Is tlic iiiorl versatilc building block in current-riiorle signal processing [ I , 21. Many realisiiticliis of h c CCII in the litelaltirc hisctl 011 ;I fccdhack-slabiliscd voltage follo~vcr Ii;ivo bccii dcvelaped in urdcr to otitain ncciirittc voltage-followiiig itclion bclwccn tiode Y aud to nbtaiti IOW power wiisiiinprinri, the aspccl ratios nfti~iisislurs IvlNv14 tirid M7-MX iirc small compared will1 Ibosc for. MI-M2 iind MS-M6. Also, ilic xgcct ratios of all tlie rciniiining lriiilsislors iirc opt iiiiised lis sliorvn in Tablc 1. Tlic current a1 nodc X is reprnduccd at nodc Z+ ihrougti ciirrcnl iiiirrors M17, M20 mid M24.

	1	I	I	VDO
			"DD
	Considcr ttic circuit sliown in LGg, 2. l'fiinsiskws MI-M2 xiid
	ducerl

6 ELECTRONICS LETTERS 6th January 2000 Vol. 36 No. I Rcfcrciiccs I cr\imn%, F ~, iiiitl ~i t i i i i i v u c ~i ~~~~. . J : 'Study iiiwl design 0 1 criinpiict wi~lcl.rend microstrip ;iiiicIiIim'. Pruc.TEE 10th Int. CoiiT. Anlcnniis a n d I'ropgitfion, Edinburgh, Ilnilcd Kingtlom, April 1997, pp. 423 426 hiiioco Ultraclcl, CIPUC: 1 X in11: d'Aiijuu 7SOOR kirk, I.'ixncc CAIU~EZ, F~: 'Contribiilion L O Ihc Fturly of intcgraietl nltil~ilaycrcd tr;ulsponders, Applicatioit to r1iicrow:ivc coiiiiiiriiiicittioiis a i d idcntificalion'. Univcrsity 'I'licsis, I d e , Francc, 1997 Enscmblc sortware, I h l d e r Microwavc l'cchilologics. Inc. IIM'I., 236 Uanyoii BLVD, Suitc 102, floolrlcr. CO 80302, [JSA 2 3 4 Low-Intiaduafion: AIlhough l n v , ~ sopply wII:qc directly tr'ansliilcs to lower powcr consuinption in digit;iI circuits, a siiniI:ir conclusion cannot be r1ri1w11 fnr al>illogtlc circuits. iicdc X [4 -61. 111 (Iicse rc;iIis;itions, rliiTereiihil ~implilicrs with hiEli curienl I d s arc rcquirctl to obhin high opcn-loop p i n . 'Mi tcacls to high powcr consuinption iii atltli[ioii to a slcw rate liiiiikd pcrform;iiicc. lu this I .ctlcr, ii novcl CMOS realisation based on an aclq~livcly limed dii'rcrt.n(i;il pair slriicture is iniro-MS M6 havc tlic sniiic rnlc ws in llic circuit sliowii in Fig. I. To control IIIC valuc of thc ciii'i'eril litils ofthe two LIT stl'llctlil'cs, wn ;idapliw biasing action is en'wlctl by iiieaiis of Iiwisisloi-~ M3 M4, llie higli-spccd cur~cnl-iiiodc niiixiriiuin siib-cii4cuil M9-M 13 (reporled in 1:7]) m r l tlic ciir'i'ciil inirrors M14-MI 7. Coiiscquciilly. tlie l a i g r thc currciit tlriveii l?om nodc X, tlie Iliglicr Lllc biasing currcnt for the lwo LTPs. Stmiby ciirrciit so~irccs (MIR-M20) :ire ncetlcd lo prcvciit thc LTI' r;lrictiircs fi.0111 turning om, lliiis ;rvoiding cross-uvcr distortion tirid fwqiicncy response liiniialioii. Lt is iiotetl IIIII~, ELECTRONKS LETTERS 6tb January 2000 Vol. 36 No. I


M Benamara
email: benamara@univ-mlv.fr

M Grzeskowiak

M Salhi

G Lissorgues

Esycom Ea

A Diet

Y Le Bihan

Array Sub-Loops Reader Antenna for HF RFID Tracking

Keywords: magnetic coupling, RFID, mutual inductance, detection, array sub-loops antenna

this paper focuses on tracking and objects identification by means of High Frequency magnetic coupling RFID (Radio Frequency IDentification) at 13, 56 MHz. The coil of the used RFID tags corresponds to 1.9% of the reader coil surface (120x160 cm²). To increase the size ratio between the two coils, we proposed the use of multiple twisted loops antenna. The reader antenna is consequently divided into four sub-loops, corresponding to 8% of the surface of each one of the sub-loops area. According to the principle of twisted loop antenna, the nearest sub-loops are feed by current in opposite phase (complementary loops principle), and. This structure creates a strength curvature of magnetic field lines between each two of them, improving the magnetic coupling for vertical magnetic dipoles. In contrast, the structure presents at its center a null of magnetic field intensity due to the symmetry. To avoid this inconvenient a resonator is added to the structure to broke the symmetry and modify the magnetic field distribution. Its positioning is studied to optimize RFID detection in different angular and lateral positioning of the tag. Simulations and measurements of the proposed design with and without resonator are presented in the different parts of this paper.

INTRODUCTION

Radio Frequency Identification (RFID) at 13.56 MHz is currently used in several applications such as transport, security and tracking. The study concerns especially surgical instruments identification and tracking using HF (High Frequency) RFID system, this means the use of small tag coil (the tag coil size is defined according to the size of the object to identify). Additionally, it is identified a high interest in optimizing the detection of freely moving small size tags. In HF RFID system, the physical link between the reader and the tag coils is the magnetic mutual coupling phenomenon. Detection is performed when the variation of the chip impedance of the tag is correctly interpreted by the reader, according to the principle of load modulation. This is possible if the magnetic coupling between the reader and the tag coil is sufficiently strong. The communication between the reader and the tag occurs when the magnetic field lines generated by the reader coil are perpendicular to the surface of the tag coil. According to this principle, the performance of detection depends on all parameters that can act on the magnetic field distribution, by the way of geometry or current phases that influence the magnetic vectors. We can enumerate the shape, the size and the electrical properties of both the reader and the tag coils, and also the distance and angular positioning between them [START_REF] Finkenzeller | RFID Handbook[END_REF][START_REF] Zierhofer | Geometric approach for coupling enhancement of magnetically coupled coils[END_REF][START_REF] Reinhold | Efficient antenna design of inductive coupled RFID-system with heigh power demand[END_REF][START_REF] Babic | New formulas for mutual inductance and axial magnetic force between magnetically coupled coils: thick circular coil of the rectangular cross-section-thin disk coil (pancake)[END_REF][START_REF] Ahmed | Multi-loop_Bridge Antenna for impoved positionning using HF RFID[END_REF]. In tracking RFID system, the tag coil has a small dimension compared to the reader coil, implying to perform a detection of moving tag in different angular positioning. In this case, optimizing the tag detection is currently done by changing the shape of the conventional (circular or rectangular) reader coil. In the context of small misaligned tag, several studies are proposed to improve RFID detection [START_REF] Hirayama | Improvement of Null Zone Avoidance Capability for HF-band RFID using Diversity Combining of Loop Antennas[END_REF][START_REF] Gong | Three Overlapping Loop Antennas for 3D RFID,13.56MHz Access Control Gate[END_REF][START_REF] Benamara | A twisted loop antenna to enhance HF RFID detection areas for different tag positioning[END_REF][START_REF] Waffenschmidt | Homogeneous Magnetic Coupling for free positioning in inductive wireless power system[END_REF][START_REF] Grzeskowiak | Pebbles Tracking Thanks to RFID LF Multi-loops Inductively Coupled Reader[END_REF][START_REF] Diet | Improving LF Reader Antenna volume of detection, for RFID token tag, with a combination of ICLs and in/out-of phase multiple-loops structures[END_REF][START_REF] Benamara | Calculation of the Equivalent Mutual Impedance in Complex HF RFID Systems[END_REF]. In [START_REF] Benamara | Calculation of the Equivalent Mutual Impedance in Complex HF RFID Systems[END_REF] reader antenna including resonator is proposed.

Sub-loop (2) Sub-loop (3)

Sub-loop (4) Current

Step1 : MTLA

Step2 :Array sub-loops antenna

Y=0mm Y=60 mm

The distance of detection is improved by the strengthening magnetic field above the surface of the resonator. This structure presents limits for detection of tag in no parallel configuration. To avoid this limit, the twisted loop antenna is proposed in [START_REF] Benamara | A twisted loop antenna to enhance HF RFID detection areas for different tag positioning[END_REF]. The antenna corresponds to two close loops, fed by currents in opposite phases. This improves RFID detection because of the curvature of the magnetic field lines between these two loops common edge. In this paper, the principles of twisted loop antenna and reader antenna including resonators are used to create a multiple twisted loop antenna (MTLA) including a resonator (Fig. 1).

The proposed design is used to detect small tags of 11 mm radius in different angular positioning (parallel and perpendicular) (Fig. 1). The figure of merit is to maximize the magnetic coupling between the reader and the tag coils at the frequency of 13.56 MHz. The proposed MTLA corresponds to four complementary sub coils of 79 x 58 mm. The tag used for detection measurements is a circular of 22 mm diameter. The added resonator corresponds to a rectangular coil of (50 x 80 mm). The MTLA is fed by the current I (see Fig. 1), the connection between the different sub-loops are presented by different colors: red to connect sub-loops 1 and 2, green to connect sub-loops 2 and 4, purple to connect sub-loops 4 and 3 and bleu to connect sub-loops 3 and 1. This connection between sub-loops enables to change the direction of the current between each sub-loops.

The study is divided into two steps: Firstly, the MTLA design is studied by simulation of the magnetic field distribution and mutual inductance. Secondly, the resonator is added at the surface of the MTLA to perform the array subloops antenna. In this part the optimization is done by changing the position tilt angle of the resonator over the MTLA (0°<θ<90°). The improvement of RFID detection is validated by measurements. Analytical formulas defining the mutual inductance in the case of the MTLA and the array subloops antenna are developed in each part.

II. STEP1 :MTLA

One of the proposed reader antenna designs to improve RFID detection is the TLA (Twisted Loop Antenna). Its principle is changing the orientation of the magnetic field lines generated by conventional loop antenna (as known, the orientation of the magnetic field lines depends on the current direction). In this part, the MTLA design is studied by simulation of magnetic field and mutual inductance.

A. Magnetic field

The principle of the MTLA is the reduction of the ratio between the sizes of the reader and the tag coils. This can improve the magnetic coupling between them; this is the first principle of twisted loops. Also, the rotation of the magnetic field lines between the juxtaposed loops improves detection for the angular misalignment of the tag.

In fig. 2, the generated magnetic field by the MTLA is reported. The magnitude in the (X, Y) plans has maxima at the edges of the sub-loops of the MTLA and minima at the surface of the sub-loops. At the center of the MTLA (X=0mm, Y=0mm), there is a zero of the generated magnetic field by the MTLA because of the sum of the magnetic field generated by each sub-loop (as the amplitudes of the generated magnetic field by each sub-loop are equal, their sum will be nil because of the opposite directions). In (Y, Z) plans, the generated magnetic field at X=-40 mm (Fig. 2.c) is more important compared to X=-0 mm (Fig. 2.b). The distribution of the generated magnetic field by the MTLA is depending on the orientation of the magnetic field lines between the juxtaposed coils. Between each juxtaposed sub-loops we can see a rotation of the magnetic field (see Fig2.d). For example, between the sub-loops (1 and 2), the rotation of the magnetic field lines can be seen at (X, Y) plans, while between subloops (1 and 3), the rotation of the magnetic field lines can be seen only in (X, Z) plans. Optimizing RFID detection needs to have the surface of the tag perpendicular to the generated magnetic field lines, the MTLA can be benefic for all possible configuration of the tag coil.

B. Mutual inductance

In HF RFID systems, the mutual inductance is calculated from the magnetic coupling between the reader and the tag coils. In this part of HF RFID system the communication corresponds to the conventional link of near field communication: the mutual inductance can be calculated from the impedance matrix parameters [START_REF] Benamara | Calculation of the Equivalent Mutual Impedance in Complex HF RFID Systems[END_REF]. (2)

(3) (4) Y X
To calculate the mutual inductance between the MTLA and the tag, the electrical model of the system is used (Fig. 3). The coils of the reader and the tag are modeled by inductances Li and their serial resistance ri (in the MTLA system the inductance of the system corresponds to the sum of four inductances). In The reader part, a capacitance is added to tuning the frequency at 13.56 MHz. The tag is represented by and an inductance with a chip. The inductances and the serial resistances are respectively 7 uH and 9 Ω for the MTLA and 58 nH and 0.075Ω for the tag coil.

According to the theoretical calculations of the equivalent mutual inductance in the case of the TLA in [START_REF] Benamara | A twisted loop antenna to enhance HF RFID detection areas for different tag positioning[END_REF] the mutual inductance in the case of MLTA can be calculated by [START_REF] Finkenzeller | RFID Handbook[END_REF]:

M M M M M T T T T RT 4 3 2 1 (1)
Where:M1T, M2T, M3T and M4T are the mutual inductances between each sub-loop and the tag. This equation is used to evaluate mutual inductance by HFSS simulation. Results are reported in Fig. 4. The evolution of mutual inductance is reported for Y misalignment (From -80mm to 80 mm and three different positions of X: X=-80 mm, X=-40 mm and X=0 mm corresponding respectively to the edges of the MTLA, the center of the sub-loops 1 and 2 and the center of the MTLA (between sub-loops 1 and 3, 2 and 4). From the results, in parallel configuration, the mutual inductance has homogeneous values around 45 nH and 20 nH respectively for X=-40 mm and X=-80 mm. At the center of the MTLA (X= 0mm), the mutual inductance is equal to zero nH for the different values of the Y misalignment except the interval Y=-10mm to Y=10mm, where the mutual inductance has a values of 2nH. The opposite sign of the mutual inductance between the two juxtaposed sub-loops [from -80 mm to 0 mm and from 0 mm to 80 mm] is explained by the opposite current direction between them. Also, the MTLA permits to improve mutual inductance at the intersection zone (between each two sub-loops). In this configuration the maximum of mutual inductance is obtained at the center of the sub coils (X= -40 mm) and the minimum is obtained at its center (X= 0 mm). For perpendicular configuration, the mutual inductance has three maxima corresponding to the edges of the MTLA (Y=±60 mm) and its center (Y=0mm). The best configuration is seen at Y= 0mm where the mutual inductance corresponds to the sum of the mutual inductances between the tag and the juxtaposed sub-loops. For X variation, the mutual inductance is better for X=-40 mm corresponding to the center of the sub-loops. At the center of the MTLA (X= 0mm) the mutual inductance is negligible (around 0 nH).

To improve mutual inductance between to MTLA and the tag, more specially at the center of the MTLA (X=0mm), an array sub-loops reader antenna is proposed in the next part of this paper. A resonator is added at the surface of the MTLA to create the array sub-loops antenna.

III. STEP II : ARRAY SUB-LOOPS ANTENNA

The interest of the proposed array sub-loops antenna is developed in this part for simulation results of magnetic field and mutual inductance. The used resonator has an inductance of 0.29 μH.

A. Magnetic field

The magnitude of the generated magnetic field by the array sub-loops antenna is presented in fig. 5 (in (X,Y) plan) for different positions of the resonator (θ=0°, θ=45°, θ=90° and θ=135°). The generated magnetic field by the array sub-loops antenna for θ=0° and θ=90° is not changed compared to the case of the MTLA (the variation is negligible). The influence of the added resonator is depicted for θ=45° and θ=135°. This is due to the reparation of the magnetic field of the MTLA. From the results, the resonator added presents advantages for no symmetric positioning over the MTLA.

B. Mutual inductance

In the case of the array sub-loops antenna, the mutual inductance is transformed to the equivalent mutual inductance [START_REF] Benamara | Calculation of the Equivalent Mutual Impedance in Complex HF RFID Systems[END_REF]. Its calculation is based on the mutual inductance between the MTLA and the tag, the mutual inductance between the resonator and the tag, the mutual inductance between the MTLA and the resonator and all the electrical parameters of the system. The equivalent electrical model of the array subloops antenna is presented in (Fig. 6) From the results, in both parallel and perpendicular configuration, the added resonator has no effect on the equivalent mutual inductance at X=-80mm corresponding to the edges of the MTLA (±20 nH and ±7nH). The equivalent mutual inductance is similar to the mutual inductance in Fig. 4. This means that the added resonator has only effect at its surface. The results can be confirmed by the generated magnetic field by the MTLA including resonator (Fig. 5), where we can see that the surface of the resonator is far away from X=-80 mm for all values of the tilt θ.

For X= -40mm, in parallel configuration, the equivalent mutual inductance is increased above the surface of the subloops respectively by 3 nH and 4 nH for θ=45° and θ=0°. For θ=90° the added resonator has no effect on the equivalent mutual inductance, the values are comparable to the mutual inductance in Fig. 4. In perpendicular configuration, the equivalent mutual inductance is increased at the zone between the sub-loops by 2nH for θ=45°. The results correspond to the generated magnetic field in field in Fig. 5 where the surface of the resonator for θ=0°, θ=45° and θ=135° includes X=-40mm, while for θ=90° the edges of the resonator are distant from X=-40mm. For X= 0mm, the improvement of equivalent mutual inductance is much more striking in parallel and perpendicular configurations compared to the case without resonator in Fig. 4: 17nH (from 0nH to 17nH) in parallel configuration and 5nH (from 0nH to 5nH) in perpendicular configuration. Also, we can see that the best results are obtained for θ= 45°.

From the different simulated results (generated magnetic field and equivalent mutual inductance), the principle of added resonator and the effect of its surface tilt is validated. As conclusion of this part, the added resonator has no effect at the edges of the TLA (X=-80 mm). In the next part, the RFID detection measurements are developed for X=-40 mm and X=0 mm.

IV. EXPERIMENTAL VALIDATION

The MTLA design is fabricated (Fig. 8.a). Detection measurements are made for the two configurations parallel and perpendicular using a commercial reader and a commercial tag of 22 mm of diameter. The results in Fig. 9 are presented for tag misalignment at X=-40mm and X=-0mm and resonator tilts (θ=0° and θ=45°). The (X, Y) axes in Fig. 9 presents respectively the tag misalignment (Y misalignment in cm) and the distance of detection (d) in cm.

From the results of detection without resonator (Fig. 8.a and Fig. 8.b), the surface and the distance of detection are significantly better in parallel configuration. For X=-40mm, the distance of detection has maxima of 2 cm corresponding to the surface of the sub-loops (near to the transit zone between the sub-loops), the zero detection is observed at the center of the MTLA according to the repartition of the magnetic field lines and mutual inductance. In perpendicular configuration three maxima of detection of 1.4 cm and 0.5cm are seen at the transit zones between the juxtaposed sub-loops and the edges of the sub-loops. For X=0mm, zero of detection is obtained in both parallel and perpendicular configuration. The detection results confirm the results of the simulated magnetic field and mutual inductance. The MLTA design presents the advantage of the rotation of the magnetic field lines between the juxtaposed sub-loops, this improves the possibility of detection of tags in different angular misalignment but in contrast, as we can see in detection results, at the center of the MTLA the detection is not performed (a and b).

To avoid this problem we proposed the array sub-loops antenna. An experimental test of tag detection using the MTLA and a resonator is made using an RFID reader from Ib Technologies (Fig. 8.b). The results are presented for the best tilt of the resonator (θ=45°). As we can see in (Fig. 9.c and Fig. 9.d), the added resonator improves detection (surface and volume) in both parallel and perpendicular configuration. The maxima of distance of detection are respectively improved by 2 cm (at the center of the MTLA) and 0.5 cm (at the surface of the MTLA) in both parallel and perpendicular configurations.

For X=0mm, the results confirm the interest of using resonator by a tilt of 45°. The maxima of distance of detection are improved respectively by 5cm and 3cm in parallel and perpendicular configuration. From the results, we can see that the proposed array sub-loops antenna including the resonator doesn't only improve distance of detection but it also creates new zones of detection.

V. CONCLUSION

A design of an array sub-loops reader antenna is proposed in this paper. The study is divided on to steps. Firstly, a multiple twisted loop antenna (MTLA) is proposed. Its principle is based on the opposite current direction between the juxtaposed sub-loops. This creates the rotation of the magnetic field lines. The HF RFID performances such as magnetic field, mutual inductance and detection are developed. The proposed design antenna is benefic to improve both the surface (according to the lateral misalignment of the tag) and the volume (the distance between the reader and the tag coils) of detection at its surface but at its center a zero of mutual inductance and RFID detection is seen in both parallel and perpendicular configurations. To avoid this problem an array sub-loops antenna is proposed. The design consists on addition of coplanar resonator at the surface of the MTLA. The solution is optimized for different tilt of resonator. The results confirm that the tilt of 45° is the best configuration.

Fig. 1 .

 1 Fig. 1. Poposed MTLA design and array sub-loops antenna

Fig. 2 .

 2 Fig. 2. Magnetic field generated by the MTLA in (X, Y) plans (a) and (Y, Z) plans at X=0 mm (b) and X=-40mm (c). (d) is the distribition of magnetic field lines at X=-40mm

Fig. 3 .

 3 Fig. 3. Electrical model of the MTLA and the tag coils

Fig. 4 .

 4 Fig. 4. Mutual inductance for parallel (a) and perpendicular (b) conficuration

Fig. 5 .

 5 Fig. 5. Generated magnetic field by the array sub-loops antenna for different resonator tilts

Fig. 6 .

 6 Fig. 6. . .Electrical model of the array sub-loops antennaThe equivalent mutual inductance between array sub-loops antenna and the tag can be calculated by:

Fig. 7 .

 7 Fig. 7. Equivalent mutual inductance for array-sub-loops antenna in parallel (a) and perpondicular (b) configuration

Fig. 8 .

 8 Fig. 8. Fabricated MTLA design and array sub-loops antenna

Fig. 9 .

 9 Fig. 9. RFID detection for MTLA design (a, b) and array sub-loops antenna (c, d) respectively in parallel and perpendicular configurations


Amélie Cavelan

Mohammed Boussafir

Claude Le Milbeau

Olivier Rozenbaum

Fatima Laggoun-Defarge

Organic matter influence on porosity of Kimmeridge-Clay source-rocks: insights from organic petrography and laboratory thermal maturation

This work investigates how slight differences in the relative proportion of OM components and maceral types of marine mudstones throughout a same formation can influence the development and the evolution of OM-pore network during thermal diagenesis of organic-rich marine mudstones. To this end, laboratory gold-tube anhydrous confined thermal maturation, geochemical characterization, organic petrography (palynofacies and macerals analysis), nitrogen adsorption porosimetry, and SEM observations were applied on low-mature marine Kimmeridge Clay (KCF) mudstones. The main properties of organic-rich KCF samples which exhibit a slightly different total particulate OM assemblage were compared before and after maturation at 325°C, 390°C and 470°C for 72h. The results show that organic-rich KCF samples containing higher proportion of oil-prone orange amorphous organic matter (AOM) derived from phytoplanktonic components have developed smaller pores during thermal maturation resulting in lower pore volumes than samples containing higher proportion of brown AOM derived from the selective preservation of cell-walls of green microalgae. Contrary to brown AOM, orange AOM appears thus to be less favorable to the formation of large mesopores. This result suggests that no clear positive correlation exists between the oil-prone quality (HI) of OM and its ability to develop pores during thermal maturation

Introduction

It has been well documented that thermal maturation of organic matter (OM) with burial is the main factor controlling the development of OM-pores in organic-rich mudstones [START_REF] Bernard | Formation of nanoporous pyrobitumen residues during maturation of the Barnett Shale (Fort Worth Basin)[END_REF][START_REF] Katz | Organic porosity: A geochemist's view of the current state of understanding[END_REF][START_REF] Ko | Pore-types and porenetwork evolution in Upper Devonian-Lower Mississippian Woodford and Mississippian Barnett mudstones: Insights from laboratory thermal maturation and organic petrology[END_REF][START_REF] Loucks | Spectrum of pore types and networks in mudrocks and a descriptive classification for matrix-related mudrock pores[END_REF]. The available literature reveals that the thermal conversion of kerogen and the subsequent hydrocarbons generation as oil, gas and solid bitumen are closely associated with changes in abundance, shape or size of OM-hosted pores [START_REF] Bernard | Formation of nanoporous pyrobitumen residues during maturation of the Barnett Shale (Fort Worth Basin)[END_REF][START_REF] Katz | Organic porosity: A geochemist's view of the current state of understanding[END_REF][START_REF] Ko | Pore-types and porenetwork evolution in Upper Devonian-Lower Mississippian Woodford and Mississippian Barnett mudstones: Insights from laboratory thermal maturation and organic petrology[END_REF][START_REF] Loucks | Spectrum of pore types and networks in mudrocks and a descriptive classification for matrix-related mudrock pores[END_REF]. Relationship between maturity and porosity is however, not always clear and contradictions exist between pore evolution models [START_REF] Katz | Organic porosity: A geochemist's view of the current state of understanding[END_REF]. Previous works suggests that OM-porosity is mainly the result of the secondary cracking of kerogen and bitumen, in response to the exsolution of gas [START_REF] Bernard | Formation of nanoporous pyrobitumen residues during maturation of the Barnett Shale (Fort Worth Basin)[END_REF]. Solid bitumen is thus often considered to be the main contributor to the porosity of thermally-mature mudstones [START_REF] Bernard | Formation of nanoporous pyrobitumen residues during maturation of the Barnett Shale (Fort Worth Basin)[END_REF]. Some evidence shows that OM-hosted pores can be occurred earlier, in the oil window within solid bitumen and/or kerogen [START_REF] Katz | Organic porosity: A geochemist's view of the current state of understanding[END_REF][START_REF] Ko | Pore-types and porenetwork evolution in Upper Devonian-Lower Mississippian Woodford and Mississippian Barnett mudstones: Insights from laboratory thermal maturation and organic petrology[END_REF]. Furthermore, for a given maturity, two formations containing a type II OM can exhibit very different OM-porosity evolution suggesting that other non-maturity related factors such as the maceral composition may have locally a significant influence on porosity [START_REF] Katz | Organic porosity: A geochemist's view of the current state of understanding[END_REF][START_REF] Ko | Pore-types and porenetwork evolution in Upper Devonian-Lower Mississippian Woodford and Mississippian Barnett mudstones: Insights from laboratory thermal maturation and organic petrology[END_REF]. For example, [START_REF] Ko | Pore-types and porenetwork evolution in Upper Devonian-Lower Mississippian Woodford and Mississippian Barnett mudstones: Insights from laboratory thermal maturation and organic petrology[END_REF] shows that Barnett and Eagle Ford mudstones characterized by differences in Tasmanites abundances exhibit different pore evolution models. Nevertheless, to isolate the influence of these non-maturity related factors on porosity turns out to be a complete exercise [START_REF] Katz | Organic porosity: A geochemist's view of the current state of understanding[END_REF]. The process of pores development during hydrocarbon generation, the influence of total organic carbon content, and more specifically the influence of the maceral composition needs to be clarified. To investigate if the composition of the total particulate OM assemblage influences the development and the evolution of OM-pore network of organic-rich marine mudstones during thermal diagenesis, laboratory gold-tube confined thermal maturation, geochemical characterization, organic petrography (palynofacies and macerals analysis), porosimetry measurement, and SEM observations were applied on low-mature marine Kimmeridge Clay mudstones. The specific research question addressed is the following: do slight differences in the relative proportion of OM components and maceral types of marine mudstones throughout a same formation affect OM pore development and evolution during maturation?

Methods

Small-diameter rock cylinders and ≈ 1 g of total rocks powder of immature organic-rich argillaceous marine mudstones collected from the Kimmeridge Clay formation (Ebberston well, Cleveland basin, UK) were artificially matured using anhydrous gold tube confined (600 bars) pyrolysis. The samples were heated under inert-gas and isothermal conditions at temperatures of 325°C, 390°C and 470°C for 72 hours. Palynofacies analysis was carried out on Kimmeridge Clay mudstones isolated OM (transmitted light microscopy, oil immersion) to quantify the relative proportion of individual organic components before maturation. The small cylinders of immature and artificially matured rocks were impregnated in epoxy resin and argon-ion milled (5kV for 1 hour, 2kV for 30 min, 4° tilt angle, 220 µA). Petrographic observations were carried under oil immersion using reflected and UV-fluorescence light to identify the different macerals and their evolution with increasing thermal maturity. SEM observations were then conducted using backscatter (BSE) and secondary electron (SE) modes. The amount and the quality of OM before and after maturation were determined using Rock Eval 6 ® pyrolysis. The molecular composition of the gas produced during maturation was determined using a Perkin Elmer® Clarus 580 gas chromatograph fitted with a Supelco® Carboxen 1010 Plot® Capillary column. The total number of moles of gas was quantified assuming ideal gas behavior and using their respective peak areas on chromatograms and calibration curves. About 1g of each powdered sample were ultrasonically extracted with a mixture of dichloromethane/methanol (1/1, v/v). The extracts were separated by deactivated silica gel (5% with water) chromatography column. The aliphatic fractions were recovered by elution with heptane, the aromatic fractions were recovered by the subsequent elution of a mixture of heptane/toluene (3/1) and (1/1). The polar fractions were recovered by elution with methanol. Each fraction was finally dried under nitrogen and weighed to obtain the total extracted mass of saturated, aromatic and polar compounds. The pore volume and the pore-size distribution were measured by nitrogen adsorption measurements using a Quantachrome® NOVA 2200 e apparatus. The total pore volume was determined at the relative pressure P/Po of 0.987. To avoid tensile strength effects pore size distributions were determined from the adsorption isotherm using the Barrett, Johner and Halenda (BJH) method [START_REF] Barrett | The Determination of Pore Volume and Area Distributions in Porous Substances. I. Computations from Nitrogen Isotherms[END_REF].

Results and discussion

The main properties of two representative organic-rich Kimmeridge Clay samples named Sp1 and Sp2 and their evolution with thermal maturity are presented in Figure 1 and 2. These low-mature Kimmeridge Clay mudstones are composed of a well-preserved type II oil-prone kerogen (HI ranges from 418-617 mg HC/g of TOC) mainly composed of brown and orange amorphous organic matter (AOM) derived respectively from cell walls of green microalgae and oil-prone phytoplanktonic OM preserved by natural sulfurization (Figure 1A). These AOM components are supplemented by minor contributions of black AOM and structure organic components (<18%) derived from algal spores, phytoplanktonic organic-walled, pollen grains and various debris derived from plant tissues (Figure 1A). In petrographic observations, this is marked by abundant alginite and bituminite macerals (Figure 1B) with a high yellowish to brown UV-fluorescence accompanied by sparse inertinite fragments. In SEM observations, the porosity of all these low-mature rocks is mainly composed of inter-particle mesopores located between grains of calcite, albite and quartz and clay minerals sheets aggregates (Figure 1C). The OM appears gellified and non-porous (Figure 1C) and does not greatly contribute to the total pore volume (≈ 3.40 cc/100g, Figure 2A) mainly composed of mesopores in the 2-30 nm pore size range (Figure 2B). Changes in the OM composition exists between samples (Figure 1A). Sample Sp2 contains higher proportions of oil-prone orange AOM and thus exhibit a slightly higher kerogen quality (HI, Figure 1A) than sample Sp1. In petrographic observations, this is marked by the presence of higher amount of bituminite macerals in Sp2 (Figure 1B). Conversely, OM of Sp1 is mainly composed of brown AOM and structured organic components such as plant tissues, algal spores and pollen grains (Figure 1A) with lower amounts of bituminite in petrographic observations.

Figure 1 A) Difference of palynofacies composition of 2 low-mature Kimmeridge Clay samples (Sp1 and Sp2) as a function of TOC and hydrogen index (HI). AOM: amorphous organic matter. B) Photomicrographs (oil immersion, transmitted light) and C) SEM images (BSE) of broad ion beam milled thin sections of Kimmeridge

Clay samples before and after maturation at 390°C/72h. OM: organic matter.

After maturation at 325°C/72h, the filling of mesopores by oil and/or bitumen generation and migration appears to have limited the availability of mineral interparticular pores causing the reduction of porosity of all samples. After maturation at 390°C and 470°C/72h, oil and gas generation (Figure 2A) has occasioned the formation of abundant secondary solid bitumen (Figure 1B) which is the dominant maceral in thermally matured samples. In SEM images, this carbon-rich residue appears to be the main contributor to the porosity of artificially matured Kimmeridge Clay samples (Figure 1C). The formation of these abundant and porous residual macerals is correlated with the re-increase of the pore volume in the gas generation stage (Figure 2A). However, during OM conversion, the difference in the relative proportion of individual OM components between Sp1 and Sp2 has led to changes in the amount of oil and gas generated during thermal maturation (Figure 2A) resulting in a different evolution of pore volume and pore size distribution during the gas generation stage (Figure 2A andB). During OM conversion, the higher proportion of oil-prone orange AOM of Sp2 has led to the production of higher amount of low viscous oil, abundant gaseous hydrocarbons and lower CO2 concentrations (Figure 2A) more favorable to the formation of abundant but smaller mesopores than for sample Sp1 (Figure 2B). After maturation at 390°C/72h, the porosity of Sp2 is mainly composed of mesopores smaller than 20 nm in diameter with a maximum of pores in the 2-7 nm pore size range (Figure 2B). Meanwhile, the slightly lower oil-potential of Sp1 OM seems to have produced heavier and more viscous oils. The secondary cracking of them have occasioned the formation of greater quantity of non-hydrocarbon gases (CO2, Figure 2A) and abundant secondary solid bitumen more favorable to the formation of fewer but larger mesopores (>10 nm, Figure 2B). After maturation at 470°C/72h, the fine mesopores of Sp2 have developed and coalesced in response of methane generation to form more complex larger mesopores and macropores (Figure 2B). Surprisingly, this phenomenon has not conduced to the increase of Sp2 pore volume which remains relatively constant throughout the gas generation stage (Figure 2A andB). Meanwhile, Sp1 OM pore network has also continued to develop in response to the production of methane (Figure 1A). This has led to the strong increase of Sp1 total pore volume (Figure 2B) marked by the formation of abundant mesopores and macropores in the 4-100 nm pore size range (Figure 2B). Despite a higher oil-prone quality, samples containing higher amount of orange AOM (Sp2) appear thus, to be less favourable to the formation of larges mesopores during thermal maturation resulting in lower pore volume in the dry gas zone (Figure 2A). Samples with the lower oil and gas generation potential are therefore not systematically those who have developed the lower pore volume during maturation. This suggest that the different properties and behaviour of orange and brown AOM during thermal maturation can have a significant influence on OM-pore development and evolution in marine mudstones.

Conclusions

This work shows that slight variations of the relative proportion of the individual organic components of similar type II kerogen can significantly affect variations of the amount of petroleum and gas generated during maturation and the evolution of porosity throughout a same formation. Our results show that organic-rich KCF samples (Sp2) containing higher proportion of oil-prone orange AOM preserved by natural sulfurization of phytoplanktonic components exhibit a slightly different pore evolution from samples (Sp1) containing higher proportion of brown AOM derived from the selective preservation of cell-walls of green microalgae. Despite their higher oil-prone quality, samples Sp2 have developed smaller pores during thermal maturation resulting in lower pore volumes. Contrary to brown AOM, orange AOM appears thus to be less favorable to the formation of large mesopores. This suggests that no clear positive correlation exists between the oil-prone quality (HI) of OM and its ability to 81st EAGE Conference & Exhibition 2019 3-6 June 2019, London, UK develop pores during thermal maturation. If maturity appears to be the dominant factor controlling porosity, this work shows that non-maturity related factors such as the original oil and gas generation potential tied with the original particulate OM assemblage can be significant. As suggested by previous works, simply considering the level of maturity is thus largely insufficient to understand the development and the evolution of OM pores in organic-rich marine mudstones. That put forward the necessity to clearly identify the composition of the original particulate OM assemblage in order to better predict the amount of oil and gas generated during maturation and the associated porosity development and evolution.

Figure 2

 2 Figure 2 A) Evolution of free hydrocarbons content (S1), condensable gases concentrations (including CO2 and C1-C5: methane, ethane, propane, butane and pentane), pore volume and saturated hydrocarbon content (in percent of the total extractible OM) before and after maturation of two Kimmeridge Clay samples (Sp1 and Sp2). B) Evolution of the pore size distribution of two Kimmeridge Clay samples (Sp1 and Sp2) before and after maturation at 390°C and 470°C/72h.

Acknowledgements

We would like to thank Mrs. Ida Di Carlo for guidance on sample preparation and SEM BSE and SE analysis and Mrs. Rachel Boscardin and Nathalie Lottier for their assistance in the laboratory.


Antoine Beugnard
email: antoine.beugnard@enst-bretagne.fr

Method overloading and overriding cause encapsulation flaw An experiment on assembly of heterogeneous components

Keywords: D.1.5 [Programming Techniques]: Object-Oriented Programming, D.2.3 [Software Engineering]: Coding Tools and Techniques, D.2.12 [Software Engineering]: Interoperability objet oriented language interoperability, encapsulation, software component

Based on an experiment using three languages under .NET, this paper argues that the semantic differences between these languages regarding method overloading and overriding give rise to significant complexity and break encapsulation. We first recalls the various interpretations of overriding and overloading in object oriented languages through what we call language signatures. Then, we realize an experimentation with .NET components coded in different programming languages in order to observe the global behavior. From this, we show that overriding and overloading are not compatible with a key property of components: encapsulation. We conclude that, in the current state of the art, in order to build predictable assembly, components must expose their internal structure! We propose a solution to this problem.

INTRODUCTION

For the past 25 years, object technologies have been spreading in programming languages, development method, and modelling technique. Almost all non-object languages have their "OO-extension": ADA, Caml, C and even COBOL. Analysis and design methods rely more and more on a unifying modelling language (UML) that relies itself on objects. But it seems that the hope object is the silver bullet solution has gone. Reusing is not so simple and assembling object remains complex. The need for a better engineering process leads to the development of software by assembly of software components. The idea to develop software systems as electronic ones is not new [START_REF] Mcilroy | Mass produced software components[END_REF], but only recently have we seen many components models being industrially used (CCM, DCOM, EJB, Fractal, .NET). All are implemented with objects.

We demonstrate that the various behaviors that object programming languages have relatively to methods overriding and overloading semantics misfit with one of the main feature of components: encapsulation.

The article is organized as follows. We first recall in the next section some of these behaviors, and in section 3 how components interfaces can be described with contracts. Then, in section 4 we present the experiment that demonstrates that the assembly of heterogeneous components cannot be predictable if their interface is not precise enough; that is exposes many implementation details. We conclude with some suggestions to solve this problem.

OVERLOADING AND OVERRIDING

The main contribution of object programming is, to our point of view, the easy access to dynamic dispatching that makes possible the development of frameworks. Frameworks can be easily extended, specialized thanks to dynamic dispatching. Being easy to use and safe, thanks to type systems (unlike in C where function pointers could be used to implement it), object-oriented languages allow the development of more flexible and reusable softwares. However, the benefit of this "late-binding" is balanced out by the time required to apply the lookup procedure that implements the dynamic dispatching and by the fact that any user needs to know the extension points (methods) of the framework s/he uses. This powerful mechanism is however difficult to use since the overriding intent expressed in a diagram such as in figure 1 is understood differently by object programming languages. As it has already been published in [START_REF] Beugnard | OO languages late-binding signature[END_REF] the interactions between overloading and overriding lead to very different behaviors. For instance, overriding can be invariant, covariant or contravariant, but nothing prevents a language to accept these three possibilities at the same time. The late-binding resulting of the detection of this overriding can be simple, the most frequent case, or multiple, like in CLOS. Overloading can be allowed or not.

In order to show the different interpretations we have implemented the model of figure 1 called all possible cases and built what is called a language signature [START_REF] Beugnard | OO languages late-binding signature[END_REF]. Table 1 shows how the signature is elaborated. Each slot1 contains the name of the class where the applied method was found. The word "Error" denotes a compilation error. First and third columns are identical since the three languages adopt an invariant overriding policy. Hence, in our C++ rejects the first line (of column 2) considering that the method cv(Middle) hides the previously defined method cv(Top).

The last line of the second column is Down for C++ and C# following the intuitive semantics of OO languages where the most specific method, accordingly to the receiver, is selected.

The result of the last line for Visual Basic is due to the priority given to the parameter over the receiver in order to select the method; Bottom in ctv(Bottom) of Up is considered by Visual Basic as more specialized than Middle in ctv(Middle) of Down. This is a strict interpretation of overloading; the parameter is used to select the method.

COMPONENT AND CONTRACT

A software component is defined in [START_REF] Szyperski | Component Software -Beyond Object-Oriented Programming[END_REF] as independent software entity, that can be deployed and composed with others. Many models of component have been proposed. All rely on a feature that allows to describe components while hiding unnecessary details: encapsulation. Information needed to assemble a component is not the component itself -considered as a white-box -but the interface of the component. In that case, the component is seen as a black-box. Many authors have noticed that to be able to compound components some implementation details must be exposed in order to ensure a correct assembly [START_REF] Büchi | The greybox approach: When blackbox specifications hide too much[END_REF]. The component is then viewed as a grey-box.

Beugnard and al. have proposed in [4] to attach a contract to a component in order to organize information of its interface. A contract may contain 4 levels: syntactic, semantic, behavioral, and quality of service. Only the first level is needed for the experiment we have realized. This level ensures the "compilability" of interfaces; it is used to check that method names, return types, parameter numbers and types are compatible with components it is assembled with.

In case of an assembly of heterogeneous components what is level of greyness of a component? As we will see, in order to be able to predict the behavior of some assembly the syntactic contract of a component may need to expose its implementation language but also make explicit assumption on the implementation languages of its clients!

COMPONENTS ASSEMBLY

.NET Experiment

The model of figure 1 may serve as an experiment of components assembly. Imagine, as in figure 2, that classes Up, Top, Middle and Bottom define a framework C1 written in a language L1. Later, an evolution of C1 is realized by the class Down written in a language L2 that extends Up. This defines the component C2. A client C3 is written in a language L3.

We have realized this experiment with the .NET [START_REF]Microsoft .NET[END_REF] framework that claims language interoperability. We used 3 languages integrated into the framework: C#, Visual Basic and C++. Each of them was used to develop the 3 components, leading to 27 (3*3*3) different assemblies.

The language signatures of many languages including (ADA, Java1.3, Java 1.4 2 , Smalltalk, CLOS) and the source code of the experiment can be seen at (hidden)

Results

Results are organized in 3 tables of 9 signatures. A table is associated to a client language (C#, Visual Basic, C++ respectively). The programming language of the basic framework (L1) appears by column. The programming language of the extension (L2) appears by line. Each cell is the observed language signature.

Table 5 shows result for a C# client. The result is mainly a C# signature but for the C++ column where the C++ signature is observed.

Table 6 shows result for a Visual Basic client. The result is mainly a Visual Basic signature but for the C++ column 2 Yes, Java signature changed between 1.3 and 1.4!

Table 5: C# client results (L3 = C#) L2/L1 C# VB C++ C# C# C# C++ VB C# C# C++ C++ C# C# C++
where the C++ signature is observed. Another difference is observed. When the framework is written in Visual Basic and the extension in C++, the observed signature is C# which is not used at all!

Interpretation

The signatures observed are mainly those expected by the client, i.e. the client's signature. C# and C++ client are the more stable with 6 over 9 "good" cells while Visual Basic has only 5 over 9 "good" results. The reasons for the "bad" behavior are mainly due to C++ when clients are C# or Visual Basic, probably because of the inheritance exception of C++ in slot line 1, column 2 of table 2 where cv(Top) of Up is hidden by the overloading cv(Middle) of Down.

If we try to write down the syntactic contract of the component C2, we would produce something like what is presented in table 9. C3 is the client.

This table reveals that the contract makes references to implementation details of the component and, worst, to a client internal feature: the implementation language. The encapsulation is broken. The black-box whitens and borders fade away . . . Explicit references to the implementation language could be replaced by generic language features following the approach proposed in [START_REF] Capouillez | Le modèle ofl au service du métaprogrammeur -application à java. L'objet[END_REF]. However, language signatures diversity and the finer points of the interpretations convinced us

C#C# VBC# C++C# u d ud u d ud u d ud cv(T) U E U U E U U E U cv(M) U D U U D U U D U cv(B) U D U U D U U D U ctv(T) E E E E E E E E E ctv(M) E D E E D E E D E ctv(B) U U U U U U U U U
that such generic language features would be more complex to describe than the simple reference to the language. Beyond a deep understanding of these results, this experiment shows that in order to be able to predict the behavior of a component assembly, the client of a component must have information on the way the overriding and overloading are interpreted. This information relies on the languages used to realize the component but also on the whole internal structure such as inheritance relationships, overloading and overriding actually done. So, what about encapsulation?

More Experiments

We are convinced, but experiments remain to be done, that the use of the Eiffel language in the experiment would increase the diversity of behaviors. The semantic distance between Eiffel and C++, C# and Visual Basic being larger as Eiffel signature of table 10 shows. Eiffel forbids overloading (Errors on line 4 and 5) and allows covariant overriding (see column 3 lines 1,2 and 3). Column 2 is a mixing of C++ on the first line (Error) and Visual Basic on the last line (Up).

CONCLUSION

Our experiment is limited to the .NET environment, with very semantically close languages; overriding is invariant and overloading is allowed. In this context, the diversity of behaviors is great.

Theoretical researches on component assembly mainly focuss on static aspects of linking [START_REF] Drossopoulou | A fragment calculus towards a model of separate compilation, linking and binary compatibility[END_REF][START_REF] Ancona | Sound and complete inter-checking (the very essence of principal typings)[END_REF][START_REF] Ancona | A calculus for dynamic linking[END_REF] even when they deal with dynamic linking; it is in the sense of "compiler linkers" not in the sense of "object-oriented late-binding". They look for typing theories that ensure error-free compilations, ignoring the expected behavior. On the other hand, practical approaches propose component models implementations in homogeneous contexts (Java for instance) or let the responsibility to programmers to manage the composition of components (CCM or CORBA for instance).

In order to be fully usable, components need to be reused in open and multi-languages contexts. The behavior of the components assembly must be predictable from components interface specification 3 .

In order to reach this goal, here are some suggestions:

• We could study the interactions combination among languages. But, as our experiment shows for only 3 languages rather semantically close, all combinations are to be considered. This is exponential, and as table 8 shows in its first line, the "combination operator" can lead to unexpected signatures. It is not a binary operation. Because of the number of programming languages and the diversity of their signatures, this approach seems untractable. But could we do otherwise?

• We could enrich the level of information in the contract in order to express how the component interprets overloading and overriding. Overloading and overriding semantics should not remain implicit, but as our experiment shows, should be explicit. This solution also requires the previous approach and a good understanding of language combination.

• We could eventually compel the use of overriding to the invariant case and forbid overloading. With such a restriction, all object programming languages have the same behavior, hence the assembly is simple. This solution requires to modify compilers and languages.

An interesting study would be to count the number of "difficult cases" to be able to evaluate the impact on existing codes 4 .

The latter solution seems to be the most tractable. But it may be considered as too strong a change. Limiting this restriction to the public interface would allow programmers to continue to use their well-known programming patterns involving overloading inside the component. Programming language history shows that programming language evolution follows a double movement; first a generation of ideas and concepts that are implemented and tested, then a selection among these concepts. This selection generates language restrictions. For instance, the "GOTO" has been replaced in order to improve the structure of programs. It may be time for object programming languages to make a decision and select the good (and constraining) rules of overriding and overloading.

Overloading have already been criticized [START_REF] Meyer | Overloading vs. object technology[END_REF][START_REF] Ducournau | Spécialisation et sous-typage : thème et variations[END_REF] and this article can be considered as another argument against overloading; it interacts badly with overriding. The choice for a covariant, invariant or contravariant overriding is more open. In practice, invariance is largely used and its implementation is rather easy. Covariance is hard to implement, and not always safe as Eiffel signature shows at column 3 line 1. Contravariant, if theoretically sound, is rarely implemented. Hence, a tradeoff could be to choose invariant overriding.

More experiments need to be made with more languages, and different scenarios. For instance, we could imagine experiments with 2 components without extension or extension within the client component. Whatever, we feel strange that researches on overriding and overloading interactions are uncommon. In a context where model transformations (MDA [START_REF]OMG. site mda[END_REF]), language interoperability through middleware (CORBA, SOAP) or virtual machine (.NET, Java), and assembly of components are considered as key technologies, it is astonishing!

The problem of assembling components realized in different languages is real. We believe that the extension of components in different languages may become frequent in the future. Whatever, both situations can occur and should be considered in theories and in programming languages design.

Figure 1 :

 1 Figure 1: How will this model behave?

Figure 2 :

 2 Figure 2: How will this assembly behave?

Table 1 :

 1 Signature elaboration

	procedure main
	-receivers
	Up u, ud;
	Down d;
	-parameters
	Top t = new Top();
	Middle m = new Middle();
	Bottom b = new Bottom();
	-First test	-Second test	-Third test
	u := new Up(); d := new Down(); ud := new Down();
	u.cv(t);	d.cv(t);		ud.cv(t);
	u.cv(m);	d.cv(m);		ud.cv(m);
	u.cv(b);	d.cv(b);		ud.cv(b);
	u.ctv(t);	d.ctv(t);		ud.ctv(t);
	u.ctv(m);	d.ctv(m);		ud.ctv(m);
	u.ctv(b);	d.ctv(b);		ud.ctv(b);
	The next three tables show the signatures of C++ [15]
	(table 2), Visual Basic [13] (table 3) and C# [9] (table 4)
	since we use them in the experiment of section 4.
	Table 2: C++ signature
	calls		u	d	ud
	cv(t)		Up	Error	Up
	cv(m)		Up	Down	Up
	cv(b)		Up	Down	Up
	ctv(t)		Error Error Error
	ctv(m) Error Down Error
	ctv(b)	Up	Down	Up

Table 3 :

 3 and ud return the same results since both are statically declared as Up. All differences are in the second column, when a receiver d is declared Down and actually Down. Differences (in bold in the tables) are due to the overloading rules that are different in C++, C# and Visual Basic.

		Visual Basic signature
	calls	u	d	ud
	cv(t)	Up	Up	Up
	cv(m)	Up	Down	Up
	cv(b)	Up	Down	Up
	ctv(t)	Error Error Error
	ctv(m) Error Down Error
	ctv(b)	Up	Up	Up
	experiment, u

Table 4 :

 4

		C# signature
	calls	u	d	ud
	cv(t)	Up	Up	Up
	cv(m)	Up	Down	Up
	cv(b)	Up	Down	Up
	ctv(t)	Error Error Error
	ctv(m) Error Down Error
	ctv(b)	Up	Down	Up

Table 6

 6

	: Visual Basic client results (L3 = VB)
	L2/L1 C# VB	C++
	C#	VB VB C++
	VB	VB VB C++
	C++	VB C# C++

Table 7

 7 shows result for a C++ client. The result is mainly a C++ signature but for the C# line where the observed signature does not match any known signature. The new signature is a mixing of C++ and Visual Basic signatures.

	Table 7: C++ client results (L3 = C++)
	L2/L1	C#	VB	C++
	C#	(C++/VB) (C++/VB) (C++/VB)
	VB	C++	C++	C++
	C++	C++	C++	C++

Table 8

 8 shows the detailed results of the first line of the previous table (D denotes Down, U Up and E Error). It shows the mixing of C++ and Visual Basic signatures. Notice the last line where the Visual Basic behavior appears everywhere, even when Visual Basic is not used!

Table 9 :

 9 Component extension (C2) contract attempt

	Services	Returns the result of method found in:
	cv(Top)	Up
		Error when receiver is Down declared Down and C1 is written in C++
		or if C3 is written in C++.
	ctv(Bottom) Up often, but
		Down when
		(1) C3 is written in C# and when receiver is Down declared Down, or
		(2) C3 is written in Visual Basic and when C1 is written in C++ or
		when (C1 is written in Visual Basic and C2 in C++), or
		(3) C3 is written in C++ and when C2 is written in Visual Basic or C++.
	cv(Middle)	Up often, but
		Down when receiver is Down declared Down.
	ctv(Middle)	Down
		Error when receiver is not Down declared Down.

Table 8 :

 8 Detailed results for a C++ client and a C# extension

Table 10

 10

		: Eiffel signature
	calls	u	d	ud
	cv(t)	Up	Error Down
	cv(m)	Up	Down Down
	cv(b)	Up	Down Down
	ctv(t)	Error Error	Error
	ctv(m) Error Error Error
	ctv(b)	Up	Up	Up

We use the word "slot" in this context and the word "cell" in the more complex tables of the following section.

Probably with more information than the simple syntactic contract used during this experiment.

ACKNOWLEDGMENTS

I want to thank the anonymous reviewers for their precise comments and suggestions.