Nathalie Aubrun

Marie-Pierre Béal

Tree-shifts of finite type

A one-sided (resp. two-sided) shift of finite type of dimension one can be described as the set of infinite (resp. bi-infinite) sequences of consecutive edges in a finite-state automaton. While the conjugacy of shifts of finite type is decidable for one-sided shifts of finite type of dimension one, the result is unknown in the two-sided case.

In this paper, we study the shifts of finite type defined by infinite ranked trees. Indeed, infinite ranked trees have a natural structure of symbolic dynamical systems. We prove a Decomposition Theorem for these tree-shifts, i.e. we show that a conjugacy between two tree-shifts can be broken down into a finite sequence of elementary transformations called in-splittings and in-amalgamations. We prove that the conjugacy problem is decidable for tree-shifts of finite type. This result makes the class of tree-shifts closer to the class of one-sided shifts of sequences than to the class of two-sided ones. Our proof uses the notion of bottom-up tree automata.

Introduction

Sofic shifts are bi-infinite sequences labeling paths in a finite automaton. Shifts of finite type are a particular important subclass of sofic shifts. Two-sided (resp. one-sided) shifts of finite type are bi-infinite (resp. right-infinite) sequences of consecutive edges in a finite-state automaton (see [12, 13.8], [START_REF] Kitchens | Symbolic dynamics[END_REF]). They are well understood in the one-sided case since the conjugacy is decidable for such shifts of finite type [START_REF] Williams | Classification of subshifts of finite type, in Recent advances in topological dynamics[END_REF]. The proof uses the Decomposition Theorem (see for instance [START_REF] Kitchens | Symbolic dynamics[END_REF]). This theorem states that every conjugacy between two one-sided shifts of finite type can be decomposed into a finite sequence of splittings and amalgamations, which are elementary operations on automata presenting the two shifts.

In the two-sided case, the decidability of the conjugacy problem between two shifts of finite type is still an open question. For class of shifts of sequences larger than the class of shifts of finite type, like sofic shifts, the problem is also open [START_REF] Fujiwara | Conjugacy for one-sided sofic systems[END_REF]. In higher dimension, many questions become more difficult. The main reason is that there exists no good representation of multidimensional shifts comparable to finite automata in dimension one. Even if there exists a generalization of finite automata to dimension two, which are called textile systems (see [START_REF] Nasu | Textile Systems for Endomorphisms and Automorphisms of the Shift[END_REF], see also the automata for tiling systems in [START_REF] Coven | The symbolic dynamics of multidimensional tiling systems[END_REF]), results are more complex than in dimension one. The Decomposition Theorem can be extended to two-sided multidimensional shifts of finite type, but an additional operation, called an inversion, is needed (see [START_REF] Johnson | The decomposition theorem for two-dimensional shifts of finite type[END_REF], and also [START_REF] Aso | Conjugacy of Z 2 -subshifts and textile systems[END_REF]).

In this paper, we introduce the notion of shifts of finite type defined on infinite ranked trees, that we call tree-shifts. Indeed, infinite ranked trees have a natural structure of one-sided symbolic systems equipped with several shift transformations. The ith shift transformation applied to a tree gives the subtree rooted at the child number i of the tree. Tree-shifts can be described thanks to top-down or bottom-up tree automata which are used in automata theory for many purposes. Tree automata have applications to logic and game theory (see for instance [START_REF] Thomas | Automata on infinite objects[END_REF], [START_REF] Comon | Tree automata techniques and applications[END_REF], [START_REF]Tree automata and languages[END_REF], and [START_REF] Perrin | Infinite words[END_REF]). The tree automata that we consider here are bottom-up tree automata. They are simpler than Büchi or Muller tree automata since they have all their states final.

We define two elementary operations on tree automata: the in-splitting operation and the in-amalgamation operation. They are very close to those existing on finite (word) automata. In particular two in-amalgamations commute. We prove a Decomposition Theorem for tree-shifts, i.e. we show that a conjugacy between two tree-shifts can be broken down into a finite sequence of in-splittings and in-amalgamations. We then prove that the conjugacy problem is decidable for the class of tree-shifts of finite type. The key of the proof is the commutation property of in-amalgamations. We prove that two tree-shifts of finite type are conjugate if and only if they have a same minimal in-amalgamation. Furthermore, the minimal in-amalgamation of a tree automaton can be computed in a polynomial time in the number of states of the automaton.

The paper is organized as follows. In Section 2 we give basic definitions about tree-shifts and tree automata. We also present the pair graph of a tree automaton and give a polynomial-time algorithm for checking the locality of a deterministic tree automaton. The Decomposition Theorem is proved in Section 3. Our main result, the decidability of the conjugacy, together with an example are given in Section 4. We end the paper with some concluding remarks. A preliminary version of this paper was presented in [START_REF] Aubrun | Decidability of conjugacy of tree-shifts of finite type[END_REF].

2 Shifts, automata and infinite trees

Tree-shifts

We give here some basic definitions from symbolic dynamics which apply to infinite trees. We consider infinite trees whose nodes have a fixed number of children and are labeled in a finite alphabet.

Let Σ = {0, 1, . . , d -1} be a finite alphabet of cardinal d. An infinite tree t over a finite alphabet A is a complete function from Σ * to A. Unless otherwise stated, a tree is an infinite tree. A node of a tree is a word of Σ * . The empty word, that corresponds to the root of the tree, is denoted by ǫ. If x is a node, its children are xi with i ∈ Σ. Let t be a tree and let x be a node, we shall sometimes denote t(x) by t x . A path in a tree t is a sequence (t xn ) n≥0 where x 0 = ε and x n ∈ Σx n-1 for any n ≥ 0.

When Σ is fixed, we denote by T (A) the set of all infinite trees on A, hence the set A Σ * . On this set we have a natural metric. If t, t ′ are two trees, we define the distance d(t, t ′ ) = 1 n+1 , where n is the length of the shortest word x in Σ * such that t x = t ′

x if such a word exists, and d(t, t) = 0. This metric induces a topology equivalent to the usual product topology, where the topology in A is the discrete one. We define the shift transformations σ i for i ∈ Σ from T (A) to itself as follows. If t is a tree, σ i (t) is the tree rooted at the i-th child of t, i.e. σ i (t) x = t ix for any x ∈ Σ * . The set T (A) equipped with these shift transformations is called the full shift of infinite trees over A.

A pattern is a function p : L → A, where L is a finite prefix closed subset1 of Σ * (hence containing the empty word). The set L is called the support of the pattern. The elements of L are called the nodes of the pattern. A block of height n is a pattern with support Σ ≤n-1 , where n is some positive integer, and Σ ≤n denotes the words of length at most n with letters in Σ.

We say that a pattern (resp. a block) p of support L is a pattern of a tree (resp. block of a tree) t if there is a node x ∈ Σ * such that t xy = p y for any y ∈ Σ * . We say that p is a pattern (or block) of t rooted at the node x. If p is not a pattern (or block) of t, one says that t avoids p. If p is a pattern (or block) of some tree of tree-shift X, it is called an allowed pattern (or allowed block ) of X.

We define a tree-shift (or tree-subshift) X of T (A) as the set X F of all trees avoiding each pattern of a set of blocks F. This tree-shift X is closed and for any shift transformation σ i , σ i (X) ⊆ X. A tree-shift of finite type (TSFT) X of T (A) is a set X F of all trees avoiding each block of a finite set of blocks F. The set F is called a set of forbidden blocks of X.

We denote by L(X) the set of allowed blocks of a tree-shift X, and by L n (X) the set of allowed blocks of height n of X. If b is a block of height n with n ≥ 2, we denote by

σ i (b) the block of height n-1 such that σ i (b) x = b ix for x ∈ Σ ≤n-2 .
The block b will be written b = (b ε , σ 0 (b), . . , σ d-1 (b)). A tree shift of finite type X F , where F is a finite set of blocks of height at most 2, is called a Markov tree-shift.

In the sequel, in order to simplify the notations, we restrict us to binary trees (Σ = {0, 1}) but all results extend trivially to the case of trees with d children for any d ≥ 1.

Example 1. In figure 1 is pictured an infinite tree of a tree-shift of finite type X = X F on the binary alphabet {0, 1} defined by a finite set F of forbidden blocks of height 2. The forbidden blocks are those whose label sum is equal to 1 modulus 2.

σ 0 σ 1 Figure 1:
A tree of the tree-shift of finite type X = X F on the alphabet {0, 1}, where F is the set of blocks of height 2 whose label sum is 1 modulus 2.

Example 2. In figure 2 is pictured an infinite tree of a tree-shift on the binary alphabet {a, b}. A block is forbidden if it contains a path with an even number of a between two b. Let A, A ′ be two finite alphabets, X be a tree-shift of T (A) and m be a nonnegative integer. A map Φ : X ⊆ T (A) → T (A ′ ) is called an m-local map (or an m-block map ) if there exists a function φ : L m (X) → A ′ such that, for any x ∈ Σ * , Φ(t) x = φ(b), where b is the block of height m of t rooted at x. The smallest integer m satisfying this property is called the memory of the block map. A block map is a map which is m-local for some nonnegative integer m.

It is known from the Curtis-Lyndon-Hedlund theorem (see [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF]) that block maps are exactly the maps Φ : X → Y which are continuous and commute with all tree-shifts transformations, i.e. such that σ i (Φ(t)) = Φ(σ i (t)) for any t ∈ X and any i ∈ Σ. The image of X by a block map is also a tree-shift. A one-to-one and onto block map from a tree-shift X onto a tree-shift Y has an inverse which is also a block map. It is called a conjugacy from X onto Y . The tree-shifts X and Y are then said conjugate. Let X be a tree-shift on the alphabet A. Let n be a positive integer. The higher block presentation of order n of X is a tree-shift on the alphabet L n (X) defined as follows. It is the set of trees t for which there is a tree t ′ in X such that, for any node x in Σ * , t x is the block of height n of t ′ rooted at x. It is easy to show that a tree-shift is conjugate to any of its higher block presentations.

