Aloïs Dreyfus

Pierre-Cyrille Héam

Olga Kouchnarenko

Random Grammar-based Testing for Covering All Non-Terminals

Keywords:

In the context of software testing, generating complex data inputs is frequently performed using a grammar-based specification. For combinatorial reasons, an exhaustive generation of the data -of a given size -is practically impossible, and most approaches are either based on random techniques or on coverage criteria. In this paper, we show how to combine these two techniques by biasing the random generation in order to optimise the probability of satisfying a coverage criterion.

I. INTRODUCTION A. Motivation

Producing trusted software is a central issue in software engineering. Testing remains an inescapable step to ensure software quality. In reaction to the limitations of manual testing, recent years have seen a rise in the research interest for systematic testing frameworks grounded in theory. Random testing is a natural approach, empirically known to detect many kinds of bugs. However, by definition, low-probability behaviours cannot be adequately tested in that way. Conversely, non-random testing tends to focus on a few edge cases of particular interest to the tester, at the expense of all others. Indeed, it can cover various behaviours, but their choice depends on tester's priorities and, in general, each behaviour is tested in a unique way.

In [START_REF] Denise | Coverage-biased random exploration of large models and application to testing[END_REF], it is explained how to bias a uniform random testing approach using constraints given by a coverage criterion, in order to optimise the probability of satisfying this criterion. The technique is developed for path generation in a graph. The contribution of the present paper consists in enriching this approach with a coverage criterion on non-terminal symbols of the grammar, allowing the user to apply it to grammar-based testing.

B. Related Work

Grammar-based testing is frequently used for generating structured inputs, as in [START_REF] Purdom | A sentence generator for testing parsers[END_REF] for parser testing or in [START_REF] Daniel | Automated testing of refactoring engines[END_REF] to test refactoring engines (program transformation software). Systematic combinatorial approaches [START_REF] Coppit | Yagg: an easy-to-use generator for structured test inputs[END_REF] lead to a huge number of sequences, and symbolic approaches are frequently preferred [START_REF] Lämmel | Controllable combinatorial coverage in grammar-based testing[END_REF], [START_REF] Majumdar | Directed test generation using symbolic grammars[END_REF], [START_REF] Godefroid | Grammar-based whitebox fuzzing[END_REF]. In [START_REF] Xu | A toolkit for generating sentences from context-free grammars[END_REF], a generic tool for generating test data from grammars has been proposed. This tool does not provide any random feature but is based on rule coverage algorithms and techniques, as defined in [START_REF] Purdom | A sentence generator for testing parsers[END_REF], [START_REF] Lämmel | Grammar testing[END_REF], [START_REF] Zheng | A sentence generation algorithm for testing grammars[END_REF], [START_REF] Alves | A case study in grammar engineering[END_REF].

Random test generation techniques -initially proposed in [START_REF] Duran | A report on random testing[END_REF], [START_REF] Hamlet | Random testing[END_REF] -are frequently used for practical reasons, as in [START_REF] Godefroid | DART: directed automated random testing[END_REF], [START_REF] Oriat | Jartege: A tool for random generation of unit tests for java classes[END_REF], [START_REF] Denise | Coverage-biased random exploration of large models and application to testing[END_REF]. Combining random generation and grammarbased testing is explored in [START_REF] Mckenzie | Generating string at random from a context-free grammar[END_REF], [START_REF] Hickey | Uniform random generation of strings in a context-free language[END_REF], [START_REF] Maurer | The design and implementation of a grammar-based data generator[END_REF], [START_REF] Héam | Seed: An easy-to-use random generator of recursive data structures for testing[END_REF], [START_REF] Dadeau | On the use of uniform random generation of automata for testing[END_REF], [START_REF] Héam | A random testing approach using pushdown automata[END_REF], without exploiting any coverage criteria, or using an isotropic random walk as in [START_REF] Enderlin | Grammarbased testing using realistic domains in php[END_REF].

C. Layout

Section II presents the notions and notations used in this paper. Section III explains how to optimise random testing to satisfy a given coverage criterion. The theoretical contributions are provided in Section IV, which shows how to use this technique to optimise the coverage of non-terminal symbols in a grammar-based testing context. An illustrating example is developed in Section V. Finally, Section VI concludes.

II. FORMAL BACKGROUND A. Context-free Grammars and Random Generation

In this paper, the cardinality of a finite set S is denoted |S|.

a) Context-free Grammars: A context-free grammar is a tuple G = (Σ, Γ, S 0 , R), where Σ and Γ are disjoint finite alphabets, S 0 ∈ Γ is the initial symbol, and R is a finite subset of Γ×(Σ∪Γ) * . The elements of Σ are called terminal symbols, and the elements of Γ are called non-terminal symbols. An element (X, u) of R is called a rule of the grammar and is frequently denoted

X → u. A word w ∈ (Σ ∪ Γ) * is a successor of v ∈ (Σ ∪ Γ) * for the grammar G if there exist v 0 ∈ Σ * , v 1 , v 2 ∈ (Σ ∪ Γ) * , S ∈ Γ such that v = v 0 Sv 1 and w = v 0 v 2 v 1 and S → v 2 ∈ R. A complete derivation 1
of the grammar G is a finite sequence x 0 , . . . , x k of words of (Σ ∪ Γ) * such that x 0 = S 0 , x k ∈ Σ * and for every i, x i+1 is a successor of x i . A derivation tree of G is a finite tree whose internal nodes are labelled by letters of Γ, whose leaves are labelled by elements of Σ ∪ {ε}, whose root is labelled by S 0 and satisfying: if a node is labelled by X ∈ Γ and its children are labelled by α 1 , . . . , α k (in this order), then either α 1 = ε and k = 1, or all the α i 's are in Γ∪Σ and (X, α 1 . . . α k ) ∈ R. The size of a derivation tree is given by the number of tree nodes. Note that there is a bijection between the set of complete derivations of a grammar and the set of derivation trees of this grammar. For a context-free grammar G, E n (G) denotes the number of derivation trees of G with n nodes. A derivation tree covers an element X of Γ if at least one of its nodes is labelled by X. For instance, for the tree in Example 1, the elements S and T are covered since they appear in the derivation tree.

b) Uniform Random Generation: The present issue is, given a positive integer and a context-free grammar, to compute randomly with a uniform distribution a derivation tree of size n of this grammar. We will briefly explain here how to tackle this problem by using well-known counting techniques [START_REF] Flajolet | Analytic Combinatorics[END_REF]. Notice that more advanced techniques allow a faster computation, like in [START_REF] Denise | Uniform random generation of decomposable structures using floating-point arithmetic[END_REF].

As usual, the non-terminals symbols are denoted by capital letters. Given a context-free grammar G = (Σ, Γ, S 0 , R), a non-terminal symbol X in Γ, and a positive integer i, the number of derivation trees of size i by (Σ, Γ, X, R) is denoted by x(i), i.e., using the corresponding lowercase letter.

Given a positive integer n, for each symbol S ∈ Γ, the sequence of positive integers s(1), . . . , s(k), . . . is introduced. The recursive computation of these s(i)'s is as follows. For each strictly positive integer k and each rule r = (S, w 1 S 1 . . . w n S n w n+1 ) ∈ R, with w j ∈ Σ * and S i ∈ Γ, let us set

             β r = 1 + n+1 i=1 |w i | α r (k) = i1+i2+...+in=k-βr j=n j=1 s j (i j ) if n = 0 α r (k) = 0 if n = 0 and k = β r α r (β r ) = 1 if n = 0. It is known [23, Theorem I.1] that s(k) = r∈R∩(S×(Σ∪Γ) * ) α r (k).
Since, by hypothesis, there is no rule of the form (S, T ) in R, with S, T ∈ Γ, all i j 's involved in the definition of β r are strictly less than k. This way, the s(i)'s can be recursively computed. Consider for instance the grammar where both Z 1 and Z 2 are derivation trees of size 2.

({a, b}, {X}, X, {r 1 , r 2 , r 3 }) with r 1 = (X, XX) r 2 = (X, a) and r 3 = (X, b). One has β r1 = 1 + 0 = 1, β r2 = 1 + 1 = 2, β r3 = 1+1 = 2. Therefore x(k) = i+j=k-1 x(i)x(j) if k = 2, and x(2) = 1 + 1 + i+j=2-1 x(i)x(j) = 2, other- wise. It follows that x(1) = 0, x(2) = 2, x(3) = x(1)x(1) = 0, x(4) = x(1)x(2) + x(2)x(1) = 0, x(5) = x(2)x(2) = 4,
In order to generate derivation trees of size n, all s(i) s, for S ∈ Γ and i ≤ n, have to be computed with the

Random Generation

Input: G = (Σ, Γ, X, R) a context-free grammar, n a strictly positive integer. Output: a derivation tree t of G size n. Algorithm:

1. Let {r 1 , r 2 , . . . , r } be set of the elements of R whose first element is X.

2.

If j= j=1 α rj (n) = 0, then return "Exception". 3. Pick i ∈ {1, . . . , } with probability P rob(i = j) = αr i (n) j= j=1 αr j (n) . 4. Let r i = (X, Z 1 . . . Z k ), with Z j ∈ Σ ∪ Γ. 5. Root symbol of t is X. 6. Children of t are Z 1 , . . . , Z k in this order. 7. Let {i 1 , . . . , i m } = {j | Z j ∈ Γ}. 8. Pick (x 1 , . . . , x m ) ∈ N m such that x 1 + . . . + x m = n -β ri with probability P rob(x 1 = 1 , . . . , x m = m ) = j=m j=1 z ij ( j ) α ri (n) .
9. For each i j , the i j -th sub-tree of T is obtained by running the Random Generation algorithm on (Σ, Γ, Z ij , R) and j .

