A Blondin Massé

A Frosini
email: andrea.frosini@unifi.it

S Rinaldi
email: rinaldi@unisi.it

L Vuillon

On the shape of permutomino tiles

Keywords: Polyominoes, Permutominoes, Tilings, Palindromes, Pseudoperiods

In this paper we explore the connections between two classes of polyominoes, namely the permutominoes and the pseudo-square polyominoes. A permutomino is a polyomino uniquely determined by a pair of permutations. Permutominoes, and in particular convex permutominoes, have been considered in various kinds of problems such as: enumeration, tomographical reconstruction, and algebraic characterization.

On the other hand, pseudo-square polyominoes are a class of polyominoes tiling the the plane by translation. The characterization of such objects has been given by Beauquier and Nivat, who proved that a polyomino tiles the plane by translation if and only if it is a pseudo-square or a pseudohexagon. In particular, a polyomino is pseudo-square if its boundary word may be factorized as XY X Y , where X denotes the path X traveled in the opposite direction.

In this paper we relate the two concepts by considering the pseudo-square polyominoes which are also convex permutominoes. By using the Beauquier-Nivat characterization we provide some geometrical and combinatorial properties of such objects, and we show for any fixed X, each word Y such that XY X Y is pseudo-square is prefix of an infinite word Y ∞ with period 4 |X| N |X| E . Also, we show that XY X Y are centrosymmetric, i.e. they are fixed by rotation of angle π. The proof of this fact is based on the concept of pseudoperiods, a natural generalization of periods.

Introduction

In the last years the problem of tiling planar surfaces has shown interesting mathematical aspects connected with computational theory, mathematical logic, discrete geometry, and also physics.

One possible explanation for so wide usage of tilings (also in different disciplines) is their capability to generate very complex configurations. As a confirmation confirmation of this assertion, let us just mention a classical result of Berger [START_REF] Berger | The undecidability of the domino problem[END_REF]: given a set of tiles, it is not decidable whether there exists a tiling of the plane which involves all its elements. This result has been achieved by constructing an aperiodic set of tiles, and successively it has been strengthened by Gurevich and Koriakov [START_REF] Gurevich | A remark on Berger's paper on the domino problem[END_REF] to the periodic case.

Further interesting results have been achieved by restricting the class of sets of tiles only to those having one single element. In particular Wijshoff and Van Leeuwen [START_REF] Wijshoff | Arbitrary versus periodic storage schemes and tesselations of the plane using one type of polyomino[END_REF] considered the exact polyominoes (i.e. polyominoes which tile the plane by translation) and proved that the problem of recognizing them is decidable. The same problem was studied in [START_REF] Beauquier | On traslating one polyomino to tile the plane[END_REF], Beauquier and Nivat from a purely geometrical point of view and they found a characterization of all the exact polyominoes by using properties of the words which describe their boundaries. In particular they stated that the boundary word coding these polyominoes shows a pattern XY ZX Y Z, called a pseudo-hexagon, where one of the variable may be empty in which case the pattern XY X Y is called a pseudo-square. However, in their work, the authors were not concerned with the combinatorial properties of these structures.

Successively, in [START_REF] Brlek | Tilings by translation: enumeration by a rational language approach[END_REF] the authors investigated some combinatorial and enumerative problems on exact polyominoes, focusing on the subclass of pseudo-square convex polyominoes. The results in [START_REF] Brlek | Tilings by translation: enumeration by a rational language approach[END_REF] have been mostly achieved using the word representation for the boundary of the polyomino, and relying on several tools and properties arising from combinatorics on words. Later, following this research line, and using similar approaches, in [START_REF] Blondin-Massé | A parallelogram tile fills the plane by translation in at most two distinct ways[END_REF] it was proved that if the tile is a parallelogram polyomino, then there are at most two distinct ways in which it can fill the plane by translation; in [START_REF] Brlek | On the Tiling by Translation Problem[END_REF] the authors present a linear time algorithm for detecting pseudo-square polyominoes.

In this paper we introduce a new and challenging research line which aims at exploring the relations between exact polyominoes and permutominoes, a recently studied class of polyominoes arising in several mathematical and combinatorial problems and strictly connected with permutations.

Let us recall that a permutomino of size n is a polyomino determined by particular pairs (π 1 , π 2 ) of permutations of length n+1 (see, for instance, Fig. 4). An equivalent definition for a permutomino is that, for each abscissa (ordinate) between 1 and n, there is exactly one vertical (horizontal) side in the boundary with that coordinate.

Permutominoes were introduced in [START_REF] Kassel | The singular locus of a Schubert variety[END_REF], and then considered by F. Incitti while studying the problem of determining the R-polynomials associated with a pair (π 1 , π 2 ) of permutations [START_REF] Incitti | Permutation diagrams, fixed points and Kazdhan-Lusztig R-polynomials[END_REF]. In recent years, a particular class of permutominoes, namely convex permutominoes, and their associated permutations, have been widely studied [START_REF] Bernini | Permutations defining convex permutominoes[END_REF][START_REF] Disanto | A closed formula for the number of convex permutominoes[END_REF]. Some enumerative results known about convex permutominoes, which may be useful in this paper, are the following [START_REF] Disanto | A closed formula for the number of convex permutominoes[END_REF]: i. the number of parallelogram permutominoes of size n is equal to the n-th Catalan number,

C n = 1 n + 1 2n n ;
ii. the number of convex permutominoes of size n is:

2 (n + 3) 4 n-2 - n 2 2n n n ≥ 1. (1)
We also recall from [START_REF] Bernini | Permutations defining convex permutominoes[END_REF] that permutations defining convex permutominoes are closely related with the so-called square permutations (or convex permutations), recently considered by several authors [START_REF] Mansour | Grid polygons from permutations and their enumeration by the kernel method[END_REF].

In order to attain our objective, we start by considering pseudo-square polyominoes which are also convex permutominoes, i.e. pseudo-square convex permutominoes (psc-permutominoes for short). This problem raises interesting properties since it relates to combinatorics on words and classical problems on polyominoes. Moreover these objects are uniquely defined by permutations, thus they give us an effective way to tile the plane using permutations. Hence this problem shows strict relations with the vast combinatorics on pattern avoiding permutations [START_REF] Bernini | Permutations defining convex permutominoes[END_REF].

Our first objective is to find a characterization of the boundary words of psc-permutominoes. More precisely, we are interested in the problem of establishing if, for a given word X, there is at least a word Y which is compatible with X, that is, XY X Y represents a psc-permutomino.

Two further goals -which are strictly connected to the previous one -are to obtain the enumeration of psc-permutominoes according to the semi-perimeter, and to characterize permutations defining psc-permutominoes.

Using the Beauquier-Nivat characterization, and the results from [START_REF] Brlek | Tilings by translation: enumeration by a rational language approach[END_REF], we show that for any given X there are at most two different words of minimal length Y and Y compatible with X. These words are such that |Y | = |Y |, and Y can be obtained from Y by means of renaming of letters. Moreover, they individuate the growing direction of the permutomino, so we distinguish among the upward and the downward growing direction of a psc-permutomino and study these two cases separately.

In studying the psc-permutominoes with upward growing direction, we prove that X uniquely determines an infinite word Y ∞ , and that every word Y which is up-compatible with X (i.e. XY X Y is a psc-permutomino with upward growing direction) is a prefix of Y ∞ . Moreover we show that Y ∞ has period 4 |X| E |X| N . The same results can be reformulated in the case of down-growing direction.

As an addition to the periodic nature of Y ∞ , we show that psc-permutominoes are centrosymmetric, i.e. they are invariant under a rotation of angle π. The proof of this fact is based on the concept of pseudoperiod, a natural generalization of periods introduced in [START_REF] Blondin Massé | A Fine and Wilfs theorem for pseudoperiods and Justins formula for generalized pseudostandard words[END_REF]. From a combinatorial point of view, it reveals a remarkable family of words who seem to share properties with central words.

Several challenging problems remain open and they are briefly presented and discussed in the final section. As a matter of fact, we point out that the same problems considered in this paper remain open if we go to consider the class of pseudo-hexagonal convex permutominoes, although some generalizations of our results seem to be possible.

We point out that this paper is an extended version of the abstract [START_REF] Frosini | Tiling the plane with permutations[END_REF] presented at the 16th Conference on Discrete Geometry for Computer Imagery 6-8 April 2011 Nancy, France. Compared to that work, here we give a detailed study of the words X and Y leading to psc-permutominoes, we show that both X and Y must be palindromic words, which was only conjectured in [START_REF] Frosini | Tiling the plane with permutations[END_REF], we provide new results, a new conjecture about the length of the word X of a psc-permutomino, and some examples concerning non convex pseudo square permutominoes, which deserve some some further inspection.

Two classes of polyominoes

In the plane Z×Z a cell is a unit square whose vertices have integer coordinates, and a polyomino is a finite connected union of cells having no cut point (see Fig. 1(a)). Polyominoes are defined up to translations, and we deal with polyominoes without "holes", i.e. polyominoes whose boundary is a single loop. A column (resp. row) of a polyomino is the intersection between the polyomino and an infinite strip of cells whose centers lie on a vertical (resp. horizontal) line. A polyomino is said to be column-convex (resp. row-convex) when its intersection with any vertical (resp. horizontal) line is connected. A polyomino is convex if it is both column and row convex (see Fig. 1(b,c)). A particular subclass of the class of convex polyominoes consists of the parallelogram polyominoes, defined by two lattice paths that use north (vertical) and east (horizontal) unitary steps, and intersect only at their origin and extremity. These paths are commonly called the upper and the lower path (see Fig. 1 (d)).

(a) (d) (c) (b)

In what follows we will use to represent the boundary of a polyomino by a boundary word defined on the alphabet Σ = {N, S, E, W }, where N (resp. E, S, W ) stands for the north (resp. east, south, west) unit step. The word representing a polyomino is obtained simply by following its boundary from a starting point in a clockwise orientation. For instance, the polyomino in Fig. 1(c), starting from the highlighted point, is represented by the word

X = N W N EN EN N N ESESSESESSW SW W N W W.
Moreover, if X = x 1 x 2 . . . x r is a word, where x i ∈ {N, E, S, W }, then the complement X = x r . . . x 2 x 1 is defined by N = S, S = N , W = E, and E = W . We define the length of a word X by |X| = r, and by |X| xi the number of occurrences of the letter x i in X. We observe that in any polyomino the length of the boundary word coincides with its perimeter.

Polyominoes that tile the plane

In [START_REF] Girault-Beauquier | Tiling the plane with one tile[END_REF], Beauquier and Nivat studied the class of exact polyominoes, i.e. polyominoes that tile the plane by translation. They found a characterization of all the exact polyominoes by using properties of the words which describe their boundaries. In particular they stated that the boundary words coding these polyominoes show a pattern XY Z X Y Z, called a pseudo-hexagon, where one of the variable may be empty in which case the pattern XY X Y is called a pseudo-square.

In the rest of the paper, we will deal with pseudo-square convex polyominoes (briefly pscpolyominoes). As an example, the polyomino in Fig. 2 (a) is a psc-polyomino, and the decomposition of its boundary word is

