Emilie Balland
email: emilie.balland@loria.fr

Pierre-Etienne Moreau
email: pierre-etienne.moreau@loria.fr

Term-graph rewriting via explicit paths

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

The notion of position is of course central as soon as one deals with data structures. Absolute as well as relative positions are at the heart of algorithms manipulating data structures and their appropriate use and representation can lead to very important differences in the complexity behavior and more generally in the expression of the algorithms themselves. A typical example is the notion of de Bruijn indexes for lambda-terms [START_REF] De Bruijn | Lambda calculus notation with nameless dummies. a tool for automatic formula manipulation with application to the church-rosser theorem[END_REF] that not only allows for an easier expression of data-structure manipulations, typically substitution, but also completely changes the way the algorithm is designed, because in this case alpha-conversion is useless.

The main idea of this paper is to make the notion of path first-class, i.e. paths become part of the terms and not just meta-information about them. Paths are defined as a generalization of positions and denote a relation from a source position to a target one. A main difference with classical positions that specify a subterm with respect to a global term is that the source position is not necessarily the root.

The first contribution of the paper is to introduce the notion of referenced terms to ground an extension of term rewriting where paths are used to express references and thus to provide a natural way to add pointers in classical terms. For instance, the term f (a, g(a)) where we want to make explicit the fact that the subterm a is shared, will be represented as the referenced term f (a, g(-1 -2 1)), where -1 and -2 denote backward move from respectively the first subterm of g and the second subterm of f . The rational term g(g(g(. . .))) (a rational term is a possibly infinite term with finitely many subterms, see [START_REF] Corradini | Rational term rewriting[END_REF]) is represented by the referenced term g(-1).

Based on the formalization of paths and a notion of rewrite relation for referenced terms, a strong contribution of this paper is to establish a simulation of term-graph rewriting by referenced term rewriting. Since this simulation is completely based on standard first-order terms, another main interest of the approach is to provide a safe and efficient way to represent and transform termgraphs in a purely term-rewriting based language. Beside the theoretical interest, this is very useful to implement program analysis tools where the representation, the analysis, and the transformation of control-flow and data-flow graphs are crucial. This new representation of terms generalizes standard first-order terms. It requires us to carefully design this new notion of terms and its use to get syntactic correctness. For instance, g(-1 -1) makes no sense as such. Completeness with respect to the standard notions of term and term-graph rewritings have also to be established. This leads to an original and clean way for representing and transforming graphs in a maximally shared rewrite-based environment, making in particular possible the use of term rewriting strategies [START_REF] Kirchner | Strategic rewriting[END_REF][START_REF] Visser | Stratego: A language for program transformation based on rewriting strategies. System description of Stratego 0.5[END_REF] for term-graph rewriting.

The paper is organized as follows. In Section 2, we formalize the notion of paths and referenced terms where paths are interpreted as pointers. Section 3 shows the relation between referenced terms and cyclic term-graphs. In this section, paths are considered as a way to identify shared parts of the term. Sections 4 presents related work as well as the implementation that has been done in the Tom system. Section 5 concludes.

Paths and Referenced terms

We assume the reader to be familiar with the basic definitions of first-order terms given, in particular, in [START_REF] Baader | Term Rewriting and all That[END_REF]. We briefly recall or introduce notations for a few concepts that will be used throughout this paper.

A signature F is a set of function symbols, each one associated to a natural number by an arity function. T (F, X ) is the set of terms built from a given finite set F of function symbols and a denumerable set X of variables. symb(t) is a partial function from T (F, X ) to F, which associates to each term t its topsymbol f ∈ F. The set of variables occurring in a term t is denoted by Var(t). If Var(t) is empty, t is called a ground term and we note T (F) = T (F, ∅) the set of ground terms. Given a set of terms T (F, X ), a substitution σ is a function from X to T (F), denoted σ = {x 1 → t 1 , . . . , x k → t k } when its domain is finite. Ran(σ) denotes its codomain. By abuse of notation, we mix up the term a ∈ T (F) and the function symbol a ∈ F when the arity of a is 0.

In term rewriting, the concept of positions is used to denote a subterm in a global term (i.e. the path from the root to this subterm). In this section, we define the notion of path, which generalizes the notion of position by denoting a path from a subterm to another one, and not only the path from the root to a given subterm. Negative numbers designate bottom-up displacements Definition 1 (Path). We denote P the set of words on Z \ {0}. We denote the empty word, p 1 p 2 the concatenation of two words p 1 and p 2 and |p| the length of a word p. We denote P * the set P \ { }.

Example 1. , 1 3, and -2 1 3 are paths, elements of P.

The notion of path is oriented and corresponds to the route from a subterm to another one. For example, considering the term f (a, b), the path -1 2 describes how to reach the subterm b starting from a. The negative integer -1 denotes a backward move from a to f , whereas 2 goes from f to b. The inverse of a path p is denoted by p and can be calculated using the equations = and i p = p -i. For example, -1 2 = -2 1.

Note that positions are a subset of paths (paths only composed of positive integers). In the rest of the paper, they will be denoted by Greek letters ω, δ. The empty word is also a position and is generally called the top-position because in term-rewriting, positions are only interpreted from the root of the term. Given two positions, we will denote by the classical relation of prefixation between two words (ω 1 ω 2 if there exists a position p such that ω 1 p = ω 2 ). The subterm of t at position ω is denoted t |ω . The replacement at position ω of the subterm t |ω by t is written t[t ] ω . The set of positions of t is denoted Pos(t). Given two positions ω src and ω dest (for source and destination), note that the path ω src ω dest corresponds to a path connecting t |ωsrc to t |ω dest . We denote < P the lexicographic order on positions. For example < P 1 and 1 2 < P 1 3.

If we want to use these paths to define term-graphs, it is necessary to consider equivalence classes. Informally, two paths are equivalent if for every source position, their target positions are equal. For example, paths 1 2 -2 and 1 are equivalent.

In the following we define the notion of canonical form as the smallest path of this equivalence class. Moreover, when interpreting a negative integer as a backward move from the i-th child to the father, we must ensure that if the previous move in the word is positive, it leads to the same i-th child. For example, the path 1 -2 cannot be considered as valid because a move downward to its first child is followed by a move backward from its second child. These observations lead us to introduce the notion of well-formed paths, as well as a constant ⊥ for representing ill-formed paths.

Definition 2 (Canonical path and path equivalence). The canonical form of a path p ∈ P, denoted p , is obtained by maximal application of the rule i -i → if i ∈ Z * . Two paths p 1 and p 2 are said equivalent if

p 1 = p 2 .
It is easy to show that the rule using to obtain canonical paths is confluent and terminating. Definition 3 (Well-formed path). We introduce a constant ⊥ for denoting ill-formed paths. A path p ∈ P is well-formed if p → * R ⊥ with R is defined by the rule p i -j p → ⊥ if i > 0, j > 0 and i = j Example 2. 1 2 -2 and 2 3 -3 -2 1 are well-formed paths, but 1 -2 is not.

Note that positions can be seen as a subset of well-formed paths because they correspond to paths only composed of positive integers. Note also that the inverse preserves the well-formedness. On the other hand, the concatenation of two wellformed paths does not always lead to a well-formed path: 1 is well-formed, -2 is well-formed, but 1 -2 is not.

From these definitions, we show how the notion of paths can be used to extend an algebraic signature in order to represent referenced terms.

Referenced Terms

A referenced term is a term whose leaves may be a path, which denotes a reference to another subterm. Definition 4 (Referenced terms). Given a set of symbols F and a set of variables X such that F, X , P are disjoint, we denote by T r (F, X ) the set of referenced terms T (F ∪ P, X ), where the elements of P are symbols of arity 0.

Example 3. For F = {f, g, a}, a, g(-1), and g(f (a, -2 1)) are referenced terms, elements of T r (F). For any F and X , we have T (F, X ) ⊂ T r (F, X ).

Definition 5 (Dereferencing). Given t ∈ T r (F, X ) and ω ∈ Pos(t):

deref(t, ω) = ω symb(t |ω ) if symb(t |ω ) ∈ P ω otherwise.
We recall that symb(t) is a partial function from T (F, X ) to F, which associates to each term t its top-symbol f ∈ F. The operation deref(t, ω) returns the position pointed by t |ω when symb(t |ω ) ∈ P, and ω otherwise. For example, deref(g(-1), 1) = , but deref(g(a), 1) = 1. Note that when ω symb(t |ω ) is ill-formed, the result of deref(t, ω) is meaningless. We now introduce a notion of valid referenced terms. The first condition ensures that the value returned by deref(t, ω) is a position of Pos(t), and thus is a well-formed path. For example, deref(g(-2), 1) is not a valid term. The second condition forbids pointers of pointers like in f (-1 2, -2 1). This last requirement is introduced only for simplicity but is not mandatory in term-graph simulation. Indeed, it could be interesting to consider such terms for modeling imperative languages for example. Definition 6 (Valid referenced terms). A term t ∈ T r (F, X ) is a valid referenced term if ∀ω ∈ Pos(t) such that symb(t |ω ) ∈ P we have:

-deref(t, ω) ∈ Pos(t), -symb(t |deref(t,ω) ) / ∈ P * .
We denote by T vr (F, X ) the set of valid referenced terms and T vr (F) the set of ground valid referenced terms.

Empty paths (denoted ) are allowed in valid referenced terms in order to deal with degenerated cycles that can appear when applying a collapsing rule, e.g. a rule of the form I(x) → x. In the term-graph rewriting formalism, a fresh constant called black hole and denoted by • is generally introduced [START_REF] Ariola | Equational term graph rewriting[END_REF]. In our context, it is not necessary since corresponds intuitively to this constant.

Example 4. The terms , g(-1), f (-1 2, a) and f (-1 2, ) are valid, but g(3) and f (-1 2, -2) are not. Terms corresponding to non-empty paths (1, -1 2, etc.) are elements of T r (F, X ) but are not valid (i.e. / ∈ T vr (F, X )). The term

t = f (-1 1 -1, -2 3) is invalid because deref(t, 2) = 2 -2 3 = 3 which is not in Pos(t) = { , 1, 2}.

Term-Graph Rewriting

There exist different formalisations of term-graph rewriting, category-theory oriented [START_REF] Kennaway | On graph rewritings[END_REF][START_REF] Löwe | Algebraic approach to single-pushout graph transformation[END_REF], equationally oriented [START_REF] Ariola | Equational term graph rewriting[END_REF][START_REF] Plump | Handbook of Graph Grammars and Computing by Graph Transformation, chapter Term graph rewriting[END_REF] or implementation oriented [START_REF] Barendregt | Term graph rewriting[END_REF]. The difference between terms and term-graphs is the notion of horizontal and vertical sharing. In this section, we base our work on the equational framework introduced in [START_REF] Ariola | Equational term graph rewriting[END_REF]. This well established framework allows the definition of possibly cyclic term-graphs, using systems of recursion equations.

Definition 7 (System of recursion equations from [START_REF] Ariola | Equational term graph rewriting[END_REF]). Given a finite set F of function symbols and a denumerable set X of variables, a system of recursion equations is of the form

{α 1 | α 1 = t 1 , . . . , α n = t n }, ∀i, j ∈ [1, n] α i ∈ X , α i = α j , t i ∈ T (F, X ) is of the form f (β 1 , . . . , β m ), f ∈ F, ∀j ∈ [1, m] β j ∈ X . Moreover, ∀i ∈ [1, n] α i must be reachable from α 1 .
Given a system of recursion equations L, the root is denoted root(L) and corresponds to the recursion variable α 1 . The set of equations is denoted set(L). A variable α is said bound when it appears in the left-hand side of an equation. Otherwise, α is free. Note that systems of recursion equations are considered modulo renaming of the recursion variables. In Definition 7, the systems of recursion equations have been presented in flattened form (t i of the form f (β 1 , . . . , β m )) which ensures the unicity of the representation of a term-graph (modulo renaming of recursion variables). An example of term-graph is given in Figure 1.

α : f β : g γ : f root Fig. 1. This cyclic term-graph corresponds to the system of re- cursion equations {α | α = f (β, γ), β = g(α), γ = f (β, α)}.
It contains horizontal sharing: α and γ share the same subterm β; as well as vertical sharing: α is a subterm of both β and γ.

Definition 8 (Equational term-graph rewriting [START_REF] Ariola | Equational term graph rewriting[END_REF]). Given a rewrite rule composed of two systems of recursion equations L 1 and L 2 with the same root (L 1 and L 2 are not necessarily in flattened form) and where the free variables of L 2 are included in the set of free variables of L 1 , a system of recursion equations L is rewritten into L by the rule L 1 → L 2 if there exists a variable substitution σ (Definition 4.1 of [START_REF] Ariola | Equational term graph rewriting[END_REF]) and a recursion equation

α = t in L such that set(σ(L 1 )) ⊆ set(L) and α = root(σ(L 1 )). root(L ) = root(L) and set(L ) = set(L) \ {α = t} ∪ set(σ (L 2 ))
where σ (L 2 ) denotes σ(L 2 ) in which every bound variable (except the root) has been renamed using a fresh name. To obtain from L a system as defined in Definition 7, equations corresponding to unreachable bound recursion variables are removed and equations are flattened (see [START_REF] Ariola | Equational term graph rewriting[END_REF] for more details). Degenerated cycles, i.e. equations of the form α = α are replaced by α = •. In case of equations of type α = β, each occurrence of α is substituted by β and the equation α = β is removed.

Example 5. Suppose we want to apply the rule

{β 1 | β 1 = f (β 2 , β 3 )} → {β 1 | β 1 = β 2 }
, which corresponds to f (x, y) → x, on the following term-graph:

α1 : f α2 : f α3 : f α4 : a α5 : g α6 : b root α1 : f α2 : f α3 : f α4 : a α5 : g α6 : b root initial subject s final result s The initial term-graph is L = {α 1 | α 1 = f (α 2 , α 3 ), α 2 = f (α 4 , α 5 ), α 3 = f (α 6 , α 4 ), α 4 = a, α 5 = g(α 6
), α 6 = b}. When applying the rule at position 1 (i.e. on α 2 ), we have σ = {β 1 → α 2 , β 2 → α 4 , β 3 → α 5 } and α 2 is the selected bound variable. σ(L 2 ) = {α 2 = α 4 } (note that renaming with fresh variables is not necessary in this case) and we get L = L \ {α 2 = f (α 4 , α 5 )} ∪ σ(L 2 ) as final result. This corresponds to the system

{α 1 | α 1 = f (α 4 , α 3 ), α 3 = f (α 6 , α 4 ), α 4 = a, α 6 = b} after cleanup.