10. Return t. above method. This can be performed in polynomial time. Afterwards, the random generation is done recursively using the given algorithm in Fig. 1. It is known [START_REF] Flajolet | Analytic Combinatorics[END_REF] that this algorithm provides a uniform generation of derivation trees of size n, i.e. each derivation tree occurs with the same probability. Note that an exception is raised at Step 2 if there is no element of the given size. For the example presented before, there is no element of size 3, then it is impossible to generate a derivation tree of size 3. Running the algorithm on this example with n = 2, one considers at Step 1 the set {r 1 , r 2 , r 3 } since all these rules have X as left element. Since α r1 (2) = 0, α r2 (2) = 1, α r3 (2) = 1, at Step 3 the probability that i = 1 is 0, the probability that i = 2 is 1/2 and the probability that i = 3 is 1/2. If i = 2 is picked, the generated tree has X as root symbol and a as unique child. Running the algorithm on this example with n = 3 stops at Step 2 since there is no tree of size 3. When running the algorithm on this example with n = 5, the set {r 1 , r 2 , r 3 } is considered at Step 1. Since α r1 (5) = 4, α r2 (5) = 0, α r3 (5) = 0, i = 1 is picked with probability 1. Therefore, the tree has X as root symbol, and its two children are both labelled by X. Therefore, at Step 7, the considered set is {1, 2}. At Step 8, one has n -β r1 = 5 -1 = 4. The probability that i 1 = 1 and i 2 = 3 is 0 since x(1) = 0. Similarly, the probability that i 1 = 3 and i 2 = 1 is 0 too. Now the probability that i 1 = 2 and i 2 = 2 is 1. Afterwards the algorithm is recursively executed on each child with n = 2: each of the 4 trees is chosen with probability 1/4.

III. MIXING RANDOM TESTING AND COVERAGE

CRITERIA In a context of functional testing, the strength of random testing is to quickly provide many different test data, for each behaviour of the system. Moreover, these test data are independent of the choices of the test designer, and consequently they can catch problem (s)he did not anticipate. For instance, fuzz testing is particularly relevant for testing security requirements [START_REF] Godefroid | Grammar-based whitebox fuzzing[END_REF]. However, random testing can miss an important behaviour occurring with a very small probability. To exploit the advantages of both random testing and deterministic testing, a solution is to combine random generation and coverage criteria.

The general schema for this combination, as described in [START_REF] Denise | Coverage-biased random exploration of large models and application to testing[END_REF], is the following: considering a random generation algorithm of test data of size n and a coverage criteria C (each element of C is or is not covered by each possible test), the goal is to use the generation algorithm N times in order to optimise the probability of covering all elements of C. For each element e ∈ C, we denote by p e,n the probability that a generated test of size n covers e. One can easily check that generating N test data independently of C provides a probability of covering C of 1-(1-p min ) N , where p min = min e∈C {p e,n }. This probability is the way to measure the quality of the testing approach, relatively to C. A better way is to repeat N times the following procedure:

1) Pick at random an element e ∈ C with a probability π e , and 2) Generate uniformly a test of size n covering e. This procedure requires to know how to uniformly generate a test of size n covering a given element, and to choose the probabilities π e 's to optimise the probability of covering all elements of C.

Following [START_REF] Denise | Coverage-biased random exploration of large models and application to testing[END_REF], the optimisation requires solving the following constraint system: maximise p satisfying p ≤ e∈C π e p e,f,n pe,n for all f ∈ C e∈C π e = 1 where p e,f,n is the probability that a randomly generated test of size n covers both e and f . This linear programming problem can be solved in an efficient way, using simplex-like approaches.

In summary, in order to combine random testing and a coverage criterion, it is required to solve a constraint system and to know 1) how to randomly generate a test of a given size covering a given element, 2) how to compute the p e,n 's; and 3) how to compute the p e,f,n 's.

The rest of the paper is dedicated to the problem of the random generation of execution trees of a grammar, with the coverage criterion All non-terminal symbols. More precisely, given a grammar G = (Σ, Γ, S 0 , R), the coverage criterion being Γ, a test of size n being a derivation tree of G of size n, we say that X ∈ Γ is covered by a test if the derivation tree covers X.

IV. COMPUTING p X,n AND p X,Y,n

In this section G = (Σ, Γ, S 0 , R) is a context-free grammar. We denote by E n (G) the set of derivation trees of size n of G. We respectively denote by E X,n (G) and E X,Y,n (G) the set of derivation trees of size n of G covering X, and covering both X and Y .

Let p X,n be the probability of a randomly generated derivation tree of size n to cover X.

Clearly, if E n (G) is empty then p X,n = 0 [resp. p X,Y,n = 0]. Otherwise, p X,n = |E X,n (G)| |En(G)| [resp. p X,Y,n = |E X,Y,n (G)| |En(G)| ].
Therefore, computing the probability defined in Section III -needed to solve the linear constraint program -reduces to the computation of the cardinality of sets E X,n (G) and E X,Y,n (G).

A. Computing |E X,n (G)| and |E X,Y,n (G)|

To compute |E X,n (G)|, we build a grammar G X such that E n (G X ) and E X,n (G) are in bijection (and therefore have the same number of elements).

For every w ∈ (Γ ∪ Σ) * , [w] 0 is recursively defined by:

[ε] 0 = ε, [Zw] 0 = (Z, 0)[w] 0 (with Z ∈ Γ) and [aw] 0 = a[w] 0 (with a ∈ Σ).
Intuitively, [w] 0 is obtained from w by changing each letter of w in Γ by the corresponding pair with 0 as second element. For instance, with the grammar of Example 1, one has [aSbbT ] 0 = a(S, 0)bb(T, 0). For every w ∈ (Γ ∪ Σ) * , [w] 2 is defined exactly in the same way, changing all 0's by 2's.

For every w ∈ (Γ∪Σ) * , {w} 1,2 is defined as the set of words w ∈ (Σ ∪ Γ × {1, 2}) * obtained from w by replacing occurrence of each letter Z of Γ either by (Z, 1) or by (Z, 2), with the restriction that at least one is replaced by (Z, 1). The letters in Σ remain unchanged. For instance, if w = aSbT , then {w} 1,2 = {a(S, 1)b(T, 1), a(S, 2)b(T, 1), a(S, 1)b(T, 2)}. Notice that if w ∈ Σ * then {w} 1,2 = ∅ since the constraint is not satisfied.

Let G X = (Σ, Γ×{0, 1, 2}, (S 0 , 1), R X ) where

R X = R 0 ∪ R 1 ∪ R 1 ∪ R 2 with: • R 0 = {(Z, 0) → [w] 0 | Z → w ∈ R}, • R 1 = {(Z, 1) → w | Z = X and ∃Z → w ∈ R such that w ∈ {w} 1,2 }, • R 1 = {(X, 1) → [w] 0 | X → w ∈ R}, • R 2 = {(Z, 2) → [w] 2 | Z → w ∈ R and Z = X}.
Intuitively, adding the value 0 to a symbol in Γ means that if this rule is used, there exists an occurrence of X at an upper position in the derivation tree. Adding the value 1 to a symbol in Γ means that there is no occurrence of X at an upper position, but there exists an occurrence of X at this or a lower position in the derivation tree. The value 2 means there is no occurrence of X appearing in the tree at an upper or lower position.

Example 2 -G X . Consider the grammar G = ({a, b}, {S, T, X}, S, R) with R = {S → SS, S → aT, S → Xb, T → aa, X → T X, X → b}. The grammar G X has the set of rules as follows: {(S, 0) → (S, 0)(S, 0), (S, 0) → a(T, 0), (S, 0) → (X, 0)b, (T, 0) → aa, (X, 0) → b, (X, 0) → (T, 0)(X, 0)} ∪ {(S, 1) → (S, 1)(S, 1), (S, 1) → (S, 1)(S, 2), (S, 1) → (S, 2)(S, 1), (S, 1) → a(T, 1), (S, 1) → (X, 1)b} ∪ {(X, 1) → b, (X, 1) → (T, 0)(X, 0)} ∪ {(S, 2) → (S, 2)(S, 2), (S, 2) → a(T, 2), (S, 2) → (X, 2)b, (T, 2) → aa}.

Proposition 1 -Bijection. There exists a bijection between E n (G X ) and E X,n (G).

Example 3 illustrates several elements of the following proof.

Proof: Let ϕ be the function from (Γ × {0, 1, 2} ∪ Σ) * into (Γ ∪ Σ) inductively defined by: ϕ(ε) = ε and ϕ(aw

) = aϕ(w) if a ∈ Σ ∪ Γ and ϕ((Z, α)w) = Zϕ(w) if Z ∈ Γ and α ∈ {0, 1, 2}. Intuitively, ϕ is a projection deleting the components in {0, 1, 2}. By construction of G X , if (Z, α) → w is a rule of G X then ϕ((Z, α)) → ϕ(w) is a rule of G. Therefore, if x 0 , . . . , x k is complete derivation of G X , then ϕ(x 0 ), . . . , ϕ(x k ) is a complete derivation of G. Moreover, the initial symbol of G X is (S, 1
) and all rules of R X with a left hand side in (Γ \ {X}) × {1} have a right hand side where an element of Γ × {1} occurs. Therefore, since x k ∈ Σ * , the only way to destroy the component 1 is to use a rule with the left hand side (X, 1). It follows that the derivation tree associated to ϕ(x 0 ), . . . , ϕ(x k ) covers X.

Consequently, ϕ induces a function from E n (G X ) into E X,n (G). Let x 0 , . . . , x k and x 0 , . . . , x k be complete derivations of G X , such that ϕ(x 0 ), . . . , ϕ(x k ) = ϕ(x 0 ), . . . , ϕ(x k ). Assuming that x 0 , . . . , x k = x 0 , . . . , x k , there exists a minimal index i 0 such that x i0 = x i0 . Since x 0 = (S 0 , 1) = x 0 , i 0 ≥ 1. Therefore x i0-1 = x i0-1 exists. Set x i0-1 = v 0 (Z, α)v 1 , with Z ∈ Γ and α ∈ {0, 1, 2}. One of the following cases arises:

• If α = 0, then there exist Z → w and Z → w in R such that

x i0 = v 0 [w] 0 v 1 and x i0 = v 0 [w ] 0 v 1 . Since ϕ(x i0 ) = ϕ(x i0 ), it follows that ϕ([w] 0 ) = ϕ([w ] 0 ). But ϕ([w] 0 ) = w and ϕ([w ] 0 ) = w , proving that x i0 = x i0 , a contradiction. • If α = 2,
then the same proof holds, replacing 0 by 2.

• If α = 1 and Z = X, then, again, the same proof holds.

• If α = 1 and Z = X, then there exist Z → w and Z → w in R such that