Tree automata

In this section we consider bottom-up automata for infinite trees where each node has d children.

A computation in such an automaton goes from the infinite branches and moves upward. A tree automaton is here a structure A = (V, A, ∆) where V is a finite set of states (or vertices), A is a finite set of input symbols, and ∆ is a set of transitions of the form (q 0 , . . , q d-1 ), a → q, with q, q i ∈ V , a ∈ A. A transition (q 0 , . . , q d-1 ), a → q is called a transition labeled by a, going out of the d-tuple of states (q 0 , . . , q d-1 ) and coming in the state q. Note that no initial nor final states are specified. This means that all states are both initial and final in the setting of classical tree automata (see for instance [START_REF] Comon | Tree automata techniques and applications[END_REF], [START_REF] Perrin | Infinite words[END_REF]).

Such an automaton is deterministic if for all d-tuple of states (q 0 , . . , q d-1 ) and for all a ∈ A, there is at most one transition (q 0 , . . , q d-1 ), a → q. Then the set of transitions defines a partial function δ from V d × A to V . In that case, the automaton is also denoted by A = (V, A, δ).

A (bottom-up) finite computation of A on a pattern p is a pattern c on the alphabet V such that, for each node x of p, there is a transition (c x0 , . . , c x(d-1) , t x ) → c x ∈ ∆. A pattern p is accepted by A if there is a if there is a finite computation of A on p.

A (bottom-up) computation of A on the infinite tree t is an infinite tree c on V such that, for each node x, there is a transition (c x0 , . . , c x(d-1) , t x ) → c x ∈ ∆. A tree t is accepted by A if there exists a computation of A on t.

The set of infinite trees accepted by A is a tree-shift. It is equal to X F , where F is the set of blocks which are not accepted by A. Indeed, the set of trees accepted by A is clearly included in X F . The converse holds by a compacity argument.

Example 4. The tree-shift of Example 2 is accepted by the tree-automaton with three states q b , q 0 , q 1 whose transitions are the followings.

a : q 1 q 0 q 0 a : q 0 q 1 q 1 a : q 0 q 1 q b a : q 0 q b q 1 a : q 0 q b q b b : q b q b q b b : q b q 0 q b b : q b q b q 0 b : q b q 0 q 0
Let m be a nonnegative integer. An m-local deterministic tree automaton (or an m-definite tree automaton) is a tree automaton A = (V, A, δ) such that whenever t and t ′ are two trees accepted by A with a same block b of height m rooted at the root ε of t and t ′ , for any computation c of A on t and any computation c ′ of A on t ′ , we have c ε = c ′ ε . Hence the memory of height m determines the state reached. We say that the block b focuses in A to the state c ε . A tree automaton is local (or definite) if it is m-local for some nonnegative integer m. Proposition 1. Any tree-shift of finite type is accepted by a deterministic local tree automaton. Conversely any tree-shift accepted by a deterministic local tree automaton is of finite type.

Proof. Let X = X F be a tree-shift of finite type defined by a finite set of forbidden blocks. Without loss of generality, we can assume that F is the set of all forbidden blocks of height m for some integer m ≥ 2. We also assume that the arity d of the trees is 2.

We define a deterministic tree automaton A = (V, A, δ) such that V = L m-1 (X). For p 0 , p 1 ∈ V , a ∈ A, if the block q = (a, p 0 , p 1 ) of height m is an allowed block of X, then δ((p 0 , p 1 ), a) = b, where b is the block of q of height m -1 rooted at the node ε. The partial function δ is undefined otherwise. By construction, the automaton A is deterministic and (m -1)-local. It clearly accepts the tree shift X, which proves the first part of the claim.

Let X be a tree-shift and A = (V, A, δ) an m-local deterministic tree automaton accepting X. We define F as the set of forbidden blocks of height m + 1 of X. One immediately get X ⊆ X F . Suppose now that t ∈ X F . We define a computation c of A on t as follows. For any x ∈ Σ * , we set c x as the state focused in A by the block of height m of t rooted at x. Let b be the block of height m + 1 of t rooted at x. Since t ∈ X F , b is an allowed block of some tree t ′ in X rooted at some at a node y. Let c ′ be the computation of A on t ′ . We have

δ(c ′ y0 , c ′ y1 , t ′ y ) = c ′ y . Since A is m-local, c xi = c ′ yi for 0 ≤ i ≤ 1, t x = t ′ y and c x = c ′ y . It follows that δ(c x0 , c x1 , t x ) = c x .
Hence c is a computation of A of t and t ∈ X, which proves the second part of the claim.

We give below a decision procedure to check whether a deterministic tree automaton is local.

Given a tree automaton A = (V, A, ∆), we define the square automaton of A, denoted by A × A = (V × V, A, ∆ ′ ), as the tree automaton whose transitions are ((p, p ′ ), (q, q ′ )), a → (r, r ′ ) if and only if (p, q), a → r and (p ′ , q ′ ), a → r ′ are transitions of A. A diagonal state of A × A is a state (p, p) for some p ∈ V .

Square automata of finite words (see for instance [17, p. 647]) are used to check properties of pairs of paths. We extend this notion, together with a notion of pair graph, to trees, to check the locality of tree automata. Seidl [START_REF] Seidl | On the finite degree of ambiguity of finite tree automata[END_REF] uses the notion of branch automata to check some properties on tree automata like the degree of ambiguity of finite tree automata. Proposition 2. A deterministic tree automaton is local if and only if there is a computation in its square automaton ending in a non diagonal state.

Proof. By definition of the square tree automaton A × A, the existence of a computation in A × A ending in a state (p, q) with p = q implies the existence of two distinct computations of A on a same tree. Conversely, if there are two distinct computations of A on a same tree t, they differ at some node x ∈ Σ * . Hence we get two computations of the subtree of t rooted at x ending in two distinct states.

In order to check the above property, we define the notion of pair graph of a tree automaton. We give the definition for binary trees. Let A = (V, A, ∆) be a automaton. The

pair graph G = (V G , E G ) of A, where V G ⊆ (V 2 × V 2 ) ∪ V 2 is the set of vertices, E G ⊆ V G × {0, 1} × A × V G
is the set of edges labeled by 0 or 1 and a letter from A. For more convenience, an edge labeled by 1 is noted by a plain arrow -→ and is called a plain edge, and an edge labeled by 0 is noted by a dashed arrow and is called a dashed edge. For each pair of transitions (p, q), a → r and (p ′ , q ′ ), a → r ′ and each pair (s, s ′ ) of states of A, the set of edges E G contains the following edges ((p, p ′ ), (q, q ′ )) a ((r, r ′ ), (s, s ′ )), ((p, p ′ ), (q, q ′ ))

a -→ ((s, s ′ ), (r, r ′ )), ((p, p ′ ), (q, q ′ )) a (r, r ′ ), ((p, p ′ ), (q, q ′ ))

a -→ (r, r ′ ).

The A-labels of the edges of G may be removed in order to reduce the complexity of the graph.

A vertex of G is useful if it has at least one incoming plain edge and at least one incoming dashed edge. We keep the essential part of the pair graph obtained by discarding vertices which are not useful, together with their incoming and outgoing edges. A vertex ((p, q), (r, s)) (resp. (p, q)) of G is called non diagonal if either p = q or r = s (resp. p = q).

It is easy to verify that a vertex ((p, p ′ ), (q, q ′ )) is a vertex of the (essential part of the) pair graph if and only if there are two computations of A on a tree s one ending in p, the other one in p ′ , and there are two computations of A on a tree t one ending in q, the other one in q ′ . Note also that there is an edge ((p, p ′ ), (q, q ′ )) 0 -→ ((r, r ′ ), (s, s ′ )) in the pair graph if and only if there is a letter a and transitions (p, q) a -→ r and (p ′ , q ′ ) a -→ r ′ in A (or transitions (p, q) a -→ s and (p ′ , q ′ ) a -→ s ′ in A). There is an edge ((p, p ′ ), (q, q ′ )) 0 -→ (r, r ′ ) in the pair graph if and only if there is a letter a and transitions (p, q) a -→ r and (p ′ , q ′ ) a -→ r ′ in A. Proposition 3. A deterministic tree automaton A is local if and only if its pair graph contains no non diagonal vertex (r, r ′ ).

Proof. Let G be the pair graph of A. Any vertex ((r, r ′ )(s, s ′ )) is in the pair graph if and only if there are two computations c, c ′ of A on a same tree t such that c ends in r and c ′ ends in r ′ , and there are two computations d, d ′ of A on a same tree t ′ such that d ends in s and d ′ ends in s ′ . Similarly, a vertex (r, r ′ ) is in the pair graph if and only if there are two computations c, c ′ of A on a same tree t such that c ends in r and c ′ ends in r ′ . Now A is not local if and only if there are two computations c (resp. c ′ ) of A on a same tree ending in a state r (resp. ending in a state r ′ = r). This is equivalent to the fact that (r, r ′ ) is a vertex of G by the above remarks.

When A is a deterministic automaton, we have

|V G | = O(|V | 4 ) and |E G | = O(|V | 6
). The essential part of the pair graph can be computed in polynomial time as described below. We call 0-predecessor a predecessor of a vertex by a dashed edge (labeled by 0) and 1-predecessor a predecessor of a vertex by a plain edge (labeled by 1). The notions of 0-sucessors and 1-sucessors are defined similarly. We build a queue of vertices called vertexQueue containing vertices which have to removed from the pair graph. As soon as such a vertex is removed, one also removes its outgoing edges. A pseudo code of the algorithm is described below. Its time complexity is