X = N N EN EEN, Y = EEN E = EESE, X = N EEN EN N = SW W SW SS, Y = EN EE = W N W W.
In [START_REF] Brlek | Tilings by translation: enumeration by a rational language approach[END_REF] the authors study the problem of enumerating psc-polyominoes according to the semiperimeter, i.e. the length of the upper (lower) path. In order to obtain the enumeration, they determined some combinatorial properties about psc-polyominoes, some of which will be recalled here since they will be useful through the paper. In order to simplify the enumeration, the whole class of psc-polyominoes can be partitioned into two sub-classes, according to the polyominoes' shape:

1. Pseudo-square parallelogram polyominoes (briefly, psp-polyominoes). A complete characterization of the elements of this class is stated by the following [START_REF] Brlek | Tilings by translation: enumeration by a rational language approach[END_REF]:

Proposition 1.
If XY X Y is a decomposition of the boundary word of a pseudo-square parallelogram polyomino, then XY encodes its upper path, and Y X its lower path. Moreover, the decomposition is unique, X starts and ends with N , and Y starts and ends with E. We also observe that each psc-polyomino with a decomposition of the second type can be transformed -under an horizontal reflection -into another psc-polyomino whose decomposition is of the first type (note that the two polyominoes may coincide). So, without loss of generality we will only consider psc-polyominoes of with a decomposition of the first type, starting from A. Hence, from now on, the word X encoding the boundary of a generic psc-permutomino is assumed to have the form

N + (E ∨ N ) * N + .
According to the purposes of our paper, we are led to formulate the previous statements in a slightly different way. Proposition 2. Let XY X Y be the decomposition of the boundary word of a psc-polyomino, and let us assume without loss of generality that the word X has the form N + (E ∨ N ) * N + . The following two cases may occur:

-Y is a north-east oriented monotone path (i.e. it uses only N and E steps), these are precisely the pseudo-square parallelogram polyominoes.

-Y is a south-east oriented monotone path (i.e. it uses only S and E steps).

According to the two cases we say that the polyomino has upward (resp. downward) growing direction. For instance, Figure 3 (a) depicts a psp-polyomino, having upward growing direction, while Figure 3

Polyominoes determined by permutations

Let P be a polyomino without holes, having n rows and n columns, n ≥ 1, and we assume without loss of generality that the south-west corner of its minimal bounding rectangle is placed at [START_REF] Blondin Massé | A Fine and Wilfs theorem for pseudoperiods and Justins formula for generalized pseudostandard words[END_REF][START_REF] Blondin Massé | A Fine and Wilfs theorem for pseudoperiods and Justins formula for generalized pseudostandard words[END_REF]. Let A = A 1 , . . . , A 2(r+1) be the list of its vertices (i.e., corners of its boundary) ordered in a clockwise direction starting from the lowest leftmost vertex, with A i = (x i , y i ). We say that P is a permutomino if P 1 = (A 1 , A 3 , . . . , A 2r+1 ) and P 2 = (A 2 , A 4 , . . . , A 2r+2 ) represent two permutations of length n. Obviously, if P is a permutomino, then r = n, see Fig. 4. As an immediate consequence we have that m = n, and so a permutomino has n rows and n columns (n is called its size), and the number of its vertices is 2(n + 1). The two sets P 1 and P 2 can be regarded as two permutation matrices of [n + 1] = {1, 2, . . . , n + 1} having no common points; we indicate the permutations associated with them by π 1 (P ) and π 2 (P ), respectively (see Fig. 4). They are called the permutations associated with P . From the definition any permutomino P of size n has the property that, for each abscissa (ordinate) between 1 and n there is exactly one vertical (horizontal) side in the boundary of P with that coordinate. It is simple to observe that this property is also a sufficient condition for a polyomino to be a permutomino.

Several combinatorial and enumerative properties of convex permutominoes have been determined in [START_REF] Disanto | A closed formula for the number of convex permutominoes[END_REF][START_REF] Bernini | Permutations defining convex permutominoes[END_REF]. Here, for brevity's sake we just recall that a complete characterization of permutations associated with convex permutominoes has been given in [START_REF] Bernini | Permutations defining convex permutominoes[END_REF]: precisely, the set {π 1 (P ), π 2 (P ) : P is a convex permutomino of size n} coincides with the set of square permutations of length n + 1 [START_REF] Mansour | Grid polygons from permutations and their enumeration by the kernel method[END_REF].

Convex permutominoes tiling the plane

In this section we study convex permutominoes which are also pseudo-square polyominoes, that we call pseudo-square convex permutominoes (briefly, psc-permutominoes). To the authors' opinion, these are interesting objects to be studied since they constitute a first step towards the more general problem of tiling the plane by permutations. Moreover, we will show that these objects present remarkable geometrical and combinatorial aspects independent of their relationship with permutations, and in particular some features related to combinatorics on words.

In the study of psc-permutominoes we plan to face the following three general problems:

1. characterizing the combinatorial properties of the words X and Y such that XY X Y ;

2. enumerating psc-permutominoes according to the semi-perimeter;

3. characterizing permutations associated with psc-permutominoes.

In this paper we will be concerned with the first of these problems, remarking that our results give us an important ideas for tackling the other two problems.

First, we recall that we assume that the word X encoding the boundary of a generic pscpermutomino has the form N + (E ∨ N ) * N + . Moreover, we will work indifferently with the word or the path representation of X and Y .

We say that a binary word X is compatible with Y if the word XY X Y represents the boundary of a psc-polyomino. So, for instance, we have that the word X = N N EN N is compatible with Y = EEN EE (see Fig. 5 (a)), with Y = EESEE (see Fig. 5 (b)), and with Y = EESEESSEESSSEESSEESEE (see Fig. 5 (c)). A word X of the form N + (E ∨ N ) * N + is said to be convex-exact (briefly, c -exact) if there is at least a word Y such that XY X Y is a psc-polyomino.

We easily observe that psc-permutominoes inherit some basic properties from being pseudosquare convex polyominoes, and in particular we may adapt the statement of Proposition 2, as follows:

Proposition 3. For each word X of the form N + (E ∨ N ) * N + there exist at most two different words Y and Y , having minimal length, compatible with X such that:

1. neither Y nor Y is a prefix of the other, 2. if there exists Y compatible with X, then either Y or Y is a prefix of Y .

It is also clear that, in a pseudo-square convex permutomino, the word X completely determines the related words Y and Y . For instance referring to Fig. 5, the word X = N N EN N is compatible with Y = EEN EE, and Y = EESEE while Y = Y SSEESSSEESSY .

We observe that the previous proposition does not hold if we relax the convexity constraint. In Fig. 6, two non convex ps-permutominoes are depicted: for each of them, the chosen word Y compatible with X, has neither Y nor of Y as prefix. Furthermore, the word X of the pspermutomino in (a) is c-exact, while that of (b) is not, giving some relevance to the study of the class of words X that are compatible with a generic word Y , and still provide a pseudo square tiling of the plane.

According to Proposition 3, and similarly to what we have done for psc-polyominoes, the first classification of psc-permutominoes can be given by the concept of growing direction. We say that a psc-permutomino has upward growing direction if the word Y has the form E + (N ∨ E) * E + . Similarly, we say that it has downward growing direction if Y has the form E + (S ∨ E) * E + . We remark that X = N N EN N is the word of minimal length for which there exists at least a psppermutomino in both growing directions (see Fig. 5). In the next sections we will study separately the psc-permutominoes having upward and downward growing direction. According to this, we say that X and Y are up-compatible (resp. down-compatible) with X if XY X Y is a psc-permutomino having upward (resp. downward) growing direction.

Upward growing direction: pseudo-square parallelogram permutominoes

Pseudo-square convex permutominoes having upward growing direction have a very simple characterization which they directly inherit from pseudo-square convex polyominoes, precisely from Proposition 2, and is stated by the following.

Proposition 4. The psc-permutominoes having upward growing direction are precisely the pseudosquare parallelogram permutominoes.

We observe that, starting from X, and given a positive integer n, there is a unique path Y (n) of length n, and using steps E and N , such that the object X(n) obtained by concatenating Y (n) at the beginning and at the end of X has exactly one side for each abscissa and ordinate between 1 and n. Similarly, letting n tend to infinity, we obtain a unique infinite path Y ∞ , and an object X(∞) having exactly one side for each abscissa and ordinate greater than 1 (see Fig. 7). In X(n), the path Y ∞ starting from the end (resp. beginning) of X will be called the upper (resp. lower) path of X(n). The following property is straightforward.

Proposition 5. Every word Y which is up-compatible with X is a prefix of Y ∞ .
In what follows, we prove that the word Y ∞ is periodic, and we provide a simple algorithm to determine a prefix of length n of Y ∞ from X.

In order to study the shape of the compatible paths, we need to introduce some useful functions on permutominoes.

First, we consider a natural function on subsets of N defined as follows. Let S ⊆ N. We define mex(S) = min(S),

where S = N -S. For instance, if S = {0, 1, 4} then S = {2, 3, 5, 6, . . .} so that mex(v) = 2. This definition appears in some works of Fraenkel and it is related to the Nim game, Sturmian and balanced sequences [START_REF] Fraenkel | The Rat game and the Mouse game, to appear in Games of No Chance[END_REF].

A psc-permutomino is in particular a permutomino, so that there must be exactly one vertical segment and one horizontal segment per row and per column. Moreover, since X and Y are monotones, the words Y ∞ is completely determined by X and can be constructed iteratively as follows: At each step, we move upward (resp. in the right direction) to the smallest ordinate (resp. abscissa). Therefore, to keep track of the visited rows and visited columns, it is convenient to construct four sequences V i , H i , p i and q i defined recursively as follows:

Base: (i) V 0 is the set of ordinates where the vertical segments of X start or end;

(ii) H 0 is the set of abscissas where the horizontal segments of X start or end;

(iii) p 0 = 0;

(iv) q 0 = 0; (iii) p i+1 = mex(V i );

Induction step: (i) V i+1 = V i ∪ {mex(V i ), mex(V i ) -p i + max(V i )}; (ii) H i+1 = H i ∪ {mex(H i ), mex(H i ) -q i + max(H i )};
(iv) q i+1 = mex(H i );

Example 1. The path X = N N EN N of Figure 7 yields the sets V 0 = {0, 2, 4} and H 0 = {0, 1}. Moreover, p 0 = q 0 = 0. Table 1 gives the first values of the sequences p i , q i , V i and H i . One can reconstruct the vectors V Y and H Y from Table 1 using the formulas