x i = v 0 w 1 v 1 and x i = v 0 w 2 v 1 , with w 1 ∈ {w} 1,2 and w 2 ∈ {w } 1,2 . Since ϕ(x i0 ) = ϕ(x i0
), one has w = w . Therefore, w 1 , w 2 ∈ {w} 1,2 . Since w 1 = w 2 , let j be the first letter of w 1 which is different from the corresponding letter in w 2 . By construction of {w} 1,2 , this letter must be in Γ × {1, 2} in both w 1 and w 2 , for instance (T, β 1 ) and (H, β 2 ). Now, since ϕ((T, β 1 )) = ϕ((H, β 2 )), one has T = H. Therefore, without loss of generality we may assume that β 1 = 1 and β 2 = 2. Consequently, x i0 has a prefix of the form v 0 (T, 1): in the derivation tree corresponding to x 0 , . . . , x k , the subtree rooted in this (T, 1) contains an X (by construction of R 1 ). Conversely, x i0 has a prefix of the form v 0 (T, 2): in the derivation tree corresponding to x 0 , . . . , x k , the subtree rooted in this (T, 2) does not contain any X (by construction of R 2 ). It follows that the two corresponding derivations cannot have the same

E n (G X ) into E X,n (G).
Now let y 0 , . . . , y k be complete derivations of G whose corresponding tree t is in E X,n (G). We consider the tree t labelled in Γ × {0, 1, 2} ∪ Σ which has exactly the same structure (the same set of positions) than t and such that:

• If a node of t is labelled by a letter of Σ, then the corresponding node in t has the same label. • If a node ρ of t is labelled by a letter T ∈ Γ, then the node ρ in t is labelled by (T, 1) if there is no X on the path from the root to ρ (excluding ρ), and if the subtree rooted in ρ (including ρ) contains one ρ, at least. It is labelled by (T, 0) if there is at least one X on the path from the root to ρ. Otherwise, it is labelled by (T, 2). One can check that t corresponds to a complete derivation tree of G X whose image by ϕ is exactly the complete execution corresponding to t, proving that ϕ is surjective, which concludes the proof.

Example 3 -Illustration of the proof of Prop. 1. Consider the grammar G = ({a, b}, {S, T, X}, S, R) with R = {S → SS, S → aT, S → Xb, T → aa, X, → T, X → b} of Example 2. Consider the derivation tree of E X,19 (G) depicted in Fig. 2, corresponding to the complete derivation S, SS, SSS, aT SS, aaaSS, aaaXbS, aaabbS, aaabbXb, aaabbT Xb, aaabbaaXb, aaabbaabb.

The associated derivation in G X is (S, 1), (S, 1)(S, 1), (S, 2)(S, 1)(S, 1), a(T, 2)(S, 1)(S, 1), aaa(S, 1)(S, 1), aaa(X, 1)b(S, 1), aaabb(S, 1), aaabb(X, 1)b, aaabb(T, 0)(X, 0)b, aaabbaa(X, 0)b, aaabbaabb, whose derivation tree from E 19 (G X ) is depicted in Fig. 3.

Using Proposition 1 and the results described in Section I, it is possible to compute |E X,n (G)|. If we denote by the maximal number of elements of Γ (with multiplicity) occurring in a right hand side of G, then G X has O(2 |R|) rules, whose sizes are bounded by the maximal size of the rules of G. Therefore if is reasonable, the computation of |E X,n (G)| is tractable in practice, even for a quite large value of n. As mentioned above, the computation of |E X,n (G)| immediately provides p X,n . It is also important to point out that G X allows the uniform random computation of execution trees of G of a given size and covering X.

Since E X,X,n (G) = E X,n (G), computing |E X,X,n (G)| is a direct application of the above techniques. Computing |E X,Y,n (G)|, with Y = X, can almost be done by a similar construction: the difference is that the construction of the rules of the grammar G XY , from the grammar G X , must take into account that both X and Y have to appear in the derivation. Let G XY = (Σ, Γ × {0, 1, 2} × {0, 1, 2}, ((S 0 , 1), 1), R XY ) where

R XY = R 0 ∪ R 1 ∪ R 1 ∪ R 2 with: • R 0 = {((Z, i), 0) → [w] 0 | (Z, i) → w ∈ R X }, • R 1 = {((Z, i), 1) → w | Z = Y and ∃(Z, i) → w ∈ R X such that w ∈ {w} 1,2 }, • R 1 = {((Y, i), 1) → [w] 0 | (Y, i) → w ∈ R X }, • R 2 = {((Z, i), 2) → [w] 2 | (Z, i) → w ∈ R X and Z = Y }.
A proof similar to the one of Proposition 1 allows showing that there is a computable bijection between E n (G XY ) and E X,Y,n (G). Note that the size of G XY is approximatively 4 times greater than the size of G.

V. EXPERIMENTS

The approach has been evaluated on a simplified version of the grammar of JSON2 (for JavaScript Object Notation) -a language independent common format for declaring objects. Formally, let us consider the grammar G = (Σ, Γ, Object, R) with Σ having the eight following elements Σ = {, , {, : , }, letter, digit, [, ]}. The set Γ of non-terminal symbols3 is composed of the elements Object , M embers , P air , Array , Elements and V alue . Finally, the set R contains the following rules:

Example 1 -

 1 Context-free grammar. Let us consider the grammar G = ({a, b}, {S, T }, S, R), with R = {S → T b, S → aSb, T → ε}). The sequence S, aSb, aT bb, abb is a complete derivation of the grammar. The associated derivation tree is

  etc. The two derivation trees of size 2 are X | a and X | b . The four derivation trees of size 5 are the trees of the form X /\ Z1 Z2

Fig. 1 .

 1 Fig. 1. Random Generation algorithm

Fig. 2 .

 2 Fig. 2. Derivation tree of G -Example 3

Fig. 3 .

 3 Fig. 3. Derivation tree of G X -Example 3

•

  Object → {} | {M embers} • M embers → P air | P air, M embers • P air → letter : V alue • Array → [ ] | • Elements → V alue | V alue, Elements • V alue → letter | Object | digit | Array

http://www.json.org/

To provide a more readable specification, the convention consisting in using capital letters for non-terminal symbols is not entirely respected here.

In order to optimise the coverage criterion, we have to solve the following system while maximising p satisfying

Using a slightly modified version of the Hoa tool ( [START_REF] Enderlin | Hoa project, a set of php libraries[END_REF]), the computation of the probabilities p X,n and p X,Y,n for all X, Y ∈ Γ and n = 20 has been performed efficiently (a few seconds). The system becomes as below, and we have then to solve it while maximising p satisfying π Object + π M embers + π P air + π Array +π Elements + π V alue = 1

This linear programming problem can be solved in an efficient way, using simplex-like approaches. We have used the tool lp solve 4 to solve it, and the result is that p = 1 if π Object = 0, π M embers = 0, π P air = 0, π Array = 0, π Elements = 1, and π V alue = 0. It means that, for this simple example, the optimised approach to cover all the nonterminals symbols, consists in generating derivation trees covering Elements. Indeed, in this grammar, the generation of a derivation tree covering the non-terminal symbol Elements provides a tree covering all the other non-terminal symbols.

VI. CONCLUSION

In this paper, we have presented a method for exploiting a coverage criterion together with random testing in the context of grammar-based testing. This automatic method lies in building a grammar and then in resolving a linear constraint system, which can be done by adapted tools, even for large values. In the future, we plan to extend the approach to other coverage criteria such as rules coverage, and also to handle attribute grammars with constraints formalising the semantics of context-free languages.


Hicham Lakhlef
email: hlakhlef@femto-st.fr

Hakim Mabed
email: hmabed@femto-st.fr

Julien Bourgeois
email: julien.bourgeois@femto-st.fr

Distributed and Dynamic Map-less Self-reconfiguration for Microrobot Networks

Keywords: distributed algorithms, DiMEMS, MEMS microrobot, self-reconfiguration, physical topology, optimization, mobility, dynamicity, energy

MEMS microrobots are low-power and lowmemory capacity devices that can sense and act. One of the most challenges in MEMS microrobot applications is the self-reconfiguration, especially when the efficiency and the scalability of the algorithm are required. In the literature, if we want a self-reconfiguration of microrobots to a target shape consisting of P positions, each microrobot should have a memory capacity of P positions. Therefore, if P equals to millions, each node should have a memory capacity of millions of positions. Therefore, this is not scalable. In this paper, nodes do not record any position, we present a self-reconfiguration method where a set of microrobots are unaware of their current position and do not have the map of the target shape. In other words, nodes do not store the positions that build the target shape. Consequently, memory usage for each node is reduced to O(1). An algorithm of self-reconfiguration to optimize the communication is deeply studied showing how to manage the dynamicity (wake up and sleep of microrobots) of the network to save energy. Our algorithm is implemented in Meld, a declarative language, and executed in a real environment simulator called DPRSim.

I. INTRODUCTION

Micro-electro-mechanical systems (MEMS) is a technology that enables the batch fabrication of miniature mechanical structures, devices and systems that can sense and act. Their applications require a massive deployment of nodes, thousands or even millions [START_REF] Warneke | Smart Dust: Communicating with a Cubic-Millimeter Computer[END_REF] which will give birth to the Distributed Intelligent MEMS (DiMEMS) [START_REF] Bourgeois | Distributed Intelligent MEMS: Progresses and perspectives, 3[END_REF].

Microrobots systems have a wide range of applications such as odor localization, firefighting, medical service, surveillance, search, rescue, and security. To do these tasks the nodes have to perform the self-reconfiguration. Selfreconfiguration can be seen from two different points of view. First, it can be defined as a protocol, centralized or distributed, which transforms a set of nodes to reach the optimal logical topology from a physical topology [START_REF] Jeon | Randomized Distributed Configuration Management of Wireless Networks: Multi-layer Markov Random Fields and Near-Optimality[END_REF], e.g, the chain represents the worst complexity case with O(n), the square represents the best one with O( √ n). On the other hand, the self-reconfiguration is built from modules which are autonomously able to change the way they are connected, thus changing the overall shape of the network. This process is difficult to control, because it involves the distributed coordination of a large numbers of identical modules connected in time-varying ways. Optimizing the energy cost of self-reconfiguration algorithms has a direct impact on the energy efficiency of any swarm. Mobility and dynamicity of the system are making the problem even harder to handle as the logical topology of the system has to be stored in a distributed structure, as the spanning tree. The range of exchanged information and the number of movements determine the communication and the energy complexity of the distributed algorithm. When the information exchange involves close neighbors, the complexity is moderate and the resulting distributed selfreconfiguration scales gracefully if the algorithm does not need the predefined positions of the target shape.