O(|V G | + |E G |).
Essential(pair graph GA)

1 Let n0(u) be the number of 0-predecessors of the vertex u ∈ VG 2 Let n1(u) be the number of 1-predecessors of the vertex u ∈ VG 3 vertexQueue ← the list of vertices u such that n0(u) = 0 or n1(u) = 0. 4 mark the vertices contained in vertexQueue 5 while vertexQueue is nonempty 6 do remove the vertex u from vertexQueue 7 for all 0-successors v de u 8 do decrement n0(v) As a consequence, it can be checked in O(|V | 6 ) time whether a deterministic tree automaton is local.

9 if n0(v) = 0
Example 5. A part of the pair graph for the tree automaton of Example 4. It contains the non diagonal state (q 1 , q 0 ) hence the tree automaton is not local.

(q 1 , q 0 ), (q 1 , q 0 ) (q 0 , q 1 ), (q 0 , q 1 ) q 0 , q 1

Vertex tree-shifts

In this section we consider a particular case of tree shifts of finite type, called vertex tree-shifts.

A vertex tree-shift is the tree shift accepted by an automaton A = (V, V, ∆) where the transitions have the form (q 0 , q 1 ), q → q. Hence the label of an accepted tree at each node is equal to the corresponding state of the computation. We simplify this setting by saying that a vertex tree-shift is the set of computations of the unlabeled automaton B = (V, Γ) with transitions in V 2 × V denoted by (q 0 , q 1 ) → q. Note that a vertex shift is a Markov shift and is thus of finite type.

Example 6. The tree-shift X of Example 1 is a vertex tree-shift accepted by the automaton A = (V, ∆) with transitions (0, 0) → 0, (1, 1) → 0, (1, 0) → 1 and (0, 1) → 1. These transitions are given in the following table t where (p, q) → t[p, q] is a transition. 0 1 0 0 1 1 1 0 Proposition 4. Any tree-shift of finite type is conjugate to a vertex tree-shift.

Proof. Let X = X F be a tree-shift of finite type defined by a finite set of forbidden blocks of height m + 1 for some nonnegative integer m. Let A = (V, A, δ) be the deterministic m-local automaton defined by V = L m (X) and, for p 0 , p 1 ∈ V, a ∈ A, δ(p 0 , p 1 , a) is the subblock of height m of b = (a, p 0 , p 1 ) rooted at ε when b is an allowed block of height m + 1 of X. The automaton A accepts X. Let Y be the vertex tree-shift made of all computations on A. Note that A has a unique computation on any tree shift of X.

We define an m-block map Φ from X to Y via φ : L m (X) → Y by setting φ(p) = p. The map Φ associates to each tree t of X the unique computation of A on t. The one-block map Ψ from Y to X given by ψ : Y → A with ψ(p) = p ε is the inverse of φ. The tree-shifts X and Y are thus conjugate.

Decomposition Theorem

The Decomposition Theorem for shifts of infinite words states that any conjugacy between shifts of finite type can be decomposed into a finite sequence of splittings and amalgamations (see for instance [START_REF] Kitchens | Symbolic dynamics[END_REF]). In this section, we prove an analogous theorem for infinite trees. The crucial lemma will show that the memory of a block map can be reduced using a notion of (input) splittings on tree automata defined below.

Let X be a tree-shift over the alphabet A. For each letter a, we consider a partition P a of the subset L 2 (X) of blocks of height 2 labeled by a at their root. Let [(a, b, c)] a denotes the partition element in P a that contains the block (a, b, c), emphasing the fact that it is a class of P a . Let P be the partition of L 2 (X) which is the union of all partitions P a . Let Φ : X → P Σ * be the 2-block map defined by φ(a, b, c) = [(a, b, c)] a . We denote by X the tree shift Φ(X). The map Φ is a 2-block conjugacy whose inverse is a 1-block map. We say that Φ is an in-splitting map and that X, and more generally that any shift obtained from X by renaming symbols, is an in-splitting of X. We also say that Φ -1 is an in-amalgamation map and that X is an in-amalgamation of X. When P a is the trivial discrete partition for any letter a (i.e. [(a, b, c)] a = (a, b, c) for any a), Φ is called the complete in-splitting map and X is the complete in-splitting of X.

A 1-block conjugacy whose inverse is also 1-block is called a renaming map. It is just a renaming of symbols.

Theorem 5. Any conjugacy between tree-shifts can be decomposed as a composition of in-splitting maps and in-amalgamation maps. Lemma 6. Let Φ : X → Y be an m-block conjugacy between two tree-shifts with m ≥ 2. Then there is an in-splitting map Ψ 1 from X to X and an (m -1)-block

conjugacy Φ from X onto Y such that Φ = Φ • Ψ 1 .
Proof. Let us assume that A is the alphabet of the tree-shift X and that B is the alphabet of the tree-shift Y . Let φ : L m (X) → B be the block function defining Φ. Let Ψ 1 : X → X be the 2-block conjugacy defined by ψ 1 (a, b, c) = (a, b, c). The map Ψ 1 is a complete in-splitting.

Let f (resp. g, h) be the map from L 2 (X) to A which maps (a, b, c) to a (resp. b, c). Let Φ : X → Y be the (m -1)-block map defined, for any block Lemma 7. Let Φ : X → Y be a 1-block conjugacy between two tree-shifts such that Φ -1 is an m-block map with m ≥ 2. Then there is an in-splitting map Ψ 1 from X to X, an in-splitting map Ψ 2 from Y to Y , and a 1-block conjugacy Φ from X onto Y such that Φ = Ψ -1 2 • Φ • Ψ 1 and Φ -1 is an (m -1)-block map. This makes the following diagram commute.

b of L m-1 ( X), by φ(b) = φ(b ′ ),
X Φ ----→ Y Ψ1     Ψ2 X Φ ----→ Y Proof. Let
Φ = Ψ -1 2 • Φ • Ψ 1 . It remains to check that Φ -1 = Ψ -1 2 • Φ -1 • Ψ 1 is an (m -1)-block map.
That is, we must show that for any tree t in Y , the coordinates in the block b of height m -1 rooted at the node ε of a tree t determines Φ -1 (t) ε . But this follows from the observation that the block of height m -1 of t rooted at ε determines all Ψ -1 2 (t) x0 and all Ψ -1 2 (t) x1 , for any word x ∈ Σ m-1 , and therefore the block of height m at the root ε of Ψ -1 2 (t). Hence, if t ′ = (Φ -1 • Ψ -1 2 )(t), t ′ ε is determined by b. Moreover, the block of height m -1 of t rooted at ε determines also Ψ 1 (t ′ ) ε .

Proof of Theorem 5. Let Φ : X → Y be an n-block conjugacy between two tree-shifts such that φ -1 is an m-block map, with n, m ≥ 1.

By Lemma 6 and Lemma 7, there are in-splitting maps Ψ 1 , . . , Ψ n+m-2 , ∆ 1 , . . , ∆ m-1 , and a renaming map ∆ such that Φ = ∆ -1

1 • ∆ -1 2 • • • • ∆ -1 m-1 • ∆ -1 • Ψ n+m-2 • Ψ 2 • Ψ 1 .
The result follows from the fact that a renaming map is a particular case of an in-splitting map or of in-amalgamation map. The decomposition into in-splitting maps and in-amalgamation maps is illustrated of transitions (p, q) → r or (q, p) → r for all pair of vertices (p, q). Let us assume that this out-degree of is bounded above by some constant k independent of |V |. This implies that the number of transitions is at most k|V | 3 .

We say that two vertices p, q of V are pre-mergeable if p and q have no common incoming transitions, i.e. for any pair (r, s) of vertices, (r, s) → p ∈ ∆ implies (r, s) → q / ∈ ∆, and (r, s) → q ∈ ∆ implies (r, s) → p / ∈ ∆. We call signature of a vertex p the sequence of triples (0, r, s) such that (p, r) → s ∈ ∆ concatenated with the sequence of triples (1, r, s) such that (r, p) → s ∈ ∆. The triples are sorted in lexicographic order. One can merge two vertices p and q if and only if they are pre-mergeable and σ(p) = σ(q).

For each pair (r, s), the number the transitions going out of (r, s) is at most k. Whenever this number is greater than or equal to 2, any pair of states ending such transitions are not pre-mergeable. Thus, one can compute in time O(k 2 |V | 2 ) a table of size |V | 2 giving, for any pair of states (p, q), whether p and q are pre-mergeable or not.

We deduce from this characterization an algorithm for computing the minimal amalgamation of a vertex tree-shift given by an automaton A = (V, ∆). The length of a signature is at most 2k|V |. It follows that the signatures of all vertices may be computed in time O(k|V | 2 ). They may then be lexicographically sorted in time O(k|V | 2 ).

Hence finding (and merging) two vertices which can be merged can be computed in time O(k 2 |V | 2 ). This step being done at most |V | times, the overall complexity for computing the minimal amalgamation is 0(k 2 |V | 3 ).

Theorem 10. Let X 1 and X 2 be two tree-shifts of finite type. It is decidable whether X 1 and X 2 are conjugate.

Proof. By Proposition 4, one may assume that X 1 and X 2 are vertex treeshifts. By Theorem 5, there is a sequence a sequence of in-splittings from X 1 to X followed (up to a relabeling of X) of in-amalgamations from X 1 to X 2 . This case is illustrated in Figure 6. By Proposition 8, there are vertex tree-shifts at the confluence of any two dashed edges of Figure 6. As a consequence, X 1 and X 2 have a common amalgamation and thus the same minimal amalgamation. Conversely, if X 1 and X 2 have the same minimal amalgamation, there is a sequence of in-splitting and in-amalgamation maps from X 1 to X 2 .