V Y [i] = p i+1 -p i and H Y [i] = q i+1 -q i . In this example, V Y = (1, 2, 3,
Y ∞ = (E 2 N 1 E 2 N 2 E 2 N 3 E 2 N 2 )(E 2 N 1 E 2 N 2 E 2 N 3 E 2 N 2 ) • • • , implying that Y ∞ has period (1 + 2 + 3 + 2) + (2 + 2 + 2 + 2) = 8 + 8 = 16.
Surprisingly, the study of psc-permutominoes leads naturally to the concept of pseudoperiod. More precisely, let w be some binary word. We say that p is a period of w if w[i] = w[i + p] whenever i and i + p are valid indices. In the same spirit, the number p is called antiperiod of w if w[i] = w[i + p]. This concept has been studied in [START_REF] Blondin Massé | A Fine and Wilfs theorem for pseudoperiods and Justins formula for generalized pseudostandard words[END_REF] where the authors prove an extended version of Fine and Wilf's theorem for two periods within some given word. It is easy to verify that Informally speaking, the word w may be interpreted as follows: If w(j) = u, then the corner at height j in the permutomino is in the upper part XY , while if w(j) = , then the corner at height j is in the lower part X Y . The function w present antiperiodic properties as well: Lemma 2. Let j ≥ 0 be an integer.

(i) If w(j) = , then w(j + |X| N ) = u. (ii) If w(j) = u, then w(j + |X| N ) = .
Proof. It follows directly from Lemma 1, since, at every step, we add and u separated by distance |X| N .

As a consequence, the following statements hold: Lemma 3. Let j ≥ 0 be an integer.

(i) If w(j) = , then w(j + 2|X| N ) = . (ii) If w(j) = u, then w(j + 2|X| N ) = u.
(iii) The word w has antiperiod |X| N .

(iv) The word w has period 2|X| N .

Proof. Follows directly from Lemma 2.

A last observation is useful: Proof. Since w has antiperiod |X| N , if we take any window w of length 2|X| N , then every occurrence of in the first half of w is in correspondence with a u in the second half, while every u is in correspondence with some in the second half, by Lemma 2. Thus the number of 's and u's must be the same.

Clearly, Lemmas 2, 3 and 4 are extended when considering horizontal steps. Using the previously defined tools, we are now ready to prove one of our main results.

Theorem 1. For any given

X = N + (E ∨ N ) * N + , the number 4 |X| N |X| E is a period of Y ∞ .
Remark 1. The period needs not be the minimal one.

Proof. We first prove that the vectors V Y and H Y have periods |X| N and |X| E respectively.

Let j ≥ 0 be an integer. By construction, we have

V Y [j] = p j+1 -p j = mex(V j ) -mex(V j-1 ),
where mex(V j-1 ) and mex(V j ) are two consecutive occurrences of the letter in w. We know from Lemma 3 that the word w has period 2|X| N , so that there are two consecutive occurrences mex(V j-1 ) + 2|X| N and mex(V j ) + 2|X| N of the letter u in w. But Lemma 4 guarantees that the number of 's and u's is the same in any window of length 2|X| N of w, so that there are exactly |X| N -1 occurrences of inbetween, i.e. V Y has period |X| N . Using a similar argument, one shows that H Y has period |X| E , so that the run vector of Y ∞ is

(H Y [0], V Y [0], H Y [1], V Y [1], H Y [2], V Y [2], . . .).
Hence, Y ∞ has period 2|X| N × 2|X| E = 4|X| N |X| E , as desired.

The proof of Theorem 1 gives us a simple recursive way to generate the infinite word Y ∞ :

Y ∞ (i) = ε if i = 0, Y ∞ (i -1) E H Y (i) mod |H Y | N V Y (i) mod |V Y | otherwise. Then Y ∞ is the limit of Y ∞ (i) for i → ∞.
From now on, let X be given, let p be the period of Y ∞ , and let W = Y ∞ [1, . . . , p]. We remark that the previously described algorithm gives us as a corollary a simple way to check if the boundary of X(∞) crosses itself or not. Since Y ∞ is periodic, it is sufficient to check it for at most p steps. Summarizing, concerning pseudo-square parallelogram permutominoes, we may have the following possibilities:

1. the boundary of X(∞) crosses itself. Then by Theorem 1 it crosses itself infinitely many times.

In this case, we may have the two possibilities: (a) we have no pseudo-square parallelogram permutomino (see Fig. 2. the boundary of X(∞) does not cross itself; in this case, it may happen that there are no words Y which are up-compatible with X (see Fig. 7 (a)); otherwise, if there is at least a word Y up-compatible with X, then there are infinitely many such words; assuming that Y is the word having minimal length among these ones, then they have the form W * Y (see Fig. 7 (b), where the black points identify the paths Y, W Y, W 2 Y, . . ., and the white points identify the paths W, W 2 , . . .).

Another remarkable observation is that pseudo-square parallelogram permutominoes are centrosymmetric, i.e. they are fixed by a rotation of angle π. This is the second of our main results: Theorem 2. If XY X Y is the boundary word of a pseudo-square parallelogram permutomino, then X and Y are palindromes.

Proof. As in the proof of Theorem 1, we study independently the vertical and horizontal steps. Therefore, it is sufficient to show that both V Y and H Y are palindromes.

Remark that if X and some prefix Y of Y ∞ yields a psc-permutomino, then there exists some prefix w of w starting with zu and ending with zu, where z is some word on { , u}. We show that z is a palindrome. Also, since w has period 2|X| N and antiperiod |X| N , then w = ( zuz) ω so that zu is a factor of either zuz or uz z

We consider only the case where zu is factor of zuz, the second one being symmetric. The situation is depicted in Figure 10 Let n = |z| -1 and p be the distance between the upper left occurrence of z and the lower occurrence of z. Then z and z have the antiperiod p. Moreover, since z overlaps itself, then q = n + 2 -p is a period of z and z as well. Thus, z admits an antiperiod p and a period q. Also, we know that p = q, since no word admits a number as both a period and an antiperiod.

Assume that z

= z[0]z[1]z[2] • • • z[n]
(the index starts at 0 and ends at n). First, we notice that the letters at positions p -1 and n -(p -1) = q -1 in z are the same. Indeed, z[p -1] = and z[q -1] = z[q -1] = u = (see Figure 10).

Let I = {0, 1, 2, . . . , n} be the set of indices of z and g = gcd(p, q). We claim that for k = 1, 2, . . . , (n + 2)/g -1, we have z[kg -1] = z[n -(kg -1)], i.e. the palindromic property is satisfied for these indices. Note in particular that p and q are both of the form kg -1 for some k, and we have already seen that z[p -1] = z[q -1]. Arguing by contradiction, assume that there exists some k ∈ {1, 2, . . . , (n + 2)/g -1 such that z[kg -1] = z[n -(kg -1)]. By Bezout's Lemma, we know that there exist two positive integers x and y such that either g = xp -yq or g = xq -yp. Without loss of generality, we assume that g = xp -yq, so that p -(kg -1) = g = x p -y q, where is some positive integer. Now, we construct a sequence a i of elements in I defined by a 0 = kg -1 and

a i+1 = a i + p if a i + p ∈ I, a i -q if a i -q ∈ I.
There are two possibilities: either the sequence a i stops when a i + p, a i -q / ∈ I or when it reaches position p -1. But the condition a i + p, a i -q / ∈ I implies a i ∈ {p -1, q -1}. Therefore, using the antiperiod p and the period q, we are able to reach from kg -1 the position p -1 or q -1. By symmetry and using exactly the same antiperiod or period, there exists a path from n -(kg -1) to position p -1 or q -1. This means that z[kg -1] = z[n -(kg -1)], contradicting our previous assumption.

Next, we show that q/g is odd. By contradiction, assume that q/g is even, so that p/g is odd (otherwise, g would not be the greatest common divisor). Let k = q/(2g). Since q/g is even, k is a valid index in I. Also, since

n -(k g -1) = n - q 2g • g -1 = n + p 2 = 2p + q -2 2 = p + q 2g • g -1 = k g -1 + p, one concludes that z[k g -1] = z[n -(k g -1)
], a contradiction. Thus, q/g is odd.

Finally, let j ∈ I. Using the same ideas as above, we construct a path from j to j + g. There are two possible cases: either (i) we reach some position of the form kg -1, therefore proving that z[j] = z[n -j] or (ii) we reach the position j + g, therefore showing that g is either a period or an antiperiod of z. It cannot be a period since g | p and p is an antiperiod. Moreover, it is neither an antiperiod since q/g is odd: this would mean that z[j] = z[j + q], which is impossible since q is a period. Hence, z is a palindrome, as desired, and so is the vector V Y A similar argument shows that H Y is a palindrome as well, so that the whole word Y is itself a palindrome, concluding the proof.

Downward growing direction

Most of the considerations made for the upward growing direction can be easily reformulated for the downward growing direction. Also in this case, for a given word X of the form N + (E ∨ N ) * N + , we can define an infinite word Y ∞ , and every word Y which is down-compatible with X is a prefix of Y ∞ . Moreover, we can write down an algorithm -completely analogous to that presented in the previous section -to recursively build the word Y ∞ . There is also a strict relation between the two words Y ∞ and Y ∞ which is exploited in the next statement. Proposition 6. Let X be a word of the form N + (E ∨ N ) * N + . The following properties hold: i) Y ∞ is obtained from Y ∞ by changing all N steps with S steps (see Fig. 9).

ii) The word Y ∞ is periodic, and its period is a divisor of 4 |X| N |X| E .

iii) If X is up-compatible with Y , then X is down-compatible with the word Y , which is obtained from Y by changing all N steps with S steps (see Fig. 5).

We point out that the converse of iii) does not hold: for instance Figure 5 shows that X = N EN EN is downward compatible with a word Y , while it is not up-compatible with the word Y -obtained from Y by changing all S steps with N steps -and there is no word Y which is up-compatible with X.

Further work

Concerning our former objective of studying permutominoes that tile the plane, there are several interesting problems which remain unsolved and should be better investigated. In the sequel we just mention a few of them. psc-permutominoes. It is worth mentioning that the converse of Theorem 2 does not hold, as one can easily check with the word X = N N N EN N N . Our main goal would be to characterize the palindromic words which determine psc-permutominoes and then possibly enumerate these words according to the length.

One step in this direction follows from an exhaustive experimental investigation of the word X up to length 15, and leads us to the following conjecture, already stated in [START_REF] Frosini | Tiling the plane with permutations[END_REF]:

Conjecture. If the word X is c-exact, then it has odd length.

As an example, we have three c-exact words of length 5, N N EN N (both in the upward growing and in the downward growing directions), N EEEN and N EN EN (only in the downward growing direction). These words seem to share some properties with central words (or cut words), i.e. words admitting two periods such that they miss only one letter so that Fine and Wilf's Theorem applies. Indeed, the first and last author of this paper proved the following theorem in [START_REF] Blondin Massé | A Fine and Wilfs theorem for pseudoperiods and Justins formula for generalized pseudostandard words[END_REF]: Theorem 3. [START_REF] Blondin Massé | A Fine and Wilfs theorem for pseudoperiods and Justins formula for generalized pseudostandard words[END_REF] Let w be a finite word. Let p and q be a periods or antiperiods of w (at least one is an antiperiod). If |w| ≥ p + q, then gcd(p, q) is an antiperiod of w.

It seems reasonable that, once we obtain the characterization of the words X and Y leading to psc-permutominoes, we can tackle their enumeration problem.