This work takes place within the Claytronics project and aims at optimizing the logical topology of the network.

II. RELATED WORKS

Many terms refer to the concept of self-reconfiguration. The self-organization term can be found in protocols for sensors networks to form a sphere or a polygon from a center node [START_REF] Mamei | Emergence and Control of Macro Spatial Structures in Perturbed Cellular Automata, and Implications for Pervasive Computing Systems[END_REF], [START_REF] Mamei | Experiments of Morphogenesis in Swarms of Simple Mobile Robots[END_REF]. The term redeployment is also a new term to address self-reconfiguration for sensor networks [START_REF] Kribi | Redeploying mobile wireless sensor networks with virtual forces[END_REF], [START_REF] Eckert | On the Feasibility of Mass-Spring-Relaxation for Simple Self-Deployment[END_REF]. For self-reconfiguration with robots or microrobots, there is the protocol in [START_REF] Stoy | Self-Repair Through Scale Independent Self-Reconfiguration[END_REF] where the desired configuration is grown from an initial seed module. A generator uses a 3D CAD model of the target configuration and outputs a set of overlapping blocks which represent this configuration. In the second step, this representation is combined with a control algorithm to produce the final self-reconfiguration algorithm. Among the centralized algorithms we find centralized selfassembly and/or reconfiguration algorithms [START_REF] Rus | Crystalline robots: Self-reconfiguration with compressible unit modules[END_REF]. Other approaches give each node a unique ID and a predefined position in the final structure; see for instance [START_REF] White | Three dimensional stochastic reconfiguration of modular robots[END_REF]. The drawback of these methods is the centralized paradigm and the need for nodes identification. More distributed approaches in [START_REF] Jones | From local to global behavior in intelligent self-assembly[END_REF], [START_REF] Lakhlef | Distributed and Efficient Algorithm for Self-reconfiguration of MEMS Microrobots[END_REF], [START_REF] Lakhlef | Parallel Selfreconfiguration for MEMS Microrobot[END_REF], [START_REF] Mabed | Bourgeois Fully Distributed Redeployement Algorithm for Multi-Robot System[END_REF]. Claytronics, is a project led by Carnegie Mellon University and Intel corporation. In Claytronics, microrobots called catoms (Claytronics atoms. The idea is to have hundreds of thousands of microrobots forming by self-reconfiguration together objects of any shape or size. Many works have already been done within the Claytronics project. In [START_REF] Dewey | Generalizing Metamodules to Simplify Planning in Modular Robotic Systems[END_REF], the authors propose a metamodel for the reconfiguration of catoms starting from an initial configuration to achieve a desired configuration using creation and destruction primitives. The authors use these two functions to simplify the movement of each catom. In [START_REF] Ashley-Rollman | A Language for Large Ensembles of Independently Executing Nodes[END_REF], a scalable protocol for Catoms self-reconfiguration is proposed, written with the MELD language [START_REF] Ashley-Rollman | Meld: A Declarative Approach to Programming Ensembles[END_REF] and using the creation and destruction primitives. In all these works, the authors assume that all Catoms know the correct positions composing the target shape at the beginning of the algorithm.

III. CONTRIBUTIONS

In this paper, we propose a new distributed approach for self-reconfiguration of MEMS microrobots, where the target form is built incrementally, and each node in the current increment acts as a landmark for other nodes to form the next increment, which will belong to the form. We introduce a state model where each node can see the state of its physical neighbors to achieve the self-reconfiguration, using the states the nodes collaborate and help each other. In this paper each node predicts its future actions (movements), so it can compute the energy amount that will spend before the beginning of the algorithm. The prediction property makes the algorithm robust and energy-aware, because the node can make sure that it has correctly followed the algorithm and it is aware of the amount of energy that it will use. Also, to keep the energy and to augment the probability that the node will finish its task, each node is aware of the time slots where it can sleep to save energy.

In the proposed algorithm, the exchange of messages is limited to the construction of the spanning tree. The spanning tree is used to ensure the connectivity of the network and dynamically manage the nodes that can move. Contrary to existing works, in our algorithm each node has no information on the correct positions (predefined positions) of the target shape, the algorithm does not need to know the network size (nodes number) and movement of microrobots is fully implemented.

We propose an efficient distributed algorithm for nodes self-reconfiguration where each node moves by rotation around their physical neighbors. We study the case of a selfreconfiguration from a chain of microrobots to a square. The performance of the self-organization algorithm is evaluated according to the number of rotations and the time taken. In this paper the MEMS network is organized initially as a chain. By choosing a straight chain as the initial shape, we aim to study the performance of our approach in extreme case. Indeed, the chain form represents the worst physical topology for many distributed algorithms in terms of fault tolerance, propagation procedures and convergence. Indeed, the number of direct contacts between macro-robots is minimal and secondly the average distance between two robots (in terms of number of hops) is of (n + 1)/3 where n is the number of robots.

We present the results of the simulations made with the declarative language Meld [START_REF] Ashley-Rollman | Meld: A Declarative Approach to Programming Ensembles[END_REF] and the open-source simulator DPRSim [START_REF]Physical rendering simulator[END_REF].

IV. MODEL AND DEFINITIONS

Within Claytronics, a catom (figure 2) called in this paper a node is modeled as a sphere which can have at most six neighbors. Each node is able to sense the direction of its physical neighbors (east (E), west (W), north-east (NE), south-east (SE), south-west (SW) and north-west (NW)). In this work, the starting physical topology is a chain of n nodes linked together. A chain is a connected set of nodes where each node has two neighbors excepting the two extremities having one neighbor. We will take the example of nodes that have neighbors in NW and SE directions and we will show after how to generalize. A node A is in neighbor's list of node B if A is physically linked to B. In Claytronics, communications are only possible through contact (i.e. only neighbors can have a direct communication). Snap-Connectivity : A dynamic network ensures a Snap-Connectivity, if in all rounds of the algorithm the network is connected (there is always a path between two nodes). Spanning tree: Is a graph composed of all nodes without any cycle. In the spanning tree, a node is either a child or a parent, a leaf is node without children. We call the own movements of a given node the number of movements performed by. Consider the figure 1 which represents a microrobot. We say that a microrobot has done a single movement if the distance between its former position and its new position is exactly twice the radius D1 = 2R. For example, if the node is in a position at a distance D2 (see the figure 3) from the former position it has done two movements. We assume (and according to the simulation tools) that the change of message (consultation) between two physical neighbors is carried without complexity (0 message), while the distance between them is zero. If a node to decide needs to know the state of a non-physical neighbor message exchange is required.

V. PROPOSED PROTOCOL

A. Dynamic Algorithm with Safe Connectivity (DASC)

In DASC, each node can only move around its physical neighbor. To ensure snap-connectivity only nodes that do not cause network non-connectivity can move around neighbors. For this purpose we introduce the use of the tree to dynamically manage the leaf nodes authorized to move.

Description of the algorithm

The algorithm runs in rounds. In each round, satisfied predicates are executed. In a current round predicates with best priority are executed while others with lowest priority are ignored. We notice that in DASC, the state change actions, represented by predicates labeled P1, are considered more prior than a movement actions represented by P2. The distributed algorithm seeks the desired form by an incrementally process. In a completed increment, the nodes that build it belong already to the form. The initiator which is the root initializes the tree and becomes a parent of itself [START_REF] Eckert | On the Feasibility of Mass-Spring-Relaxation for Simple Self-Deployment[END_REF]. A node if it does not have a parent becomes a child of one of the neighbor parents (6), a node is a leaf if all its neighbors are parents [START_REF] Jeon | Randomized Distributed Configuration Management of Wireless Networks: Multi-layer Markov Random Fields and Near-Optimality[END_REF]. At the beginning all nodes are initialized with the bad state with predicate (2). The initiator belongs to the target shape, so it changes its state to good (3), it will help its neighbors or future neighbors to take correct positions. The nodes already in the target shape act as a benchmark to neighbor or future neighbor nodes to complete a new layer. The nodes already in the form change their states with the predicate (3) and ( 8) and they become constant, the node can check if its neighbor have the good state with the predicate (3) and [START_REF] Kribi | Redeploying mobile wireless sensor networks with virtual forces[END_REF]. The node that starts the move is the lowest node in the chain that is the first leaf of the first tree built, it rises until the root using motion around other nodes with predicates [START_REF] Mabed | Bourgeois Fully Distributed Redeployement Algorithm for Multi-Robot System[END_REF] and [START_REF] Mamei | Emergence and Control of Macro Spatial Structures in Perturbed Cellular Automata, and Implications for Pervasive Computing Systems[END_REF]. The nodes of the current layer (layer being built) may make motion either at left directly or NW directly with the last three predicates. The node can change its state to good with predicate (3) if it cannot move to left or in NW. With the predicate [START_REF] Mamei | Experiments of Morphogenesis in Swarms of Simple Mobile Robots[END_REF] the node moves at left, it will have the neighbor that used it to move at NE direction, it repeats the same motion until it arrives to the diagonal node that have the state spe, it cannot move around this last only if the diagonal node has not a neighbor node in the E direction. Diagonal nodes take the state spe with the predicate (4) and [START_REF] Lakhlef | Parallel Selfreconfiguration for MEMS Microrobot[END_REF], and with [START_REF] Rus | Crystalline robots: Self-reconfiguration with compressible unit modules[END_REF] the node moves until it takes a correct position. The state change has a priority as the moving actions to avoid bad motion, because of this we introduce the priority in our algorithm. To avoid message exchange the node can change its state to good if it has 3 neighbors having the state good [START_REF] Lakhlef | Distributed and Efficient Algorithm for Self-reconfiguration of MEMS Microrobots[END_REF] or one neighbor has spe state and has neighbors in the both NE and NW directions with predicate [START_REF] Lakhlef | Parallel Selfreconfiguration for MEMS Microrobot[END_REF].

Variables and predicates v, u, u1, u2: variables denote a node belongs to the network.

-{U }:set of nodes.

good, bad, spe: states, a node can take one or two states at the same time, but not spe and bad or good and bad.

-N x (v): the neighbor in the direction x of the node v: x ∈ {(N ), (E), (W ), (N E), (SE)or(N W )}.

connected v : true if the node v is connected to the network, f alse else (Boolean).

-State v (k): the state of the node v, taking one or two of these values k = good, bad or spe.

-State v (s, good): the node v has s (s an integer) neighbors that have the good state State(good) .

-moveAroundgood v (u, P x ): move around the neighbor u in such a way that u becomes a v's neighbor in the direction x relative to v.

-P arent(v, u): the node v is parent of node u.

-isLeaf (v): the node v is a leaf in the tree.

Predicates checked only in the first round

1: Initiator(v) ≡ (¬N nw (v) =) ∧ connected v . 2: State v (bad) ≡ connected v ∧ ¬Initiator(v). 3: State v (good) ≡ Initiator(v). 4: State v (spe) ≡ Initiator(v).
Predicates checked in each round

5: Parent(v, v) ≡ Initiator(v). 6: Parent(v, u) ≡ (P arent(w, v), u = w) ∧ neighbor(v, u) ∧ State u (bad) ∧ ( ∃z ∈ N (v), P arent(v, z)). 7: isLeaf(v) ≡ (∀u ∈ N (v), ¬P arent(v, u) ∧ ¬P arent(v, v)). 8: (P1): State v (good) ≡ (N e (v) = u ∧ State u (good) ∧ ¬N ne (u)) ∨ State v (3, good) ∨ (State v (2, good) ∧ (N ne (v) = u ∧ State u (spe)) ∨ (N w (v) = u ∧ State u (good))) ∨ State v (spe). 9: State v (s, good) ≡ (N x (v) = {U } , |U | = s ∧ State {u} (good)). 10: (P1): State v (spe) ≡ (N nw (v) = u1)) ∧ (N ne (v) = u2, State u2 (spe)). 11: (P2): moveAroundbad v (u, P e ) ≡ isLeaf (v) ∧ State v (bad) ∧ (N nw (v) = u ∧ State u (bad)). 12: (P2): moveAroundbad v (u, P se ) ≡ isLeaf (v) ∧ State v (bad) ∧ (N ne (v) = u ∧ State u (bad)). 13: (P2): moveAroundgood v (u, P ne ) ≡ isLeaf (v) ∧ State v (bad) ∧ (N nw (v) = u ∧ State u (good)). 14: (P2): moveAroundgood v (u, P e ) ≡ isLeaf (v) ∧ State v (bad) ∧ (N ne (v) = u ∧ State u (good)).
the DASC Algorithm .