We deduce from this result an algorithm for deciding the conjugacy of two tree-shifts of finite type X 1 , X 2 accepted by two deterministic local automata. By Proposition 4, we build two automata

A 1 = (V 1 , ∆ 1 ) and A 2 = (V 2 , ∆ 2 )
accepting the vertex tree-shifts Y 1 , Y 2 such that X 1 and Y 1 (resp. X 2 and Y 2 ) are conjugate. We compute the minimal amalgamations Z 1 and Z 2 of Y 1 and Y 2 respectively in polynomial time. Then X 1 and X 2 are conjugate if and only if Z 1 and Z 2 are the same vertex tree-shift up to a renaming of the vertices. This test can be done in an exponential time only, making the whole time complexity of this procedure exponential.

Example 7. Let X 1 and X 2 be two vertex tree-shifts over the alphabet V = {a, b, c}. The tree-shift X 1 is accepted by A 1 = (V, ∆ 1 ) and the tree-shift X 2 is accepted by A 2 = (V, ∆ 2 ) where ∆ 1 and ∆ 2 are given in the two following

X 1 X 2 X Y Φ 1 Φ 2 Ψ 1 Ψ 2
Figure 6: A sequence of tree in-splittings from X 1 to X is followed (up to a relabeling of X), by a sequence of tree in-amalgamations from X to X 2 . Any edge represents an in-amalgamation. The tree-shifts X 1 and X 2 have the same minimal amalgamation Y .

tables. If t is a table, (p, q) → t[p, q] is a transition. Since the second and third row of ∆ 1 and the second and third column of ∆ 1 are equal, the vertices b and c can be amalgamated. There is an in-amalgamation from A 1 to A 3 = (V 3 , ∆ 3 ) where V 3 = {a, b} and ∆ 3 is given by the following tables.

No more in-amalgamation is possible from A 3 and thus A 3 is minimal. Similarly, the second and third row of ∆ 2 and the second and third column of ∆ 2 are equal, the vertices b and c can be amalgamated. There is an in-amalgamation from A 2 to A 4 = (V 4 , ∆ 4 ) where V 4 = {a, b} and ∆ 4 is given by the following tables.

Finally, relabeling the states of A 4 by exchanging a and b gives A 3 . Hence, X 1 and X 2 have the same minimal amalgamation and are conjugate.

Conclusion

We have shown that it decidable whether two tree-shifts of finite type are conjugate. This result makes the class of tree-shifts of finite type close to the class of one-sided shifts of sequences of dimension one. The Decomposition Theorem that we have proved for tree-shifts of finite type may allow us to define a notion of strong tree-shift equivalence between tree-shifts and to deduce that two tree-shifts of finite type are equivalent if and only if their transition matrices are related by a sequence of simple algebraic matrix conditions. In [START_REF] Béal | Sofic and Almost of Finite Type Tree-Shifts[END_REF], we have started the study of sofic tree-shifts, a class which is larger than tree-shifts of finite type, using tree automata techniques and symbolic dynamic notions similar to the one used for sofic shifts of sequences (see [START_REF] Nasu | Topological conjugacy for sofic systems and extensions of automorphisms of finite subsystems of topological markov shifts[END_REF], [START_REF] Krieger | On sofic systems. I[END_REF], [START_REF]On sofic systems. II[END_REF]).

Figure 2 :

 2 Figure 2: A tree of the tree-shift Y = X F ′ on the alphabet {a, b}, where F ′ is the set of blocks containing a path with an even number of a between two b.

Example 3 .Figure 3 :

 33 Figure 3: A 2-block map Φ : X → Y , where X is the tree-shift of Figure 1 and Y a tree-shift of finite type over the alphabet {a, b, c}. The map Φ is a conjugacy.

Figure 4 :

 4 Figure 4: A part of the pair graph for the tree automaton of Example 4.

  where b ′ is the block of height m defined by b ′ x = f (b x ) for any word x of length at most m -1 of Σ, and b ′ x0 = g(b x ), and b ′ x1 = h(b x ) for any x of length m -1 of Σ. We have Φ = Φ • Ψ 1 .

  us assume that X (resp. Y ) is a tree-shift over the alphabet A (resp. B). Let P a be the partition of the blocks of height 2 rooted by a such that two blocks (a, b, c) and (a, b ′ , c ′ ) belong to the same class if and only ifφ(b) = φ(b ′ ) and φ(c) = φ(c ′ ) where φ : A → B is the block function defining Φ. Let [(a, b, c)] a denotes the class of (a, b, c) in P a . We denote φ(X) by X. Let Ψ 1 : X → X be the 2-block map defined by ψ 1 (a, b, c) = [(a, b, c)] a . Then X is an in-splitting of X.Let B be the alphabet of Y , and Y be the complete in-splitting of Y over the alphabet B 2 = L 2 (Y ). We denote by Ψ 2 the complete in-splitting map from Y to Y .We define a 1-block map Φ from X onto Y by φ[(a, b, c)] a = (φ(a), φ(b), φ(c)). It is consistent by definition of the partition P a . We have

Figure 7 :

 7 Figure 7: A 2-block map Φ : X → Y , where X is the tree-shift of Figure 1 and Y a tree-shift of finite type over the alphabet {a, b, c}. The 2-block map Φ : X 2 → X 1 of Figure 7 is a conjugacy. It is defined by φ(a, a, b) = b, φ(a, b, a) = c, φ(a, a, c) = b, φ(a, c, a) = c, φ(b, b, b) = a, φ(b, b, c) = a, φ(b, c, b) = a, φ(b, c, c) = a, φ(c, a, a) = a.

any prefix of a word of L belongs to L.

in the following diagram.

4 Deciding conjugacy for tree-shifts of finite type

In this section we prove that for the particular case of tree-shifts of finite type, the conjugacy problem is decidable. The key point is that for tree shifts of finite type, the in-amalgamation maps commute. We first consider the case of vertex tree-shifts. We will show the following proposition.

Proposition 8. Suppose X 1 is a vertex tree-shift and X 2 , X 3 are vertex treeshifts obtained from X 1 by in-amalgamations. Then there is a vertex tree-shift X 4 that can be obtained from both X 3 and X 4 by in-amalgamations and such the following diagram commutes.

Figure 5: The commutation of in-amalgamation maps. If X 2 , X 3 are vertex tree-shifts which are in-amalgamations of X 1 , then there is a vertex tree-shift X 4 which is a common amalgamation of X 2 , X 3 .

In Figure 5, the maps Φ and Ψ are in-amalgamation maps. As a consequence of Proposition 8 the maps Ω and Θ are also in-amalgamation maps.