Column-convex pseudo-square permutominoes. The problem of studying non convex permutominoes which tile the plane by translation is completely open and difficult to tackle. Also considering a slight relaxation of the convexity constraint, for instance the class of pseudo square column-convex permutominoes, we observe that some basic properties holding for psc-permutominoes do not hold anymore. In Fig. 6, we provide two examples of non convex ps-permutominoes: we notice that the word X of the permutomino (a) is c-exact, and admits a compatible Y both in the downward and in the upward growing direction; on the other side, the word X of the permutomino (b) is not c-exact and all the pseudo square permutominoes where X is one of the components are non convex. So, the psc-permutominoes are properly contained in the class of non convex ps-permutominoes, as expected. It is straightforward to check that an infinite number of words Y compatible with X exist in both cases, since some properties about the period and the antiperiod of Y still hold.

As a first step, it seems possible that some generalization of the results holding for pscpermutominoes can be found (e.g. Propositions 3,[START_REF] Berger | The undecidability of the domino problem[END_REF] Pseudo-hexagon permutominoes. Another challenging and more general problem concerns the study of pseudo-hexagon convex permutominoes; in this case, as established in [START_REF] Brlek | Tilings by translation: enumeration by a rational language approach[END_REF], many of the basic properties of pseudo-square convex polyominoes do not hold so we do not have unicity of the decomposition.

Figure 1 :

 1 Figure 1: A polyomino (a), a column-convex polyomino (b), a convex polyomino (c).

Figure 2 :

 2 Figure 2: (a) a psc-polyomino (with highlighted cells) having only a decomposition of the first type, and the corresponding tiling of the plane; (b) a psc-polyomino having one decomposition of the second type, and the corresponding tile of the plane.

2 .

 2 P sc-polyominoes which are not parallelogram. In this case, we can have at most two decompositions which are strictly related to each other: (a) the first one is such that the path X of the decomposition starts from the lowest point in the leftmost column and ends in the leftmost point in the uppermost row (see Figure 3 (a)), then it has the form N + (E ∨ N ) * N + . The starting point of such decomposition is denoted by A; we observe that also parallelogram polyominoes have this kind of decomposition; (b) the second one is such that the path X starts from the uppermost point in the leftmost column and ends in the rightmost point in the uppermost row, (see Figure 3 (b), (c)). The starting point of such decomposition is called B.

  (b), (c) depict two psc-polyominoes having downward growing direction.

Figure 3 :

 3 Figure 3: (a) a psp-polyomino and its unique decomposition; in (b), (c) a non parallelogram psc-polyomino admitting decompositions of the first and of the second type; the starting points are A and B, respectively.

Figure 4 :

 4 Figure 4: A permutomino and the two associated permutations. The dotted black vertices represent the elements of P1, while the circled vertices the elements of P2.

Figure 5 :

 5 Figure 5: Three psc-permutominoes obtained from the same word X = N N EN N . The permutomino in (a) has an upward growing direction, and it is a psp-permutomino, while those in (b) and (c) have a downward growing direction.

Figure 6 :

 6 Figure 6: Two non convex ps-permutominoes obtained from the c-exact word X = N N EN N , (a), and from the word X = N N N EN N N , (b), that is non c-exact.

Figure 7 :

 7 Figure 7: The path X(∞) does not cross itself: (a) we have no pseudo-square parallelogram permutomino; (b) there is a word Y of length less than the period W of Y∞ such that X is up-compatible with Y , and we have a pseudo-square parallelogram permutomino.

Lemma 4 .

 4 Let w be a factor of length 2|X| N of w. Then |w | = |w | u = |X| N .

  8 (a)); (b) there is a prefix Y of W which is up-compatible with X, and we have a pseudo-square parallelogram permutomino (see Fig. 8 (b)).

Figure 8 :

 8 Figure 8: The path X(∞) crosses itself: (a) there is no pseudo-square parallelogram permutomino; (b) there is a word Y of length less than the period W of Y ∞ such that X is up-compatible with Y , and we have a pseudo-square parallelogram permutomino.

Figure 9 :

 9 Figure 9: (a) the path Y∞: there is no word Y which is up-compatible with X; (b) a prefix Y of the path Y ∞ which is down-compatible with X.

Figure 10 :

 10 Figure 10: The word zu is factor of the word zuz.

if the word w overlaps itself with delay d, then d is a period of w. Similarly, if w overlaps with w with delay d, then d is an antiperiod of w.

The sequences V i and H i satisfy the following properties:

Lemma 1. Let i ≥ 1 be an integer.

(iii) and (iv) are proved similarly.

Roughly speaking, at each iteration, we add two new elements mex(V i ) and mex(V i ) -p i + max(V i ) and Lemma 1 states that those elements are apart by distance |X| N . The idea is the same for the horizontal steps. Therefore, it is useful to define auxiliary objects that keep track of which element is obtained from mex(V i ) and which is obtained from mex(V i ) -p i + max(V i ). For every natural j, let f (j) = 0 if j ∈ V 0 , otherwise let f (j) be the integer such that j ∈ V f (j) but j / ∈ V f (j)-1 . Clearly, f (j) has exactly two preimages whenever j = 0. Moreover, for every integer j ≥ 0, we set w(j) = if j = 0 or j = min(f -1 (f (j))), u if j ∈ V 0 -{0} or j = max(f -1 (f (j))),


Laurent Vuillon
email: laurent.vuillon@univ-savoie.fr

2L-CONVEX POLYOMINOES: GEOMETRICAL ASPECTS

Keywords: Mathematics Subject Classification. (Missing.) Key words and phrases. Discrete geometry, convex polyominoes, discrete tomography

A polyomino P is called 2L-convex if for every two cells there exists a monotone path included in P with at most two changes of direction. This paper studies the geometrical aspects of a sub-class of 2L-convex polyominoes called 0,0 2L and states a characterization of it in terms of monotone paths. In a second part, four geometries are introduced and the tomographical point of view is investigated using the switching components (that is, the elements of this sub-class that have the same projections). Finally, some unicity results are given for the reconstruction of these polyominoes according to their projections.

Introduction

There are many notions of discrete convexity of polyominoes (namely HV -convex [START_REF] Barcucci | Reconstructing convex polyominoes from horizontal and vertical projections[END_REF], Q-convex [START_REF] Brunetti | An algorithm reconstructing convex lattice sets[END_REF], L-convex polyominoes [START_REF] Castiglione | A reconstruction algorithm for L-convex polyominoes[END_REF]) and each one leads to interesting studies. One natural notion of convexity on the discrete plane is the class of HV -convex polyominoes that is polyominoes with consecutive cells in rows and columns. Following the works of Del Lungo, Nivat, Barcucci, and Pinzani [START_REF] Barcucci | Reconstructing convex polyominoes from horizontal and vertical projections[END_REF] we are able using discrete tomography to reconstruct polyominoes that are HV -convex according to their horizontal and vertical projections. In addition to that, for an HV -convex polyomino P every pair of cells of P can be reached using a path included in P with only two kinds of unit steps (such a path is called monotone). A polyomino is called kL-convex if for every two cells we find a monotone path with at most k changes of direction. Obviously a kL-convex polyomino is an HVconvex polyomino. Thus, the set of kL-convex polyominoes for k ∈ N forms a hierarchy of HV -convex polyominoes according to the number of changes of direction of monotone paths. This notion of L-convex polyominoes has been introduced by Castiglione and Restivo [START_REF] Castiglione | Reconstruction of L-convex polyominoes[END_REF] and their geometrical structure and tomographical reconstruction are well known. In fact 2L-convex polymoninoes are more geometrically complex and there is no result for their direct reconstruction. We could notice that Duchi, Rinaldi, and Del Lungo are able to enumerate this class in an interesting and technical article [START_REF] Duchi | The number of Z-convex polyominoes[END_REF].

But the enumeration technique gives no idea for the tomographical reconstruction. In this paper, we study the geometrical aspects of a sub-class of 2L-convex polyominoes called 0,0 2L and we state a characterization of it in terms of monotone paths. In a second part, we introduce 4 geometries of this sub-class and we investigate the switching components (that is the elements of this sub-class that have the same projections) and we give also some unicity results.

This paper is divided into 6 sections. After basics on polyominoes, Section 3 gives the geometrical properties and the characterization of a sub-class of 2L-convex polyominoes. In Section 4, the possible configurations of polyominoes in the class 0,0 2L are investigated using switching components made of 1-cycle or 2-cycles. We also focus on the unicity results for this class of polyominoes. All the cases are summarized in a table at the end of this section. Section 5 has a look to directed sets of 2L convex polyominoes. The last section is about the final comments.

Definition and notation

A planar discrete set is a finite subset of the integer lattice N 2 defined up to translation. A discrete set can be represented either by a set of cells, i.e. unitary squares of the cartesian plane, or by a binary matrix, where the 1's determine the cells of the set (see Figure 1).

A polyomino P is a finite connected set of adjacent cells, defined up to translation, in the cartesian plane. A polyomino is said to be columnconvex (resp. row-convex ) if every column (resp. row) is connected (see [START_REF] Delest | Algebraic language and polyominoes enumerations[END_REF][START_REF] Klarner | Some results concerning polyominoes[END_REF]). Finally, a polyomino is said to be convex (or HV -convex) if it is both column and row-convex (see Figure 2). To each discrete set S, represented as a m × n binary matrix, we associate two integer vectors H = (h 1 , ..., h m ) and V = (v 1 , ..., v n ) such that for each 1 ≤ i ≤ m, 1 ≤ j ≤ n, h i and v j are the number of cells of S (elements 1 of the matrix) which lie on row i and column j, respectively. The vectors H and V are called the 2L-convex Tawbevuillon.tex horizontal and vertical projections of S, respectively (see Figure 3). By convention, the origine of the matrix (that is the cell with coordinates (1, 1)) is in the upper left position. For any two cells A and B in a polyomino P , a path AB , from A to B, is a sequence (i 1 , j 1 ), (i 2 , j 2 ), ..., (i r , j r ) of adjacent disjoint cells of P , with A = (i 1 , j 1 ), and B = (i r , j r ). For each 1 ≤ k ≤ r -1, we say that the two consecutive cells (i k , j k ), (i k+1 , j k+1 ) form:

• an east step if i k+1 = i k and j k+1 = j k + 1; • a north step if i k+1 = i k -1 and j k+1 = j k ; • a west step if i k+1 = i k and j k+1 = j k -1; and
• a south step if i k+1 = i k + 1 and j k+1 = j k . Finally, we define a path to be monotone if it is entirely made of only two of the four types of steps defined above.

Proposition 1 (Castiglione,Restivo [4]). A polyomino P is convex if and only if every pair of cells is connected by a monotone path.

Let us consider a polyomino P . A path in P has a change of direction in the cell (i k , j k ), for 2 ≤ k ≤ r -1, if

i k = i k-1 ⇐⇒ j k+1 = j k . Definition 1.
A convex polyomino such that every pair of its cells can be connected by a monotone path with at most k changes of direction is called kL-convex.

In [START_REF] Castiglione | Reconstruction of L-convex polyominoes[END_REF][START_REF] Castiglione | A tomographical characterization of L-convex polyominoes[END_REF], it is proposed a hierarchy on convex polyominoes based on the number of changes of direction in the paths connecting any two cells of the polyomino.