B. Predicting the number of movements for each node

To form the matrix of our square with N xN nodes, we begin with an incremental process with a single node that we assume in a correct square 1x1. After, we add each time a new layer contains the number of nodes of the last column plus the number of nodes of the last line of the current square plus one node. Considerer the figure 4, the node i will take a position p + x. Following the path from top to bottom the node i will never move or move after all nodes after it, so if node A is before B, A will take a position p + c, and node B will take a position p + k, with c > k. Adding layers, each time we add a new layer with number of nodes equal to the number of nodes of the previous layer plus two nodes, this can be expressed on the form of this numerical sequence:

U j = U j-1 + 2.
(

) 1
Where: U j is the number of nodes in the layer j and U j-1 is the number of nodes in layer j -1.

In the chain we take a partitioning of the nodes to levels, a level can be associated to one or many nodes. The nodes take their levels with this following process: the first nodes that have i ≤ √ n take the root level (level 0), for the other nodes, the first x = ( 2√ n -2) nodes after the node i = √ n take the first level (level 1), and the second x -2 nodes take the second level and so on (figure 4 shows an example). So each node i gets one level at the end. The number of movements for each node i of level j can be given with the composition of two sequences U i,j and R j .

R j =      0, if j = 0 2 √ n -5, if j = 1 R j-1 -2, otherwise (2)
With R j is a number associated to nodes having the level j and n is network size.

U i,j =          0, if i ≤ √ n 2, if i = √ n + 1, j = 1 U i-1 -R j , if l(i + 1) = j U i-1 + 2, otherwise (3)
Where: U i,j and U j is the number of movements of node i having level j or the number of movements rounds of nodes having the level j and n is the network size. Theorem 5.1: n is highest number of movements in this algorithm. Special case This case deals with the situation when the number of nodes is not a square root. We assume it r. To calculate the own movements we take a similar partitioning to the previous. In this special case also r is the number of movements. The next lines are used to express the own movements for each node. Let n = √ r , and dif f = r -n 2 .

U i,j =                    0, if i ≤ n. dif f + 2n -1, if i = n + 1. U i-1 -2, if n + dif f ≥ i > n. dif f + 2, if i = n + dif f + 1. U i-1 -R j , if i > n + dif f, l(i + 1) = j. U i-1 + 2, otherwise. (4)

C. Energy saving