Let X be a vertex tree-shift accepted by an automaton A = (V, ∆) and Φ be an in-splitting map from X to X defined by partitioning the sets ∆ r of transitions coming in p for each vertex r in V . We denote by V the alphabet of X. It is the union of the sets {[(r, p, q)] r , | (p, q) → r ∈ ∆}. The vertices [(r, p, q)] r are called in-splitted (or splitted) vertices of r. One says that the vertices [(r, p, q)] r are amalgamated (or merged) to r. Then X is a vertex tree-shift accepted by the automaton A = ( V , ∆) defined by ([(r, p, q)] r ,

For more convenience, the vertices of ∆ corresponding to a partitioning of ∆ r are denoted r 1 . . , r ℓ(r) . An in-amalgamation of a vertex tree-shift X accepted by A is a vertex tree-shift Y accepted by A such that Y is an in-splitting of X. The vertices r 1 . . , r l(p) of A are amalgamated to the vertex r. Note that whenever (p ′ , q ′ ) → r i ∈ ∆, then (p ′ , q ′ ) → r j / ∈ ∆, for any p ′ , q ′ ∈ V and any 1 ≤ i = j ≤ ℓ(r). This also implies that (r i , p ′ ) → q ′ ∈ ∆ if and only if (r j , p ′ ) → q ′ ∈ ∆, and (p ′ , r i ) → q ′ ∈ ∆ if and only if (p ′ , p j ) → q ′ ∈ ∆ for any vertices p ′ , q ′ ∈ V and any 1 ≤ i, j ≤ ℓ(r). Roughly speaking, if a vertex r is splitted into r 1 . . , r ℓ(r) , the transitions coming in a r are splitted while transitions going out of r are duplicated after the in-splitting.

Proof of Proposition 8. Suppose that X n is the vertex tree-shift accepted by (V n , ∆ n ) for n = 1, 2, 3. We assume that there is an in-amalgamation Φ : X 1 → X 2 and a in-amalgamation Ψ : X 1 → X 3 . Let us assume that vertices p 1 , . . , p ℓ(p) of V 1 are amalgamated to a vertex p of V 2 .

By definition of an in-amalgamation, this implies that if (q ′ , r ′ )

Suppose also that vertices q 1 , . . , q ℓ(q) of V 1 are amalgamated to a vertex q of V 3 . Let us first assume that the vertices p 1 , . . , p ℓ(p) and q 1 , . . , q ℓ(q) are all distinct. We define X 4 as the in-amalgamation of X 2 obtained by amalgamating the vertices p, q 1 , . . , q l(q) to a vertex q. It is also the in-amalgamation of X 3 obtained by amalgamating the vertices q, p 1 , . . , p l(p) to a vertex q.

Let us now assume that p 1 = q 1 , . . , p ℓ = q ℓ for some integer 1 ≤ ℓ ≤ min(ℓ(p), ℓ(q)). This implies that, for any 1 ≤ i ≤ ℓ(p), 1 ≤ j ≤ ℓ(q), one has (p i , q ′ ) → r ∈ ∆ 1 (resp. ∆ 2 ) if and only if (p j , q ′ ) → r ∈ ∆ 1 (resp. ∆ 2 ), and (q ′ , p i ) → r ∈ ∆ 1 (resp. ∆ 2 ) if and only if (q ′ , p j ) → r ∈ ∆ 1 (resp. ∆ 2 ).

We define X 4 as the in-amalgamation of X 2 obtained by amalgamating the vertices p, q l+1 , . . , q l(q) to the vertex p. It is also the in-amalgamation of X 3 obtained by amalgamating the vertices q, p l+1 , . . , p l(p) to a vertex p. Hence, if Φ and Ψ are in-amalgamations, then Ω and Θ also.

The previous theorem allows us to define the notion of minimal (in)-amalgamation of a vertex tree-shift X. It is defined as the vertex tree-shift defined by the smallest automaton (in the number of vertices) which is obtained by in-amalgamations of X.

Corollary 9. Any vertex tree-shift has a unique minimal in-amalgamation.

Proof. Let us assume that X has two minimal amalgamations X 2 and X 3 . By Proposition 8, X 2 and X 3 have a common in-amalgamation Y . By minimality, Y = X 2 = X 3 .

We now describe an algorithm for computing the minimal amalgamation of a vertex tree-shift. Let us assume that X is a vertex tree-shift defined by an n-vertex automaton A = (V, ∆). We call out-degree of A the maximal number


Michel Chilowicz

Etienne Duris

Gilles Roussel

Syntax tree fingerprinting: a foundation for source code similarity detection

Plagiarism detection and clone refactoring in software depend on one common concern: finding similar source chunks across large repositories. However, since code duplication in software is often the result of copy-paste behaviors, only minor modifications are expected between shared codes. On the contrary, in a plagiarism detection context, edits are more extensive and exact matching strategies show their limits.

Among the three main representations used by source code similarity detection tools, namely the linear token sequences, the Abstract Syntax Tree (AST) and the Program Dependency Graph (PDG), we believe that the AST could efficiently support the program analysis and transformations required for the advanced similarity detection process.

In this paper we present a simple and scalable architecture based on syntax tree fingerprinting. Thanks to a study of several hashing strategies reducing false-positive collisions, we propose a framework that efficiently indexes AST representations in a database, that quickly detects exact (w.r.t source code abstraction) clone clusters and that easily retrieves their corresponding ASTs. Our aim is to allow further processing of neighboring exact matches in order to identify the larger approximate matches, dealing with the common modification patterns seen in the intra-project copy-pastes and in the plagiarism cases.

Introduction

Software analysis, maintenance and reengineering could often benefit from performing clone detection, either for software evaluation or for refactoring issues [START_REF] Baker | On finding duplication and near-duplication in large software systems[END_REF][START_REF] Burd | Evaluating clone detection tools for use during preventative maintenance[END_REF][START_REF] Baxter | Dms R : Program transformations for practical scalable software evolution[END_REF][START_REF] Mende | Supporting the growand-prune model in software product lines evolution using clone detection[END_REF]. Several tools address the problem of identifying software clones that come from copy-paste modifications sometimes followed by slight modifications [START_REF] Bellon | Comparison and evaluation of clone detection tools[END_REF][START_REF] Chanchal | Scenario-based comparison of clone detection techniques[END_REF]. A related problem is the detection of software plagiarism, i.e. copies with intentional obfuscations, for instance for license issues or in evaluation of student projects [START_REF] Parker | Computer algorithms for plagiarism detection[END_REF][START_REF] Clough | Plagiarism in natural and programming languages: an overview of current tools and technologies[END_REF]. Even if they could rely on similar transformations, tools addressing this latter issue often require more complex abstraction and processing than for simple clone detection. They also support a loosened association of code chunks [START_REF] Michael | YAP3: improved detection of similarities in computer program and other texts[END_REF][START_REF] Prechelt | Finding plagiarism among a set of programs JPlag[END_REF][START_REF] Moss | [END_REF][START_REF] Chen | Shared information and program plagiarism detection[END_REF].

To bring these two problems together into the general issue of source code similarity detection, the choice of an appropriate representation for the source code is required. Linear representations by (abstracted) token sequences of source code allow the comparison algorithms to be efficient, inspired from text pattern-matching and genomics, but they hide the structural organization of the program. For instance, they might identify clones corresponding to parts of code in between two distinct syntactic blocks, that are often not relevant, e.g. in between functions like return; } public static void. From the point of view of similarity detection, complex obfuscation patterns cannot be dealt with without manipulation of a structured representation like the ASTs. Let us consider the simple example where an operator is known to be commutative, like + in the expressions e 1 = a * b + c/d and e 2 = c/d + a * b: a linear sequence of tokens does not enable the perception of such equivalence (unless abstracting all the operators). Apart from this example, several parameters could be considered for defining an acceptable degree of similarity that could rely on language constructs, type abstractions, operator properties or various thresholds. Thus, richer representations, like the ASTs or the PDGs, permit fine-grained analysis, manipulation and comparison possibilities, even if they often imply more expensive processing.

Beyond the comparison of costs, a key-point of similarity detection tools relies on their scalability. Indeed, the search for common parts of code could be performed inside a huge project (e.g. for refactoring), between two large projects (e.g. for plagiarism litigation), between an important number of projects, or against a database of projects and could concern a large amount of data. This scalability requires not only practical space and time complexities but also the possibility to incrementally store and re-use the processed data. We also expect from a similarity detection tool to retrieve direct clone clusters rather than numerous simple clone pairs that would later be costly to group by a clustering algorithm.

The usual process for clone detection consists in a dedicated process that looks for approximate matches that might yield a large amount of false-positives. Matches have to be further confirmed or discarded. If there is a change in the set of parameters defining an acceptable degree of similarity, this costly process has to be completely redone. Rather, our approach consists in providing an efficient access to exact AST clones (w.r.t representation abstraction), like a * b and c/d, and to their parent nodes, like e 1 and e 2 . Instead of providing a global solution, clones are available to be extended into larger approximate matches through various analysis and transformation plugins.

In this paper, after briefly presenting related works in section 2, we present in section 3 our system of source code matching that allows large-scale software systems to be stored and processed. It first parses each compilation unit and serializes, stores and references its AST in a repository. Next, each node of this AST is associated with a fingerprint based on a hash value (incrementally computed) of the subtree rooted at the node in question allowing parent and children node information to be reached. These fingerprints are indexed and the system permits the retrieval of clusters of exact matches in the database but also looks for clones matching a (part of a) given single query tree. In both cases, the ASTs of detected clones could be retrieved from the repository to discard the possible false-positives but, contrary to existing methods that artificially choose bad hash function to associate a same value for near-miss clones, we prefer syntax tree hashing that avoids collisions, saving us the costly detection of false-positives. Section 4 presents several studied tree fingerprinting methodologies, and evaluates their theoretical efficiency. For a concrete case study, section 5 shows some results of our system for the Java API source code. Prior to the conclusion, we study in section 6 the behavior of our approach on different clone scenarios.

State of the art and issues raised

Bellon et al. propose in [START_REF] Bellon | Comparison and evaluation of clone detection tools[END_REF] an extensive survey of clone detection tools. Roy and Cordy give in [START_REF] Chanchal | Scenario-based comparison of clone detection techniques[END_REF] a short but relevant overview testing existing techniques against several editing scenarios. Thus, instead of an exhaustive presentation of existing tools, we present in this section some characteristics of the four main approaches in order to put our contribution in context.

Metrics based techniques

Metrics like Halstead measures [START_REF] Halstead | Elements of Software Science[END_REF] are widely used in software engineering to quantitatively assess properties on a given project by associating to each chunk of code (package, compilation unit, method, ...) a vector. Unfortunately clone detection techniques based on metrics perform very poorly due to the high sensitivity of most metrics to minor edits and a fortiori to plagiarism cases. Thus nowadays few clone detection tools use pure metrics methods. Nevertheless we can quote Deckard [START_REF] Jiang | Deckard: Scalable and accurate tree-based detection of code clones[END_REF][START_REF] Gabel | Scalable detection of semantic clones[END_REF] that computes degraded hash values for subtrees of an AST applying an LSH-hash function [START_REF] Gionis | Similarity search in high dimensions via hashing[END_REF] on node type-counting metrics.

Token sequence based techniques

After simple string matching techniques (easy defeated by simple formatting edits), token based matching is the first historical approach to deal with source code similarity detection using sequence matching algorithms. As a first step, source code projects are tokenized to provide sequences of tokens that are supplied to string matching algorithms, usually inspired from genomics applications. The tokenized representation is generally abstracted (e.g. identifiers are not distinguished). The chosen algorithm depends on the source comparison context and on the computation capabilities. To extensively compare a single pair of projects represented by two sequences of n tokens, their Levenstein distance may be computed and local alignments [START_REF] Irving | Plagiarism and collusion detection using the Smith-Waterman algorithm[END_REF] are inferred with the time complexity of O(n 2 ) using dynamic programming algorithms. This approach is not scalable either for the comparison of a set of projects (all pairs have to be compared) nor for the search of similarities of a single project against a database of projects. For such contexts, token sequence fingerprinting appears unavoidable. It consists in computing fingerprints of token k-grams that will be inserted in a database (n -k + 1 fingerprints for n tokens). A fingerprint selection strategy (like Winnowing used by the Moss [START_REF] Moss | [END_REF] tool) can be used to divide by a constant the amount of fingerprints kept. The greedy string tiling algorithm [START_REF] Michael | Running karp-rabin matching and greedy string tiling[END_REF] implemented by JPlag [START_REF] Jplag | [END_REF] permits the search of exact matches between two sequences of tokens through increasing k-grams fingerprinting in experimental quasi-linear time, but requires comparison of all of the pairs of projects. Another approach is based on the factorization of the tokenized source code into synthesized functions, allowing for a quantification of similarities at a function-level through call-graph [START_REF] Chilowicz | Finding similarities in source code through factorization[END_REF].