For k = 1, we have the first level of hierarchy, i.e. the class of 1-convex polyominoes, also denoted L-convex polyominoes for the typical shape of each path having at most one single change of direction. In the present studies we focus our attention to the next level of the hierarchy, i.e. the class of 2L-convex polyominoes, whose tomographical properties turn out to be more interesting and substantially harder to be investigated than those of L-convex polyominoes (see Figure 4).

Geometrical properties of 2L-convex polyominoes

In this section, we study the geometrical properties of 2L-convex polyominoes in terms of positions of the feet. Let (H, V ) be two vectors of projections and let P be a convex polyomino, that satisfies (H, V ). By a classical argument P is contained in a rectangle R of size m × n (called minimal bounding box). Let [min(S), max(S)] ([min(E), max(E)], [min(N ), max(N )], [min(W ), max(W )]) be the intersection of P 's boundary on the lower (right, upper, left) side of R (see [START_REF] Barcucci | Reconstructing convex polyominoes from horizontal and vertical projections[END_REF]). By abuse of notation, for each 1 ≤ i ≤ m and 1 ≤ j ≤ n, we call min(S) [resp. min(E), min(N ), min(W )] the cell at the position (m, min(S)) [resp. (min(E), n), (1, min(N )), (min(W ), 1)] and max(S) [resp. max(E), max(N ), max(W )] the cell at the position (m, max(S)) [resp. (max(E), n), (1, max(N )), (max(W ), 1)] (see Figure 5). Definition 3. Let P be a convex polyomino, we say that P is h-centered [resp. v-centered], if its W -foot and E-foot [resp. N -foot and S-foot] intersect (see Figure 6), (they are defined in [START_REF] Chrobak | Reconstructing hv-convex polyominoes from orthogonal projections[END_REF]). The following property links h-centered and v-centered polyominoes to 2L-convex polyominoes.

Proposition 2. If P is an h-centered polyomino or a v-centered polyomino, then it is a 2L-convex polyomino.

Proof. Let us assume that P is h-centered, the W -foot and the E-foot intersect in a row i. The row i is used to go from any point of P to any other point of P. Thus there is at most two changes of direction. That is P is a 2L-convex polyomino. If P is v-centered a similar reasoning holds.

From now on, we suppose that P is not h-centered, v-centered and Lconvex polyomino. Let C be the class of convex polyominoes, thus we have Let us define the horizontal transformation (symmetry)

S H : (i, j) -→ (m -i + 1, j)
which transforms the polyomino P from the class to the class . Note that S H maps to and γ to γ and obviously by involution to and γ to γ. Indeed the transformation acts on the feet of the polyomino as it is shown in the following table (see Figure 7). Thus we only give the proofs of the classes and γ. The classes γ and γ lead to 2L-convex polyominoes.

N, S W, E S -→ N N -→ S min -→ min max -→ max W -→ W E -→ E ≤ ⇐⇒ ≥ min -→ max max -→ min
Proposition 3. If P is a convex polyomino in γ, then it is a 2L-convex polyomino.
Proof. By convexity, there exists an L-path between min(W ) and min(N ), an L-path between max(W ) and min(S), an L-path between max(S) and max(E) and, an L-path between min(E) and max(N ). One can deduce that any two points belonging to P can be connected by a path having at most two changes of direction, hence P is 2L-convex polyomino (see Figure 8). Proposition 4. If P is a convex polyomino in γ , then it is a 2L-convex polyomino (see Figure 9). Proof. Same arguments as of the class γ up to the symmetry S H .

The study of the classes and is more difficult and technical. We make the choice of studying a special case called 0,0 where the upper left corner and the lower right corner of the polyomino is empty. For this case, we introduce 4 geometries in order to describe the geometries of 2L-convex polyominoes in the class 0,0 and to give characterizations of such 2L-convex polyominoes in terms of paths. ,

where P is a 2L-convex polyomino (see Figure 10). Note that the horizontal symmetry S H maps 0,0 2L to 0,0 2L . The following characterizations hold for convex polyominoes in the class 0,0 . Theorem 1. Let P be a convex polyomino in the class 0,0 , P is 2L-convex if and only if there exist four paths

(1) from min(N ) to max(E), (2) from min(N ) to max(S), (3) from min(W ) to max(E), and (4) from min(W ) to max(S). having at most two changes of direction.

Proof.

(=⇒) It is an immediate consequence of the definition of 2L-convex polyomino.

(⇐=) Suppose that P is not 2L-convex, then there exist two points (i 0 , j 0 ), (i 1 , j 1 ) such that any path between them has more than two changes of direction. The worst case occurs when the two points are situated on two distinct feet. We make the proof for the feet N and E (the other cases are similar). Assume that (i 0 , j 0 ) is at the position (1, min(N ) ≤ j 0 ≤ max(N )) and (i 1 , j 1 ) is at the position (min(E) ≤ i 1 ≤ max(E), n). We have the two following cases.

Case 1:

If the path from min(N ) to max(E) has one change of direction, i.e. there exists an L-path between them, then by convexity there is an L-path between (i 0 , j 0 ) and (i 1 , j 1 ), hence the contradiction. Case 2:

If the path from min(N ) to max(E) has two changes of direction, one can observe the following cases.

• Either the path goes through min(E) and then there exist an Lpath between min(N ) and min(E), thus by convexity there exists a 2L-path from (i 0 , j 0 ) to (i 1 , j 1 ), hence the contradiction; or • the path goes through max(N ) and then there is an L-path between max(N ) and max(E), thus there exists a 2L-path from (i 0 , j 0 ) to (i 1 , j 1 ), hence the contradiction (see Figure 11).

The proofs for ( 2), (3), and ( 4) are similar up to symmetry. (⇐=) Suppose that P satisfies only the first geometry, i.e., there exist Lpaths from max(N ) to max(E) and from max(W ) to max(S). From the first L-path one can deduce that there exists a 2L-path from min(N ) to max(E). From the second L-path one can deduce that there exists a 2Lpath from min(W ) to max(S). Now by convexity, there exists an L-path between max(W ) and min(N ) hence, there exists a 2L-path from min(N ) and max(S). Similarly, by convexity there exists an L-path between min(W ) and max(N ) hence, there exists a 2L-path from min(W ) to max(E). To summarize, all four paths in Theorem 1 are in P and hence P is 2L-convex. Similar reasoning holds for the geometries (2), (3), and (4).

(=⇒) P is 2L-convex polyomino then, there exist 2L-paths from min(W ) to max(E), and from min(N ) to max(S). Now suppose that the four minimal geometries in Figure 12 are not satisfied. Then we have the following possibilities.

Case 1:

There exist L-paths from min(N ) to max(E) and from max(W ) to min(S). From the first L-path, one can deduce that there exists an L-path between min(N ) and min(E). From the second L-path, one can see that there is no information between min(W ) and max(S), hence P is not 2L-convex polyomino.

Case 2:

There exist L-paths from min(W ) to max(S) and from max(N ) to min(E).

From the first L-path, one can deduce that there is an L-path between min(W ) and min(S). From the second L-path, one can see that there is no information between min(N ) and max(E), hence P is not 2L-convex polyomino.

In conclusion, the four geometries are necessary to characterize a 2Lconvex polyomino in the class 0,0 . In Figure 13, X represents the position of a point not belonging to the discrete set. The two configurations are called switching components.

Definition 5. We call 2-switching chain (2-cycles), the switching structures which are obtained by composing 2 elementary switchings such that the lower-rightmost point of the first one coincides with the upper-leftmost point of the second one.

We represent the 2-switching chain with the sequence of its 6 points, starting from the upper-leftmost one, then leading right till the next one, and then following the ideal straight lines connecting all the other couples of them. The switching in the Figure 14 is a 2-switching chain represented by the sequence of the six points (1, 2), (1, 4), [START_REF] Chrobak | Reconstructing hv-convex polyominoes from orthogonal projections[END_REF][START_REF] Castiglione | Reconstruction of L-convex polyominoes[END_REF], [START_REF] Chrobak | Reconstructing hv-convex polyominoes from orthogonal projections[END_REF][START_REF] Chrobak | Reconstructing hv-convex polyominoes from orthogonal projections[END_REF], [START_REF] Castiglione | Reconstruction of L-convex polyominoes[END_REF][START_REF] Chrobak | Reconstructing hv-convex polyominoes from orthogonal projections[END_REF], [START_REF] Castiglione | Reconstruction of L-convex polyominoes[END_REF][START_REF] Brunetti | An algorithm reconstructing convex lattice sets[END_REF]. Notice that two consecutive points share a row or a column. Proposition 5. Any 2L-convex polyominoes cannot contain any n-switching chain, with n ≥ 3.

Proof. Let us proceed by contradiction assuming that there exists a 2Lconvex polyominoes P containing a 3-switching chain, say (i 1 , j 1 ), (i 1 , j 2 ), ..., (i 4 , j 4 ), (i 4 , j 1 ). Let us further suppose that the cells (i 1 , j 1 ) belongs to P , and so it is for the cell (i 3 , j 3 ). An easy check reveals that there does not exist in P a monotone path connecting (i 1 , j 1 ) and (i 3 , j 3 ) and having two changes of direction at most, against the assumption. The same conclusion is obtained if we try to connect the cells (i 1 , j 2 ) and (i 2 , j 3 ) supposing that (i 1 , j 1 ) does not belong to P . Obviously, the same result holds for any n-switching chain, with n ≥ 3. Proposition 6. Let P be a 2L-convex polyomino in the class 0,0 2L , and suppose that P satisfies the first geometry and does not satisfy the geometries 2, 3 and 4 (see Theorem 2); in other words, there is an L-path between max(N ) and max(E), and an L-path between max(W ) and max(S). Then P does not have the configuration

0 1 1 1 0 0 1
Proof. Let us proceed by contradiction assuming that the configuration 0 1 1 1 0 0 1 exists. Since card(ES) = 0, then the position of the lower right 1 is either on max(S) or on max(E). Suppose that the lower right 1 is on max(S), then the upper right 0 is in the column max(S). If the upper right 0 is in the row max(W ), then one can deduce that the L-path between max(W ) and max(S) is violated, hence the contradiction. The upper right 0 can not be in a row between max(W ) and min(W ) because of the definition of 2-cycles. If the upper right 0 is in the row min(W ), then an L-path between min(W ) and min(S) appears, in contradiction with the fact that P satisfies only the first geometry.

Same arguments when the lower right 1 is on max(E).

Proposition 7. Let P be a 2L-convex polyomino in the class 0,0 2L , and suppose that P satisfies the second geometry and does not satisfy the geometries 1, 3 and 4 (see Theorem 2), i.e. there is an L-path between min(N ) and min(E), and an L-path between min(W ) and min(S), then P does not have the configuration 1 0 0 1 1 1 0

Proof. As in above, we proceed by contradiction assuming that the other configuration exists.

Corollary 3. If P is a convex polyomino in the class γ or γ , then P does not contain any configuration of the 2-cycles.

Proof. It is an immediate checking from the definition of the 2-cycles and the positions of the feet.