Referenced term equivalence

In order to simulate term-graphs with referenced terms, we need to establish equivalence classes between valid referenced terms. For example, f (-1 2, a) and f (a, -2 1) should be equivalent. They both correspond to the term-graph rooted by f whose two children correspond to the shared subterm a. To define the equivalence, we introduce three intermediate functions that characterize translation, expansion and sharing. The first one, called subterm translation, is essential in the following. Given a term t and two positions ω 1 , ω 2 , as illustrated in Figure 2, the translation in t from ω 1 to ω 2 , denoted t [ω1 ω2] , returns the subterm t |ω1 where the references contained in t |ω1 that point outside t |ω1 have been updated as if t |ω1 was moved to the position ω 2 .

Definition 9 (Subterm translation). Given t ∈ T vr (F, X ) and two positions ω 1 , ω 2 , we consider the subterm translation t [ω1 ω2] defined such that Pos(t [ω1 ω2] ) = Pos(t |ω1 ) and ∀δ ∈ Pos(t |ω1 ):

symb(t [ω1 ω2] |δ ) =    ω 2 δ deref(t, ω 1 δ) if symb(t |ω1 δ ) ∈ P * and ω 1 deref(t, ω 1 δ) symb(t |ω1 δ ) otherwise. t t [ω1 ω2] ω1 ω2 ω δ δ d = deref(t, ω)
Fig. 2. Given t and ω1, let us suppose that at position ω the subterm t |ω contains a reference to the subterm d (i.e. d = deref(t, ω)). The translation from ω1 to ω2 corresponds to an update of t |ω 1 as if it was moved to ω2. To maintain the pointers to the referenced terms, the paths stored in t |ω 1 are updated. The result of this operation is the updated subterm

t |ω 1 . For example, f (g(-1 -1), a) [1 2] = g(-1 -2).
The operation expansion noted exp consists in replacing all the sharing by duplication. Given a set of function symbols F, exp is a function from T vr (F) to T ∞ (F ∪ { }) where T ∞ (F ∪ { }) is the set of infinite terms over F ∪ { } defined as partial functions from the infinite set of positions to F ∪ { }. We denote ⊥ the undefined term represented by the empty function ∅ → F ∪ { }. See [START_REF] Corradini | Cpo models for infinite term rewriting[END_REF] for more details.

Definition 10 (Expansion). Given t ∈ T vr (F), we consider the chain {t i } i∈N of terms of T ∞ (F ∪ P) defined as follows:

-t 0 = t -t n+1 = t n [t n[deref(t n,ω) ω] ] ω
where ω is the smallest position of Pos(t n ) such that symb(t n|ω ) ∈ P * (We consider the following order:

ω < ω if |ω| < |ω | ∨ (|ω| = |ω | ∧ ω < P ω ) ) exp(t) ∈ T ∞ (F) is defined as ∞ i=0
t i where t i corresponds to t i where every path p ∈ P * has been replaced by ⊥. Proposition 1. Given t ∈ T vr (F), exp(t) is a total function (i.e. total w.r.t. to the arities, not totally defined over the set of all positions. For more explanations, see [START_REF] Corradini | Cpo models for infinite term rewriting[END_REF]).

Proof. By definition of the chain {t i } i∈N , exp(t) is a function. Moreover, as every path is replaced by a subterm, exp(t) does not contain ⊥ and the symbol arities are respected. Example 6. The function exp replaces in a valid referenced term every reference by the corresponding expanded subterm. exp(f (-1 2, a)) = exp(f (a, -2 1)) = f (a, a) and exp(g(-1)) = g(g(g(. . .))). Note that in case of a cycle, the expanded term corresponds to an infinite term. A non-trivial example is f (g(-1 -1 2), h(-1 -2 1)). In this case, we need to update paths at every application of the rule. As the shared subterms are dependent, the result is infinite. We finally obtain f (g(h(g(h(. . .)))), h(g(h(g(. . .))))).

Thus two equivalent referenced terms have the same expansion. However, this condition is necessary but not sufficient because the two terms to compare must also have a similar sharing. For example, f (a, a) is not equivalent to f (a, -2 1) because a is not explicitly shared in the first one. For this, we introduce a third relation called sharing which computes the set of shared positions.

Definition 11 (Sharing). Given t ∈ T vr (F), we consider:

-share 0 (t) = {{ω, deref(t, ω)} | ω ∈ Pos(t) and symb(t |ω ) ∈ P * } -share n+1 (t) = {{ω q, q } | {ω, ω }, {ω q, q } ∈ share n (t)}
The function share(t) is defined as

∞ n=0 share n (t).
Example 7. The function share computes the set of shared position pairs. For example, share(f (-1 2, a)) = {{1, 2}} and share(g(-1)) = {{1, }}. A nontrivial example is f (g(-1 -1 2), h(-1 -2 1)). At the first step, share 0 (t) = {{1, 2 1}, {2, 1 1}}. In this case, it is necessary to close the relation of sharing with prefixes. We finally obtain the infinite set of related positions share(t) = {{1, 2 1}, {2, 1 1}, . . . , {1 (1 1) * , 2 1 (1 1) * }, {2 (1 1) * , 1 1 (1 1) * }} ( * denotes the sublist repetition). This infinite result is due to the inter-dependency of the two references.

Definition 12 (Equivalence). Two valid referenced terms t 1 , t 2 are equivalent (denoted by t 1 t 2 ) if share(t 1 ) = share(t 2 ) and exp(t 1 ) = exp(t 2 ).

It is easy to show that is an equivalence relation.

Canonical referenced terms

For every equivalence class, we define a canonical form using < P , the lexicographic order on positions.

Definition 13 (Canonical referenced terms). A valid referenced term t ∈ T vr (F, X ) is canonical if for every position ω ∈ Pos(t) such that symb(t |ω ) ∈ P * , symb(t |ω ) is a canonical path and deref(t, ω) < P ω. We denote by T g (F, X ) the set of canonical referenced terms and T g (F) the set of ground canonical referenced terms.

Example 8. The term f (a, -2 1) is canonical but f (-1 2, a) is not because deref(f (-1 2, a), 1) = 2 (the position of the pointed subterm a) is not smaller than 1.

To define the normalization function that returns the canonical form of any valid referenced term, we introduce a swapping function that permutes two subterms and updates all the paths contained in the global term in order to preserve the sharing. First, we translate the two subterms. This translation updates the pointers from the subterms to the external context. To obtain a valid referenced term, we still have to update every pointer from the outside to the subterms. Definition 14 (Swapping). Given t ∈ T vr (F, X ) and two disjoint positions

ω 1 , ω 2 (ω 1 ω 2 and ω 2 ω 1 ), we consider u = t [ω1 ω2] , v = t [ω2 ω1] , t = t[v] ω1 [u] ω2 .
The swapping in t of the subterms at position ω 1 and ω 2 is denoted by t [ω1 ω2] , and is defined such that ∀ω ∈ Pos(t ), we have:

symb(t [ω1 ω2] |ω ) =            ω ω 2 δ if symb(t |ω ) ∈ P * , ω ω 1 and ∃δ s.t. deref(t , ω) = ω 1 δ ω ω 1 δ if symb(t |ω ) ∈ P * , ω ω 2 and ∃δ s.t. deref(t , ω) = ω 2 δ symb(t |ω ) otherwise. Example 9. f (a, b) [1 2] = f (b, a), f (g(-1 -1 2), h(-1 -2 1)) [1 2] = f (h(-1 - 1 2
), g(-1 -2 1)). A more complex example is the swap of a and b in t = f (f (a, b), -2 1 2). In this case, the reference -2 1 2 has to be updated because it has to reference b. Thus, the result is f (f (b, a), -2 1 1).

The swapping function preserves the notion of validity (Definition 6). Its complexity is linear on the size of the term since in the worst case, all the references in the term must be updated. In the following, we introduce a normalization function that associates to every valid referenced term its canonical form.

Definition 15 (Normalization). We define : T vr (F, X ) → T g (F, X ) such that given t ∈ T vr (F, X ), t is the normal form of t (t where every path is in canonical form) with respect to the conditional rule: t → t [ω deref(t ,ω)] if ω < P deref(t , ω). The proof of this rule convergence can be found in the Appendix A.

Example 10. a = a, f (-1 2, a) = f (a, -2 1), and

f (g(-1 -1 2), h(-1 -2 1)) = f (g(h(-1 -1)), -2 1 1)
Note that the normalization is linear in the size of the term when the swapping is applied in a leftmost-innermost way.

Proposition 2. ∀t ∈ T vr (F, X ), we have t t .

Proof. Given t ∈ T vr (F, X ), t is trivially equivalent to t and every rewriting step of normalization preserves the two functions share(t) and exp(t). In fact, the swapping between a pointer and its corresponding pointed subterm preserves the sharing and as only references are updated, the expansion is the same.

Proposition 3. ∀t 1 , t 2 ∈ T vr (F, X ), we have:

t 1 t 2 ⇔ t 1 = t 2 .
Proof. First, the proof that t 1 = t 2 ⇒ t 1 t 2 is trivial because as is an equivalence relation and thus is reflexive. Secondly, we prove that t 1 t 2 ⇒ t 1 = t 2 . Suppose they are not equal, it means that there exists a shared subterm at a position ω referenced at a position ω in t 1 and the contrary in t 2 . As t 1 , t 2 are canonical, it implies that ω < P ω and ω < P ω which is impossible due to the total order on positions. So t 1 = t 2 .

Theorem 1. ∀t 1 , t 2 ∈ T vr (F, X ), we have:

t 1 t 2 ⇔ t 1 = t 2
Proof. Direct consequence of the propositions 2 and 3.

In practice, to verify that two terms are equivalent we compare their canonical forms. It is simpler and more realistic than computing exp(t) and share(t), which can be infinite.

Term-graph rewriting using canonical referenced terms

We introduce an original algorithm for implementing term-graph rewriting using canonical referenced terms. By manipulating only canonical referenced terms, we obtain a mapping one-to-one with term-graphs which makes easier the encoding of matching and rewriting. In Figure 3 we present a set of rules (T g -Matching), which is a specialization of the syntactic pattern matching algorithm presented in [START_REF] Kirchner | Rewriting, solving, proving. A preliminary version of a book is available at[END_REF].

Decompose E ∧ f (p1, . . . , pn) s,ω δ f (t1, . . . , tn) ∆ → → E ∧ n î=1 pi s,ω i δ i ti ∆ ∪ {(δ, ω)} Variable E ∧ x s,ω δ t ∆ → → E ∆ ∪ {(δ, ω)} Stability E ∧ π s,ω δ f (t1, . . . , tn) ∆ → → E ∆ ∪ {(δ, ω)} if ( δ symb(π) , ω) ∈ ∆ Dereferencing E ∧ p s,ω δ π ∆ → → E ∧ p s,ω δ s |ω ∆ ∪ {(δ, ω)} where ω = ω symb(π)
Fig. 3. We consider the set of rules Tg-Matching where E is a conjunction of constraints, ∆ is a set of pairs, x is a variable (∈ X ), f is a symbol, element of ∈ F ∪ { }, (remember that corresponds to •), s, t, t1, . . . , tn are ground referenced term (∈ Tg(F )), π is a non-empty path (symb(π) ∈ P * ), p is a pattern not reduced to a variable (∈ Tg(F , X ) \ X ), pi are patterns (∈ Tg(F , X )), ∧ is the classical boolean connector, which is associative and commutative. Starting from a constraint l s,ω s |ω ∅, the reduction leads either to (the neutral element of ∧) or a conjunction of matching constraints of the form p s,ω δ t, where δ and ω correspond to the positions of p and t with respect to l and s (i.e. p = l |δ and t = s |ω ). The context ∆ corresponds to the set of positions already visited. This set is necessary to correctly handle the case of cyclic terms.

Definition 16 (Rule application). Given s ∈ T g (F) and l, r ∈ T g (F, X ), the rule l → r can be applied to subject s at position ω if l s,ω s |ω ∅ reduces to ∆ by application of T g -Matching.

Note that the algorithm given Figure 3 does not compute a substitution. Moreover, contrary to syntactic term matching algorithms, there is no rule for handling variables that have multiple occurrences. The notion of non-linearity in term rewriting should not be confused with the notion of non-linearity in termgraph rewriting. The latter one corresponds to subterms sharing. For example, {α | α = f (β, β)} denotes a term-graph where the two subterms of f are shared. This does not match {α | α = f (β, γ), β = a, γ = a}. In our formalism, linear term-rewriting is sufficient to simulate non-linear term-graph rewriting. For example, the system of recursion equations {α | α = f (β, β)} can be encoded by f (x, -2 1), where x appears only once.

Proposition 4. Given a subject s ∈ T g (F), a pattern l ∈ T g (F, X ), a position ω ∈ Pos(s), the reduction of l s,ω s |ω ∅ by T g -Matching is convergent.

Proof. First, we prove the termination. We consider the lexicographic combination of prefix ordering on positions ( ) and < P . This strict order is well-founded because Pos(l) × Pos(s) is finite. Its multiset extension to (p s,ω δ t)∈E (δ, ω) decreases at each application of T g -Matching rules.

Secondly, proving the local confluence is trivial because there is no interference between the rules. When two rules r 1 and r 2 can be applied on a subject t, we obtain the same result t when applying r 1 followed by r 2 or r 2 followed by r 1 . As T g -Matching terminates, local confluence implies convergence.

Definition 17 (Rewriting algorithm). Given t ∈ T g (F) and l, r ∈ T g (F, X ):

l and r are both linear.

we denote by ω xl the position of the variable x in l.

t is rewritten into t by the rule l → r if:

1. there exists a position ω such that the rule can be applied to t (following the Definition 16),

2. t = ṫ, ṙ [1 ω 2] |1 , where
, is a fresh binary symbol, ṫ corresponds to t where every path towards the position 1 ω has been replaced by a path towards the position 2, ṙ is the ground term corresponding to r in which the occurrence of a variable x (whose position is denoted by ω xr ) is replaced by the path ω xr -2 deref( ṫ, r , 1 ω ω xl ) .

In this algorithm, no substitution is explicitly computed. Instead, the righthand side of the rule is instantiated by replacing every variable by paths to their corresponding subterm in t |ω . The binary symbol , enables to connect it with the global subject in a valid referenced term ṫ, ṙ . By swapping the redex and the right-hand side of the rule in ṫ, ṙ [1 ω 2] , the substitution is automatically applied. The main subtlety of the algorithm is to rebalance the whole term using normalization. All the shared subterms in t |ω that must be conserved are moved to the term and the unused part is left in the right part of ṫ, ṙ [1 ω 2] . At the end, the result of the rewrite step corresponds exactly to the left child of ṫ, ṙ