Our system shares some techniques with these approaches, like suffix arrays for sequence matching [START_REF] Manber | Suffix arrays: a new method for on-line string searches[END_REF] or for the incremental fingerprinting processing, like Karp-Rabin [START_REF] Karp | Efficient randomized pattern-matching algorithms[END_REF].

Tree based techniques

In order to exploit the syntactic properties of the programs, another approach considers the syntax trees of compilation units obtained through parsing. Next, an abstracted version of the trees is considered (e.g. abstraction of identifiers, loop constructs...) to achieve a better recall. Similar to the token sequences, edit distances can be computed for each pair of trees [START_REF] Zhang | Simple fast algorithms for the editing distance between trees and related problems[END_REF], but tree fingerprinting allows for a more scalable behavior. This method is widely used by tools advertising themselves as clone retrieval systems, but strangely not by the plagiarism detection tools. Since comparing nm subtrees of m projects of size n (in terms of nodes) for exact equality detection would require O((nm) 2 ) comparisons with a naive approach, all subtrees are rather fingerprinted and put in buckets according to their hash value. To retrieve not only exact subtree matches (considering the level of abstraction of the tree), but also near-miss ones, degraded hash functions are used for fingerprinting (like in CloneDr [START_REF] Baxter | Clone detection using abstract syntax trees[END_REF] where subtrees below a weight level are hashed with a single value). The drawback of this approach is the potential increase of false-positive clones.

Comparatively, our system focuses on exact tree matching retrieval through the use of a good hash function minimizing collisions between false-positives. Quite close to the Koschke et al. approach [START_REF] Koschke | Clone detection using abstract syntax suffix trees[END_REF] that uses suffix tree clone detection on AST node types, our system uses AST node fingerprints that reflect the whole underlying subtree. This provides an efficient clustering mechanism for exact match of sequences of sibling subtrees. Direct access to indexed ASTs allows further analysis and manipulations to extend neighboring matches into larger near-miss similarities.

PDG based techniques

Generating PDGs for source code through program slicing is an interesting semantic approach to detect complex syntactic modifications [START_REF] Horwitz | Interprocedural slicing using dependence graphs[END_REF][START_REF] Komondoor | Using slicing to identify duplication in source code[END_REF][START_REF] Krinke | Identifying similar code with program dependence graphs[END_REF][START_REF] Horwitz | The use of program dependence graphs in software engineering[END_REF]. However, finding isomorphisms between subgraphs is very costly (being a NP-complete problem in general): comparison of large sets of projects implies some compromises. For plagiarism detection, pruning filters may be used to reduce the number of graph pairs to be compared [START_REF] Liu | Gplag: detection of software plagiarism by program dependence graph analysis[END_REF]. We detail in this section the main steps of our source code matches retrieval system, summarized in figure 1.

Parsing the source

Given a compilation unit, we want to produce a syntax tree representation to perform the fingerprinting process. The knowledge of the token definitions and of the context-free grammar of the language handled permits the generation of a lexer and parser with dedicated tools (lexer generators producing a DFA and parser generators allowing linear time syntactic analysis using for example LALR(k) or LR(k) algorithms). To obtain the abstract syntax tree, either a postprocessing of the concrete syntax tree or the integration of customized actions with the grammar specification is needed. Specifying common abstract tree nodes for different languages of the same type (procedural, object, functional...) permits the use of abstract post-processing normalization tools, for instance to remove trivial, useless or unreachable instructions or to allow cross-language plagiarism detection. Once computed, the abstract syntax tree is stored in a repository for further references, e.g. for false-positive checking or match back-tracing during the result reporting. The tree is saved level by level in a customized binary XML representation with a companion index allowing the user to randomly access the nodes and a lazy deserialization: when a node is requested for deserialization its heirs are not automatically deserialized but are done so on demand.

Fingerprinting and indexing syntax trees

Each subtree, from the syntax trees obtained from parsing, is represented with a digest form (a fingerprint). The fingerprint of subtree t is a tuple including its weight w(t) (in fact the size of the subtree), its hash value H(t) reflecting its structural properties computed thanks to a hash function (cf. section 4) and a pointer p(t) to its related subtree root node t and to its parent node. A double index is maintained on the fingerprint database: fingerprints are first sorted according by decreasing weight, then by hash value, and also by parent linked node. We implement these indexes using a B+-k-tree [START_REF] Bayer | Organization and maintenance of large ordered indices[END_REF] (k to 2k arity tree indexing structure adapted for mass storage). Thanks to this structure, it is possible to iterate over the database to retrieve first the most weighted clones and to get all of the fingerprints of children subtrees of a given node. Assuming a linear parsing algorithm and an incremental hashing function for the subtrees (allowing computation of the hash value of a subtree with the knowledge of hash values of its child subtrees in O(1)) the time complexity is limited by the fingerprint indexing process requiring O(n log k n) I/O accesses for a B+-k-tree to index a tree of size n. We study and evaluate several tree fingerprinting methodologies in section 4.

Since we are not interested in finding tiny clones and we want to minimize the size of our database, only fingerprints whose linked subtrees are greater than a weight threshold are kept. Another solution can also be proposed to aggregate sibling subtrees of sub-threshold weight to represent them with a single composed fingerprint.

In addition, in order to spare storage space by discarding the weight field, the database can be distributed in sub-databases containing only fingerprints of subtrees of a given weight. The fingerprint hash lengths can be adapted for the subtree sizes: intuitively, subtrees of greater weight require hash values of greater length to minimize false-positive collisions (cf. section 4).

Retrieving clusters of exact matches

Single subtree exact match clusters

A simple iteration over the fingerprint database enables the retrieval of clusters of exact subtree matches: clusters share the same weight and hash value. However, even if false-positives are relatively improbable (syntactically different subtrees with same weight and hash value, see section 4.1), they must not be ignored. The length of hash values can be increased to reduce the occurrences of false-positives with a detrimental burden on the size of the database.

To discard false-positives in clusters, we examine a fixed number of children fingerprints in a breadth-first exploration, that drastically reduces the collision probability. For instance, considering two subtrees, rooted at nodes α and β with respective children a 1 , . . . , a i and b 1 , . . . , b i . If α and β share the same weight and hash values, we compare the weight and hash values of the children pairs (a 1 , b 1 ), . . . , (a i , b i ). This is easily done through the parent node pointer of the fingerprint that allows, given a node, the retrieval of the fingerprints of its children. This probabilistic approach of false-positive detection does not require the deserialisation of the syntax trees.

Furthermore, an subtree exact matches cluster C of a given weight implies the existence of clusters of smaller weights containing each subtrees of the trees in C. Iterating from greatest weight to smallest weight in the database allows us to discard these sub-matches.

Multi-subtrees exact matches clusters

The fingerprint database structure does not address the problem of finding clusters of sequence of consecutive sibling subtrees (except for small trees through composed fingerprints, cf. 3.2). Basically, this would require fingerprinting all factors of sequences of child nodes and would consequently multiply the size of the database by a factor up to the maximal arity of the tree. To efficiently cope with this problem, we use a suffix tree or a suffix array to index all of the suffixes (and implicitly the factors) of the sequences of child node fingerprints. This approach has already been used on token sequences or tokenized representations of syntax trees (obtained from complete tree depth traversal) [START_REF] Tairas | Phoenix-based clone detection using suffix trees[END_REF], or on AST node types [START_REF] Koschke | Clone detection using abstract syntax suffix trees[END_REF], but not yet on sequences of fingerprints representing sibling subtrees. This allows minimizing the size of handled structures and to syntactically bind matches, contrary to pure token sequences used (e.g. a match cannot contain a large function and stop with the duplicated first statement of the next function: such a match must be split).

Suffix array

Interval tree with suffix-links Given single subtree exact match clusters (cf. section 3.3.1), our algorithm uses a suffix array to compute consecutive multi-subtrees exact matches. First, an array of all of the single subtree nodes contained in an exact match cluster (i.e. subtrees occurring at least twice) is sorted according to the syntax tree links, such that fingerprints of sibling nodes in the syntax tree are adjacent in the sorted array. Next, all of the segments of consecutive sibling subtrees (represented by their cluster, i.e. their equivalence class identifier) are collected to build a generalized suffix array. This suffix array contains all of the suffixes of fingerprint segments sorted such that matching consecutive sibling subtrees are adjacent in the suffix array. We next create an interval tree from the suffix array: this interval tree is homomorph with the generalized suffix tree (without its leaves) that may be built from the fingerprint segments.

Rank Suffix 1 s 1 [1..] = abcdef 2 s 1 [2..] = bcdef 3 s 2 [2..] = bcdeh 4 s 1 [3..] = cdef 5 s 2 [3..] = cdeh 6 s 3 [3..] = cdeh 7 s 1 [4..] = def 8 s 2 [4..] = deh 9 s 3 [4..] = deh 10 s 1 [5..] = ef 11 s 2 [5..] = eh 12 s 3 [5..] = eh 13 s 1 [6..] = f 14 s 2 [1..] = gbcdeh 15 s 2 [6..] = h 16 s 3 [6..] = h 17 s 3 [1..] = ijcdeh 18 s 3 [2..] = jcdeh Clone cluster bcde cde cdeh Members {s 1 [2..5], s 2 [2..5]} {s 1 [3..5], s 2 [3..5], s 3 [3..5]} {s 2 [3..6], s 3 [3..6]}
For instance, let us consider the fingerprint segments s 1 = abcdef , s 2 = gbcdeh and s 3 = ijcdeh: s 1 represents the fact that a, b, c, d, e and f are the fingerprints of six consecutive sibling children of a given node. In the same way as s 2 and s 3 represent other sequences with some shared fingerprint values. a, f , g, i and j are fingerprints expressed once in s 1 , s 2 and s 3 but they are present in other segments not explicited here. We then compute the suffix array and interval tree presented on figure 2 that specifies, besides the parenthood relationship, the suffix links between intervals. Each interval with a lcp (length of common prefix) greater than 1 is suffix-linked to an interval that contains at least the suffixes of the segments of length lcp -1. If it contains no other segment suffix, this interval is not interesting for clone cluster reporting, since the clones of this interval are included into an interval of greater lcp. The discarded intervals are shown in gray in figure 2; for instance, the interval de [7..9] only contains 3 suffixes that directly come from interval cde [4..6]. On the other hand, if the suffix interval contains one or several new segments, it has to be considered as a clone cluster; for instance, the interval cde [4..6] contains not only suffixes of the interval bcde[2..3], but also of the suffix s 3 [3..5]. Finally, all of the intervals, minus the discarded ones due to suffix inclusion, represent the clone clusters containing segments of consecutive sibling subtrees.