4.1. 2-Cycles in the class 0,0 2L . In this paragraph, we give the conditions to obtain 2-cycles in the class 0,0 2L . Proposition 8. Let P be a 2L-convex polyomino in the class 0,0 2L such that, P satisfies the third geometry and does not satisfy the geometries 1, 2 and 4. If P has 2-cycles in the class 0,0 2L , then P which is the image of P by the 2-cycles is in the class 0,0 2L and we have the two following cases: (1) If the configuration 1 0 0 1 1 1 0 exists for P, then min(N ) is at the position (1, 2) and max(E) is at the position (m -1, n). Moreover P satisfies the second geometry.

(2) If the configuration 0 1 1 1 0 0 1 exists for P, then min(W ) is at the position (2, 1) and max(S) is at the position (m, n -1). Moreover P satisfies the first geometry.

Proof. Suppose that P has the configuration

1 0 0 1 1 1 0
The upper left 1 of the configuration is on min(W ) and not on min(N ). In fact if the upper left 1 is on min(N ), and since we have an L-path between min(N ) and min(E), then the 0 1 1 of the configuration can not be on the row min(E), or in a row in between max(W ) and min(E), in contradiction with the definition of the 2-switching. Now we have that P is 2L-convex in the class 0,0 2L , thus card(W N ) = 0 and card(ES) = 0, one can deduce that min(N ) is at the position (1, 2), max(E) is at the position (m -1, n), and max(S) is not at the position (m, n -1). In fact if max(S) is at the position (m, n -1) then one can see that max(S) = max(E) in P , and thus P is not in the class 0,0 2L (see section: Directed sets). Now, P has the configuration 0 1 1 1 0 0 1 in the class 0,0 2L , then the lower right 1 of the configuration is on max(S), the L-path between min(N ) and min(E) still exists and P is 2L-convex, one can deduce that there exists a L-path between min(W ) and min(E). Hence P satisfies the second geometry (see Figure 15).

Similar reasoning holds if P has the other configuration. Proposition 9. Let P be a 2L-convex polyomino in the class 0,0 2L such that, P satisfies the fourth geometry and does not satisfy the geometries 1, 2 and 3 (see Theorem 2). If P has 2-cycles in the class 0,0 2L , then P is in the class 0,0 2L and we have the two following cases:

(1) If the configuration

1 0 0 1 1 1 0
exists for P, then min(W ) is at the position (2, 1) and max(S) is at the position (m, n -1). Moreover P satisfies the second geometry.

(2) If the configuration 0 1 1 1 0 0 1 exists for P, then min(N ) is at the position (1, 2) and max(E), i.e. the m -1 row and the n column, and min(N ) is not at the position (1, 2). Moreover P satisfies the first geometry.

Proof. Similar to the above proof.

4.2.

Conditions of the two kinds of the simple configurations and relation with the 2-cycles in the class 0,0 2L .

Proposition 10. Let P be a 2L-convex polyomino in the class 0,0 2L , and suppose that P has the two kinds of the simple configurations, then P verifies all four geometries and if P has the simple configuration 1 0 0 1 then min(N ) = max(N ) and min(S) = max(S), or min(W ) = max(W ) and min(E) = max(E).

Proof. Suppose that P has the simple configuration 0 1 1 0 By construction, the upper left 0 is situated at the position where I min = min(W ) -1 and J min = min(N ) -1. The lower right 0 is situated at the position where I max = max(E)+1 and J max = max(S)+1. Thus this simple configuration gives the following rectangle: One can deduce the following cases J min < min(N ) ≤ max(N ) < J max ; J min < min(S) ≤ max(S) < J max ; I min < min(W ) ≤ max(W ) < I max ; and

I min < min(E) ≤ max(E) < I max .
Thus there exists an L-path between min(N ) and max(E), an L-path between min(W ) and max(S), hence we have the four geometries. Now suppose that the simple configuration 1 0 0 1 exists and that the upper left 1 is on min(W ). Since card(ES) = 0, then the lower right 1 is on max(E). Suppose that min(W ) = max(W ), then there exists a cell between min(W ) and max(W ) such that to obtain the configuration, P must be h-centered. Hence the contradiction. If the upper left 1 is on min(N ), then the lower right 1 is on max(S). Suppose that min(N ) = max(N ), then there exists a cell between them such that to obtain the configuration, P has to be v-centered. Hence the contradiction (see Figure 16). Proposition 11. Let P be a 2L-convex polyomino in the calss 0,0 2L , and suppose that P has the two kinds of the simple configurations, then the two configurations below do not exist and so P has no 2-cycles 0 1 1 1 0 0 1 and

1 0 0 1 1 1 0
Proof. Suppose that P has the simple configuration 0 1 1 0 and min(W ) = max(W ) and min(N ) = max(N ) so that the other simple configuration does not exist. Let us proceeding by contradiction assuming that the two configurations exist. First we begin with the configuration

0 1 1 1 0 0 1
The lower right 1 is on max(S) or max(E). If the lower right 1 is on max(S), then the upper right 0 is at the position where i < I min and j = max(S), and the upper left 1 in the middle of the configuration is at the position where i < I min and j ≤ J min , thus card(WN) ≥ 1, hence the contradiction. Now suppose that the lower right 1 is on max(E), then the position of the upper left 1 in the middle of the configuration is in (1, min(W )), in contradiction with the fact that P is not h-centered.

Same arguments hold for the other simple configuration.

4.3. Table of intersections and uniqueness of the class 0,0 2L . In this paragraph we give the table of intersections of the four geometries and the uniqueness of the class 0,0 2L .

Proposition 12. Let P be a 2L-convex polyomino in the class 0,0 2L , then we have the following facts

(1) if P satisfies the first and the second geometries, then it satifies all four geometries and then P does not contain any configuration of the 2-switching chain.

(2) if P satisfies the third and the fourth geometries, then it satisfies all four geometries and then P does not contain any configuration of the 2-switching chain.

(3) if P satisfies the first and the fourth or the first and the third geometries, then P does not have the configuration 0 1 1 1 0 0 1 (4) if P satisfies the second and the fourth or the second and the third geometries, then P does not have the configuration

1 0 0 1 1 1 0
Proof. See Propositions 6 and 7.

Corollary 4. Let P be a 2L-convex polyomino in the class 0,0 2L , if P contains a simple configuration then the polyomino P is always 2L-convex, and P is unique in the class 0,0 2L .

Proof. Let us begin with the simple configuration 1 0 0 1 and suppose that min(W ) = max(W ) and min(E) = max(E), thus the upper left 1 of the configuration is on min(W ) = max(W ) and the lower right 1 is on min(E) = max(E). By applying the configuration, one can deduce that max(N ) < min(S) and min(W ) = max(W ) > min(E) = max(E), and then P belongs to the class γ and P is unique in the class 0,0 2L . By convexity of the class of P , it is a 2L-convex polyomino. Now suppose that min(N ) = max(N ) and min(S) = max(S), thus the upper left 1 is on min(N ) = max(N ) and the lower right 1 is on min(S) = max(S). By applying the configuration, one can deduce that max(W ) < min(E) and min(N ) = max(N ) > min(S) = max(S), then P belongs to the class γ and P is unique in the class 0,0 2L . By convexity of the class of P , it is a 2L-convex polyomino.

If we have min(N ) = max(N ) and min(S) = max(S), min(W ) = max(W ) and min(E) = max(E), then P has min(N ) = max(N ) > min(S) = max(S), min(E) = max(E) > min(W ) = max(W ) and P is unique in the class 0,0 2L . If card(NE) = 0 and card(WS) = 0, then P belongs to the class 0,0 2L and by the transformation S H (see Figure 7), one can deduce that P is 2L-convex. If card(NE) = 0 and card(WS) = 0, it is also 2L-convex (see the form of the configuration).

If we have the other simple configuration 0 1 1 0 then by Proposition 10 and the form of the configuration, P has card(WN) = 1 and card(ES) = 1, thus P is unique in the class 0,0 2L (see Figure 17). This simple configuration does not change the position of the feet and since we have the following rectangle in P

1 1 • • • 1 0 1 1 • • • 1 1 1 1 • • • 1 1 • • • • • • • • • • • • • • • • • • • • • 1 1 • • • 1 1 0 1 • • • 1 1
So one can deduce that P is 2L-convex. Corollary 5. Let P be a 2L-convex polyomino in the class 0,0 2L , if P does not have the conditions of the 2-cycles and if the four geometries are not satisfied, then the polyomino P is unique in the class 0,0 2L . Proof. See Propositions 8, 9, and 10.

We put the previous results of the class 0,0 2L in a table (see Table 1) in order to summarize them.

Remark 1.

(

1) 1 ∩ 2 = 3 ∩ 4 = 1 ∩ 2 ∩ 3 ∩ 4.
(2) The empty cells in the table mean that the unicity in the class 0,0 2L with the geometries (1), ( 2), (3), and (4) is not guaranteed.

(3) By "simple configuration" we mean the two configurations 0 1 1 0 and 1 0 0 1 Proof. See Theorem 1.

Corollary 6. If P satisfies the conditions of Theorem 3, then P is in the class ℘ 0 2L . Theorem 4. Let P be a convex polyomino in the class ℘ 0 , P is 2L-convex if and only if there exists an L-path from max(N ) to max(E) and max(W ) to max(S).

Proof. (=⇒)

We have an L-path between max(N ) and max(E), then there exists a 2L-path from min(N ) to max(E) and from min(W ) to max(E) since min(W ) = min(N ). Similarly, there exists a 2L-path from min(N ) to max(S) and from min(W ) to max(S) since we have an L-path between max(W ) and max(S), using Theorem 5, we get that P is 2L-convex.

(⇐=) Suppose that the L-path between max(N ) and max(E) is not minimal, since P is 2L-convex, then we have the three following possibilities:

(1) There exists an L-path between min(N ) and min(E), one can deduce that P is h-centered. (2) There exists an L-path between min(N ) and max(E), one can deduce that P is v-centered. (3) There exists an L-path between max(N ) and min(E), then there is no information between min(N ) and max(E).

Hence the contradiction. Similarly for the other minimal L.

Corollary 7. If P satisfies the conditions of Theorem 4, then P is in the class ℘ 0 2L .

Let P be a convex polyomino in the class η 0 . Then following characterizations hold Theorem 5. Let P be a convex polyomino in the class η 0 , P is 2L-convex if and only if there exists a 2L-path from (1) min(N ) to max(E) = max(S), ( 2) min(W ) to max(E) = max(S).

Corollary 8. If P satisfies the conditions of Theorem 5, then P is in the class η 0 2L .

Theorem 6. Let P be a convex polyomino in the class η 0 , P is 2L-convex if and only if there exists an L-path from min(N ) to min(E) and min(W ) to min(S).

Corollary 9. If P satisfies the conditions of Theorem 6, then P is in the class η 0 2L .

Theorem 7. If min(N ) = min(W ) and max(S) = max(E), then P is 2Lconvex if and only if P is h-centered or v-centered.

Proof. Suppose that P is not h-centered or v-centered, one can deduce that there is no path from min(N ) = min(W ) to max(S) = max(E) that has at most two changes of direction, hence the contradiction. Note that the transformation S H maps ℘ to ℘ and η to η . To avoid repetitions, one can see that the same characterizations hold for these classes with the following changes.