Sleeping state is used to save energy and awake state is used to do the task for each node. The node cannot enter to a sleep state by changing its state to good since the node after changing its state to good becomes a reference for neighbors or future neighbors and it should help its neighbors so they can take correct positions belong to the final shape. So, it should stay wake to send messages (consultation) to neighbor nodes that need to know its state to decide. The aim of the following functions is to find with an optimal and deterministic method the time slots when the node must wake up to help neighbors and where the node must sleep to save energy. The following functions have a form of mathematical sequences which are in fact messages. Thus, by receiving the information from its neighbor the node can know its value which refers to the time of entering wake or sleep state. We take a partitioning of nodes to levels, each node will have a level l(i), and some nodes take special level say ls i . Nodes with i ≤ √ n take the level 0. For the others nodes: the x = 2 √ n -2 nodes after i = √ n take level 1. After, the following x -2 nodes take the following level (level 2) and so on. A special level ls i is associated to some nodes: node 4 √ n -4 takes the level ls i , the following node that takes the level ls i is the one after y = 2 √ n -5, and the the following node that will take the level ls i is the one after y -2 nodes and so on. Figure 4 shows an example. Once the node has taken a child (in the tree) it may enter to the sleep state and it must wake up at time when it will have new neighbors, it is the time to reach it for nodes that are going up. The root node starts the building of the tree at the round t0, it becomes a parent and enters into sleep state to save energy. Since the first leaf node will move n rounds, (to become root's neighbor in the E direction) it will be neighbor of the root at the time n -1. So, the root adjusts the local clock to wake up at n -1 + O(n)(with O(n)) is the time the first tree) in order to collaborate with its new neighbors. Similarly, other nodes are waiting for the construction of the first tree and enter into sleep sate after having a child, each node located after z nodes from the root enters into awake state at n -z -1 + O(n). The sequence S i expresses in term of n the time when each node can enter into sleep state after helping its neighbors to take correct positions.

T i = 7, if i = 1. T i-1 + 4, otherwise. (5)
Where : T i is a number associated to node i, i ≤ √ n -2.

I j = 2 √ n -1, if j = 3. I j-1 -2, otherwise. (6)
Where : I j is a number associated to node i has evel j > 1.

S i =                          n + 2, if i = 1. S i-1 + T i-1 , if i ≤ √ n -1. S i-1 , if i = √ n ∨ i = √ n + 1. S i-1 + 2 √ n -4, if l(i) = 2 ∧ l(i -1) = 1. S i-1 -2, if ls(i -1).(E) S i-1 -I i , if l(i -1) = l(i). S i-1 -1, otherwise. (7)
Where : S i + O(n) refers to the sleeping time for node i.

D. Generalization of the algorithm (DGASC)

We have presented an algorithm that deals with one case of the chain, exactly with the case where nodes can have at the beginning neighbors in directions SE or NW or in both directions at the same time. To show how to generalize the algorithm in order to deal with any chain at the beginning it is important to show how to distinguishing the initiator (the root) whatever the case. For other nodes can know what form of chain is by looking at the direction of their two neighbors. The root can be distinguished with principle that it has only one neighbor in the direction SW or SE or E, obviously whatever the shape of the chain we cannot find one where another node that has only one neighbor in the direction SW or SE or E, other nodes have two neighbors in the same time one in the direction D and the other in the inverse direction say -D for examples: one neighbor in SE direction and the other in the direction NW (NW-SE), SW and NE (NE-SW) or E and W(W-E). The last node in the chain has one neighbor in the direction NW, NE or W. After recognizing the form of chain, an algorithm similar to DASC presented is called, for example if the chain was with the form where the nodes can only have neighbors in the directions NE or SE or in both directions, we have to call DASC -d if we define DASC -d as the previous algorithm but the move is made from NE to NW or to W or from NW to W.

VI. SIMULATION

We have done the simulation with the declarative language Meld using DPRSim. In our simulations the radius of the node is 1 mm. We simulated with a laptop with processor Intel(R) Core(Tm) i5, 2.53 Ghz. The results of these simulations come to agree the results obtained previously, in particular the number of movements for each node and the effectiveness of dynamicity. The nodes applied the procedure of partitioning to levels and predicted with the two functions U i,j and R j the number of movements for each node, at the end of the algorithm each node compares the results of prediction to the results calculated by it. The figure 6 represents the overall number of movements in the networks corresponds to The nodes applied the procedure of nodes partitioning into levels and obtain with the function discussed previously the time slot when they enter into the sleep state and the wake up state. The figure 5 represents the execution time in ticks by the number of nodes, with counting the tree (DASC') and without counting the tree (DASC). In the curve representing the number of movements, we remark for some values of the network size n, the number is always n as found in theory. For the curves that represents the execution time figure 5, without counting the time of construction of the tree of DASC we see that if the number of nodes increases the time increase. If we count the time of the tree (O(n) time), the execution time of the algorithm increases dramatically. As conclusion, to ensure a Snap-connectivity through all time slots of the algorithm and to manage dynamically the nodes that can move, we have to use the tree, and by using the tree, we need more time to achieve the self-reconfiguration.

O = i=n,j= √ n-1 i=1,j=0 U i,j (8)

VII. CONCLUSION

In this paper, we presented a new method to complete the self-reconfiguration where the nodes do not know the fixed positions of the target shape but only the aimed shape; nodes collaborate and help each other by analyzing the characteristics of the target shape. Compared to the literature works this algorithm is scalable because each node needs only three state to achieve the Nodes in our paper can perform the algorithm regardless the place where they are because the algorithm is independent of the map, that what we call portability. We have presented a protocol that guarantees the connectivity throughout the execution time of the algorithm. The proposed algorithm is characterized by a constant memory needs and message exchange is limited to neighboring consultations. Consequently, system reconfiguration is fast. We presented how to manage the dynamicity of the network to save the energy and how to predict the movements of nodes in order to make the algorithm robust and energy-aware. However, some open problems remain; we will study the fault tolerance on self-reconfiguration in microrobots networks. The study of the effect of self-reconfiguration on the permutation routing where the objective will be to optimize the path of a node to go to the correct position where it finds its correct data. Also, the use of tabu algorithms to achieve the self-reconfiguration.

Figure 1 .

 1 Figure 1.Node modeling, in each movement the node travels the same distance.

Figure 2 .Figure 3 .

 23 Figure 2. Two catoms.

Figure 4 .

 4 Figure 4. Example of nodes partitioning into levels and the final positions of nodes

Figure 5 .Figure 6 .

 56 Figure 5. Execution time.

VIII. ACKNOWLEDGMENTS

This work is funded by the Labex ACTION program (contract ANR-11-LABX-01-01), ANR/RGC (contracts ANR-12-IS02-0004-01 and 3-ZG1F) and ANR (contract ANR-2011-BS03-005). The authors wish to express their appreciation to the anonymous reviewers for their constructive comments.


Giuseppe Iurato
email: giuseppe.iurato@unipa.it

On Jacques Lacan Psychosis Theory and ERPs Analysis

If properly interpreted, some recent neurolinguistic researches, based on the socalled Event-Related Potentials (ERPs) and conducted on patients showing schizophrenic spectrum disorders (SSDs), seem to corroborate some of the main Jacques Lacan theses on psychosis. In this brief note, we simply want to highlight the existence of this possible and interesting link.

Introduction

According to [START_REF] De | Come il cervello comprende il linguaggio[END_REF], the neurophysiological investigations methodologically based on the Event-Related Potentials (ERPs, acronym of Event-Related Potentials) have revealed to be of fundamental importance in the study of neurolinguistic alterations and anomalies, since they are functionally connected with the basic syntactic, semantic and pragmatic aspects of human language. For these reasons, the ERPs analysis is one of the main neurolinguistic experimental research methodologies. The Event-Related Potentials differ from the simple Evoked Potentials (with acronym EPs) for their major specificity of the elicited neurophysiological functions and for a greater information's complexity treated; furthermore, they elicit high and more structured cognitive function responses respect to the simplest ones processed by Evoked Potentials.

In this brief note, we simply want put the attention on the existence of a considerable number of experimental researches based on ERPs and conducted on patients showing disorders belonging to the schizophrenic spectrum, whose results, if opportunely interpreted, might to confirm the main theses on the nature of psychosis according to Jacques Lacan. Moreover, this paper has also been thought with the aim to tribute, for what has been possible to do, a right acknowledgment to the ingenious ideas of this Author, even nowadays little understood 1 .

The Lacan's Theory of Psychosis: a first brief sketch

According to 2 Rifflet- [START_REF] Rifflet-Lemaire | Introduzione a Jacques Lacan[END_REF], the main necessary (but not sufficient, in general) condition for the occurrence of a psychotic state, is the structural lack of a particular, but fundamental, Signifier, that of the Name-of-the-Father, whose pathological mechanism is named, d'après Lacan, Forclusion or Preclusion 3 (of The-Name-of-the-Father). This structural lack implies an impediment to the access to Symbolic Order, hence to the language-mediated order of Culture (following Claude Lévi-Strauss 4 ). Therefore, due just to this lack, the psychotic's Other is denoted by Ⱥ (the Barred Other), which also denotes the Hole in the Symbolic Order and is determined by the existence of every personal subjectivity; it hinders the possibility of a Signification of the real that the psychotic, accordingly, tries to fill up with other Signifiers (in a manner 1 From our viewpoint, the various criticisms raised in regards to the Lacanian theories by many authors, may turn out to be quite unfounded from a more properly epistemological stance simply because conducted respect to different knowledge levels not easily comparable. 2 See also [START_REF] Di Ciaccia | Jacques Lacan, un insegnamento sul sapere dell'inconscio[END_REF]. 3 See also [START_REF] Laplanche | The Language of Psychoanalysis[END_REF]. 4 In this regard, see the Introduction of D. Macey to [START_REF] Lacan | The Four Fundamental Concepts of Psychoanalysis[END_REF], as well as Umberto Eco (1984), who identifies the symbolic with the semiotic, and this with the linguistic order. Certain other authors, with whom we do not agree, argue on the inconsistency of this last identification.

which does not correspond to the usual and common pragmatic rules5 ) different from the paternal one. In particular, and this is an important remark, the psychotic is unable to articulate the Other of the Signifier (A) with the Other of the Law (a), that is to say, to build up the binary Algorithm6 A/a just because of the Nameof-the-Father Forclusion, with consequent defects to the Symbolic Order, but not to the Imaginary one. Thus, to definitely shape the rise of a psychotic framework, it would be the pregnancy lack of one of the main Signifiers, precisely that of the Name-of-the-Father which has not been able to inscribe itself in the linguistic register of the individual. All this implies an Hole in the Signifier field which, in turn, induces a collapse of the Signifier chain to detriment of the Symbolic Order7 . On the other hand, this inaccessibility to the Symbolic Order by psychotic individuals, is also witnessed by the difficulties that there exist in treating these subjects with the usual orthodox Freudian analysis, just due to their impossibility to verbally communicate with the analyst [START_REF] Schraml | Elementi di Psicologia Clinica[END_REF]. Furthermore, according to [START_REF] Scabini | Ideazione e psicoanalisi[END_REF], the Symbolic Order is, roughly, the register of the words and of the language, the latter being meant, in a pregnancy sense, as formed by all the significative expressions, that is to say, it contains all that which may evocates and not all that that informs, this marking the transition from Nature to Culture (according to Lévi-Strauss).

Finally, following Lacan, we recall the assumption of the superiority of the Symbolic Order (that is to say, the priority of the Signifier chains) respect to the remaining other two (namely, the Imaginary and Real ones), so that, now, it is possible to understand what dramatic and harmful consequences can spring out of its defects, like in the psychosis. However, further recalls to Lacan's theory of psychosis will be given in the next Section 4, which will be discussed in relation to what is clinically observed in Section 3.

ERPs Analysis on schizophrenic patients

In recent years, many scientific publications related to the analysis of ERPs made on patients classified as having disorders belonging to the schizophrenic spectrum (SSD), have appeared. Amongst these (see [START_REF] Bagner | Language comprehension and working memory deficits in patients with schizophrenia[END_REF], [START_REF] Bentin | Event-related potentials associated with semantic priming[END_REF], [START_REF] Bharath | P300 in family studies of schizophrenia: review and critique[END_REF], [START_REF] Chenery | Maintaining and updating semantic context in schizophrenia: an investigation of the effects of multiple remote primes[END_REF], [START_REF] Condray | The language system in schizophrenia: effects of capacity and linguistic structure[END_REF], [START_REF] Condray | Language disorder in schizophrenia as a developmental learning disorder[END_REF], [START_REF] Covington | Schizophrenia and the structure of language: the linguist's view[END_REF], Crow, T.J. (2000), David, A.S. & Cutting, J.S. (Eds) (1994), [START_REF] Ditman | The time course of building discourse coherence in schizophrenia: an ERP investigation[END_REF], [START_REF] Fogelson | A common N400 EEG component reflecting contextual integration irrespective of symbolic form[END_REF][START_REF] Friederici | Event-related brain potentials during natural speech processing: effects of semantic, morphological and syntactic violations[END_REF][START_REF] Friederici | Temporal structure of syntactic parsing: early and late event-related brain potential elicited by syntactic anomalies[END_REF], [START_REF] Grillon | N400 and semantic categorization in schizophrenia[END_REF], [START_REF] Grillon | Assessing a minimal executive operation in schizophrenia[END_REF], [START_REF] Iakimova | ERPs of metaphoric, literal and incongruous semantic processing in schizophrenia[END_REF], [START_REF] Kiang | Association of schizotypy with semantic processing differences: an eventrelated brain potential study[END_REF], [START_REF] Kiang | Abnormal typicality of responses on a category fluency task in schizotypy[END_REF], Kiang, M. et al. (2007), Kiang, M. et al. (2007) 1 , [START_REF] Kostova | N400 anomalies in schizophrenia are correlated with the severity of formal thought disorder[END_REF], [START_REF] Kumar | Semantics and N400: insights for schizophrenia[END_REF], [START_REF] Kutas | Reading senseless sentences: brain potentials reflect semantic incongruity[END_REF], [START_REF] Kutas | Event-related brain potentials to grammatical errors and semantic anomalies[END_REF], [START_REF] Lecardeur | Semantic hyperpriming in schizophrenic patients: increased facilitation or impaired inhibition in semantic association processing[END_REF], [START_REF] Leeson | Formal thought disorder is characterized by impaired lexical access[END_REF], [START_REF] Manschreck | Semantic priming in thought disordered schizophrenic patients[END_REF][START_REF] Martìn-Loeches | An electrophysiological (ERP) component, the recognition potential, in the assessment of brain semantic networks in patients with schizophrenia[END_REF], [START_REF] Matsumoto | Impairment of an event-related potential correlate of memory in schizophrenia: effects of immediate and delayed word repetition[END_REF], [START_REF] Matsumoto | Reduced word-repetition effect in the event-related potential of thoughtdisordered patients with schizophrenia[END_REF], McKenna, P.J. (1994), [START_REF] Mohr | Functional asymmetry in schizophrenic patients during auditory speech processing[END_REF], [START_REF] Morgan | Evidence of semantic disorganization using semantic priming in individuals with high schizotypy[END_REF], [START_REF] Moritz | Increased automatic spreading of activation in thought-disordered schizophrenic patients[END_REF], [START_REF] Moritz | False memories in schizophrenia[END_REF], [START_REF] Moritz | Patients with schizophrenia do not produce more false memories than controls but are more confident in them[END_REF], [START_REF] Ohta | An event related potential study in schizophrenia using Japanese sentences[END_REF][START_REF] Ozgürdal | Reduction of auditory event-related P300 amplitude in subjects with at-risk mental state for schizophrenia[END_REF], [START_REF] Pancheri | Schizofrenia[END_REF], [START_REF] Pardo | Auditory processing during speech production in schizophrenia[END_REF], [START_REF] Quelen | An investigation of semantic priming in schizophrenia using a new priming paradigm[END_REF], [START_REF] Rossell | Are semantic deficits in schizophrenia due to problem with access or storage[END_REF]), Rossi, A. (Ed.) (2006), [START_REF] Ruchsow | Semantic and syntactic processes during sentence comprehension in patients with schizophrenia: evidence from event-related potentials[END_REF], [START_REF] Salisbury | N400 lexical ambiguity and semantic incongruity in schizophrenia[END_REF], [START_REF] Sartori | An EPR study of low and high relevance semantic features[END_REF], [START_REF] Spitzer | Associative semantic network dysfunction in thought-disordered schizophrenic patients: Direct evidence from indirect semantic priming[END_REF], [START_REF] Weinstein | Do you hear what I hear? Neural correlates of thought disorder during listening to speech in schizophrenia[END_REF], [START_REF] Ye | Semantic and syntactic processing in Chinese sentence comprehension: evidence from event-related potentials[END_REF][START_REF] Yoshino | Relationship between the late positive component following N400 during a linguistic task and P300 during an oddball task in schizophrenia[END_REF]), there is a considerable number which, substantially, show as schizophrenic patients have no remarkable linguistic dysfunctions at the syntactic, phonological/phonemic, morphological and lexical levels, whereas many other papers have instead mainly disclosed that they present anomalies either in the semantic and pragmatic levels, and in the related integration processes; precisely they have disclosed that:

• the schizophrenic patients does not have impaired the main syntactic linguistic structures as detected by the analysis of the ELAN potential8 (see [START_REF] Ruchsow | Semantic and syntactic processes during sentence comprehension in patients with schizophrenia: evidence from event-related potentials[END_REF] and [START_REF] Ye | Semantic and syntactic processing in Chinese sentence comprehension: evidence from event-related potentials[END_REF]), but, instead, they primarily show impairments concerning both the semantic-syntactic integration processes, as proves the analysis of the P600 (or LPC) potential9 (see [START_REF] Friederici | Event-related brain potentials during natural speech processing: effects of semantic, morphological and syntactic violations[END_REF](1996)), and the semantic-pragmatic integration ones, as proves the analysis of the N400 potential10 (see [START_REF] Ditman | The time course of building discourse coherence in schizophrenia: an ERP investigation[END_REF] and [START_REF] Iakimova | ERPs of metaphoric, literal and incongruous semantic processing in schizophrenia[END_REF]);

• various deficits of the semantic processes take up a central rule amongst the cognitive anomalies showed by schizophrenic patients whose measured negative values of the N400 potential mainly prove that they are unable in using the contextuality in a suitable and correct manner (see [START_REF] Bharath | P300 in family studies of schizophrenia: review and critique[END_REF], [START_REF] Grillon | N400 and semantic categorization in schizophrenia[END_REF], [START_REF] Kiang | Association of schizotypy with semantic processing differences: an eventrelated brain potential study[END_REF], [START_REF] Kostova | N400 anomalies in schizophrenia are correlated with the severity of formal thought disorder[END_REF], Martìn-Loeches, M. et al. ( 2004), [START_REF] Matsumoto | Impairment of an event-related potential correlate of memory in schizophrenia: effects of immediate and delayed word repetition[END_REF], [START_REF] Moritz | Increased automatic spreading of activation in thought-disordered schizophrenic patients[END_REF], [START_REF] Ohta | An event related potential study in schizophrenia using Japanese sentences[END_REF] and [START_REF] Yoshino | Relationship between the late positive component following N400 during a linguistic task and P300 during an oddball task in schizophrenia[END_REF]);

• the anomalous activation of the semantic networks and of the related semantic priming tasks, are at the basis of the formal Thought Disorders (TD) of schizophrenic patients (see [START_REF] Manschreck | Semantic priming in thought disordered schizophrenic patients[END_REF], [START_REF] Quelen | An investigation of semantic priming in schizophrenia using a new priming paradigm[END_REF] and [START_REF] Spitzer | Associative semantic network dysfunction in thought-disordered schizophrenic patients: Direct evidence from indirect semantic priming[END_REF]);

• the schizophrenic patients have difficulty to access to the long-term semantic-lexical memory which can be at the origin of specific linguistic processes associated to formal thought disorders and semantic incongruities (see Covington, M. et al. (2005), McKenna, P.J. (1994) and Salisbury, D. ( 2010));

• the schizophrenic disorders are mainly associated with dysfunctions of the linguistic elaboration as showed by reduced values of the11 N100/N200 and P300 potentials (see [START_REF] Ozgürdal | Reduction of auditory event-related P300 amplitude in subjects with at-risk mental state for schizophrenia[END_REF] and [START_REF] Yoshino | Relationship between the late positive component following N400 during a linguistic task and P300 during an oddball task in schizophrenia[END_REF]).

In conclusion (see Falzone, A. ( 2004)), the schizophrenic patients have no remarkable dysfunctions neither at the basic linguistic levels (see [START_REF] Covington | Schizophrenia and the structure of language: the linguist's view[END_REF]), as those perceptive (see [START_REF] Mohr | Functional asymmetry in schizophrenic patients during auditory speech processing[END_REF] and [START_REF] Pardo | Auditory processing during speech production in schizophrenia[END_REF]), phonological/phonetic and morphological (see [START_REF] Covington | Schizophrenia and the structure of language: the linguist's view[END_REF]), nor at the syntactic level (see [START_REF] Ruchsow | Semantic and syntactic processes during sentence comprehension in patients with schizophrenia: evidence from event-related potentials[END_REF] and [START_REF] Ye | Semantic and syntactic processing in Chinese sentence comprehension: evidence from event-related potentials[END_REF]), as has already been said above. The unique, relevant anomalies and incongruities showed by the language of schizophrenic patients, regard the semantic level (see [START_REF] Bharath | P300 in family studies of schizophrenia: review and critique[END_REF], [START_REF] Grillon | N400 and semantic categorization in schizophrenia[END_REF] 2005)), with their relative integration processes, which, roughly speaking, point out on a clear difficult to insert the word signifieds within the various contexts social-culturally shared. This, if opportunely interpreted, may be related to Lacanian theory, as follows.

The Lacan's Theory of Psychosis: further outlines

From what has been said above as regards the aspects of the schizophrenic language, it is evident as such dysfunctions at the semantic and pragmatic levels (with difficulties in the respective integration processes) imply, in turn, inabilities in the use and in the choice of the correct and suitable signifiers (in the semantic sense) and incapacities in their correlations with the related signifieds, within the usual and commonly shared social-cultural context in which the lived experience of the schizophrenic patient has structurally evolved. On the other hand, following [START_REF] Bär | Semiotic Approaches to Psychotherapy[END_REF], Jacques Lacan has however based the construction of his ingenious theoretical framework on the De Saussure's structural linguistic, but recasting the main aspects and notions of the latter in an original manner suitable for his clinical and theoretical-psychoanalytic purposes. In this historical-epistemological context, the De Saussure's relationship between Signified (roughly, related to the conceptual level) and Signifier (roughly, related to the phonological level) is inverted from the Lacanian viewpoint: in the De Saussure's framework, prevails the ratio S/s between Signified (s) and Signifier (S) considered respect to a given system of values charactering the linguistic sign, whereas in the Lacan's one this ratio is inverted12 , giving rise to the first Lacanian matheme S/s, formalizing, in the Lacanian algebra (not in a mathematical sense), the Signification process which characterizes the Symbolic Order. Instead, the De Saussure's ratio s/S gives precedence to the thing signified s rather than to the signifier S (the word), establishing a sort of almost one-to-one correspondence between them, which is more suitable to denote a ''meaning'' process concerning the Imaginary Order and not the Symbolic one (see [START_REF] Schroeder | The Four Lacanian Discourses: or Turning Law Insied-Out[END_REF]).

Instead, again following [START_REF] Schroeder | The Four Lacanian Discourses: or Turning Law Insied-Out[END_REF], the Lacanian first matheme m 1 , that is to say S/s, explicitly invokes the bar between S and s, which refers to the fact that not necessarily does exist a natural one-to-one correspondence between S and s, since every their possible relationship may be logically arbitrary, contingent and only temporally imposed by the speaker's will, so that this bar indeed denotes the splitting of the subject herself or himself who associates Signifier with Signified, in an unending infinite chain of Signification. On the other hand, this slipping carried out continuous postponements between signifier and signified, in which the signified of a signifier is another signifier 13 , that is, the former is explained by the latter through a paradigmatic and/or a syntagmatic axis, in such a manner that each signified is itself a signifier, standing for another signified, which, in turn, stands for another signifier, and so forth. Roughly speaking, this ad infinitum process, which gives a Signification Chain, may be reflected in the fact that no individual law and no word, have meaning in the abstract but only within the context of a common legal system having primary and secondary rules (of change, recognition and adjudication) with principles of interpretation (for individual laws), and, respectively, within the context of a language having a vocabulary and grammar (for words).

According to Lacan, the signifier does not express the meaning but anticipate it, that is to say, it is in the signifier (or signification) chain that the meaning presses, no element of it consisting in the signification of which it is able to express in that moment, whence it follows that the meaning is, as say, subordinated to this signification chain. Therefore, a signification, in the Lacanian view, is always in a state of continuous flux of slippage (or glissement) and ambiguity, so that it is necessary to impose the notion of an incessant slipping of the signified under the signifiers, the cross point between the signifier path and the signified slipping ellipses is said to be the quilting point (or point de capiton, or anchoring point), whose lack characterizes many delirant psychotic states (see [START_REF] Dell'io | Dictionnaire inespéré de 55 termes visités par Jacques Lacan[END_REF], [START_REF] Roudinesco | Jacques Lacan -Esquisse d'une vie, historie d'un système de pensée[END_REF] and also [START_REF] Filloux | L'inconscient[END_REF]).

For a subject to can communicate and, hence, in order to the symbolic order can to run or function 14 , it is necessary 'to freeze' the shifting of the unending chain of the signifiers, albeit contingently and temporarily. A way to do this is, according to Lacan, through the adoption of a master signifier (or a significant-maître) which, in turn, is structurally formalizable in the form in turn, equivalent to the following (see (Galimberti, 1990)). Suitable compositions of them lead to the so-called Lacan transfer algorithm, which is related to the structural formation of the signification chain by means of metonymy and metaphor. 13 Which, following R. Jakobson, is correlated with the previous one by means of the unconscious mechanisms of condensation (metaphor) and displacement (metonymy). 14 According to the ordinary linguistic levels of the syntax, semantics and pragmatics.

stopping the chain of signification of above. These last signifiers are the keys that give meaning to the other signifiers, and are absolutely necessary because a chain of signification stand for nothing but itself. In such a chain, signifier and signified are one and the same, so that it therefore can serve as the period that momentarily ends the run-on sentence of signification. Hence, it is crucial that a symbolic order have master signifiers: in the Lacanian theory, it is assumed as main master signifier that of the Name-of-the-Father (in turn, referring to the Phallus symbol).

However, it is fundamental to point out the essential dissimilarity between the main De Saussure's structural linguistic ideas and the Lacanian ones, above all as concerns the notions of signifier and signified with their relationships: in fact, according to Lacan (see [START_REF] Fages | Che cosa ha veramente detto Lacan[END_REF]), the signifier seems to evolve separately from the signified, this taking also place unbeknownst of the subject. The signifiers are taken into a of relations (of reciprocal variations and differences) to form an articulated chain (exactly, the signification chain), whose elements are structured amongst them through metonymy and metaphor, while the signifieds depend on the personal lived experience of the subject15 and take their structural coherence only under the determination by signifiers 16 . The Lacanian first matheme S/s is therefore quite different from the De Saussure's one: following [START_REF] Fages | Che cosa ha veramente detto Lacan[END_REF], it would also include the following corresponding Lacan's barred condensations Langue/Parole, Synchrony/Diachrony and Paradigm/Syntagm, according to the following, general table

Signifier (S)

Signified (s) Langue Parole Synchrony Diachrony Paradigm Syntagm in which each column, as elementary category, would contain elements equivalent to the heading element of it (see [START_REF] Rifflet-Lemaire | Introduzione a Jacques Lacan[END_REF]). This revolutionary Lacanian subversion of the elementary categories of the De Saussure's linguistic, is only motivated by clinical applications and oriented to show the supremacy of the signifier on signified, emphasizing the separation bar between them, even if this has no linguistic meaning from the operational point of view but only psychoanalytic value. Indeed, Lacan wants to point out on the essential inaccessibility to the signified sphere, which is mainly unconscious, denoting such a slipping of the signified with a sort of ellipsis17 , schematized by Δ → $ (Lacan preferring barred $ rather than indicate directly s), which continuously intersects the signification chain S → S', but always postponing at the Imaginary Order (of the unconscious language), in certain points called points de capiton (already mentioned above), often absent in psychotics (see [START_REF] Dell'io | Dictionnaire inespéré de 55 termes visités par Jacques Lacan[END_REF]), in which infiltrates, at the moment, the signified. Therefore, taking also into account certain aspects of the subconscious formation of the language according to [START_REF] Thass-Thienemann | La formazione subconscia del linguaggio[END_REF], from what has been established in the previous Section 3 as regard the semantic and pragmatic anomalies and inabilities, with related inefficiencies about their integration processes, observed in schizophrenic spectrum disorders showing subjects, it necessarily follows as them are unable to construct any signification chain: indeed, if they were able to make this, then it would be possible to yield sense (or meaning) to their discourse since this, as has already been said, basically presses in such a dominant signification chain. Hence, we must conclude affirming as such pathological subjects aren't able to perform such a signification chain, or else, it does not take place the formation of it that, as known, starts from the master signifier called Name-of-the-Father. Hence, it follows that they necessarily have rejected (Forclusion) this primary and primordial signifier (the only one that will allow signified's effects), which prevent them the access to the Symbolic Order. In fact, if S s is a symbolic (conscious) signifier, like the Name-of-the-Father (whose unconscious signifier is that of Phallus), and S i is an imaginary (unconscious) signifier, like the mother desire, then the passage to the symbolic's register takes place by means of the following Lacanian transfer algorithm18 with S i often denoted by $ (see [START_REF] Fages | Che cosa ha veramente detto Lacan[END_REF]) and s belonging to the real's register. In it, the related points de capiton will act suturing the signifier slipping ellipsis Δ → $ = S i (this action being just represented by in the left-hand side of the above transfer algorithm) on the signifier postponement (or slipping) concatenation S i → S s which marks the corresponding passage from the imaginary register to the symbolic one, with the result given by the right-hand side of the above transfer algorithm. On the other hand, from the above mentioned table, we may consider the Lacanian algorithm Signifier/Signified S/s as an equivalence class of the type where, respectively, L/P stands for the Lacanian algorithm Langue/Parole, stands for the Lacanian algorithm Synchrony/Diachrony and stands for the Lacanian algorithm Paradigm/Syntagm, with that is to say, S/s is equivalent, by means of the Lacanian equivalence relation (given by the above table ), to each of the Lacanian algorithms contained in the above table (see [START_REF] Rifflet-Lemaire | Introduzione a Jacques Lacan[END_REF]). Therefore, in particular, via this equivalence relation, the above Lacanian transfer algorithm, is also equivalently rewritable in the form where L s is the (conscious) Langue in the symbolic's register, P i is the (unconscious) Parole in the imaginary's register and t is the (unconscious) thing. This algorithm is related to the signifier concatenation P i → L s , marking the passage from the imaginary's register to the symbolic's one, which gives a temporary signifier to the thing t through the suturing points de capiton connected with the related signified slipping ellipsis Δ → $. In particular, the semantic and pragmatic levels act on the Lacanian algorithm L s /P i , so that anomalies and dysfunctions at these linguistic levels are, in turn, due to the impossibility to build up this algorithm L s /P i which will make that hole in the signification chain, recalled in Section 2; all this is just coherent with the detected experimental data of Section 3 as concerns schizophrenic patients. These last considerations, on the other hand, are also confirmed from what said in [START_REF] Fages | Che cosa ha veramente detto Lacan[END_REF] just on psychotics. Indeed, this author says that the psychotic is unable to correctly use the language since the linguistic sign S/s (or, in our case, its equivalent L s /P i ) have undergone radical alteration in her or him: precisely, as regards a schizophrenic, every signifier (or each symbol) may points out on the same signified, or else, different signifiers may have the same signified; instead, as regards a deliriant, an unique signifier may points out on every signified, or else, different signifieds may have an equal signifier.

In conclusion, in the light of what has been said so far, it is possible to consider the data of the analyses recalled in Section 3 as a sort of experimental confirmation of the main Lacan's theses on Psychosis.

  ,[START_REF] Kiang | Association of schizotypy with semantic processing differences: an eventrelated brain potential study[END_REF],[START_REF] Kostova | N400 anomalies in schizophrenia are correlated with the severity of formal thought disorder[END_REF], Martìn-Loeches, M. et al. (2004),[START_REF] Matsumoto | Impairment of an event-related potential correlate of memory in schizophrenia: effects of immediate and delayed word repetition[END_REF],[START_REF] Moritz | Increased automatic spreading of activation in thought-disordered schizophrenic patients[END_REF],[START_REF] Ohta | An event related potential study in schizophrenia using Japanese sentences[END_REF],[START_REF] Salisbury | N400 lexical ambiguity and semantic incongruity in schizophrenia[END_REF] and[START_REF] Yoshino | Relationship between the late positive component following N400 during a linguistic task and P300 during an oddball task in schizophrenia[END_REF]) and the pragmatic one (see[START_REF] Ditman | The time course of building discourse coherence in schizophrenia: an ERP investigation[END_REF] andIakimova, G. et al. (

From this point of view, we might also draw a connection line with the conception of schizophrenia meant by Existential-Phenomenological Analysis (Daseinanalyse) according to which the schizophrenia should be interpreted as a her or his own mode of being in the world, by the patient.

Which is the reciprocal of the De Saussure's one and that it is, in turn, reconstructed reinterpretating the originary binary Freudian system Ego's Ideal/Ideal of the Egosee[START_REF] Roudinesco | Jacques Lacan -Esquisse d'une vie, historie d'un système de pensée[END_REF] and[START_REF] Di Ciaccia | Jacques Lacan, un insegnamento sul sapere dell'inconscio[END_REF]. In this regards, see also what thereupon said[START_REF] Lagache | La Psychanalyse et la structure de la personnalité[END_REF] and the related Lacan's reply (see[START_REF] Lacan | Scritti[END_REF].

See, for instance,[START_REF] Fossi | Psicologia dinamica: una eredità del XX secolo[END_REF].

This ERP is detected when syntactically wrong words are present. Furthermore, this potential is believed reflecting the automatic assignment of a grammatical structure to a given word string.

This ERP is elicited from syntactically wrong phrases, being associated to semantic-syntactic integration processes.

This ERP is considered as the specific electrophysiological correlate of the semantic incongruities (see[START_REF] De | Come il cervello comprende il linguaggio[END_REF]).

The N100 and N200 potentials are respectively correlated to the elicitation of auditory stimuli and to the temporal processing of semantic and phonological aspects. The P300 potential is generally related to the cognitive functionality (see[START_REF] De | Come il cervello comprende il linguaggio[END_REF]).

The separation between conscious and unconscious underwent to the splitting of the subject, is formally described by means of the Lacanian algorithm S/s (even if Lacan himself continues to call it saussurian algorithm). This type of algorithm includes every ratio of the type

Which is just correlated to her or his linguistic pragmatic level, and vice versa, this last being that having the largest number of psychological implications (see[START_REF] Galimberti | Dizionario di Psicologia[END_REF]).

The signifier order and the signified one are structurally thought as two particular nets of relations, whose reciprocal interconnections, according to Lacan, are quite different from those provided by De Saussure: precisely, the net of signifiers and the net of signifieds does not recover one with the other. The first has a synchronic structure whereas the second has a diachronic structure which historically reacts on the first, whose dominant structure, in turn, orders the ways of the second.

This term being understood as a rhetorical figure.

See what is said in the footnote 12 about some possible equivalent forms of the fundamental Lacanian transfer algorithm, of which, here, we have only used two of them.


Microstructural influence on heat conduction

C. Boutin

To cite this version:

C. Boutin. Microstructural influence on heat conduction. International Journal of Heat and Mass Transfer, 1995, 38 (17), pp.3181-3195. hal-00940469

Iikllmdv=ffl(Vy*kllm)xJdO~-ffl~pXlVyp(XJ)]-~k~Xldv.

That is, when introducing k ° : fnk)~m dv = fn(Vy.kltm)XJ dv+ fnk°JX' dv and, by replacing the divergence by its expression, we establish the identity : K)'~-K°'(pCXJ)/(pC) = (kn°JXt-k°m'XJ). Note. In the case of a constant value of pC this relation becomes :

If,) t~ = <k °mJXt --k° tXJ > which proves the antisymmetry of tensor K ~ with regards to the indexes (j,/).