Building the suffix array can be achieved in a time linear with the cumulated lengths of segments [START_REF] Kärkkäinen | Simple linear work suffix array construction[END_REF] whereas the interval tree construction is also obtained in linear time iterating over the computed lcp-table (also in linear time [START_REF] Kasai | Linear-time longest-common-prefix computation in suffix arrays and its applications[END_REF]) using a stack.

Finding exact single node matches between a query tree and a database

Given a single source code project, we also want to search for existing exact matches between this project and all of the projects in the database. This problem can be seen as a specific case of those described in 3.3: instead of iterating on all of the database, we limit the exploration to fingerprint matching subtrees of the query tree. Initially, the fingerprints of the nodes of the query tree are computed1 . Starting form the root node, and in breadth-first order, these fingerprints are then searched in the database to retrieve clusters of single node clones As in 3.3, sub-matches can be discarded and multi-node exact match clusters (clusters of exact matches of sibling nodes) can be retrieved. If a match cluster is found between a subtree c q of the query tree and subtrees from other trees in the database and we are not interested in matches containing subtrees under c q , we can stop the search for subtrees under c q . Thus it enables the detection of exact clones of compilation units through a single database query.

Tree fingerprinting methodologies

Given a tree (AST), with internal nodes and leaves, we want to index by a digest value each subtree of this tree, using a hash function. The first problem encountered is to find such a hash function, with the good properties. Since we want to represent the syntax tree and not only its leaves token sequence, we have to use a hash function that is sensitive to the tree structure: thus, we must take into account the internal nodes of the AST to compute the hash value of a subtree. Furthermore, since we want our process to be scalable, and efficient for a large amount of data, it would be better to use an incremental hash function, that only needs the hash values of its direct children to compute the hash value of a subtree. This means that hashing all of the subtrees of a given AST could be made in linear time.

We split the hash function problem in two parts. The first part concerns the study of a hash function for an individual node (without subtree): how to represent the syntactic properties of a single node with an integer? The second part has to do with assembling hash values of individual nodes to infer hash values for subtrees (collection of nodes with sibling and parent relations): we propose and study three hash functions. Finally, we evaluate the theoretical effectiveness of these fingerprinting techniques.

Hash functions and node-type vector

We characterize each subtree of the syntax tree of a compilation unit via a good hash function. A hash function is considered good if it minimizes the probability p of hash value collision for two structurally different subtrees. The choice of the length 2 k of the hash value depends on the cardinality of handled tree space that induces the probability of collision p (bound by 1 2 k for an infinite set of tree).

We define the node-type vector as the vector specifying for each single node-type (variables, constants, statements, block statements, conditional structures, loop structures...) a constant hash value: this vector is unique for all hash computation for a given language and abstraction level. Depending on the desired abstraction level, certain types of nodes can be represented by the same hash value. For example, it is possible to abstract all of the loop structures (while, for, repeat...until ) with a unique hash value since common obfuscation patterns use simple transformation of loop structures. Another concern is related to the abstraction of primitive types. Obfuscation could easily replace a boolean or a byte type by another embracing primitive type such as an integer: it could then be pertinent to use the same hash value for some primitive types or, more generally, for numerical values.

On the contrary, for copy-paste exact match detection, it might be useful to include additional parameters for the hash value computation of an abstract node (such as the name of an identifier).

Finally choosing the better abstraction for hash values of individual nodes is a compromise depending on the language and the application: since obfuscation patterns are expected, maximizing the abstraction level can be considered at the cost of a loss of precision. We then consider a unique mapping between the space of individual nodes and integers, two individual nodes with the same hash value being later considered as an exact match.

A practical solution adopted for our system consisted in setting a random integer value to each type of node, through the cryptographic hash (with MD5 for example) of a char-sequence representing the node type in our AST. For a node a, we note this node hash value V (a). For the set A of (abstracted) node types for a language we obtain the node type hash vector:

V(A) = V (A 1 ), V (A 2 ), • • • , V (A |A| ) .

Candidate hash functions

We propose and examine the advantages and weaknesses of some candidate hash functions to be used for the fingerprinting process of the syntax tree.

Sum hashing (node type metrics) Simple metrics for subtrees consist in counting each type of node in them: then, each subtree is characterized by a vector where the i-th component is the number of nodes of type i. This approach has been successfully used by Deckard [START_REF] Jiang | Deckard: Scalable and accurate tree-based detection of code clones[END_REF] to hash syntax trees: the principle is extended from counting single node types to counting small subtrees and then a LSH-hash function is applied on each count-vector to clusterize them according to their proximity following their Euclidean distance. Since this method ignores the structural organization of trees, near-miss and even completely irrelevant matches can be retrieved. For our tests, presented in section 4.3, we introduce the sum hash function that is the product of the node type-count vector by the node type hash vector (each node type is defined by a randomly-set integer).

Dyck word hashing

As previously seen, a subtree can be mapped to a representative integer. Here, we propose to represent a subtree as a Dyck word, i.e. a serialized form of the subtree obtained from depth-traversal. Contrary to a node type-count vector, a Dyck word takes into account the structural properties of the tree.

The Dyck word D(α) for a leaf α is defined as the integer sequence V ⊳ (α)V ⊲ (α) whereas the Dyck word D(β) of an internal node β with a children set

{b 1 , • • • , b k } is recursively defined as the concatenation V ⊳ (β) • D(b 1 ) • • • D(b k ) • V ⊲ (β).
We compute the values V ⊳ (η) and V ⊲ (η) for a node η from the node type vector V (η) using for example a cryptographic hash function2 .

Then, we build a Karp-Rabin hash function K on the Dyck word. A Karp-Rabin hash function [START_REF] Karp | Efficient randomized pattern-matching algorithms[END_REF] can be incrementally computed. For our purpose we want to efficiently compute the hash function of a subtree given its root and its children subtrees. Indeed, the Karp-Rabin hash function K is a polynomial function on a word of integers m = a 1 a 2 • • • a |m| defined as follows, with the base B being chosen as a prime number (e.g. 33, 65599...) in order to limit hash collisions:

K(m) = (. . . ((a 1 × B + a 2 ) × B + a 3 ) . . .) × B + a |m|
We deduce a formula to recursively compute the hash value of concatenated subsequences of integers m = s 1 s 2 • • • s n knowing the hash value and the length of each subsequence s i :

K(m) = • • • K(s 1 ) × B |s2| + K(s 2 ) • • • × B |sn| + K(s n )
Thus K(m) can be computed in time t(m) = 1≤i≤n (log 2 (|s i |) + t(s i )) using a fast exponentiation. The computation of the hash values of all nodes of a tree of size N can be made in O(N log N ). Cryptographic hashing Finally we consider indexing nodes of the tree by a cryptographic hash function such as SHA-1 [START_REF]Secure Hash Standard[END_REF] or MD5 [33]. Thus, given a tree, each node is hashed bottomup: leaves are indexed first (as described in section 4.1), and the hash value of a node is the cryptographic hash of the concatenation of the node hash with the hash values of the children subtrees. This provides us with a completely incremental indexation process, linear in the number of nodes in the tree. This hash method is expected to be a good approximation of a perfect hash function.

Given a cryptographic hashing function C, such as SHA-1, we define the hash function H C . It is defined recursively for a tree t rooted at node r and with children subtrees t 1 • • • t n as follows:

H C (t) = C(V (r) • H C (t 1 ) • H C (t 2 ) • ... • H C (t n ))
The size of hash values generated by cryptographic functions is reduced by selecting first or last bytes with a conventional order (e.g. big-endian).

Exploiting the commutativity of nodes Since some types of node from the grammar of a language can be defined as commutative (e.g. the order of operands of the addition operator can be ignored) structurally-sensitive hash functions like Karp-Rabin and cryptographic functions can be adapted: the concatenated child subtrees hash values can be sorted by increasing hash values prior to their combination.

Practical quantification of hash function efficiency

In order to test the efficiency and speed of the previously defined hash functions, we compute hash values on sets of randomly generated binary trees of different sizes. The collision results are expressed in figure 3 for randomly generated binary trees of 127 nodes (and height of 7) and are compared with the expected results of a perfect node types and structurally comprehensive hash function. For each test, we fingerprinted 10 6 random binary trees using 10 different types of internal nodes and 10 types of leaves. We notice in figure 3 that Karp-Rabin and cryptographic hash functions are almost as efficient for limiting false-positive collisions and offer results very close to a theoretically perfect hash function 3 .

Even if more simply defined than a non-linear cryptographic hash function, the Karp-Rabin hashing function induces a theoretical detrimental run-time cost on large trees due to the base exponentiation cost (in O(log 2 n) for a tree of n nodes). However on small trees encountered when parsing source code, MD5 and SHA-1 hashing are experimentally more time costly (respectively 26.3% and 35.0% more costly than sum hashing on trees of 1023 nodes) than Karp-Rabin hashing function (22.8% more costly than sum hashing). Since in practice I/O database time cost is much higher (∼10 times) the choice of the hash function should not rely on this criterion.