Final comments

This study is a theoretical step for the reconstruction of the sub-class 0,0 2L . In the spirit of discrete tomography the design of a reconstruction algorithm for such polyominoes would be the subject of a future article. We are also able to develop the material for the whole 2L-convex class with the study of 16 geometries and a reconstruction algorithm for 2L-convex polyominoes in a future article.

Figure 1 .

 1 Figure 1. A finite set of N × N, and its representation in terms of a binary matrix and a set of cells. (The origin of the this figure is in [3]).

Figure 2 .

 2 Figure 2. A column convex (left) and a convex (right) polyomino. (The origin of the this figure is in [5]).

Figure 3 .

 3 Figure 3. A polyomino P with H = (2, 4, 5, 4, 5, 5, 3, 2) and V = (2, 3, 6, 7, 6, 4, 2).

Figure 4 .

 4 Figure 4. The convex polyomino on the left is 2L-convex, while the one on the right is L-convex. For each polyomino, two cells and a monotone path connecting them are shown. (The origin of the this figure is in [3].)

Definition 2 .

 2 The segment [min(S), max(S)] is called the S-foot. Similarly, the segments [min(E), max(E)], [min(N ), max(N )] and [min(W ), max(W )] are called E-foot, N -foot and W -foot.

Figure 5 .

 5 Figure 5. Min and max of the four feet in the rectangle R.

Figure 6 .

 6 Figure 6. A v-centered polyomino on the left and an hcentered polyomino on the right.

  four classes of polyominoes regarding the position of the non-intersecting feet. = {P ∈ C | max(N ) < min(S) and max(W ) < min(E)}, = {P ∈ C | max(S) < min(N ) and max(E) < min(W )}, γ = {P ∈ C | max(N ) < min(S) and max(E) < min(W )}, γ = {P ∈ C | max(S) < min(N ) and max(W ) < min(E)}.

Figure 7 .

 7 Figure 7. The horizontal transformation S H on the feet of P .

Figure 8 .

 8 Figure 8. L's between the feet.

Figure 9 .

 9 Figure 9. L's between the feet. For a bounding rectangle R and for a given polyomino P , let us define the following sets WN = {(i, j) ∈ P | i < min(W ) and j < min(N )}, SE = {(i, j) ∈ P | i > max(E) and j > max(S)}, NE = {(i, j) ∈ P | i < min(E) and j > max(N )}, WS = {(i, j) ∈ P | i > max(W ) and j < min(S)}.

Figure 10 .

 10 Figure 10. An element of the class 0,0 2L on the left and one of the class 0,0 2L on the right.

Figure 11 .

 11 Figure 11. L-path and 2L-path between min(N ) and max(E) through max(N ) and min(E).

Corollary 2 .Figure 12 . 4 .Definition 4 .Figure 13 .

 2124413 Figure 12. Geometries in the class 0,0 2L .

Figure 14 .

 14 Figure 14. The two kinds of configurations for 2-cycles and two polyominoes belonging to the class U (H, V ), with H = (2, 4, 5, 4, 4, 2, 1) and V = (2, 3, 5, 5, 5, 2).

Figure 15 .

 15 Figure 15. Third geometry and the 2-cycles in the class 0,0 2L .

Figure 16 .

 16 Figure 16. A simple configuration in the class 0,0 2L .

Figure 17 .

 17 Figure 17. The 2L-convex P in the left and P in the right.

Figure 18 .

 18 Figure 18. 2L-convex polyominoes in the classes ℘ 0 2L (left) and η 0 2L (right). 5.1. Properties of the classes ℘ 0 and η 0 . Let P be a convex polyomino in the class ℘ 0 . Then the following characterizations hold. Theorem 3. Let P be a convex polyomino in the class ℘ 0 , P is 2L-convex if and only if there exists a 2L-path from (1) min(N ) = min(W ) to max(E), (2) min(N ) = min(W ) to max(S).

  The transformation S H allows us to define the following classes℘ = {P ∈ C | min(S) = max(W )}, ℘ 0 = {P ∈ C | min(S) = max(W ) and card(NE) = 0}, η = {P ∈ C | max(N ) = min(E)}, η 0 = {P ∈ C | max(S) = max(E)and card(WS) = 0}; and for a 2L-convex polyomino P , ℘ 2L = {P | min(S) = max(W )}, ℘ 0 2L = {P | min(S) = max(W ) and card(NE) = 0}, η 2L = {P | max(N ) = min(E)}, η 0 2L = {P | max(S) = max(E) and card(WS) = 0}.

. 8 .

 8 Theorem If min(S) = max(W ) and max(N ) = min(E), then P is 2Lconvex if and only if P is h-centered or v-centered.

Table 1 .

 1 Summary of the results of the class 0,0 2L

	Geometry	Simple	1-cycle	Configuration	2-cycles	Unicity 0,0 2L
		configuration
	1	Impossible	Impossible	Possible	Possible
				Proposition 6 Proposition 8,9
	2	Impossible	Impossible	Possible	Possible
				Proposition 7 Proposition 8,9
	3	Impossible	Impossible	Possible	Possible
				Proposition 8	Proposition 8
	4	Impossible	Impossible	Possible	Possible
				Proposition 9	Proposition 9
	1 ∩ 3
	1 ∩ 4	Impossible	Impossible	Possible	Impossible	Yes
	2 ∩ 3			Proposition 12 Proposition 12	Corollary 5
	2 ∩ 4
	1 ∩ 2 ∩ 3 ∩ 4	Possible	Impossible	Impossible	Impossible	Yes
		Proposition 10 Proposition 10 Proposition 11 Proposition 11	Corollary 4

And by "configuration" we mean the two configurations 0 1 1 1 0 0 1 and 1 0 0 1 1 1 0

Remark 2. Note that similar results can be obtained in the class 0,0 , on the basis of the properties of the transformation S H (see Figure 7) with the following changes:

Directed sets

There are four kinds of directed sets. The first one is denoted by ℘ where, the N -foot and the W -foot intersect at the position (min(W ), min(N )), i.e. they share the cell (1, 1) in the polyomino P . The second kind is denoted by η where, the E-foot and the S-foot intersect at the position (max(E), max(S)), i.e. they share the cell (m, n) in the polyomino P . By the horizontal transformation S H (see Figure 7), one can see that there are two other directed sets denoted by ℘ and η . In this section we characterize the structure of the classes ℘ 0 2L and η 0 2L . Their reconstruction would be the goal of a future work. It is important to note that the more general class of HV -convex directed sets iniqueness is well-known from [START_REF] Del Lungo | Polyominoes defined by two vectors[END_REF].

Let us define the following classes


Juan-Pablo Suarez-Coloma

Christine Verdier

Claudia Roncancio

Personalized Temporal Medical Alert System Trend configuration and follow-up

Keywords: time series, trend, alert, fuzzy logic, quality metric, valid time, personalization I

The continuous increasing needs in telemedicine and healthcare, accentuate the need of well-adapted medical alert systems. Such alert systems may be used by a variety of patients and medical actors, and should allow monitoring a wide range of medical variables. This paper proposes Tempas, a personalized temporal alert system. It facilitates customized alert configuration by using linguistic trends. The trend detection algorithm is based on data normalization, time series segmentation, and segment classification. It improves state of the art by treating irregular and regular time series in an appropriate way, thanks to the introduction of an observation variable valid time. Alert detection is enriched with quality and applicability measures. They allow a personalized tuning of the system to help reducing false negatives and false positives alerts.

INTRODUCTION

Alert systems have been largely implemented in different domains as home, car, natural risks surveillance, or medical follow-up. In most cases, alerts are notified when a monitored variable value is out of a predefined range. In medical domain, alerts concern different users and a variety of interests. More automatic and popular alert systems concern drug prescription [START_REF] Phansalkar | A review of human factors principles for the design and implementation of medication safety alerts in clinical information systems[END_REF]. Alert systems detect drug interaction, contraindication, cross allergies, and other drug related events [START_REF] Luo | Electronic Prescribing Systems with Computer Decision Support[END_REF] [3] [START_REF] Kilbridge | Development of the Leapfrog methodology for evaluating hospital implemented inpatient computerized physician order entry systems[END_REF]. Such alert systems are often included in drugs databanks (in France, Claude Bernard's, Vidal's or Thériaque's). More expert alert systems are used in Intensive Care Units (ICUs) [START_REF] Charbonnier | A trend-based alarm system to improve patient monitoring in intensive care units[END_REF] [START_REF] Hunter | Knowledge-Based Event Detection in Complex Time Series Data[END_REF]. These systems are based on the same model: vital parameters monitoring and alert notification when the measured value goes beyond predefined thresholds. Alerts are notified to physicians and nurses. Medical alert systems are mostly used in health professional environments (office or hospital).

Telemedicine tends to a largely and legal development for different and complementary reasons as reducing health costs and improving patients' quality of life. Transferring medical actions towards paramedical professionals or patients themselves become a reality. Context-aware medical alerts measuring trends becomes particularly important in the new private environment where there are no, or few, medical skills. Some already existing systems are dedicated to elderly surveillance (physiological or home sensors). These Alert systems are preconfigured with most often no actions except: on or off position. Systems are activated manually by elderly people themselves each time they feel in danger. A customer service is informed and decisions are taken. This paper presents Tempas, a context-aware alert system based on linguistic trends. Tempas works with different kind of variables, and can be used in all environments (specialized or not) by every kind of users (expert or not). Trends are detected over regular and irregular time series extracted from patient observations. Linguistic trend values are stemmed from fuzzy logic. The application index measures the quality of the trend classification. It is used for alert filtering.

Tempas extends Pas [START_REF] De Arantes | Defining qualitymeasurable medical alerts from incomplete data through fuzzy linguistic variables and modifiers[END_REF], an alert system, based on fuzzy logic and linguistic values, connected to medical and environmental databases. The linguistic values are expressed in natural language such as "low", "normal", and "high". Tempas introduces time management in the system. Linguistic values are used to classify variable evolution such as "decreasing", "stable", and "increasing". Tempas has been implemented and integrated within an ERP solution called Futura, owned by Calystene S.A.

Section II presents a global view of Tempas and focuses on alert configuration. Trend definition and trend detection are explained in detail in section III and section IV, respectively. Section V presents related works on alert systems, time series, and trends. We present our conclusions and perspectives in section VI.

II. TEMPAS

In this section, we present an overview of Tempas and a brief summary of the alert configuration process. Tempas is not an expert system but a decision making help tool. Next sections explain how the user defines trends and how the algorithm detects alerts.

Tempas is a context-aware alert systems based on trend analysis and user personalization. The personalization allows medical actors to create their own alert system by defining:

• The variables to monitor, vital and non-vital parameters, environmental conditions, etc.

• Specific valid value ranges for the monitored variables. This information allows overriding default values if required

• Relevant trends leading to alerts during variable monitoring. For example monitoring increasing trends in body temperature to alert detection.

• Target population, patient or group of patients potentially concerned by the alert. • Alert notification parameters as the users to notify and the notification method.

• The expected alert quality. This is provided by the application index, which expresses how much an alert concerns a patient.

An example of alert definition is the following: "Send an alert to all nurses if a decreasing body temperature trend is detected for patient Johnson". The alert behavior is adapted to the whole context (user, patient, alert itself) e.g. use a range of [36°C -42°C] for body temperature in all alerts, and [37°C -40°C] in alerts created by Dr. Smith. Only the alerts with an AI superior to 0.8 are notified.

Personalization and context-awareness tend to reduce the false negatives and false positives, and to have always relevant alerts. Anyone can use Tempas. No high mathematics or informatics skills are required to create or edit trend alerts. The more the system is used, the highest its quality becomes.

III. TREND DEFINITION

We explain in this section how the user defines linguistic trends. Each linguistic value is stemmed from fuzzy logic. Each fuzzy set represents a linguistic value. Segments are classified in a trend from its slope (angle) and the fuzzy sets. In section IV we explain how to find segments in time series and how to proceed to alert detection. Before be informed by alerts, users need to define how trends can be linguistically classified e.g. "decreasing", "stable", "increasing". A range of angles is specified for each classification set. Tempas provides a fuzzy set generation algorithm to help the user to avoid the tedious task of trapezoidal sets definition. The algorithm requires two input values: the number of sets (the different linguistic values) and a classification tolerance CT. Generated fuzzy sets can be modified by users if needed. Fig. 1 shows the generated sets for different CT and five linguistic values.

The Trapezoidal membership function maps each element from the universe X to a value between 0 and 1. The membership degree (computed from trapezoidal membership function) covers the classification ambiguity. Fig. 2 shows the trapezoidal membership function that computes the AI of a segment. The segment AI is the same as the alert AI. Equation (1) computes the membership degree.

Segment classification is closely related to false positives and false negatives. Users may reduce false positives increasing the AI quality filtering, redefining the number of classification sets, or redefining the CT. In case of false negatives, users may decrease AI, redefine the number of trends, or redefine the CT.

IV. TREND DETECTION

Trend detection in Tempas consists in three steps explained in the next subsections. The normalization process transforms the observation information (measured value and timestamp) into a space between 0 and 1. Segmentation and fusion finds the most important k segments on regular and irregular time series. Finally, segment classification classifies each obtained segment as a linguistic trend.

1) Normalization