[1 ω 2] .
The complexity of the rewriting step is linear in the size of the global subject because the complexity of the swapping and the normalization are linear.

Example 11. Suppose we want to apply the rule f (x, y) → f (y, x) on the subject t = f (a, b). The rule is applied at top-position, therefore we have

ω xl = 1, ω yl = 2, ω xr = 2, ω yr = 1, ṫ = f (a, b) and ṙ = f ( ω yr -2 (1 ω yl ) , ω xr -2 (1 ω xl ) ) = f (-1 -2 1 2, -2 -2 1 1). Starting from f (a, b), ṙ , we get f (a, b), ṙ [1 2] = f (-1 -1 2 2, -2 -1 2 1), f (a, b) . When computing the canonical form, we obtain f (a, b), ṙ [1 2] = f (b, a), f (-1 -2 1 1, -2 -2 1 2) . Finally, the result is f (a, b), ṙ [1 2] |1 = f (b, a) as expected.
The following example illustrates how collapsing rules are handled. Suppose we want to apply the rule f (x) → x to the subject t = f (-1). Since -1 is a path to the top of the redex, we have ṫ = f (-1 -1 2). In a second step ṙ is evaluated to ṙ = -2 deref( f (-1 -1 2), x , 1 1) = -2 2 = and we get f (-1 -1 2), [1 2] = , f (-1 -2 1) which is already normalized. The result of the rewrite step is , f (-1 -2 1) |1 = in accordance with [START_REF] Ariola | Equational term graph rewriting[END_REF].

By applying the rule f (x, y) → x to the first subterm, this last example shows what happens to pointers to subterms that disappear: In this example, the subterm g(b) is not preserved by the rule, therefore the reference to b is replaced by a copy of the subterm.

Theorem 2. The set of ground canonical terms T g (F) is closed under rewriting.

Proof. Given a term t ∈ T g (F), we have to prove that ṫ, ṙ

[1 ω 2] |1 ∈ T g (F).
The ground term ṙ is not a valid referenced term in itself because of the references that replace variables. The term ṫ is neither valid because some paths can have been replaced by paths to the position 2. But, ṫ, ṙ is valid because invalid paths in ṫ are now referencing the top position of ṙ and invalid paths in ṙ are referencing subterms of t. Since the swapping function preserves the notion of validity, the normal form ṫ, ṙ [1 ω 2] exists. Thanks to the property of canonical referenced terms (pointers only from the right to the left), we can conclude that ṫ, ṙ

[1 ω 2] |1 ∈ T g (F).
As the main result of the paper we show in the next section that every term-graph can be represented by a canonical referenced term and that termgraph rewriting (Definition 8) can be simulated by the algorithm introduced in Definition 17.

Simulation of term-graph rewriting

We introduce a function φ that translates any valid referenced term in T vr (F, X ) into a system of recursion equations (under the same set F and X ). For this purpose, we associate to every term t ∈ T vr (F, X ) a total function ψ t from Pos(t) to X defined as follows:

ψ t (ω) =            x if symb(t |ω ) ∈ F ∪ { } where x is a fresh variable t |ω if t |ω ∈ X ψ t (ω ) if t |ω ∈ P *
where ω = deref(t, ω)

Definition 18. Given a valid referenced term t ∈ T vr (F, X ), we define its representation in systems of recursion equations by φ(t) = {α | ∆} where α = ψ t ( ) is the root, and ∆ is a set of equation defined by:

∆ = {β = f (β 1 , . . . , β n ) | ω ∈ Pos(t), β = ψ t (ω), β i = ψ t (ω i), symb(t |ω ) = f ∈ F, arity(f ) = n} ∪ {γ = • | ω ∈ Pos(t), γ = ψ t (ω), symb(t |ω ) = }
φ can be naturally extended to rules: φ(l → r) = φ(l) → φ(r).

Note that the equational representations of two equivalent valid referenced terms are equal modulo renaming. Moreover, the φ function is surjective so every system of recursion equations has an unique representation in T g (F, X ).

Theorem 3 (Rewrite step simulation). Given a canonical referenced term t ∈ T g (F) and a rule R, we have:

t → R t ⇔ φ(t) → φ(R) φ(t )
Proof. The proof is in the Appendix B.

Theorem 3 shows how to simulate term-graph rewriting using term-rewriting and provides a technique for easily extending rule-based languages with termgraphs and more generally with a notion of pointers.

Acyclic term graphs are widely used to obtain efficient term rewriting implementation [START_REF] Hoffmann | Implementing term rewriting by jungle evaluation[END_REF]. On the contrary, our goal is not to improve the efficiency of term-rewriting engines but to offer a support for graph structure manipulation. The main objective of such extensions is to perform static analysis by rewriting control flow graphs or data-structures with pointers.

Related work

The notion of term graph has been intensively studied in the literature, in particular in [START_REF] Barendregt | Term graph rewriting[END_REF], where a restricted form of acyclic term-graph has been used to represent terms with sharing. There is also a rich literature on modeling functional languages [START_REF] Benaissa | Modeling sharing and recursion for weak reduction strategies using explicit substitution[END_REF][START_REF] Ariola | Cyclic lambda calculi[END_REF][START_REF] Ariola | Skew confluence and the lambda calculus with letrec[END_REF]. This approach leads to efficient implementations of functional languages or term rewriting engines, as in Clean, Elan, or Maude.

We are in a dual situation: we already have a very efficient term rewriting engine. This implementation is based on the notion of maximally shared terms, internally represented by acyclic graphs. Such a representation is purely functional and does not allow any side effect. This constraint makes the implementation of graphs and term-graphs difficult. The contribution of the paper is to provide a solution to represent and transform graphs in a functional environment. In addition to reuse efficient term structures, a main advantage of using a classical underlying term representation is to make possible the reuse of the notion of term rewriting strategy [START_REF] Kirchner | Strategic rewriting[END_REF][START_REF] Visser | Stratego: A language for program transformation based on rewriting strategies. System description of Stratego 0.5[END_REF] which allows control over how rules are applied.

The extension to cyclic term-graph rewriting has been studied and in particular linked up with rational term rewriting [START_REF] Corradini | cyclic) term graph rewriting is adequate for rational parallel term rewriting[END_REF][START_REF] Corradini | Rational term rewriting[END_REF]. Especially, a mapping from cyclic term-graph rewriting to rational parallel term rewriting can be defined. In this context, it is often difficult to deal with graph homomorphism. In this work, we choose to simulate term-graph rewriting as defined in [START_REF] Ariola | Equational term graph rewriting[END_REF] and to favor practical aspects. In this formalism, the matching corresponds to functional bisimulation. As a consequence, the pattern g(-1) cannot be matched with the subject g(g(-1 -1)) at the root position even if they both represent the same infinite term g(g(g(. . .))).

Moreover, the set of valid referenced terms where references are not interpreted as sharing but as oriented pointers (Definition 6) is to our knowledge a new approach that can be interesting to study and simulate object-oriented languages [START_REF] Dougherty | Addressed term rewriting systems: Application to a typed object calculus[END_REF][START_REF] Echahed | Narrowing data-structures with pointers[END_REF]. For example, it could be used to model garbage collection algorithms. In the context of term-graph rewriting, an original approach is the formalism presented in [START_REF] Echahed | Narrowing data-structures with pointers[END_REF] where the right-hand side of the rules consists in a set of actions on the pointers. The work presented in this paper is a first step towards an implementation of such a formalism.

Integration in a rewrite environment: the Tom language

As canonical referenced terms are terms, it is possible to extend in a nonintrusive way any rule-based language in order to support term-graph rewriting. The presented formalism is implemented in Tom and thus directly available at http://tom.loria.fr.

For now, it is possible to automatically generate from a signature the extended version for referenced terms where the normalization is integrated. As the Tom terms are implemented with maximal sharing, so are the term-graphs. This part of the implementation is presented in [START_REF] Balland | Term-graph rewriting in tom using relative positions[END_REF]. All the operations on paths have been also implemented. Thus users can define a system of term-graph rules and it is automatically compiled in a basic Tom strategy based on the rewriting algorithm (Definition 17). These term-graph rewriting rules can then be integrated in a more complex strategy using Tom strategy combinators. As a consequence, all Tom features are available for term-graphs.

Conclusion

We have generalized the notion of term positions with term paths that are closely related to the notion of path in graphs and to the concept of de Bruijn indices [START_REF] De Bruijn | Lambda calculus notation with nameless dummies. a tool for automatic formula manipulation with application to the church-rosser theorem[END_REF]. By extending a signature with paths we obtained a new kind of terms called referenced terms which can contain pointers. This representation of pointers can be useful to model the semantics of imperative programming languages for instance.

In the second part of the paper, we introduced canonical referenced terms to represent term-graphs. As in the case of de Bruijn indices, the interest of this representation is to avoid problems of alpha conversion, compared to representations with labels or variables. Another advantage is that contrary to a recursion equation, the hierarchical structure of the term-graph is explicit because of its term representation. The last contribution of the paper is an original algorithm that simulates cyclic term-graph rewriting using canonical referenced terms. Thanks to pointers, the substitution can be applied in an unusual way, using swapping between the redex and the right-hand side of the rule.

To conclude, this formalism opens promising perspectives in terms of program transformation and code analysis. To the best of our knowledge, the integration in the Tom language constitutes actually one of the most active and maintained implementation of term-graph rewriting and thus provides a solid platform to experiment graph transformations in a concise and expressive way.

A Proof of convergence for the Definition 15

We have to prove termination and confluence. The termination property is trivial because of the total order on positions and of the fact that valid addressed terms do not contain pointers to pointers. Consider the multiset {deref(t, ω) | t |ω ∈ P} composed of the pointed positions and the order on multisets (a multiset N is smaller than a multiset M if it is obtained by replacing finitely many elements of M by smaller elements). This multiset decreases strictly at each rewriting step. Indeed, after applying the rule at a given position, t |ω ∈ P and t |deref(t,ω) ∈ P. Now deref(t, deref(t, ω)) = ω and ω < P deref(t, ω). Concerning the other updated addresses, deref(t, ω) is either smaller (pointers to the swapped subterm or to subterms of it) or remains unchanged (pointers inside the subterm). Finally, the cardinality of the multiset has not evolved and each replaced element has been substituted by a smaller one so the termination is ensured.

Moreover, we will show that for the same reason, the normal form is unique. Suppose there are two distinct positions ω and ω where the rule can be applied. We denote ω 1 = deref(t, ω ) and ω 2 = deref(t, ω ). We distinguish several cases depending on the order between positions and the prefixation (noted ). Some combinations of conditions are impossible because the rule can be applied only if ω < P ω 1 and ω < P ω 2 . Moreover, each prefixation ω β implies that ω < P β. If we consider that ω < P ω , there are eight cases to consider:

ω < ω 1 < ω 2 ∧ ω 1 ω 2 ω 1 ω 2 ω < ω 2 < ω 1 ∧ ω 2 ω 1 ω 2 ω 1 ω < ω 1 < ω < ω 2 ∧    ω 1 ω ∧ ω 1 ω 2 ω 1 ω ∧ ω 1 ω 2 ω 1 ω ∧ ω 1 ω 2 ω 1 = ω 2
For each case, we can prove local confluence. We will only detail the first case ω < P ω 1 < P ω 2 ∧ ω 1 ω 2 . The other cases are analogous. ↓ ω ω1

If we start by swapping ω and ω 1 , as ω 1 ω 2 , the subterm at position ω 2 is translated to the position ω ω 2 -ω 1 and its pointer at position ω is updated. Now deref(t, ω ) = ω ω 2 -ω 1 and as ω < P ω , deref(t, ω ) < P ω , we do not need a second swapping.

If we start by swapping ω and ω 2 , ω is not updated and ω < P deref(t, ω ) = ω 1 . So we need to swap ω and ω 1 and then translate the pointer at position ω 2 to the position ω ω 2 -ω 1 which does not respect the order on positions (ω ω 2 -ω 1 < P deref(t, ω ω 2 -ω 1 ) = ω ). We need a third swapping between ω and ω ω 2 -ω 1 .

As the normalization terminates, local confluence implies convergence.

B Proof of Theorem 3

Theorem. Given a canonical referenced term t ∈ T g (F, X ) and a rule R, we have:

t → R t ⇔ φ(t) → φ(R) φ(t )
First (I), we show that the notions of matching for systems of recursion equations and canonical referenced terms are equivalent. More formally, if we denote p the left-hand side of R, we have to prove that there exists a position ω such that p t,ω t |ω ∅ reduces to ∆ by application of T g -Matching if and only if there exists a variable substitution σ such that set(σ(φ(p))) ⊆ set(φ(t)). In (II), we will show that given t and t such that t → R t , the reduction of φ(t) by φ(R) is φ(t ).

(I) (⇒) Let ω be a position ω such that p t,ω t |ω ∅ reduces to ∆, let σ be the relation {(ψ p (δ), ψ t (ω)) | (δ, ω) ∈ ∆}. It is easy to show that σ is a functional bisimulation (the notion of bisimulation is explained in Definition 3.5 of [START_REF] Ariola | Equational term graph rewriting[END_REF]):

1. σ is a function from the variables of φ(p) to the variables of φ(t) because it is a relation with the appropriate domains and codomains by definition and because every rule of T g -Matching preserves the fact that for every pairs (δ, ω 1 ) and (δ, ω 2 ) in ∆, ψ t (ω 1 ) = ψ t (ω 2 ), 2. the first step of rewriting ensures that ( , ω) ∈ ∆ so the root of σ(p) is in relation with the root of the matched subterm ψ t (ω), 3. the condition about congruence is respected due to the rule Decompose and because every pair of positions that appeared in a constraint has been added in ∆ when the normal form has been reached.

As a consequence we have set(σ(φ(p))) ⊆ set(φ(t)).

(⇐) We now consider that there exists a variable substitution σ such that set(σ(φ(p))) ⊆ set(φ(t)). We need to show that there exists a position ω such that p t,ω t |ω ∅ reduces to ∆ by application of T g -Matching. Let ω be the position such that symb(t |ω ) ∈ F and ψ t (ω) = root(σ(φ(p))). By construction of ψ t and φ t , ω exists and is unique.

To show that any reduction of p t,ω t |ω ∅ leads to , we show that if the conjunction of matching constraints E is not reduced to , there is a rule of T g -Matching that can be applied. Since T g -Matching is convergent, is the normal form. Thanks to the convergence property proved in the Proposition 4, we can choose any strategy, in particular the one that consists in selecting the matching constraints which have the smallest δ according to < P . The considered matching constraint is unique because at each rewriting step, the conjunction E contains matching constraints with distinct δ. We now consider two invariants that are used to show the expected result:

-Inv1: ∀δ, ω (δ, ω) ∈ ∆ ∪ Γ ⇒ (ψ p (δ), ψ t (ω)) ∈ σ,
where Γ is the set of pairs (δ , ω ) that appear in the matching constraints of E -Inv2: for every position δ ∈ Pos(p) smaller than the smallest position δ in E, ∃ω such that (δ , ω ) ∈ ∆

It is easy to show that Inv1 and Inv2 are invariant: they are true for the initial term p t,ω t |ω ∅ and they are maintained by every rewrite step, for the considered strategy. Now, we show that at each step of the derivation, a rule of T g -Matching can be applied. When considering the matching constraint p t,ω δ t , we can distinguish four cases:

1. symb(p ) ∈ F ∪ { } and symb(t ) ∈ F ∪ { }. In this case, symb(p ) = symb(t ) because due to the invariant Inv1, (ψ p (δ), ψ t (ω)) ∈ σ and as the substitution is a bisimulation, the property about congruence is respected. Decompose can be applied, 2. symb(p ) ∈ X . We can apply the rule Variable, 3. symb(t ) ∈ P * . We can apply the rule Dereferencing, 4. symb(p ) ∈ P * and symb(t ) ∈ F∪{ }. We need to show that ( δ symb(π) , ω) ∈ ∆ to apply the rule Stability. Thanks to Inv2 and as δ symb(π) < P δ due to the Definition 13, there exists a pair ( δ symb(π) , ω ) ∈ ∆. This pair is in ∆ means that one of the four rules has been applied. Due to the Definition 13, we know that symb(p | δ symb(π) ) ∈ F ∪ { }. Moreover, as (ψ p (δ), ψ t (ω)) ∈ σ (Inv1) and ψ p ( δ symb(π) ) = ψ p (δ) by definition of ψ, we know that (ψ p ( δ symb(π) ), ψ t (ω)) ∈ σ. As σ is a function, we have ψ t (ω ) = ψ t (ω). There are two cases:

the rule Decompose has been applied so symb(t |ω ) ∈ F. As symb(t |ω ) ∈ F and ψ t (ω ) = ψ t (ω), ω = ω. the rule Dereferencing has been applied so the rule Decompose has been applied with the pair ( δ symb(π) , ω) and thus belongs to ∆.

T g -Matching is convergent. With the considered strategy, a matching constraint can always be reduced by a rule of T g -Matching. Therefore, the resulting normal form is . First φ( ṫ, ṙ ) can be expressed as {α | ∆} where ∆ = {α = α t , α } ∪ set(φ (t)) ∪ set(σ (φ(r))). Let α be a fresh variable, φ (t) corresponds to φ(t) where the equation α = t is replaced by α = t and if there exists a position β and a positive integer i such that ω = β i, the equation ψ t (β) = f (. . . , α, . . .) is replaced by ψ t (β) = f (. . . , α , . . .). Now, we need to interpret the swapping operation in the context of equation systems. From the definitions of swapping and translation (Definitions 14 and 9), it is possible to derive φ(t [ω1 ω2] ) from φ(t). Indeed, the swapping just consists in exchanging two subterms in t. φ(t [ω1 ω2] ) is defined by:

root(t [ω1 ω2] ) = root(t), set(φ(t [ω1 ω2] )) is set(φ(t)) where the equation β 1 = f (. . . , α 1 , . . .) is replaced by β 1 = f (. . . , α 2 , . . .) and the equation β 2 = f (. . . , α 2 , . . .) is replaced by β 2 = f (. . . , α 1 , . . .). α 1 , α 2 , β 1 , β 2 are respectively ψ t (ω 1 ), ψ t (ω 2 ), ψ t (π 1 ), ψ t (π 2 ) where ω 1 = π 1 i, ω 2 = π 2 j and i, j ∈ N * .

By applying the swapping operation, we get φ( ṫ, ṙ [ω1 ω2] ) = {α | {α = α t , α } ∪ (φ(t) \ {α = τ }) ∪ {α = τ } ∪ σ (φ(r))}. As two equivalent valid referenced terms have the same representation by φ, we have φ( ṫ, ṙ [ω1 ω2] ) = φ( ṫ, ṙ [ω1 ω2] ). In general, φ(t |ω ) = {ψ t (ω) | ∆} where ∆ corresponds to the subset of set(φ(t)) of bounded variables reachable from ψ t (ω). In our case ω = 1, and thus the root is α t . In addition, since there is no pointer to α and α , we can suppress their corresponding equations and we finally obtain φ(t ) = φ( ṫ, ṙ [ω1 ω2] |1 ) = φ( ṫ, ṙ [ω1 ω2] |1 ) = {α t | (set(φ(t)) \ {α = τ }) ∪ set(σ (φ(r)))} where equations corresponding to bounded variables unreachable from α t have been cleaned. This shows that given t and t such that t → R t , the reduction of φ(t) by φ(R) is φ(t ).

(

  II) According to Definition 17, we have t = ṫ, ṙ [1 ω 2] |1 , where r is the righthand side of R. We want to show that for the system of recursion equations L such that φ(t) → φ(R) L and ψ t (ω) = root(σ(φ(p))) we have L = φ(t ). According to Definition 8, we have L = {α t | (set(φ(t)) \ {α = τ }) ∪ set(σ (φ(r)))}, where α t = root(φ(t)), α = root(σ(φ(p))).

Acknowledgments: We are extremely grateful to Claude Kirchner who has been strongly involved in this work. He greatly contributed to the foundations of the paper. We also sincerely thank Rachid Echahed and Joe Wells for fruitful exchanges and remarks about preliminary versions of this work.


Frédéric Butin
email: butin@math.univ-lyon1.fr

HOCHSCHILD COHOMOLOGY OF KLEIN SURFACES

Keywords: cohomology, Hochschild, Klein surfaces, Gröbner bases, quantization, star-products

Given a mechanical system (M, F(M )), where M is a Poisson manifold and F(M ) the algebra of regular functions on M , it is important to be able to quantize it, in order to obtain more precise results than through classical mechanics. An available method is the deformation quantization, which consists in constructing a star-product on the algebra of formal power series F(M ) [[ ]]. A first step toward study of star-products is the calculation of Hochschild cohomology of F(M ). The aim of this article is to determine this Hochschild cohomology in the case of singular curves of the planeso we rediscover, by a different way, a result proved by Fronsdal and make it more precise -and in the case of Klein surfaces. The use of a complex suggested by Kontsevich and the help of Gröbner bases allow us to solve the problem.

Résumé

Etant donné un système physique (M, F(M )), où M est une variété de Poisson et F(M ) l'algèbre des fonctions régulières sur M , il est important de pouvoir le quantifier pour obtenir des résultats plus corrects que ceux donnés par la mécanique classique. Une solution est fournie par la quantification par déformation qui consiste à construire un star-produit sur l'algèbre des séries formelles F(M ) [[ ]]. Un premier pas vers l'étude des star-produits est le calcul de la cohomologie de Hochschild de F(M ). Le but de l'article est de déterminer cette cohomologie de Hochschild dans le cas des courbes singulières du plane -on précise ainsi, par une démarche différente, un résultat démontré par Fronsdal -et dans le cas des surfaces de Klein. L'utilisation d'un complexe proposé par Kontsevich et l'emploi des bases de Gröbner permettent de résoudre le problème.

1 Introduction

Deformation quantization

We consider a mechanical system given by a Poisson manifold M , endowed with a Poisson bracket {•}. In classical mechanics, we study the (commutative) algebra F (M ) of regular functions (ie, for example, C ∞ , holomorphic or polynomial) on M , that is to say the observables of the classical system. But quantum mechanics, where the physical system is described by a (non commutative) algebra of operators on a Hilbert space, gives more correct results than its classical analogous. Hence the importance to get a quantum description of the classical system (M, F (M )) : such an operation is called a quantization. One option is geometric quantization, which allows to construct in an explicit way a Hilbert space and an algebra of operators on this space. This very interesting method presents the drawback of being seldom applicable. That's why have been introduced other methods such as asymptotic quantization and deformation quantization. The latter, described in 1978 by F. Bayen, M. Flato, C. Fronsdal, A. Lichnerowicz and D. Sternheimer in the article [START_REF] Bayen | Deformation theory and quantization. I and II. Physical applications[END_REF], is a good alternative : instead of an algebra of operators on a Hilbert space, a formal deformation of F (M ). This is given by the algebra of formal power series F (M )[[ ]], endowed with some associative, but not commutative, star-product :

f * g = ∞ j=0 m j (f, g) j (1)
where the maps m j are bilinear and where m 0 (f, g) = f g. Then quantization is given by the map f → f , where the operator f satisfies f (g) = f * g.

In which cases does a Poisson manifold admit such a quantization ? The answer was given by Kontsevich in his article [K97] : in fact he constructed a star-product on every Poisson manifold. Besides he proved that if M is a smooth manifold, then the equivalence classes of formal deformations of the zero Poisson bracket are in bijection with equivalence classes of star-products. Moreover, as a consequence of Hochschild-Kostant-Rosenberg theorem, every abelian star-product is equivalent to a trivial one.

In the case where M is a singular algebraic variety, say

M = {z ∈ C n / f (z) = 0}
with n = 2 or 3, where f belongs to C[z] -and this is the case which we shall study -we shall consider the algebra of functions on M , ie the quotient algebra C[z] / f . So the above mentioned result is no more valid. However, the deformations of the algebra F (M ), defined by the formula (1), are always classified by the Hochschild cohomology of F (M ), and we are led to the study of the Hochschild cohomology of C[z] / f .

Cohomologies and quotients of polynomial algebras

We shall now consider R = C[z 1 , . . . , z n ] = C[z] the polynomial algebra with complex coefficients and n variables. We also fix m elements f 1 , . . . , f m of R, and we define the quotient algebra

A := R / f 1 , . . . , f m = C[z 1 , . . . , z n ] / f 1 , . . . , f m .
Several articles were devoted to the study of particular cases, for Hochschild as well as for Poisson cohomology :

C. Roger and P. Vanhaecke, in the article [START_REF] Roger | Poisson cohomology of the affine plane[END_REF], consider the case where n = 2 and m = 1, and where f 1 is an homogeneous polynomial. They calculate Poisson cohomology in terms of the number of irreducible components of the singular locus {z ∈ C 2 / f 1 (z) = 0} (in this case, we have a symplectic structure outside the singular locus).

M. Van den Bergh and A. Pichereau, in the articles [START_REF] Van Den Bergh | Noncommutative homology of some three-dimensional quantum spaces[END_REF], [P05] and [P06], are interested in the case where n = 3 and m = 1, and where f 1 is a weighted homogeneous polynomial with an isolated singularity at the origin. They compute the Poisson homology and cohomology, which in particular can be expressed in terms of the Milnor number of the space

C[z 1 , z 2 , z 3 ] / ∂ z1 f 1 , ∂ z2 f 1 , ∂ z3 f 1 (the definition of this number is given in [AVGZ86]).
Once more in the case where n = 3 and m = 1, in the article [AL98], J. Alev and T. Lambre compare the Poisson homology in 0 degree of Klein surfaces with the Hochschild homology in 0 degree of A 1 (C) G , where A 1 (C) is the Weyl algebra and G the group associated to the Klein surface. We shall give more details about those surfaces in section 4.1.

C. Fronsdal studies in the article [START_REF] Fronsdal | avec un appendice de Maxim Kontsevich[END_REF] Hochschild homology and cohomology in two particular cases : the case where n = 1 and m = 1, and the case where n = 2 and m = 1. Besides, the appendix of this article gives another way to calculate the Hochschild cohomology in the more general case of complete intersections.