Deviation from a theoretical hash function highlighted on small trees hashing when the tree space cardinality is smaller than the hash value space cardinality: e.g. 5 • 10 7 7-weighted trees can be enumerated whereas the first collision is encountered (for SHA-1 hashing) for a 41-bit hash (vs. 25-bit hash for a perfect hash function). Thus rather than using a hash value for small subtrees an interesting idea would be to introduce a specific companion repository dedicated to small subtree storage replacing the hash value in the fingerprint database by a link to the subtree.

A case study: retrieving clones on the OpenJDK

In order to test several abstraction levels we apply our clone detection tool on the Java classes of the source code of the Open JDK 1.7 [2] (build 42 of 2008-12-19 with ∼2.5M LOC in 7378 files parsed in 29.9 million nodes). We fingerprint the subtrees extracted from syntax trees generated by the Eclipse parser (built with LALR Parser Generator [START_REF]LALR parser generator[END_REF]). We propose the following fingerprinting methodologies:

1. Standard fingerprinting (std). The syntax trees are abstracted regarding to the identifiers.

Only fingerprints for subtrees greater than a set weight threshold w (in terms of number of nodes) are kept.

2. Fingerprinting with subtree abstraction (subAbstr). A new level of abstraction is introduced by attributing to all of the subtrees of strictly smaller weight than w ′ (w ′ ≤ w) the same hash value. Even if close to Asta's approach [START_REF] Evans | Clone detection via structural abstraction[END_REF] that abstracts subtrees at a depth greater than a given threshold it may detect less false-positives in depth-unbalanced trees. Minor edit operations done on small subtrees are ignored by the fingerprinting process and near-miss clones can be detected with a risk of increasing false-positives.

3. Fingerprinting with consideration of commutative operators (comm). Subtrees that are a child of a commutative operator are considered as interchangeable and their order is normalized for hash value computation (see 4.2). For our tests on Java source code we considered the TypeDeclaration node as a commutative operator (order of field and method declarations in a class is not important) and all InfixOperation nodes (even if not semantically correct for all infix operators).

4. Fingerprinting with primitive type abstraction (primAbstr). Since Java does not provide a template system for primitive types, large amount of code may be duplicated for different primitive types: abstracting primitive types enables the localizing of these chunks of code even if they cannot be factorized.

5.

Fingerprinting with total node abstraction (struct). Only the structure of the syntax trees is considered for the hashing process, i.e. the uniform node type vector.

6. Fingerprinting using the sum hash function (sum). The sum hash function does not consider the structure and may induce numerous false-positives on semantically different subtrees sharing the same number of nodes of each type.

The quantitative results obtained4 with these different methodologies applied on the Open JDK 1.7 can be found in figure 4. Since the notion of good matches is a very subjective one, computerized quantification of accuracy and recall of results is very touchy. However if all of the exact subtree matches (considering the tree abstraction level induced by the fingerprinting methodology) can be retrieved, no guarantee can be provided on their semantic value. We note that struct fingerprinting induces almost two times more clone pairs than sum fingerprinting: the probability of chunks of code with shared structure being semantically different is high whereas considering only the types of node provides a relatively better accuracy. We observe that the fingerprinting methodologies are more or less neutral in terms of clone numbers whereas the size of these clusters may vary especially for small to medium clones. The detection of large clones (w ≥ 100) is hardly impacted. We also studied the localization of clone pairs among the packages: figure 5 shows that most clones can be found inside the same package.

In terms of source code coverage the clones found using the different fingerprinting methodologies represent less than 8% of the source code (see figure 6). Unsurprisingly subAbstr methodology induces the better clone code coverage: the additional large clones reported are comparatively relevant according to a preliminary analysis on a little sample. Finally figure 7 shows the number of clusters and their average size by weight: as expected the extension of sibling exact subtrees allows clones of higher weight to be reported.

Scenario-based behavior

In [START_REF] Chanchal | Scenario-based comparison of clone detection techniques[END_REF], C.K. Roy and J.R. Cordy propose a taxonomy of editing scenarios that is used to compare clone detection techniques. In this section, we will use this taxonomy to present the result of our syntax tree fingerprinting technique and to show how we plan to extend it.

The first set of copy-paste scenarios proposed in [START_REF] Chanchal | Scenario-based comparison of clone detection techniques[END_REF] concerns changes in whitespaces, comments and formatting. Since our tree fingerprinting technique is based on a complete tree abstraction, these clones are detected regardless of the modifications.

The second set of copy-paste scenarios concerns identifier renaming, parameter permutation in function calls, changes in types and replacement of parameters by expressions. No matter what abstraction is used, the tree fingerprint is not sensible to identifier renaming. On the contrary, depending on the abstraction used for function calls, types and constants, the tree fingerprint may be affected by the three other types of modifications. Changes in types are not perceptible if primAbstr abstraction is used. Clones containing permutations of arguments or changes in expressions may be detected if subAbstr is used.

The third set of copy-paste scenarios concerns changes in arguments, insertion or deletion of a line and modification of a line. Clones containing changes in arguments may be detected by subAbstr, but the other types of modifications cannot be detected, changing the abstraction. In order to find these modifications, the subtree fingerprint has to be extended to find near miss clones. For instance, using multi-subtrees exact match clusters (see section 3.3), we can detect that two distinct nodes have similar children with the exception of the one inserted, modified or deleted. Thus, a simple post-processing after exact clone matching can enable the detection of these clones.

The last set of scenarios concerns line permutations and a for -into-while translation. The line permutations can be detected by the same post-processing as in the previous scenarios. The for -into-while translation detection requires, on top of post-processing, the common abstraction for loop instructions.

This presentation demonstatres that the use of an exact matching technique followed by a degree of post-processing in a specific location of the code may detect the same clones as those detected by techniques based on near-match hashing techniques but at the same time reduces in the first step the false positives. Other post-processings may by applied to detect intentional obfuscations.

Conclusion and future works

In this paper we focused on a method using fingerprinting on syntax trees to retrieve clone clusters of exact matches across sets of projects or between a given project and a database of projects. We proposed a technique to aggregate continuous sequences of matched single clones thanks to a suffix array. Then we focused on evaluating several hash functions to minimize collisions between false positives: our results show that both Karp-Rabin hashing on Dyck words of serialized subtrees and cryptographic hashing could be efficiently used on syntax trees. Beyond these technical consideration, the most important parameter in the fingerprinting process is the level of abstraction under consideration of the syntax trees handled: we tested several fingerprint methodologies, based on different abstraction levels. Finally, we reviewed the cases where an exact matching system, based on syntax tree fingerprinting, showed its limits. However the system described must be seen as a foundation permitting later extension of exact matches to near-miss matches, in order to detect more sophisticated obfuscation patterns, plagiarized code like modifications of control structures or inlining/outlining of functions. Extension methods from exact match germs have already been studied through local alignment on token sequences [START_REF] Ueda | On detection of gapped code clones using gap locations[END_REF][START_REF] Wettel | Archeology of code duplication: Recovering duplication chains from small duplication fragments[END_REF] but not on AST structures. The formal definition and description of a scalable extension process on ASTs that could consolidate not only sibling non-consecutive exact matches but also cousin exact matches with a behavior adapted to the types of encountered nodes remain.

A Appendix: examples of clones in the OpenJDK

In this appendix, we present some examples (summarized in figure 8) of code clones found on the OpenJDK with our system. We classify these clones according to several criteria. The first criterion concerns the proximity of each component of the clone pair in the source code. As seen in figure 5, most of the clones are either found in the same class or in the same package. Following a code factorization goal, two clones in a same class may be merged into a new function in the same class; if the clones are far apart, the creation of a new helper class containing the common code can be envisaged. We have only studied the proximity in terms of package location and not related to the positioning in the class ancestry tree. In fact some clones found in sibling or near cousin classes could be merged into a common ancestor abstract class. Another useful criterion analyzed concerns the hash methodologies able to identify these clones: thus we provide some examples showing that a higher abstraction level of the syntax tree may increase the recall of matches but may decrease the accuracy as in some false-positives presented . Finally we note, as a third criterion, the usefulness of the clone report for refactoring. In fact, the largest clones found in the OpenJDK are automatically generated code and their refactoring may not be pertinent. Other clones found with the primAbstr methodology highlight repetitive code adapted to different primitive types that cannot be merged. Only a small part of the source code can actually be refactored, but sometimes with a detrimental effect on runtime costs.

Figure 1 :

 1 Figure 1: Overview of the system

Figure 2 :

 2 Figure 2: An example of extension of single subtree matches to consecutive sibling nodes between sequences of fingerprints s 1 = abcdef , s 2 = gbcdeh and s 3 = ijcdeh

Figure 3 :

 3 Figure 3: Hash pair collisions (log 10 (c)) on 10 6 127-weighted trees

Figure 5 :

 5 Figure 5: Distance of 10947 largest clone pairs (w ≥ 100) across the code (using std)

2Figure 6 :Figure 7 :

 67 Figure 6: Clone coverage (ratio of duplicated clones weight sum on global syntax tree weight)

Figure 8 :

 8 Figure 8: Evaluation of sample code clones

If the query tree is already present in the database, this step can be skipped.

The use of a polynomial formula to infer these values (e.g. V⊳(η) = B • V (η) where B is a prime number) should be avoided because it may degrade the onto property of the hash function.

Concerning Karp-Rabin hashing, we underline the necessity of using a prime base B: for example the use of the base 32 generates numerous hash value collisions.

The parsing and fingerprint processes using the six methodologies were executed with the Sun client JVM 1.6 on an Intel P8600 2.4 Ghz with 4 GB of RAM in about 24 minutes. Iterating over the fingerprint database, the creation of exact match clusters and the extension of single exact matches to consecutive sibling exact matches were executed in less than 3 minutes.