Data normalization translates data obtaining values between 0 and 1, allowing using segment slope as unique criteria for its classification. The algorithm uses segment angle, easy human eye understandable, for trend detection. The advantage is to avoid graphic perception problems. Graphically, the slope in Fig. 3 seems to be the same at left and right. Apparently, Unit changing does not affect the trend form. This happens when axis units are well chosen to draw both time series. In fact, the slope (defined as "vertical changing over horizontal changing") changes if unit does. A temperature changing from 37.7 to 38.2 degrees Celsius in an 8 hours period can be presented as a changing from 99.86 to 100.76 degrees Fahrenheit in a 28800 seconds period. Slope is defined as 0.5/8 in the first case and 32.9/28800 in second. Slope is 0.1 in both cases if data are normalized. Tempas normalize data using variable and time ranges obtained from variable context and window length, respectively.

2) Segmentation and fusion

In this step, Tempas gets the observation set, segments the data, and merges until obtaining the k most significant segments. The k value is defined by the user. The segmentation algorithm uses a Piecewise Linear Representation [START_REF] Keogh | Segmenting Time Series: A Survey and Novel Approach[END_REF] and data approximation by linear interpolation for two related reasons. It is easy to understand, thus, users can configure alerts by themselves.

The segmentation algorithm uses a bottom-up approach and a window based approach to deal with real time data streams [START_REF] Petit | An algebric window model for data stream management[END_REF]. A window corresponds to time series containing a Each set represents an ordered linguistic value among: "strongly decreasing", "decreasing", "stable", "increasing", "strongly increasing". patient observation set. The user specifies (1) the period length containing the desired observation set, and (2) the wished number of observations (no). These two parameters are used by the algorithm to create a hybrid window. A hybrid window has two measures, size and length. The window length is a temporal distance between the two extreme points of the observation set. The size is a quantitative measure defined by the number of points of the window. The window size and length do not always correspond to the number of observations and the period length specified by the user. A two-step algorithm uses the window to find the k most representative segments. Each segment is used to calculate one trend.

AI(x) = AI(x) = AI(x) = (1)
The first step is the segmentation. Tempas pass from n points to n-1 or less segments. Tempas uses the observation variable valid time OVVT (how long the variable value is true for trend detection) [START_REF] Jensen | The Consensus Glossary of Temporal Database Concepts -February[END_REF]. OVVT is a segmentation parameter (see Trendability). This parameter let to handle regular and irregular time series differently. Segment fusion comes after time series segmentation.

Trendability is the ability that two consecutive points have to belong to the same trend. If the temporal distance between them is superior to the OVVT, they cannot belong to the same trend. Consequently, it is possible to find non-connected segments after segmentation. Fig. 4 shows two segmentations. One segmentation process (top-right) generates two nonconnected segments. The second segmentation process (bottom-right) generates three connected segments.

An iterative algorithm finds the k most representative segments. Each cycle merges two connected segments into one. The decision is based on the smallest merging cost. Merging cost is a metric for merging two connected segments. It represents the Manhattan distance between the extreme points of two segments. If there is more than one smallest merging cost, the rightmost one is chosen. It is nearest the current time. The algorithm stops when the k segments have been found, or when the smallest merging cost goes over a user defined value. Fig. 5 shows the iterative fusion process until getting two segments.

3) Segment classification

Segment classification is the final step of trend detection. Final Segments are classified using the fuzzy sets generated by the user. Each segment classification returns a linguistic trend value and an AI. Detected trends with an AI over the threshold are notified to users e.g. a segment is classified as "stable" and "increasing" with a membership degree of 0.4 and 0.6, respectively. If threshold defined by the user is inferior or equal to 0.6, then, the system sends an increasing trend notification.

V. RELATED WORK Medical alert systems are often preconfigured alerts. The main problem is that users lose interest in these types of alert systems because: they produce many false positives, false negatives, not well targeted alerts, or useless alerts [START_REF] Iskio | Improving Acceptance of Computerized Prescribing Alerts in Ambulatory Care[END_REF][12] [START_REF] Van Der Sijs | Review Paper: Overriding of Drug Safety Alerts in Computerized Physician Order Entry[END_REF]. For this reason, alert systems are not well accepted in clinical information systems [START_REF] Phansalkar | A review of human factors principles for the design and implementation of medication safety alerts in clinical information systems[END_REF]. Time-series are multidisciplinary and produces huge amounts of data. Many works use dimensionality reduction based on signal treatment [14][15][16] [START_REF] Eamonn | Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases[END_REF]. Charbonnier and Gentil [START_REF] Charbonnier | A trend-based alarm system to improve patient monitoring in intensive care units[END_REF] define three thresholds to detect a trend in a signal. Their values are chosen from normal behavior of monitored variables. Their algorithm uses these thresholds to classify online-detected segments as one of seven temporal shapes. Fuzzy logic on time-series helps to get human understandable results according to context situations [START_REF] Chen | Mining Linguistic Trends from Time Series[END_REF] [19] [START_REF] Udechukwu | Discovering all frequent trends in time series[END_REF]. These works find only one trend on the time series from predefined fuzzy sets. In some cases, fuzzy sets are domain independent. Time warping techniques are used to compare time-series with different time length with the purpose of pattern matching [START_REF] Müller | Dynamic Time Warping[END_REF]. Existing works are domain-dependent. To the best of our knowledge, no other works propose trend and variable information normalization Most online segmentation algorithms use a sliding window approach. The algorithm tries to merge the new segment with the current segment. In case of positive merging, the current segment grows, else, the new segment becomes the current [5] [8]. Other approaches extend from two to three consecutive segments merging [START_REF] Hunter | Deriving Trends in Historical and Real-Time Continuously Sampled Medical Data[END_REF]. Time-series segmentation is achieved by bottom-up techniques [START_REF] Hunter | Knowledge-Based Event Detection in Complex Time Series Data[END_REF]. SWAB is a generic algorithm for time-series segmentation [START_REF] Keogh | An Online Algorithm for Segmenting Time Series[END_REF]. SWAB mix a sliding window approach with a bottom-up approach for online segmentation. Systems express trends using rules over time-series segments e.g. "oxygen interval slope > 0.4 Kilopascal per second".

Papadimitriou, Sun et Faloutsos introduce SPIRIT [START_REF] Papadimitriou | Streaming Pattern Discovery in Multiple Time-Series[END_REF]. SPIRIT monitors multiple streams at same time to found k hidden variables. Each hidden variable corresponds to a summarization of a group of correlated streams. Hidden variables are used to found (forecasting) trends using multiple variables. Forecasting trends are commonly used for anomaly detection [25] [26]. TrendX use trend templates to express expected behaviors (trend) of specific disorders [START_REF] Haimowitz | Managing temporal worlds for medical trend diagnosis[END_REF]. Normal or abnormal behaviors are used for diagnostics. A trend template contains a temporal pattern in multiple variables.

VI. CONCLUSION AND PERSPECTIVES

This paper presented Tempas, a temporal alert system allowing customized variable monitoring. It facilitates alert configuration by using linguistic trends. The system is generic -working with several kind of variables -and can be instantiated in any application domain. Tempas has been implemented in a real ERP solution. Preliminary experiments have been made. A non-expert user was able to create an alert to monitor rising body temperature. He adjusted the application index and the classification tolerance following his common sense. An expert user validated the results. More experiments will be realized in the near future. Automatic validation is not advised given that quality is a subjective value in alert systems. This work introduced a quality index expressing how much an alert concerns a patient. Future work will improve quality information by introducing a trust index metric. This trust index will reflect how much the user can trust the alert. We will investigate the introduction of complex alerts combining trends and simple events (as medicine taking) and simultaneous trends.

Fig. 3 .

 3 Fig. 3. Left graphic uses degrees Celsius for temperature and hours for time. Right one uses degrees Fahrenheit and seconds instead. Body temperature range is [37 °C -42 °C] equivalent to [98.6 °F -107.6 °F], time range is [0 h -60 h] equivalent to [0 s -216000 s].

Fig. 2 .Fig. 1 .

 21 Fig. 2. Trapezoidal membership function

Fig. 4 .

 4 Fig.4. At left, a 4 points time series with a valid time vt1 (square markers) and a valid time vt2 (triangle markers). At the top right, the segmentation uses vt1 and produces 2 non-connected segments. At the bottom right, the segmentation uses a valid time vt2 producing 3 connected segments.

Fig. 5 .

 5 Fig.5. Iteration process. A shadowed row contains the selected two consecutive segments to be merged. At the top left, the merging cost for the segments [0.4, 0.8] and [0.6, 1] is 0.1616 and is the smallest. The system chooses the rightmost one ([0.6, 1]).

ACKNOWLEDGMENT

Many thanks to Mr. Babouchkine and Mr. Dufour (Calystene) for sharing their experiences in health information systems. This work is supported by the ANR project Innoserv.