In this paper, we propose to calculate the Hochschild cohomology in two particularly important cases : the case of the singular curves of the plane, with polynomials f 1 which correspond to their normal forms (this case already held C. Fronsdal's attention) ; and the case of Klein surfaces X Γ which are the quotients C 2 / Γ, where Γ is a finite subgroup of SL 2 C (this case corresponds to n = 3 and m = 1). These latter have been the subject of many works ; their link with the finite subgroups of SL 2 C, with the Platonic polyhedra, and with McKay correspondence explain this large interest. Moreover, the preprojective algebras, to which the article [START_REF] Crawley-Boevey | Noncommutative Deformations of Kleinian Singularities[END_REF] is devoted, constitute a family of deformations of the Klein surfaces, parametered by the group which is associated to them : this fact justifies once again the calculation of their cohomology.

The main result of the article is given by two propositions :

Proposition 1 Let be a singular curve of the plane, defined by a polynomial

f 1 ∈ C[z], of the type A k , D k or E k . Then H 0 ≃ C[z] / f 1 , H 1 ≃ C[z] / f 1 ⊕ C k , and for all j ≥ 2, H j ≃ C k . Proposition 2 Let Γ be a finite subgroup of SL 2 C and f 1 ∈ C[z] such that C[x, y] Γ ≃ C[z] / f 1 . Then H 0 ≃ C[z] / f 1 , H 1 ≃ ∇f 1 ∧ (C[z] / f 1 ) 3 ⊕ C µ , H 2 ≃ C[z] / f 1 ⊕ C µ ,
and for all j ≥ 3, H j ≃ C µ , where µ is the Milnor number of X Γ .

For explicit computations, we shall use methods suggested by M. Kontsevich in the appendix of [START_REF] Fronsdal | avec un appendice de Maxim Kontsevich[END_REF] ; we will develop a little bit that method.

We will first study the case of singular curves of the plane in section 3 : we will use this method to rediscover the result that C. Fronsdal proved by direct calculations. Then we will refine it by determining the dimensions of the cohomology spaces by means of the multivariate division and of the Gröbner bases. Next, in section 4, we will consider the case of Klein surfaces X Γ . We will first prove that H 0 identifies with the space of polynomial functions on the singular surface X Γ . We will then prove that H 1 and H 2 are infinite-dimensional. We will also determine, for j greater or equal to 3, the dimension of H j , by showing that it is equal to the Milnor number of the surface X Γ . Now, section 1.3 will recall important classical results about deformations.

Hochschild cohomology and deformations of algebras

• Given an associative C-algebra, denoted by A, the Hochschild complex of A is the following

C 0 (A) d0 / / C 1 (A) d1 / / C 2 (A) d2 / / C 3 (A) d3 / / C 4 (A) d4 / / . . .
where the space C p (A) of p-cochains is defined by C p (A) = 0 for p ∈ -N * , C 0 (A) = A and ∀ p ∈ N * , C p (A) = L(A ⊗p , A), where L(A ⊗p , A) defines the space of C-linear maps from A ⊗p to A, and where differential d = ∞ i=0 d p is given by

∀ f ∈ C p (A), d p f (a 0 , . . . , a p ) = a 0 f (a 1 , . . . , a p )- p-1 i=0
(-1) i f (a 0 , . . . , a i a i+1 , . . . , a p )+(-1) p-1 f (a 0 , . . . , a p-1 )a p .

We can write it in terms of Gerstenhaber bracket [•] G as follows :

d p f = (-1) p+1 [µ, f ] G ,
where µ is the product of the algebra A, and [•] G the Gerstenhaber brachet.

Then we define the Hochschild cohomology of A as the cohomology of the Hochschild complex associated to A. We note HH 0 (A) = Ker d 0 and ∀ p ∈ N * , HH p (A) = Ker d p / Im d p-1 .

• We denote by

C[[ ]] (resp. A[[ ]]
) the algebra of formal power series in the parameter , with coefficients in C (resp. A). A deformation of the algebra A is defined as a map

m from A[[ ]] × A[[ ]] to A[[ ]] which is C[[ ]]
-bilinear and such that

∀ (s, t) ∈ A[[ ]] 2 , m(s, t) ≡ st mod A[[ ]], ∀ (s, t, u) ∈ A[[ ]] 3 , m(s, m(t, u)) = m(m(s, t), u).
This means that there exists a sequence of bilinear maps m j from A × A to A of which the first term m 0 is the product of A and such that

∀ (a, b) ∈ A 2 , m(a, b) = ∞ j=0 m j (a, b) j , ∀ n ∈ N, i+j=n m i (a, m j (b, c)) = i+j=n m i (m j (a, b), c), that is to say i+j=n m i • m j = 0,
by using the notation • for the Gerstenhaber product. We talk about deformation of order p if the previous formula is satisfied (only) for n ≤ p. Two deformations m and m ′ of A are called equivalent if there exists a C

[[ ]]-automorphism of A[[ ]], denoted by ϕ, such that ∀ (s, t) ∈ A[[ ]] 2 , ϕ(m(s, t)) = m ′ (ϕ(s), ϕ(t)) ∀ s ∈ A[ ], ϕ(s) ≡ s mod A[[ ]],
that is to say if there exists a sequence of linear maps ϕ j from A to A of which the first term ϕ 0 is the identity of A and such that

∀ a ∈ A, ϕ(a) = ∞ j=0 ϕ j (a) j , ∀ n ∈ N, i+j=n ϕ i (m j (a, b)) = i+j+k=n m ′ i (ϕ j (a), ϕ k (b)).
• One of the advantages of Hochschild cohomology is its classification of deformations of the algebra A.

In fact, if π ∈ C 2 (A), we can construct a first order deformation m of A such that m 1 = π if and only if π ∈ Ker d 2 . Moreover, two first order deformations are equivalent if and only if their difference is an element of Im d 1 . So the set of classes of first order deformations is in bijection with HH 2 (A).

If m is a deformation of order p, then we can extend m to a deformation of order p + 1 if and only if there exists m p+1 such that

∀ (a, b, c) ∈ A 3 , p i=1 (m i (a, m p+1-i (b, c)) -m i (m p+1-i (a, b), c)) ωp(a, b, c) = -d 2 m p+1 (a, b, c), ie p i=1 m i • m p+1-i = d 2 m p+1 .
But ω p belongs to Ker d 3 , as an easy computation shows, so HH 3 (A) contains the obstructions to extend a deformation of order p to a deformation of order p + 1.

Presentation of the Koszul complex

We recall in this section some results about the Koszul complex used in the following and which are given in the appendix of the article [START_REF] Fronsdal | avec un appendice de Maxim Kontsevich[END_REF].

Kontsevich theorem and notations

• As indicated in section 1.2, we consider R = C[z] and (f 1 , . . . , f m ) ∈ R m , and we note A = R / f 1 , . . . , f m . We suppose that there is a complete intersection, ie the dimension of the solution set of the system

{f 1 = • • • = f m = 0} is n -m.
• We also define the super-commutative super-algebra

A = R ⊗ {α j , j = 1 . . . m} = C[z 1 , . . . , z n , α 1 , . . . , α m ].
Then we introduce η i = ∂ ∂zi and b j = ∂ ∂αj . We denote the even variables by roman letters and the odd variables by greek letters.

• We consider the differential graded algebra

T = A[η 1 , . . . , η n , b 1 , . . . , b m ] = C[z 1 , . . . , z n ] f 1 , . . . , f m [η 1 , . . . , η n , b 1 , . . . , b m ],
endowed with the differential

d T = n j=1 m i=1 ∂f i ∂z j b i ∂ ∂η j
and the Hodge grading, defined by deg

(z i ) = 0, deg(η i ) = 1, deg(α j ) = -1, deg(b j ) = 2.
Then we can set forth the main theorem which allows us the calculation of the Hochschild cohomology :

Theorem 3 (Kontsevich)
Under the previous assumptions, the Hochschild cohomology of A is isomorphic to the cohomology of the complex ( T , d T ) associated to the differential graded algebra T .

Remark 4

Theorem 3 can be seen as a generalization of Hochschild-Kostant-Rosenberg theorem to the case of nonsmooth spaces.

• There is no element of negative degree. So the complex is as follows :

T (0) 0 / / T (1) d (1) T / / T (2) d (2) T / / T (3) d (3) T / / T (4) d (4) T / / . . .
For each degree p, we choose a basis B p of T (p). For example for p = 0 . . . 3, let's take :

T (0) = A T (1) = Aη 1 ⊕ • • • ⊕ Aη n T (2) = Ab 1 ⊕ • • • ⊕ Ab m ⊕ i<j A η i η j T (3) = i=1...m j=1...n A b i η j ⊕ i<j<k A η i η j η k
Then we can make matrices M at Bp, Bp+1 (d

(p) T ) explicit. • We note p : C[z] → A = C[z]/ f 1 , . . . , f m the canonical projection.
For each ideal J of C[z], we denote by J A the image of this ideal by the canonical projection.

Similarly if (g 1 , . . . , g r ) ∈ A r we denote by g 1 , . . . , g r A the ideal of A generated by (g 1 , . . . , g r ).

Besides, if g ∈ C[z], and if J is an ideal of C[z], then we note

Ann J (g) := {h ∈ C[z] / hg = 0 mod J}.
In particular, g doesn't divide 0 in C[z]/J if and only if Ann J (g) = J.

We deduce

H 0 = A, H 1 = {g 1 η 1 / g 1 ∈ A and g 1 ∂ z1 f 1 = 0} and ∀ p ∈ N * , H 2p = Ab p 1 {g 1 (∂ z1 f 1 )b p 1 / g 1 ∈ A}
, and

H 2p+1 = {g 1 b p 1 η 1 / g 1 ∈ A and g 1 ∂ z1 f 1 = 0}. • Now if f 1 = z k 1 , then H 0 = A = C[z 1 ] / z k 1 ≃ C k-1 H 1 = {g 1 η 1 / g 1 ∈ A and kg 1 z k-1 1 = 0} ≃ C k-1 and ∀ p ∈ N * , H 2p = Ab p 1 {g 1 (kz k-1 1 )b p 1 / g 1 ∈ A} ≃ C k-1
and

H 2p+1 = {g 1 b p 1 η 1 / g 1 ∈ A and kg 1 z k-1 1 = 0} ≃ C k-1 . 3 Case n = 2, m = 1.
-singular curves of the plane

Description of the cohomology spaces

With the help of theorem 3 we calculate the Hochschild cohomology of A. We begin by making cochains and differentials explicit.

• The various spaces of the complex are given by

T (0) = A T (5) = Ab 2 1 η 1 ⊕ Ab 2 1 η 2 T (1) = Aη 1 ⊕ Aη 2 T (6) = Ab 3 1 ⊕ Ab 2 1 η 1 η 2 T (2) = Ab 1 ⊕ Aη 1 η 2 T (7) = Ab 3 1 η 1 ⊕ Ab 3 1 η 2 T (3) = Ab 1 η 1 ⊕ Ab 1 η 2 T (8) = Ab 4 1 ⊕ Ab 3 1 η 1 η 2 T (4) = Ab 2 1 ⊕ Ab 1 η 1 η 2 T (9) = Ab 4 1 η 1 ⊕ Ab 4 1 η 2 , ie, in the generic case, T (2p) = Ab p 1 ⊕ Ab p-1 1 η 1 η 2 and T (2p + 1) = Ab p 1 η 1 ⊕ Ab p 1 η 2 .
We have

∂ ∂η k (η k ∧ η l ) = 1 ∧ η l = -η l ∧ 1, hence d (2) T (η k η l ) = -∂f1 ∂z k b 1 η l + ∂f1 ∂z l b 1 η k . From now on, we note ∂ ∂z j = ∂ zj = ∂ j .
The matrices of d T are therefore given by M at B2p,B2p+1 (d

(2p) T ) = 0 ∂ 2 f 1 0 -∂ 1 f 1 M at B2p+1,B2p+2 (d (2p+1) T ) = ∂ 1 f 1 ∂ 2 f 1 0 0 .
• We deduce a simpler expression for the cohomology spaces :

H 0 = A H 1 = {g 1 η 1 + g 2 η 2 / (g 1 , g 2 ) ∈ A 2 and g 1 ∂ 1 f 1 + g 2 ∂ 2 f 1 = 0} ≃ g = g 1 g 2 ∈ A 2 / g • ∇f 1 = 0 ∀ p ∈ N * , H 2p = {g1b p 1 +g2b p-1 1 η1η2 / (g1, g2)∈A 2 and g2 ∂1f1=g2 ∂2f1=0} {(g1 ∂1f1+g2 ∂2f1)b p 1 / (g1, g2)∈A 2 } ≃    g=   g 1 g 2   ∈A 2 / g2 ∂1f1=g2 ∂2f1=0         g • ∇f 1 0   / g∈A 2    ≃ A ∂1f1, ∂2f1 A ⊕ {g ∈ A / g ∂ 1 f 1 = g ∂ 2 f 1 = 0} H 2p+1 = {g1b p 1 η1+g2b p 1 η2 / (g1, g2)∈A 2 and g1 ∂1f1+g2 ∂2f1=0} {g2(∂2f1b p 1 η1-∂1f1b p 1 η2) / g2∈A} ≃    g=   g 1 g 2   ∈A 2 / g•∇f1=0       g2   ∂ 2 f 1 -∂ 1 f 1   / g2∈A    .
It remains to determine these spaces more explicitly. It will be done in the two following sections.

3.2 Explicit calculations in the particular case where f 1 has separate variables

In this section, we consider the polynomial

f 1 = a 1 z k 1 + a 2 z l 2 , with 2 ≤ l ≤ k and (a 1 , a 2 ) ∈ (C * ) 2 . The partial derivative of f 1 are ∂ 1 f 1 = ka 1 z k-1 1 and ∂ 2 f 1 = la 2 z l-1 2 .
• We already have

H 0 = C[z 1 , z 2 ]/ a 1 z k 1 + a 2 z l 2 .
• Besides, as f 1 is of homogeneous weight, Euler's formula gives

1 k x 1 ∂ 1 f 1 + 1 l x 2 ∂ 2 f 1 = f 1 . So we have the inclusion f 1 ⊂ ∂ 1 f 1 , ∂ 2 f 1 , hence A ∂z 1 f1, ∂z 2 f1 A ≃ C[z1, z2] ∂z 1 f1, ∂z 2 f1 ≃ V ect z i 1 z j 2 / i ∈ 0, k -2 , j ∈ 0, l -2 . But ∂ 1 f 1 and f 1 are relatively prime, just as ∂ 2 f 1 and f 1 are, hence if g ∈ A satisfies g∂ 1 f 1 = 0 mod f 1 , then g ∈ f 1 , ie g is zero in A. So, H 2p ≃ V ect z i 1 z j 2 / i ∈ 0, k -2 , j ∈ 0, l -2 ≃ C (k-1)(l-1)
.

• Now we determine the set g =

g 1 g 2 ∈ A 2 / g • ∇f 1 = 0 : First we have f 1 , ∂ 1 f 1 = a 1 z k 1 + a 2 z l 2 , z k-1 1 = z l 2 , z k-1 1
. So the only monomials which are not in this ideal are the elements z i 1 z j 2 with i ∈ 0, k -2 and j ∈ 0, l -1 . Every polynomial P ∈ C[z] can be written in the form

P = αf 1 + β∂ 1 f 1 + i=0...k-2 j=0...l-1 a ij z i 1 z j 2 .
The polynomials

P ∈ C[z] such that P ∂ 2 f 1 ∈ f 1 , ∂ 1 f 1 are hence the elements P = αf 1 + β∂ 1 f 1 + i=0...k-2 j=1...l-1 a ij z i 1 z j 2 .
So we have calculated Ann f1, ∂1f1 (∂ 2 f 1 ). The equation

g • ∇f 1 = 0 mod f 1 (2) yields g 2 ∂ 2 f 1 = 0 mod f 1 , ∂ 1 f 1 , (3)
ie g 2 ∈ Ann f1, ∂1f1 (∂ 2 f 1 ), ie again

g 2 = αf 1 + β∂ 1 f 1 + i=0...k-2 j=1...l-1 a ij z i 1 z j 2 , (4) with
(α, β) ∈ C[z] 2 . It follows that g 1 ∂ 1 f 1 + αf 1 ∂ 2 f 1 + β∂ 1 f 1 ∂ 2 f 1 + i=0...k-2 j=1...l-1 a ij z i 1 z j 2 ∂ 2 f 1 ∈ f 1 . (5)
And, from the equality

z 2 ∂ 2 f 1 = lf 1 -l k z 1 ∂ 1 f 1 , one deduces : ∂ 1 f 1     g 1 + β∂ 2 f 1 - l k i=0...k-2 j=1...l-1 a ij z i+1 1 z j-1 2     ∈ f 1 . (6) ie g 1 = -β∂ 2 f 1 + l k i=0...k-2 j=1...l-1 a ij z i+1 1 z j-1 2 + δf 1 , with δ ∈ C[z].
Then we verify that the elements g 1 and g 2 obtained in this way are indeed solutions of the equation (2). Finally, we have :

g ∈ A 2 / g • ∇f1 = 0 =      α δ f1 -β ∂2f1 -∂1f1 + i=0...k-2 j=1...l-1 aij z i 1 z j-1 2 l k z1 z2 (α, β, δ) ∈ C[z] 3 and aij ∈ C      .
We immediately deduce the cohomology spaces of odd degree :

∀ p ≥ 1, H 2p+1 ≃ C (k-1)(l-1) H 1 ≃ C (k-1)(l-1) ⊕ C[z 1 , z 2 ]/ a 1 z k 1 + a 2 z l 2 .
Remark 5

We obtain in particular the cohomology for the cases where

f 1 = z k+1 1 + z 2 2 , f 1 = z 3 1 + z 4 2 and f 1 = z 3 1 + z 5
2 . These cases correspond respectively to the weight homogeneous functions of types A k , E 6 and E 8 given in [START_REF] Arnold | Singularités des applications différentiables[END_REF] p. 181.

The table below summarizes the results obtained for the three particular cases we have just obtained :

H 0 H 1 H 2p H 2p+1 A k C[z] / z k+1 1 + z 2 2 C[z] / z k+1 1 + z 2 2 ⊕ C k C k C k E 6 C[z] / z 3 1 + z 4 2 C[z] / z 3 1 + z 4 2 ⊕ C 6 C 6 C 6 E 8 C[z] / z 3 1 + z 5 2 C[z] / z 3 1 + z 5 2 ⊕ C 8 C 8 C 8
The cases where

f 1 = z 2 1 z 2 + z k-1 2
and f 1 = z 3 1 + z 1 z 3 2 , ie respectively D k and E 7 , will be studied in the next section.

Explicit calculations for D k and E 7

To study these particular cases, we use the following result about Gröbner bases (theorem 7). First, recall the definition of a Gröbner basis. For g ∈ C[z], we denote by lt(g) its leading term (for the lexicographic order). Given a non trivial ideal J of C[z], a Gröbner basis of J is a finite subset G J of J\{0} such that for all f ∈ J\{0}, there exists g ∈ G J such that lt(g) divides lt(f ).

Definition 6 1. Let J be a non trivial ideal of C[z] and G J := [g 1 , . . . , g r ] a Gröbner basis of J. A polynomial p ∈ C[z] is reduced relatively to G J if it is zero or if none of the terms of p is divisible by the leading term lt(g j ) of one of the elements of G J . 2. The set of the G J -standard terms is the set of all monomials of C[z] except the set of the leading terms lt(f ) of the polynomials f ∈ J\{0}.

Theorem 7 (Macaulay)

The set of the G J -standard terms forms a basis of the quotient vector space C[z] / J.

Case of f

1 = z 2 1 z 2 + z k-1 2 , ie D k
Here we have

f 1 = z 2 1 z 2 + z k-1 2 , ∂ 1 f 1 = 2z 1 z 2 and ∂ 2 f 1 = z 2 1 + (k -1)z k-2 2 . A Gröbner basis of the ideal f 1 , ∂ 2 f 1 is B := [b 1 , b 2 ] = [z 2 1 + (k -1)z k-2 2 , z k-1 2
]. So the set of the standard terms is{z i 1 z j 2 / i ∈ {0, 1} and j ∈ 0, k -2 }. Then we can solve the equation p ∂

1 f 1 = 0 in C[z] / f 1 , ∂ 2 f 1 .
In fact, by writing p := i=0,1j=0...k-2 a ij z i 1 z j 2 , the equation becomes

q := i=0,1j=0...k-2 a ij z i+1 1 z j+1 2 ∈ f 1 , ∂ 2 f 1 .
So we look for the normal form of the element q modulo the ideal f 1 , ∂ 2 f 1 .

The multivariate division of q by B is q = q 1 b 1 + q 2 b 2 + r with r = k-3 j=0 a 0,j z 1 z j+1 2 . Thus the solution is

p = a 0,k-2 z k-2 2 + k-2 j=0 a 1,j z 1 z j 2 .
But the equation g

• ∇f 1 = 0 mod f 1 (7) yields g 1 ∂ 1 f 1 = 0 mod f 1 , ∂ 2 f 1 , (8)
ie

g 1 = αf 1 + β∂ 2 f 1 + az k-2 2 + k-2 j=0 b j z 1 z j 2 , (9)
with (α, β) ∈ C[z] 2 and a, b j ∈ C. Hence

g 2 ∂ 2 f 1 + β∂ 1 f 1 ∂ 2 f 1 + az k-2 2 ∂ 1 f 1 + k-2 j=0 b j z 1 z j 2 ∂ 1 f 1 ∈ f 1 . (10)
And with the equalities,

z k-1 2 = 1 2 -k (f 1 -z 2 ∂ 2 f 1 ) = - 1 2 -k z 2 ∂ 2 f 1 mod f 1 , and k -2 2 z 1 ∂ 1 f 1 + z 2 ∂ 2 f 1 = (k -1)f 1 (Euler),
we obtain

∂ 2 f 1   g 2 + β∂ 1 f 1 - 2a 2 -k z 1 z 2 + k-2 j=0 b j 2 2 -k z j+1 2   ∈ f 1 . (11) ie, g 2 = -β∂ 1 f 1 + 2a 2 -k z 1 z 2 - k-2 j=0 b j 2 2 -k z j+1 2 + δf 1 , with δ ∈ C[z]. So g ∈ A 2 / g • ∇f1 = 0 =    α δ f1 + β ∂2f1 -∂1f1 + z k-2 2 2 2-k z1z2 + k-2 j=0 bj z j 2 z1 -2 2-k z2 (α, β, δ) ∈ C[z] 3 and a, bj ∈ C    .
On the other hand, a Gröbner basis of

∂ 1 f 1 , ∂ 2 f 1 is [z 2 1 + (k -1)z k-2 2 , z 1 z 2 , z k-1 2 ], thus C[z] / ∂ 1 f 1 , ∂ 2 f 1 ≃ V ect z 1 , 1, z 2 . . . , z k-2 2 .
Let's summarize,

H 0 = C[z] / z 2 1 z 2 + z k-1 2 H 1 ≃ C[z] / z 2 1 z 2 + z k-1 2 ⊕ C k H 2p ≃ C k H 2p+1 ≃ C k . 3.3.2 Case of f 1 = z 3 1 + z 1 z 3 2 , ie E 7 Here we have ∂ 1 f 1 = 3z 2 1 + z 3 2 and ∂ 2 f 1 = 3z 1 z 2 2 . A Gröbner basis of the ideal f 1 , ∂ 1 f 1 is [3z 2 1 + z 3 2 , z 1 z 3 2 , z 6 2 ]
, and a Gröbner basis of

∂ 1 f 1 , ∂ 2 f 1 is [3z 2 1 + z 3 2 , z 1 z 2 2 , z 5 2 ]
. By an analogous proof, we obtain :

H 0 = C[z] / z 3 1 + z 1 z 3 2 H 1 ≃ C[z] / z 3 1 + z 1 z 3 2 ⊕ C 7 H 2p ≃ C 7 H 2p+1 ≃ C 7 .
4 Case n = 3, m = 1. -Klein surfaces

Klein surfaces

Given a finite group G acting on C n , we associate to it, according to Erlangen program of Klein, the quotient space C n /G, ie the space whose points are the orbits under the action of G ; it is an algebraic variety, and the polynomial functions on this variety are the polynomial functions on C n which are G-invariant. In the case of SL 2 C, invariant theory allows us to associate a polynomial to any finite subgroup, as explained in proposition 9. Thus, to every finite subgroup of SL 2 C are associated the zero set of this polynomial ; it is an algebraic variety, called Klein surface.

In this section we recall some results about this surfaces. See the references [S77] and [START_REF] Chiang | Generation of Invariants[END_REF] for more details.

Proposition 8

Every finite subgroup of SL 2 C is conjugate to one of the following groups :

• A n (cyclic), n ≥ 1 (|A n | = n) • D n (dihedral), n ≥ 1 (|D n | = 4n) • E 6 (tetrahedral) (|E 6 | = 24) • E 7 (octahedral) (|E 7 | = 48) • E 8 (icosahedral) (|E 8 | = 120).

Proposition 9

Let G be one of the groups of the preceding list. The ring of invariants is the following :

C[x, y] G = C[e 1 , e 2 , e 3 ] = C[e 1 , e 2 ] ⊕ e 3 C[e 1 , e 2 ] ≃ C[z 1 , z 2 , z 3 ]/ f 1 ,
where the invariants e j are homogeneous polynomials, with e 1 and e 2 algebraically independent, and where f 1 is a weighted homogeneous polynomial with an isolated singularity at the origin. These polynomials are given in the following table.

G

e 1 , e 2 , e 3

f 1 C[z 1 , z 2 , z 3 ]/ ∂ 1 f 1 , ∂ 2 f 1 , ∂ f 1 A n e 1 = x n e 2 = y n e 3 = xy -n(z 1 z 2 -z n 3 ) V ect(1, z 1 , . . . , z n-2 3 ) dim = n -1 D n e 1 = x 2 y 2 e 2 = x 2n + (-1) n y 2n e 3 = x 2n+1 y + (-1) n+1 xy 2n+1 λn(4z n+1 1 +(-1) n+1 z1z 2 2 +(-1) n z 2 3 ) with λ n = 2n(-1) n+1 V ect(1, z 2 , z 1 , . . . , z n-1 1 ) dim = n + 1 E 6 e 1 = x 5 y -xy 5 e 2 = 14y 4 x 4 + x 8 + y 8 e 3 = 33y 8 x 4 -y 12 + 33y 4 x 8 -x 12 4(z 2 3 -z 3 2 + 108z 4 1 ) V ect(1, z 2 , z 1 , z 1 z 2 , z 2 1 , z 2 1 z ) dim = 6 E 7
e 1 = 14y 4 x 4 + x 8 + y 8 e 2 = -3y 10 x 2 + 6y 6 x 6 -3y 2 x 10 e 3 = -34x 5 y 13 -yx 17 +34y 5 x 13 +xy 17 8(3z

2 3 -12z 3 2 + z 2 z 3 1 ) V ect(1, z 2 , z 2 2 , z 1 , z 1 z 2 , z 1 z , z 2 1 ) dim = 7
E 8 e 1 = x 11 y + 11x 6 y 6 -xy 11 e 2 = x 20 -228x 15 y 5 + 494x 10 y 10 +228x 5 y 15 + y 20 e 3 = x 30 + 522x 25 y 5 -10 005x 20 y 10 -10 005x 10 y 20 -522x 5 y 25 + y 30

10(1 728z 5 1 + z 3 2 -z 2 3 ) V ect(z i 1 z j 2 ) i=0...3, j=0...1 dim = 8
We call Klein surface the algebraic hyper-surface defined by {z ∈ C 3 / f 1 (z) = 0}.

Theorem 10 (Pichereau) Consider the Poisson bracket defined on C[z 1 , z 1 , z 3 ] by

{•} f1 = ∂ 3 f 1 ∂ 1 ∧ ∂ 2 + ∂ 1 f 1 ∂ 2 ∧ ∂ 3 + ∂ 2 f 1 ∂ 3 ∧ ∂ 1 = i(df 1 )(∂ 1 ∧ ∂ 2 ∧ ∂ 3 ),
and denote by HP * f1 (resp. HP f1 * ) the Poisson cohomology (resp. homology) for this bracket. Under the previous assumptions, the Poisson cohomology HP * f1 and the Poisson homology

HP f1 * of (C[z 1 , z 1 , z 3 ]/ f 1 , {•} f1 ) is given by HP 0 f1 = C, HP 1 f1 ≃ HP 2 f1 = {0} HP f1 0 ≃ HP f1 2 ≃ C[z 1 , z 2 , z 3 ]/ ∂ 1 f 1 , ∂ 2 f 1 , ∂ 3 f 1 dim(HP f1 1 ) = dim(HP f1 0 ) -1 HP f1 j = HP j f1 = {0} si j ≥ 3. The algebra C[x, y] is a Poisson algebra for the standard symplectic bracket {•} std . As G is a subgroup of the symplectic group Sp 2 C (since Sp 2 C = SL 2 C), the invariant algebra C[x, y] G is a Poisson subalgebra of C[x, y].
Then the following proposition allows us to deduce from theorem 10 the Poisson cohomology and homology of C[x, y] G for the standard symplectic bracket.

Proposition 11

The isomorphism of associative algebras

π : (C[x, y] G , {•} std ) → (C[z 1 , z 1 , z 3 ]/ f 1 , {•} f1 ) e j → z j is a Poisson isomorphism.
Subsequently, we will calculate the Hochschild cohomology of C[z 1 , z 1 , z 3 ]/ f 1 . Then we will deduce immediately the Hochschild cohomology of C[x, y] G , with the help of the isomorphism of associative algebras π.

Description of the cohomology spaces

• In this case, we change the ordering of the basis : we shall use (η 1 η 2 , η 2 η 3 , η 3 η 1 ) instead of (η 1 η 2 , η 1 η 3 , η 2 η 3 ).

Then the different spaces of the complex are given by

T (0) = A T (1) = Aη 1 ⊕ Aη 2 ⊕ Aη 3 T (2) = Ab 1 ⊕ Aη 1 η 2 ⊕ Aη 2 η 3 ⊕ Aη 3 η 1 T (3) = Ab 1 η 1 ⊕ Ab 1 η 2 ⊕ Ab 1 η 3 ⊕ Aη 1 η 2 η 3 T (4) = Ab 2 1 ⊕ Ab 1 η 1 η 2 ⊕ Ab 1 η 2 η 3 ⊕ Ab 1 η 3 η 1 T (5) = Ab 2 1 η 1 ⊕ Ab 2 1 η 2 ⊕ Ab 2 1 η 3 ⊕ Ab 1 η 1 η 2 η 3 ie, in the general case, for p ∈ N * , T (2p) = Ab p 1 ⊕ Ab p-1 1 η 1 η 2 ⊕ Ab p-1 1 η 2 η 3 ⊕ Ab p-1 1 η 3 η 1 and T (2p + 1) = Ab p 1 η 1 ⊕ Ab p 1 η 2 ⊕ Ab p 1 η 3 ⊕ Ab p-1 1 η 1 η 2 η 3 . We have ∂ ∂η1 (η 1 ∧η 2 ∧η 3 ) = 1∧η 2 ∧η 3 = η 2 ∧η 3 ∧1, thus d (3) T (η 1 η 2 η 3 ) = ∂f1 ∂z1 b 1 η 2 η 3 + ∂f1 ∂z2 b 1 η 3 η 1 + ∂f1 ∂z3 b 1 η 1 η 2 .
The matrices of d T are therefore given by M at B1,B2 (d

(1) T ) =     ∂ z1 f 1 ∂ z2 f 1 ∂ z3 f 1 0 0 0 0 0 0 0 0 0     ∀ p ∈ N * , M at B2p,B2p+1 (d (2p) T ) =     0 ∂ z2 f 1 0 -∂ z3 f 1 0 -∂ z1 f 1 ∂ z3 f 1 0 0 0 -∂ z2 f 1 ∂ z1 f 1 0 0 0 0     ∀ p ∈ N * , M at B2p+1,B2p+2 (d (2p+1) T ) =     ∂ z1 f 1 ∂ z2 f 1 ∂ z3 f 1 0 0 0 0 ∂ z3 f 1 0 0 0 ∂ z1 f 1 0 0 0 ∂ z2 f 1     .
• We deduce

H 0 = A H 1 = {g 1 η 1 +g 2 η 2 +g 3 η 3 / (g 1 , g 2 , g 3 ) ∈ A 3 and g 1 ∂ z1 f 1 +g 2 ∂ z2 f 1 +g 3 ∂ z3 f 1 = 0} ≃    g =   g 1 g 2 g 3   ∈ A 3 / g • ∇f 1 = 0    H 2 =
{g0b1+g3η1η2+g1η2η3+g2η3η1 / (g0, g1, g2 g3)∈A 4 and g3 ∂z 2 f1-g2 ∂z 3 f1=g1 ∂z 3 f1-g3 ∂z 1 f1=g2 ∂z 1 f1-g1 ∂z 2 f1=0} {(g1 ∂z 1 f1+g2 ∂z 2 f1+g3 ∂z 3 f1)b1 / (g1, g2, g3

)∈A 3 } ≃              g=        g 0 g 1 g 2 g 3        ∈A 4 ∇f1∧     g 1 g 2 g 3     =0                   g • ∇f 1 0 3,1   / g∈A 3    ≃ A ∂z 1 f1, ∂z 2 f1, ∂z 3 f1 A ⊕ {g ∈ A 3 / ∇f 1 ∧ g = 0} ∀ p ≥ 2, H 2p = g0b p 1 +g3b p-1 1 η1η2+g1b p-1 1 η2η3+g2b p-1 1 η3η1
(g0, g1, g2 g3)∈A 4 and g3 ∂z 2 f1-g2 ∂z 3 f1=g1 ∂z 3 f1-g3 ∂z 1 f1=g2 ∂z 1 f1-g1 ∂z 2 f1=0 {(g1 ∂z 1 f1+g2 ∂z 2 f1+g3 ∂z 3 f1)b p 1 +g0(∂z 3 f1 b p-1

1 η1η2+∂z 1 f1 b p-1 1 η2η3+∂z 2 f1 b p-1 1 η3η1) / (g0, g1, g2, g3)∈A 3 } ≃              g=        g 0 g 1 g 2 g 3        ∈A 4 ∇f1∧     g 1 g 2 g 3     =0                                  g • ∇f 1 g 0 ∂ z1 f 1 g 0 ∂ z2 f 1 g 0 ∂ z3 f 1        / g∈A 3 and g0∈A              ≃ A ∂z 1 f1, ∂z 2 f1, ∂z 3 f1 A ⊕ {g∈A 3 / ∇f1∧g=0} {g∇f1 / g∈A} ∀ p ∈ N * , H 2p+1 = g1b p 1 η1+g2b p 1 η2+g3b p 1 η3+g0b p-1 1 η1η2η3
(g0, g1, g2 g3)∈A 4 and g1 ∂z 1 f1+g2 ∂z 2 f1+g3 ∂z 3 f1=0 g0 ∂z 3 f1=g0 ∂z 1 f1=g0 ∂z 2 f1=0

{(g3 ∂z 2 f1-g2 ∂z 3 f1)b p 1 η1+(g1 ∂z 3 f1-g3 ∂z 1 f1)b p 1 η2+(g2 ∂z 1 f1-g1 ∂z 2 f1)b p 1 η3 / (g1, g2, g3)∈A 3 } ≃              g=        g 1 g 2 g 3 g 0        ∈A 4 ∇f1•     g 1 g 2 g 3     =0 and g0 ∂z 3 f1=g0 ∂z 1 f1=g0 ∂z 2 f1=0                                  ∇f 1 ∧   g 1 g 2 g 3   0        g∈A 3              ≃ {g∈A 3 / ∇f1•g=0} {∇f1∧g / g∈A 3 } ⊕ {g ∈ A / g ∂ z3 f 1 = g ∂ z1 f 1 = g ∂ z2 f 1 = 0}.
The following section will allows us to make those various spaces more explicit.

Explicit calculations in the particular case where f 1 has separate variables

In this section, we consider the polynomial f 1 = a 1 z i 1 + a 2 z j 2 + a 3 z k 3 , with 2 ≤ i ≤ j ≤ k and a j ∈ C * .

Its partial derivative are

∂ 1 f 1 = ia 1 z i-1 1 , ∂ 2 f 1 = ja 2 z j-1 2 and ∂ 3 f 1 = ka 3 z k-1 3 .
• We have already

H 0 = C[z 1 , z 2 , z 3 ]/ a 1 z i 1 + a 2 z j 2 + a 3 z k 3 .
• Moreover, as f 1 is weight homogeneous, Euler's formula gives

1 i z 1 ∂ 1 f 1 + 1 j z 2 ∂ 2 f 1 + 1 k z 3 ∂ 3 f 1 = f 1 . So we have the inclusion f 1 ⊂ ∂ 1 f 1 , ∂ 2 f 1 , ∂ 3 f 1 , thus A ∂ 1 f 1 , ∂ 2 f 1 , ∂ 3 f 1 A ≃ C[z 1 , z 2 , z 3 ] ∂ 1 f 1 , ∂ 2 f 1 , ∂ 3 f 1 ≃ V ect (z p 1 z q 2 z r 3 / p ∈ 0, i -2 , q ∈ 0, j -2 , r ∈ 0, k -2 ) .
Finally, as ∂ 1 f 1 and f 1 are relatively prime, if g ∈ A verifies g∂ 1 f 1 = 0 mod f 1 , then g ∈ f 1 , ie g is zero in A.

• Now we determine the set

   g =   g 1 g 2 g 3   ∈ A 3 / g • ∇f 1 = 0    : First we have f 1 , ∂ 1 f 1 , ∂ 2 f 1 = a 1 z i 1 +a 2 z j 2 +a 3 z k 2 , z i-1 1 , z j-1 2 = z i-1 1 , z j-1 2 z k 3 .
Thus the only monomials which are not in this ideal are the elements z p 1 z q 2 z r 3 with p ∈ 0, i -2 , q ∈ 0, j -2 and r ∈ 0, k -1 . So every polynomial P ∈ C[z] can be written in the form :

P = αf 1 + β∂ 1 f 1 + γ∂ 2 f 1 + p=0...i-2 q=0...j-2 r=0...k-1 a pqr z p 1 z q 2 z r 3 .
The polynomials P ∈ C[z] such that P ∂ 3 f 1 ∈ f 1 , ∂ 1 f 1 , ∂ 2 f 1 are therefore the following ones :

P = αf 1 + β∂ 1 f 1 + γ∂ 2 f 1 + p=0...i-2 q=0...j-2 r=1...k-1 a pqr z p 1 z q 2 z r 3 .
So we have calculated Ann f1, ∂1f1, ∂2f1 (∂ 3 f 1 ). The equation g

• ∇f 1 = 0 mod f 1 (12)
leads to g 3 ∈ Ann f1, ∂1f1, ∂2f1 (∂ 3 f 1 ), ie

g 3 = αf 1 + β∂ 1 f 1 + γ∂ 2 f 1 + p=0...i-2 q=0...j-2 r=1...k-1 a pqr z p 1 z q 2 z r 3 , (13) with
(α, β, γ) ∈ C[z] 3 . Hence g 2 ∂ 2 f 1 + γ∂ 2 f 1 ∂ 3 f 1 + p=0...i-2 q=0...j-2 r=1...k-1 a pqr z p 1 z q 2 z r 3 ∂ 3 f 1 ∈ f 1 , ∂ 1 f 1 . (14)
Thus, according to Euler's formula,

∂ 2 f 1       g 2 + γ∂ 3 f 1 - k j p=0...i-2 q=0...j-2 r=1...k-1 a pqr z p 1 z q+1 2 z r-1 3       ∈ f 1 , ∂ 1 f 1 . (15) Since Ann f1, ∂1f1 (∂ 2 f 1 ) = f 1 , ∂ 1 f 1 , this equation is equivalent to g 2 = -γ∂ 3 f 1 + k j p=0...i-2 q=0...j-2 r=1...k-1 a pqr z p 1 z q+1 2 z r-1 3 + δf 1 + ε∂ 1 f 1 , with δ, ε ∈ C[z]. It follows that g 1 ∂ 1 f 1 + β∂ 1 f 1 ∂ 3 f 1 + ε∂ 1 f 1 ∂ 2 f 1 + p=0...i-2 q=0...j-2 r=1...k-1 a pqr z p 1 z q 2 z r 3 ∂ 3 f 1 + k j p=0...i-2 q=0...j-2 r=1...k-1 a pqr z p 1 z q+1 2 z r-1 3 ∂ 3 f 1 ∈ f 1 . (16)
And, according to Euler's formula,

∂ 1 f 1       g 1 + β∂ 3 f 1 + ε∂ 2 f 1 - k i p=0...i-2 q=0...j-2 r=1...k-1 a pqr z p+1 1 z q 2 z r-1 3       ∈ f 1 . (17)
ie

g 1 = -β∂ 3 f 1 -ε∂ 2 f 1 + k i p=0...i-2 q=0...j-2 r=1...k-1 a pqr z p+1 1 z q 2 z r-1 3 + ηf 1 , (18)
with η ∈ C[z]. Finally g ∈ A 3 / g • ∇f1 = 0 =              η δ α   f1 + ∇f1 ∧   -γ β -ε   + p=0...i-2 q=0...j-2 r=1...k-1 apqr z p 1 z q 2 z r-1 3   k i z1 k j z2 z3   (α, β, γ, δ, ε, η) ∈ A 6 and apqr ∈ C            .
We deduce immediately the cohomology spaces of odd degrees :

∀ p ≥ 1, H 2p+1 ≃ C (i-1)(j-1)(k-1) H 1 ≃ ∇f 1 ∧ (C[z]/ f 1 ) 3 ⊕ C (i-1)(j-1)(k-1) . Remark : We also have ∇f 1 ∧ (C[z]/ f 1 ) 3 ≃ (C[z]/ f 1 ) 3 / {g / ∇f 1 ∧ g = 0} = (C[z]/ f 1 ) 3 / (C[z]/ f 1 )∇f 1 . Moreover the map (C[z]/ f 1 ) 2 → ∇f 1 ∧ (C[z]/ f 1 ) 3 g 1 g 2 → ∇f 1 ∧   g 1 g 2 0   is injective, thus ∇f 1 ∧ (C[z]/ f 1 ) 3 is infinite-dimensional .
• It remains to determine the set

   g =   g 1 g 2 g 3   ∈ A 3 / ∇f 1 ∧ g = 0    :
Let g ∈ A 3 be such that ∇f 1 ∧g = 0. It means that, modulo f 1 , g verifies the system

   ∂ 2 f g 3 -∂ 3 f 1 g 2 = 0 ∂ 3 f g 1 -∂ 1 f 1 g 3 = 0 ∂ 1 f g 2 -∂ 2 f 1 g 1 = 0 The first equation gives, modulo f 1 , ∂ 2 f 1 , ∂ 3 f 1 g 2 = 0. Now Ann f1, ∂2f1 (∂ 3 f 1 ) = f 1 , ∂ 2 f 1 , therefore g 2 = αf 1 + β∂ 2 f 1 . Hence ∂ 2 f 1 (g 3 -β∂ 3 f 1 ) = 0 mod f 1 , ie g 3 = γf 1 + β∂ 3 f 1 . Finally, we obtain ∂ 3 f 1 (g 1 -β∂ 1 f 1 ) = 0 mod f 1 , ie g 1 = δf 1 + β∂ 1 f 1 . So, {g ∈ A 3 / ∇f 1 ∧ g = 0} =    f 1   δ α γ   + β∇f 1 / α, β, γ, δ ∈ A    .
We deduce the cohomology spaces of even degrees :

∀ p ≥ 2, H 2p ≃ A / ∂ 1 f 1 , ∂ 2 f 1 , ∂ 3 f 1 ≃ C[z] / z i-1 1 , z j-1 2 , z k-1 3 ≃ V ect (z p 1 z q 2 z r 3 / p ∈ 0, i -2 , q ∈ 0, j -2 , r ∈ 0, k -2 ) ≃ C (i-1)(j-1)(k-1) H 2 ≃ {β ∇f 1 / β ∈ A} ⊕ C (i-1)(j-1)(k-1) ≃ C[z] / a 1 z i 1 + a 2 z j 2 + a 3 z k 3 ⊕ C (i-1)(j-1)(k-1) .

Remark 12

In particular, we obtain the cohomology for the cases where f 1 = z 2 1 + z 2 2 + z k+1

3

, f 1 = z 2 1 + z 3 2 + z 4 3 and f 1 = z 2 1 + z 3 2 + z 5 3 . These cases correspond respectively to the types A k , E 6 and E 8 of the Klein surfaces.

The following table sums up the results of those three special cases :

H 0 H 1 H 2 H 2p H 2p+1 A k C[z] / z 2 1 + z 2 2 + z k+1 3 ∇f 1 ∧ (C[z] / f 1 ) 3 ⊕ C k C[z] / z 2 1 + z 2 2 + z k+1 3 ⊕ C k C k C k E 6 C[z] / z 2 1 + z 3 2 + z 4 3 ∇f 1 ∧ (C[z] / f 1 ) 3 ⊕ C 6 C[z] / z 2 1 + z 3 2 + z 4 3 ⊕ C C 6 C 6 E 8 C[z] / z 2 1 + z 3 2 + z 5 3 ∇f 1 ∧ (C[z] / f 1 ) 3 ⊕ C 8 C[z] / z 2 1 + z 3 2 + z 5 3 ⊕ C C 8 C 8
The cases where f 1 = z 2 1 + z 2 2 z 3 + z k-1 3 and f 1 = z 2 1 + z 3 2 + z 2 z 3 3 , ie respectively D k and E 7 are studied in the following section. In this section, we consider the polynomial

f 1 = z 2 1 + z 2 2 z 3 + z k-1 3 . Its partial derivatives are ∂ 1 f 1 = 2z 1 , ∂ 2 f 1 = 2z 2 z 3 and ∂ 3 f 1 = z 2 2 + (k -1)z k-2 3 .
• We already have

H 0 = C[z]/ z 2 1 + z 2 2 z 3 + z k-1 3 .
• Besides, since f 1 is of homogeneous weight, Euler's formula gives

k -1 2 z 1 ∂ 1 f 1 + k -2 2 z 2 ∂ 2 f 1 + z 3 ∂ 3 f 1 = (k -1)f 1 . (19)
Thus, we have the inclusion

f 1 ⊂ ∂ 1 f 1 , ∂ 2 f 1 , ∂ 3 f 1 . Moreover, a Gröbner basis of ∂ 1 f 1 , ∂ 2 f 1 , ∂ 3 f 1 is [z k-1 3 , z 2 z 3 , z 2 2 + (k -1)z k-2 3 , z 1 ], therefore A ∂ 1 f 1 , ∂ 2 f 1 , ∂ 3 f 1 A ≃ C[z 1 , z 2 , z 3 ] ∂ 1 f 1 , ∂ 2 f 1 , ∂ 3 f 1 ≃ V ect z 2 , 1, z 3 , . . . , z k-2 3 .
Finally, as ∂ 1 f 1 are f 1 relatively prime, if g ∈ A verifies g∂ 1 f 1 = 0 mod f 1 , then g ∈ f 1 , ie g is zero in A, thus {g ∈ A / g ∂ z3 f 1 = g ∂ z1 f 1 = g ∂ z2 f 1 = 0} = 0.

• Now we determine the set

   g =   g 1 g 2 g 3   ∈ A 3 / g • ∇f 1 = 0    : A Gröbner basis of f 1 , ∂ 1 f 1 , ∂ 3 f 1 is [z 1 , z k-1 3 , z 2 2 + (k -1)z k-2 3 ], thus a basis of C[z] / f 1 , ∂ 1 f 1 , ∂ 3 f 1 is {z i 2 z j 3 / i ∈ {0, 1}, j ∈ 0, k -2 }.
We have already solved the equation p ∂ 2 f 1 = 0 in this space ; its solution is p = a 0,k-2 z k-2

3 + k-2 j=0
a 1,j z 2 z j 3 .

The equation

g • ∇f 1 = 0 mod f 1 (20) leads to g 2 ∂ 2 f 1 = 0 mod f 1 , ∂ 1 f 1 , ∂ 3 f 1 , (21)
hence

g 2 = αf 1 + β∂ 1 f 1 + γ∂ 3 f 1 + az k-2 3 + k-2 j=0 b j z 2 z j 3 , (22)
with (α, β, γ) ∈ C[z] 3 . And

g 3 ∂ 3 f 1 + γ∂ 3 f 1 ∂ 2 f 1 + az k-2 3 ∂ 2 f 1 + k-2 j=0 b j z 2 z j 3 ∂ 2 f 1 ∈ f 1 , ∂ 1 f 1 . (23)
Now according to Euler's formula (19) and the equality

z k-1 3 z 2 = 1 2 -k z 2 f 1 -z 2 z 3 ∂ 3 f 1 - 1 2 z 2 z 1 ∂ 1 f 1 = - 1 2 -k z 2 z 3 ∂ 3 f 1 mod f 1 , ∂ 1 f 1 , (24)
the equation (23) becomes

∂ 3 f 1   g 3 + γ∂ 2 f 1 - 2a 2 -k z 2 z 3 - k-2 j=0 b j 2 2 -k z j+1 3   ∈ f 1 , ∂ 1 f 1 . (25)
As Ann f1, ∂1f1 (∂ 3 f 1 ) = f 1 , ∂ 1 f 1 , this equation is equivalent to

g 3 = -γ∂ 2 f 1 + 2a 2 -k z 2 z 3 + k-2 j=0 b j 2 2 -k z j+1 3 + δf 1 + ε∂ 1 f 1 , with δ, ε ∈ C[z].
We find

g 1 = -β∂ 2 f 1 -ε∂ 3 f 1 + k-2 j=0 b j k -1 k -2 z 1 + a 2 -k z 2 z 1 + ηf 1 , (26)
with η ∈ C[z].

234

  Deformation quantization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Cohomologies and quotients of polynomial algebras . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Hochschild cohomology and deformations of algebras . . . . . . . . . . . . . . . . . . . . . . 4 Presentation of the Koszul complex 5 2.1 Kontsevich theorem and notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Particular case where n = 1 and m = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Case n = 2, m = 1. -singular curves of the plane 6 3.1 Description of the cohomology spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2 Explicit calculations in the particular case where f 1 has separate variables . . . . . . . . . . . 7 3.3 Explicit calculations for D k and E 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.3.1 Case of f 1 = z 2 1 z 2 + z k-1 2 , ie D k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.3.2 Case of f 1 = z 3 1 + z 1 z 3 2 , ie E 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Case n = 3, m = 1. -Klein surfaces 11 4.1 Klein surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Description of the cohomology spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.3 Explicit calculations in the particular case where f 1 has separate variables . . . . . . . . . . . 14 4.4 Explicit calculations for D k and E 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.4.1 Case of f 1 = z 2 1 + z 2 2 z 3 + z k-1 3 , ie D k . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.4.2 Case of f 1 = z 2 1 + z 3 2 + z 2 z 3 3 , ie E 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

•

  Finally, let's denote by ∇g the gradient of a polynomial g ∈ C[z]. 2.2 Particular case where n = 1 and m = 1 In the case where n = 1 and m = 1, according to what we have seen, we have for p ∈ N * , T (2p) = Ab p 1 and T (2p + 1) = Ab p 1 η 1 .

4. 4

 4 Explicit calculations for D k and E 7 4.4.1 Case of f 1 = z 2 1 + z 2 2 z 3 + z k-1 3 , ie D k

Finally, we have

as well as cohomology spaces of odd degrees :

, β ∈ A , we proceed as in the case of separate variables. We deduce the cohomology spaces of even degrees :

The proof is similar to the one of the previous cases. A Gröbner basis of

. We obtain the following results :

Remark 13

In all the previously studied cases, there exists a triple (i, j, k) such that {i, j, k} = {1, 2, 3}, and such that the map

is an isomorphism of vector spaces.


Claire David
email: david@lmm.jussieu.fr

A note on solitary waves solutions of classical wave equations

come

Introduction

Consider a differential equation of the form:

F (u, ∂u r ∂x r , ∂u s ∂t s ) = 0, (1)
The determination of travelling wave solutions of specific cases of (1), such as the Burgers or Burgers-Korteweg-De Vries equations, for instance, has been a major topic in the past few years, and play a crucial role in the study of wave equations. We presently aim at extending previous results, and give the whole classes of solitary wave solutions general for [START_REF] David | Structural stability of finite dispersion-relation preserving schemes[END_REF]. The paper is organized as follows. The general method is exposed in Section 2. A specific case is studied in section 3.

Solitary waves

Following Feng [START_REF] Feng | Solitary Wave Solutions of the Compound Burgers-Korteweg-de Vries Equation[END_REF] and our previous work [START_REF] David | A note on "general solitary wave solutions of the Compound Burgers-Korteweg-de Vries Equation[END_REF], in which travelling wave solutions of the CBKDV equation were exhibited as combinations of bell-profile waves and kink-profile waves, we aim at determining travelling wave solutions of (1) (see [START_REF] Li | Explicit exact solutions for new general twodimensional KdV-type and two-dimensional KdVBurgers-type equations with nonlinear terms of any order[END_REF], [START_REF] Whitham | Linear and Nonlinear Waves[END_REF], [START_REF] Ablowitz | Solitons and the Inverse Scattering Transform[END_REF], [START_REF] Dodd | Solitons and Nonlinear Wave Equations[END_REF], [START_REF] Johnson | A Modern Introduction to the Mathematical Theory of Water Waves[END_REF], [START_REF] Ince | Ordinary Differential Equations[END_REF], [START_REF] Zhang | Qualitative Analysis of Nonlinear Differential Equations[END_REF], [START_REF] Birkhoff | Ordinary Differential Equations[END_REF], [START_REF] Polyanin | Handbook of Nonlinear Partial Differential Equations[END_REF]).

Following [START_REF] Feng | Solitary Wave Solutions of the Compound Burgers-Korteweg-de Vries Equation[END_REF], we assume that equation (1) has travelling wave solutions of the form

u(x, t) = u(ξ), ξ = x -v t ( 2
)
where v is the wave velocity. Substituting (2) into equation (1) leads to:

F (u, u (r) , (-v) s u (s) ) = 0, (3)
Performing an integration of (3) with respect to ξ leads to an equation of the form:

F P ξ (u, u (r) , (-v) s u (s) ) = C, (4)
where C is an arbitrary integration constant, which will be the starting point for the determination of solitary waves solutions.

In the previous works, this integration constant is usually taken equal to zero. Yet, it should not be so, since it can lead to a loss of solutions, as we are going to show it in the following.

3 Travelling Solitary Waves

Hyperbolic Ansatz

The discussion in the preceding section provides us useful information when we construct travelling solitary wave solutions for equation [START_REF] Burgers | Mathematical examples illustrating relations occurring in the theory of turbulent fluid motion[END_REF]. Based on these results, in this section, a class of travelling wave solutions is searched as a combination of bell-profile waves and kink-profile waves of the form

ũ(x, t) = n i=1 U i tanh i C i (x -v t) + V i sech i C i (x -v t + x 0 ) + V 0 (5)
where the

U ′ i s, V ′ i s, C ′ i s, (i = 1, • • • , n
), V 0 and v are constants to be determined. In the following, c is taken equal to 1.

Theoretical analysis

Substitution of (5) into equation ( 4) leads to an equation of the form i, j, k

A i tanh i C i ξ sech j C i ξ sinh k C i ξ = C (6)
the A i being real constants.

The difficulty for solving equation ( 6) lies in finding the values of the constants U i , V i , C i , V 0 and v by solving the over-determined algebraic equations. Following [START_REF] Feng | Solitary Wave Solutions of the Compound Burgers-Korteweg-de Vries Equation[END_REF], after balancing the higher-order derivative term and the leading nonlinear term, we deduce n = 1.

Then, following [START_REF] David | A note on "general solitary wave solutions of the Compound Burgers-Korteweg-de Vries Equation[END_REF] we replace sech(C 1 ξ) by

2 e C 1 ξ +e -C 1 ξ , sinh(C 1 ξ) by e C 1 ξ -e -C 1 ξ 2 , tanh(C 1 ξ) by e C 1 ξ -e -C 1 ξ e C 1 ξ +e -C 1 ξ
, and multiply both sides by (1 + e 2 ξ C 1 ) 2 , so that equation ( 6) can be rewritten in the following form:

4 k=0 P k (U 1 , V 1 , C 1 , v, V 0 ) e k C 1 ξ = 0, (7)
where the P k (k = 0, ..., 4), are polynomials of

U 1 , V 1 , C 1 , V 0 and v.
Depending wether (6) admits or no consistent solutions, spurious solitary waves solutions may, or not, appear.

A specific case

Consider the specific case when (1) is the equivalent equation of a DRP scheme, the coefficients of which will be denoted by γ k , k ∈ {-m, m} (see [START_REF] David | Structural stability of finite dispersion-relation preserving schemes[END_REF]):

-ut - σ 2 utt + 2 σ µ Re h m k=1 k γ k ux = 0 (8)
where Re h denotes the mesh Reynolds number, σ, the cf l coefficient, and µ, the viscosity. Equation ( 3) is then given by:

-v ũ′ (ξ) - v 2 σ 2 ũ′′ (ξ) + 2 σ µ Re h m k=1 k γ k ũ′ (ξ) = 0 (9)
Performing an integration of ( 9) with respect to ξ yields:

-v ũ(ξ) - v 2 σ 2 ũ′ (ξ) + 2 σ µ Re h m k=1 k γ k ũ(ξ) = C (10)
i. e.:

2 σ µ Re h m k=1 k γ k -v ũ(ξ) - v 2 σ 2 ũ′ (ξ) = C ( 11
)
where C is an arbitrary integration constant. Substitution of ( 5) for n = 1 into equation ( 11) leads to:

2 σ µ Re h m k=1 k γ k -v {U 1 tanh [ C 1 ξ ] + V 1 sech [ C 1 ξ ] + V 0 } - v 2 σ 2 U 1 sech 2 [ C 1 ξ ] -V 1 sinh [ C 1 ξ ] cosh 2 [ C 1 ξ ] = C (12)
i. e.:

2 σ µ Re h m k=1 k γ k -v U 1 e C 1 ξ -e -C 1 ξ e C 1 ξ + e -C 1 ξ + 2 V 1 e C 1 ξ + e -C 1 ξ + V 0 - v 2 σ 2 U 1 2 e C 1 ξ + e -C 1 ξ 2 -2 V 1 e C 1 ξ -e -C 1 ξ e C 1 ξ + e -C 1 ξ 2 = C (13)
Multiplying both sides by 1 + e 2 C 1 ξ 2 yields:

2 σ µ Re h m k=1 k γ k -v U 1 e 4 C 1 ξ -1 + 2 V 1 e 3 C 1 ξ + e C 1 ξ + V 0 1 + e 2 C 1 ξ 2 - v 2 C 1 σ C 1 2 4 U 1 -2 V 1 e 3 C 1 ξ -1 = C (14)
which is a fourth-order equation in e C 1 ξ . This equation being satisfied for any real value of ξ, one therefore deduces that the coefficients of e k C 1 ξ , k = 0, . . . , 4 must be equal to zero, i.e.:

                                                 2 2 σ µ Re h m k=1 k γ k -v {-U 1 + V 0 } - v 2 C 1 σ 2 {4 U 1 + 2 V 1 } = C 2 σ µ Re h m k=1 k γ k -v 2 V 1 = 0 2 2 σ µ Re h m k=1 k γ k -v V 0 = 0 2 2 σ µ Re h m k=1 k γ k -v V 1 + v 2 C 1 σ V 1 = 0 2 σ µ Re h m k=1 k γ k -v {U 1 + V 0 } = 0 (15) v = 2 σ µ Re h m k=1 k γ k , V 1 = 0 leads to the trivial null solution. Therefore, V 1 is necessarily equal to zero, which implies:                v = 2 σ µ Re h m k=1 k γ k U 1 = - C 2 C 1 v 2 σ V 0 ∈ IR , C 1 ∈ IR (16)
It is easy to note that, if the integration constant C had been taken equal to zero, the solitary waves of the considered equation would have been loss.

Conclusions

The importance of choosing an integration constant which is not equal to zero, in the determination of solitary wave solutions of wave equations, has been carried out. We show that taking this constant equal to zero leads to a loss of solutions.