Jérôme Leroux

Vector Addition System Reversible Reachability Problem

The reachability problem for vector addition systems is a central problem of net theory. This problem is known to be decidable but the complexity is still unknown. Whereas the problem is EXPSPACE-hard, no elementary upper bounds complexity are known. In this paper we consider the reversible reachability problem. This problem consists to decide if two configurations are reachable one from each other. We show that this problem is EXPSPACE-complete. As an application of the introduced materials we characterize the reversibility domains of a vector addition system.

Introduction

Vector addition systems (VASs) or equivalently Petri nets are one of the most popular formal methods for the representation and the analysis of parallel processes [START_REF] Esparza | Decidability issues for petri nets -a survey[END_REF].

Their reachability problem is central since many computational problems (even outside the realm of parallel processes) reduce to the reachability problem. Sacerdote and Tenney provided in [START_REF] Sacerdote | The decidability of the reachability problem for vector addition systems (preliminary version)[END_REF] a partial proof of decidability of this problem. The proof was completed in 1981 by Mayr [START_REF] Mayr | An algorithm for the general petri net reachability problem[END_REF] and simplified by Kosaraju [START_REF] Kosaraju | Decidability of reachability in vector addition systems (preliminary version)[END_REF] from [START_REF] Sacerdote | The decidability of the reachability problem for vector addition systems (preliminary version)[END_REF][START_REF] Mayr | An algorithm for the general petri net reachability problem[END_REF]. Ten years later [START_REF] Luc | A structure to decide reachability in petri nets[END_REF], Lambert provided a further simplified version based on [START_REF] Kosaraju | Decidability of reachability in vector addition systems (preliminary version)[END_REF]. This last proof still remains difficult and the upper-bound complexity of the corresponding algorithm is just known to be non-primitive recursive. Nowadays, the exact complexity of the reachability problem for VASs is still an open-problem. The problem is known to be EXPSPACE-hard [START_REF] Cardoza | Exponential space complete problems for petri nets and commutative semigroups: Preliminary report[END_REF] but even the existence of an elementary upper-bound complexity is open.

Recently, in [START_REF] Leroux | Vector addition system reachability problem: a short self-contained proof[END_REF] we provided a new proof of the reachability problem based on the notion of production relations inspired by Hauschildt [START_REF] Hauschildt | Semilinearity of the Reachability Set is Decidable for Petri Nets[END_REF]. That proof shows that reachability sets are almost semilinear, a class of sets introduced in that paper that extends the class of Presburger sets. An application of that result was provided; we proved that a final configuration is not reachable from an initial one if and only if there exists a forward inductive invariant definable in the Presburger arithmetic that contains the initial configuration but not the final one. Since we can decide if a Presburger formula denotes a forward inductive invariant, we deduce that there exist checkable certificates of non-reachability in the Presburger arithmetic. In particular, there exists a simple algorithm for deciding the general VAS reachability problem based on two semi-algorithms. A first one that tries to prove the reachability by enumerating finite sequences of actions and a second one that tries to prove the non-reachability by enumerating Presburger formulas. The Presburger inductive invariants presented in that paper are obtained by over approximating production relations thanks to strongly connected subreachability graphs (called witness graph and recalled in Section 6). As a direct consequence, configurations in these graphs are reachable one from each other.

In this paper we consider the reversible reachability problem that consists to decide if two configurations are reachable one from each other. We prove that this problem is EXPSPACE-complete. This result extends known result for the subclasses of reversible and cyclic vector addition systems [START_REF] Bouziane | Cyclic petri net reachability sets are semi-linear effectively constructible[END_REF]. We also prove that the general coverability problem reduces to the reversible reachability problem (see Section 3). As an application of the introduced materials we characterize the reversibility domains of a vector addition system in the last Section 11.

Projected Vectors

In this paper, some components of vectors in Z d are projected away. In order to avoid multiple dimensions, we introduce an additional element ∈ Z, the set Z = Z ∪ { }, and the set Z

)(i) = k(z(i)) for every i ∈ I. The relation ≤ is extended over Z d * component-wise by z 1 ≤ z 2 if z 2 (i) = then z 1 (i) = and in this case z 1 (i) ≤ z 2 (i).
Example 2.1. We have k( , 1) = ( , k) even if k = 0. We also have ( , 5) -( , 2) = ( , 3) and ( , 1) + ( , 2) = ( , 3). We have Example 2.2. Let L = {1}. We have π L (1000, 1) = ( , 1) and π L (4, ) = ( , ). We also have π L ({(2, 0), (1, 1), (2, 0)}) = {( , 0), ( , 1), ( , 2)}.

• • • ≤ -1 ≤ 0 ≤ 1 ≤ • • • ≤ .
Let z ∈ Z d I . We denote by ||z|| ∞ the natural number equals to 0 if I = {1, . . . , d} and equals to max i ∈I |z(i)| otherwise. Given a finite set Z ⊆ Z d I we denote by ||Z|| ∞ the natural number max z∈Z ||z|| ∞ if Z is non empty and 0 is Z is empty. I such that c 0 = x, c k = y and such that c j = c j-1 + π I (a j ) for every j ∈ {1, . . . , k}. Note that in this case ρ is unique and yx = ∆ I (σ). This run is denoted by x σ -→ y. The set I is called the set of projected components of ρ. The projection π L (ρ) of a run ρ = c 0 . . . c k over a set of indexes L ⊆ {1, . . . , d} is defined as expected as the run π

Vector Addition Systems

L (ρ) = π L (c 0 ) . . . π L (c k ). Observe that if ρ is the run x σ -→ y then π L (ρ) is the run π L (x) σ -→ π L (y).
The following lemma provides a simple way to deduce a converse result.

Lemma 3.1. Let L be a set of indexes and c be a configuration such that there exists a run from π L (c) labelled by a word σ. If c(i) ≥ |σ| ||A|| ∞ for every i ∈ L then there exists a run from c labelled by σ.

Proof. Let c ∈ N d I be a configuration such that there exists a path from π L (c) labelled by a word σ = a 1 . . . a k where a j ∈ A. Let us introduce the vector c j = c + π I (a 1 + . . . + a j ). Since there exists a run from π L (c) labelled by σ we deduce that π L (c j ) ∈ N d I∪L . Observe that for every j ∈ {0, . . . , k} and for every i ∈ I we have

c j (i) ≥ c(i) -|σ| ||A|| ∞ . In particular if c(i) ≥ |σ| ||A|| ∞ for every i ∈ L\I we deduce that c j ∈ N d I . Therefore ρ = c 0 . . . c k is a run from c labelled by σ. Example 3.2. ρ = (2, 0)(1, 1)(0, 2) is the run (2, 0) (-1,1)(-1,1) --------→ (0, 2). Let L = {1}
and observe that π L (ρ) = ( , 0)( , 1)( , 2) is the run ( , 0)

(-1,1)(-1,1) --------→ ( , 2).
Let x and y be two standard configurations. When there exists a run from x to y we say that y is reachable from x and if there also exists a run from y to x we say that (x, y) is in the reversible reachability relation. The problem of deciding this last property is called the reversible reachability problem. This problem is shown to be EXPSPACE-hard by a reduction of the coverability problem as follows. Given two standard configurations x and y we say that y is coverable by x if there exists a standard configuration in y +N d reachable from x. The coverability problem is known to be EXPSPACE-complete [START_REF] Cardoza | Exponential space complete problems for petri nets and commutative semigroups: Preliminary report[END_REF][START_REF] Rackoff | The covering and boundedness problems for vector addition systems[END_REF]. We reduce the coverability problem as follows.

We first observe that we can add to a vector addition system A additional actions of the form (0, . . . , 0, -1, 0, . . . , 0) without modifying the coverability problem. Thanks to this transformation a standard configuration y is coverable from a standard configuration x if and only if y is reachable from x. We introduce the VAS V in dimension d + 2 defined by V = ((0, 0) × A) ∪ {(-1, 1, -y), (1, -1, x)}. Observe that (1, 0, x) and (0, 1, 0) are in reversible reachability relation of V if and only if y is coverable from x in A. As a direct consequence, the reversible reachability problem is EXPSPACE-hard.

Subreachability Graphs

A subreachability graph is a graph G = (Q, T ) where Q ⊆ N d I is a non empty finite set of configurations called states and T ⊆ Q × A × Q is a finite set of triples (x, a, y) ∈ Q × A × Q satisfying x a -→ y called transitions.
The set I is called the set of projected components of G and the subreachability graph is said to be standard if I is empty. A witness graph is a strongly connected subreachability graph (see Fig. 1 for examples). The projection π L (t) of a transition t = (x, a, y) over a set of indexes L ⊆ {1, . . . , d} is defined by π L (t) = (π L (x), a, π L (y)) and the projection of the set of transitions T is defined by π

L (T ) = {π L (t) | t ∈ T }. The projection π L (G) of a subreachability graph G = (Q, T ) is the subreachability graph π L (G) = (π L (Q), A, π L (T )).
(1, 1, 0) (0, 2, 1) A path in a subreachability graph G from a configuration x ∈ Q to a configuration y ∈ Q labelled by a word σ = a 1 . . . a k of actions a j ∈ A is a word p = t 1 . . . t k of transitions t j ∈ T of the form t j = (c j-1 , a j , c j ) with c 0 = x and c k = y. We observe that the word p is unique. This path is denoted by x σ -→ G y. Let us observe that in this case ρ = c 0 . . . c k is the unique run x σ -→ y. In particular if a path x σ -→ G y exists then the run x σ -→ y also exists. Note that conversely if there exists a run x σ -→ y then there exists a subreachability G such that x σ -→ G y. Such a G is obtained by introducing the set of states Q = {c 0 , . . . , c k } and the set of transitions T = {t 1 , . . . , t k } where

(1, 0, 1) (0, 1, 2) (-1, 1, 1) (1, -1, -1) (1, -1, -1) (0, -1, 1) (0, 1, -1) (1, , ) (0, , ) (-1, 1, 1) (1, -1, -1) (0, -1, 1) (0, 1, -1)
t j = (c j-1 , a j , c j ). A path x σ -→ G y is called a cycle if x = y. The cycle is said to be simple if c j1 = c j2 with j 1 < j 2 implies j 1 = 0 and j 2 = k. The projection π L (p) of a path p = t 1 . . . t k in G over a set of indexes L ⊆ {1, . . . , d} is the path π L (p) = π L (t 1 ) . . . π L (t k ) in π L (G). Observe that the projection of a path x σ -→ G y over L is the path π L (x) σ -→ π L (G) π L (y).
The Parikh image of a path is the function µ : T → N defined by µ(t) is the number of occurrences of t in this path. A cycle is said to be total if its Parikh image µ satisfies µ(t) ≥ 1 for every t ∈ T .

Example 4.2. Let us come back to the standard witness graph G depicted in Fig. 1.

Let us consider the cycle (1, 1, 0)

(-1,1,1)(1,-1,-1) -----------→ G (1, 1, 0) in G. Its projection over L = {2, 3} is the cycle (1, , ) (-1,1,1)(1,-1,-1) -----------→ π L (G) (1, , ) in the witness graph π L (G) also depicted in Fig. 1.
A word σ ∈ A * is said to be forward iterable from a configuration c if there exists a run c σ -→ y such that c ≤ y. In this case the configuration c = π L (c) where L = {i | c(i) = y(i)} is called the forward limit of σ from c. We observe that σ is forward iterable from c if and only if for every n ∈ N there exists a run c

σ n --→ y n .
In that case L is the minimal set of indexes such that π L (y n ) does not depend on n. Symmetrically σ is said to be backward iterable from a configuration c if there exists a run x σ -→ c such that c ≤ x. In this case the configuration c = π L (c) where

L = {i | c(i) = x(i)} is called the backward limit of σ from c. Example 4.3. The action a = (0, -1, 1) is forward iterable from x = (0, , 0) since (0, , 0) a -→ (0, , 1). Observe that in this case (0, , 0) a n --→ (0, , n) for every n ∈ N. The forward limit of a from (0, , 0) is (0, , ).
A configurations c is said to be forward pumpable by a cycle q σ -→ G q if σ is forward iterable from c with a forward limit equals to q. Note that in this case q is unique since it satisfies q = π I (c) where I is the set of projected components of G. Symmetrically a configuration c is said to be backward pumpable by a cycle q σ -→ G q if σ is backward iterable from c with a backward limit equals to q.

Example 4.4. Let us come back to the witness graph π L (G) depicted in Fig. 1. Observe that (0, , 0) is forward pumpable by (0, , )

(0,-1,1) -----→ π L (G) (0, , ).

Outline

The reminder of this paper is a proof that the reversible reachability problem is in EX-PSPACE. We prove that if a pair (x, y) of standard configurations are in the reversible reachability relation then there exist runs from x to y and from y to x with lengths bounded by a number double exponential in the size of (x, A, y). Using the fact that NEXPSPACE=EXPSPACE, and that double exponential numbers can be stored in exponential space, one obtain the EXPSPACE upper bound. These "short" runs are obtained as follows.

Theorem 6.3 gives a bound on the size of the Parikh image of a cycle in a witness graph to achieve a particular displacement vector, using a result of Pottier [START_REF] Pottier | Minimal solutions of linear diophantine systems: Bounds and algorithms[END_REF]. This result is used in Section 7, which considers the special case of reversible witness graphs in which each path can be followed by another path such that the total displacement is zero. In Theorem 7.3 it is shown that a reversible witness graph possesses a "short" total cycle that has a zero displacement.

Section 9 takes an arbitrary witness graph G and asserts the existence of a set of indexes J such that the witness graph π J (G) has a "small" number of states and such that states of G that are not "too" large are pumpable by "short" cycles in π J (G).

The development culminates with the main result in Section 10. There, it is shown that x and y are two states of a reversible witness graph G. One then uses the result from Section 9 to generate a reversible witness graph π J (G). Most of the work involves showing how to replace arbitrary path between x and y by "short" paths by exploiting the fact that x and y are pumpable to move from π J (G) back to G.

A displacement vector of a witness graph G is a finite sum of vectors of the form ∆(σ) = k j=1 a j where σ = a 1 . . . a k is a word labelling a cycle in G. We denote by Z G the set of displacement vectors. Observe that Z G is a submonoid of (Z d , +). Displacement vectors are related to Kirchhoff functions as follows. A Kirchhoff function for a witness graph G = (Q, T ) is a function µ : T → N such that the functions in(µ), out(µ) : Q → N defined bellow are equal.

in(µ)(x) = t∈T ∩(Q×A×{x}) µ(t) out(µ)(x) = t∈T ∩({x}×A×Q) µ(t) A Kirchhoff function µ : T → N is said to be total if µ(t)
z = t=(x,a,y)∈T µ(t)a
In this case z is called the displacement of µ.

Example 6.2. Let us come back to the witness graph π L (G) depicted in Fig. 1. A function µ : π L (T ) → N is a Kirchhoff function for π L (G) if and only if µ(t 1 ) = µ(t 2 ) where t 1 = ((1, , ), (-1, 1, 1), (0, , )) and t 2 = ((0, , ), (1, -1, -1), (1, , )).

In particular the set of displacement vectors of π L (G) satisfies

Z π L (G) = {z ∈ Z 3 | z(1) = 0 ∧ z(2) + z(3) = 0}.
The following theorem shows that the displacement vectors z ∈ Z G are displacement of Kirchhoff functions µ for G such that ||µ|| ∞ = max t∈T µ(t) is bounded by a polynomial in |Q|, ||A|| ∞ , and ||z|| ∞ . Theorem 6.3. Vectors z ∈ Z G are displacement of Kirchhoff functions µ such that the following inequality holds where q = |Q|, a = ||A|| ∞ , and m = ||z|| ∞ :

||µ|| ∞ ≤ (q d+1 a(1 + 2a) d + m) d
Proof. We first recall a "Frobenius theorem" proved in [START_REF] Pottier | Minimal solutions of linear diophantine systems: Bounds and algorithms[END_REF]. Let H ∈ Z d×n be a matrix and let us denote by h i,j for each i ∈ {1, . . . , d} and j ∈ {1, . . . , n} the element of H at position (i, j). We denote by ||H|| 1,∞ the natural number max 1≤i≤d n j=1 |h i,j |. Given a vector v ∈ N n , we introduce the natural number ||v|| 1 = n j=1 v(j). Let V be the set of vectors v ∈ N n such that Hv = 0. Recall that V is a submonoid of (N n , +) generated by the finite set min(V \{0}) of minimal elements for ≤. From [START_REF] Pottier | Minimal solutions of linear diophantine systems: Bounds and algorithms[END_REF] we deduce that vectors v ∈ min(V \{0}) satisfy the following inequality where r is the rank of H:

||v|| 1 ≤ (1 + ||H|| 1,∞ ) r
Observe that if a = 0 then z = 0 and the theorem is proved with the Kirchhoff function µ defined by µ(t) = 0 for every t ∈ T . So we can assume that a ≥ 1. Since every cycle labelled by a word σ can be decomposed into a finite sequence of simple cycles labelled by words σ 1 , . . . , σ k such that ∆(σ) = k j=1 ∆(σ j ) we deduce that the set of displacement vectors Z G is the submonoid of (Z d , +) generated by the set Z of non-zero vectors z = ∆(σ) where σ is the label of a simple cycle. Since the length of a simple cycle is bounded by the cardinal q of Q, we get ||Z|| ∞ ≤ qa. As a corollary we deduce that the cardinal k of Z is bounded by k ≤ (1 + 2qa) d -1 (the -1 comes from the fact that vectors in Z are non-zero).

Let us consider a vector z ∈ Z G and let us introduce a whole enumeration z 1 , . . . , z k of the vectors in Z and the following set V where n = k + 1:

V = {v ∈ N n | d i=1 k j=1 v(j)z j (i) -v(n)z(i) = 0}
We observe that V is associated to a matrix H ∈ Z d×n . The rank of H is bounded by d and ||H|| 1,∞ ≤ kqa + m. We deduce from the Frobenius theorem that vectors v ∈ min(V \{0}) satisfy the following inequality:

||v|| 1 ≤ (1 + kqa + m) d ≤ (q d+1 a(1 + 2a) d + m) d
Since z ∈ Z G , there exists a vector v ∈ V such that v(n) = 1. In particular there exists another vector v ∈ min(V \{0}) such that v(n) = 1. Observe that for every j ∈ {1, . . . , k} there exists a function λ j that is the Parikh image of a simple cycle such that z j is the displacement of λ j . We introduce the Kirchhoff function µ = k j=1 v(j)λ j . Since v ∈ V and v(n) = 1 we deduce that the displacement of µ is z. The theorem is proved by observing that µ(t) = k j=1 v(j)λ j (t) ≤ ||v|| 1 since λ j (t) ∈ {0, 1}.

Reversible Witness Graphs

A witness graph G is said to be reversible if for every path x u -→ G y there exists a path y v -→ G x such that ∆(u) + ∆(v) = 0. Observe that standard witness graphs are reversible since the condition ∆(u) + ∆(v) = 0 is implied by the two paths. Let us recall that a submonoid Z of (Z d , +) is said to be a subgroup if -z ∈ Z for every z ∈ Z. The following lemma provides two characterizations of the reversible witness graphs.

Lemma 7.2. A witness graph G is reversible if and only if Z G is a subgroup of (Z d , +) if and only if the zero vector is the displacement of a total Kirchhoff function.

Proof. Assume first that G is reversible and let us prove that Z G is a subgroup of (Z d , +). Let us consider a cycle x u -→ G x. Since G is reversible, there exists a cycle x v -→ G x such that ∆(u) + ∆(v) = 0. We deduce that -Z G = Z G since vectors in Z G are finite sums of vectors ∆(u) where u is the label of a cycle in G. Therefore Z G is a subgroup of Z d . Now let us assume that Z G is a subgroup of (Z d , +) and let us prove that the zero vector is the displacement of a total Kirchhoff function. Since G is strongly connected, there exists a total cycle

x u -→ G x. Observe that z = ∆(u) is in Z G . Since Z G is a subgroup we deduce that -z ∈ Z G . Hence -z is the displacement of a Kirchhoff function λ. Let λ be Parikh image of x u -→ G x and observe that µ = λ + λ is a total Kirchhoff function. Moreover the displacement of µ is -z + z = 0.
Finally, let us assume that the zero vector is the displacement of a total Kirchhoff function µ and let us prove that G is reversible. Let us consider a path x u -→ G y. Since G is strongly connected, there exists a path y α -→ G x. Let us consider the Parikh image λ of the cycle x uα --→ G x and let m = 1+||λ|| ∞ . We observe that µ = mµ-λ is a total Kirchhoff function and the Euler's Lemma shows that µ is the Parikh image of a cycle

x β -→ G x. From µ = mµ -λ we deduce that ∆(β) = m0 -∆(uα). Let us consider v = αβ and observe that y v -→ G x and ∆(u) + ∆(v) = 0. Thus G is reversible.
The following theorem shows that if G is a reversible witness graph then the zero vector is the displacement of a total Kirchhoff function µ such ||µ|| ∞ can be bounded by a polynomial in |Q| and ||A|| ∞ .

Theorem 7.3. Let G be a reversible witness graph. The zero vector is the displacement of a total Kirchhoff function µ such that the following inequality holds where q = |Q| and a = ||A|| ∞ :

||µ|| ∞ ≤ (q(1 + 2a)) d(d+1)
Proof. Since G is strongly connected, every transition t ∈ T occurs in at least one simple cycle. We denote by λ t the Parikh image of such a simple cycle and we introduce the Kirchhoff function λ = t∈T λ t . We have λ(t) ∈ {1, . . . , |T |} for every t ∈ T . We introduce the displacement z of λ. Since G is reversible, we deduce that -z is the displacement vector of a Kirchhoff function for G. As ||z|| ∞ ≤ |T |qa, |T | ≤ q|A|, and |A| ≤ (1 + 2a) d we deduce that ||z|| ∞ ≤ q 2 a(1 + 2a) d . Theorem 6.3 shows that -z is the displacement of a Kirchhoff function λ satisfying the following inequalities:

||λ || ∞ ≤ (q d a(1 + 2a) d + q 2 a(1 + 2a) d ) d ≤ (q d+1 2a(1 + 2a) d ) d
Let us consider the total Kirchhoff function µ = λ + λ . Observe that the displacement of µ is the zero vector and since ||λ|| ∞ ≤ |T | ≤ q(1 + 2a) d ≤ (q d+1 (1 + 2a) d ) d we get the theorem with:

||µ|| ∞ ≤ (q d+1 2a(1 + 2a) d ) d + (q d+1 (1 + 2a) d ) d ≤ (q(1 + 2a)) d(d+1)
In this section we introduce a way for extracting "large" components of configurations. An extractor is a non increasing sequence λ = (λ n ) 1≤n≤d of natural numbers λ n ∈ N. Let X ⊆ N d I . An excluding set for (λ, X) is a set of indexes J such that x(i) < λ |J|+1 for every i ∈ J and for every x ∈ X. Since λ is non increasing we deduce that the class of excluding sets for a couple (λ, X) is stable by intersection. As this class contains {1, . . . , d} we deduce that there exists a unique minimal excluding set J for (λ, X). By minimality of this set we deduce that for every i ∈ J there exists x ∈ X such that x(i) ≥ λ |J| . We denote λ(X) the set π J (X) where J is the minimal excluding set for (λ, X). A set X ⊆ N d I is said to be normalized for λ if λ(X) = X. As a direct consequence of the following lemma we deduce that λ(X) is normalized for λ for every set X ⊆ N d I . Lemma 8.1. Let X ⊆ N d I and let L be a set of indexes included in the minimal excluding set of (λ, X). Then λ(X) = λ(π L (X)).

Proof. Note that if X is empty the result is immediate so we can assume that X is non empty. Let J be the minimal excluding set of (λ, X) and observe that J is an excluding set for X = π L (X). In particular the minimal excluding set J for X satisfies J ⊆ J. Since J is an excluding set of (λ, X ) we deduce that x (i) < λ |J |+1 for every i ∈ J . Hence π L (x)(i) < λ |J |+1 for every x ∈ X. As x ≤ π L (x) we deduce that J is an excluding set of (λ, X). By minimality of J we get the other inclusion J ⊆ J . Thus J = J and we have proved that λ(X) = λ(π L (X)).

Example 8.2. Let λ = (5, 3, 2) be an extractor. We have λ({(1, 8, 1)}) = {(1, , 1)}, λ({(1, 8, 1), (3, 1, 1)}) = {( , , 1)}.

Pumpable Configurations

In this section we show that for arbitrary witness graph G, there exists a set J of indexes such that the number of states of π J (G) is "small" and such that states with "small" size of G are pumpable by "short" cycles of π J (G). The proof of this result is inspired by the Rackoff ideas [START_REF] Rackoff | The covering and boundedness problems for vector addition systems[END_REF]. All other results or definitions introduced in this section are not used in the sequel.

Theorem 9.1. Let G be a witness graph and let s ∈ N >0 be a positive integer. We introduce the positive integer x = (1 + ||A|| ∞ )s. There exists a set of indexes J such that the number of states of π J (G) is bounded by x d d and such that every state q ∈ Q such that ||q|| ∞ < s is forward and backward pumpable by cycles of π J (G) with lengths bounded by dx d d .

Such a set J is obtained by introducing the class of adapted extractors. An extractor λ is said to be adapted if the following inequality holds for every n ∈ {2, . . . , d}:

λ n-1 ≥ λ d-n+1 n ||A|| ∞ + λ n
Lemma 9.2. Let λ be an adapted extractor, G be a witness graph with a set of states Q ⊆ N d I , and let J be the minimal excluding set for (λ, Q). For every state q ∈ Q there exists a run q u -→ y such that π J (q) u -→ π J (G) π J (y) and such that the bounds |u| ≤ |I|<n≤|J| λ d+1-n n , and y(j) ≥ λ |J| for every j ∈ J hold.

Proof. Since Q ⊆ N d I we deduce that I ⊆ J. We introduce a parameter k ∈ N and we prove the lemma by induction over k under the constraint |J| -|I| ≤ k. Observe that if k = 0 then I = J and the property is proved with u = and y = q. Assume the property proved for a natural number k ∈ N and let us consider a witness graph G with a set of projected components I such that |J| -|I| ≤ k + 1 where J is the minimal excluding set for (λ, Q). We consider a state q ∈ Q.

We say that a state p ∈ Q is normalized if {p} is normalized for λ, i.e λ({p}) = {p} or equivalently p(i) < λ |I|+1 for every i ∈ I. Observe that if every state p ∈ Q is normalized then λ(Q) = Q and in particular J = I and the property is proved. So we can assume that there exists a state in p ∈ Q that is not normalized. Since G is strongly connected, there exists a path q σ -→ G p with a minimal length such that p is not normalized. Let us observe that the number of states in Q that are normalized is bounded by λ We introduce the minimal excluding set K for (λ, {p}). Observe that I is strictly included in K since p is not normalized. Moreover K is included in J since J is an excluding set for (λ, {p}). Lemma 8.1 shows that J is the minimal excluding set of (λ, π K (Q)). Observe that |J| -|K| < |J| -|I| ≤ k + 1. By applying the induction on the witness graph π K (G) and the state π K (p), we deduce that there exists a run

π K (p) u -→ y such that π J (p) u -→ π J (G) π J (y) with |u| ≤ |K|<n≤|J| λ d+1-n n
and such that y(j) ≥ λ |J| for every j ∈ J. We introduce the word v = σu. Since λ is an adapted extractor we deduce that λ |K| ≥ ||A|| ∞ |K|<n≤|J| λ d+1-n n . From p(k) ≥ λ |K| for every k ∈ K we deduce that p(k) ≥ ||A|| ∞ |u|. Since there exists a run from π K (p) labelled by u, Lemma 3.1 shows that there exists a run

p u -→ z. For every k ∈ K we have z(k) ≥ λ |J| if p(k) = and z(k) ≥ p(k) -||A|| ∞ |u| ≥ λ |J| otherwise since λ is an adapted extractor. As p u -→ z we deduce that π K (p) u -→ π K (z). In particular π K (z) = y. Let j ∈ J\K.
From the previous equality we get z(j) = y(j). Moreover since y(j) ≥ λ |J| we get z(j) ≥ λ |J| . We have proved that z(j) ≥ λ |J| for every j ∈ J. Hence the induction is proved. Now let us prove Theorem 9.1. We consider a witness graph G with a set of states

Q ⊆ N d I .
We also consider a positive integer s ∈ N >0 and we introduce the positive integers a = ||A|| ∞ and x = (1+a)s. Let λ be the adapted extractor defined by λ d = s and the following induction for every n ∈ {2, . . . , d}:

λ n-1 = λ d n (1 + ||A|| ∞ )
An immediate induction provides λ d+1-n n ≤ x d d for every n ∈ {1, . . . , d}. We introduce the minimal excluding set J for (λ, Q). Observe that the number of states in

π J (Q) is bounded by λ d-|J| |J|+1 . Hence |π J (Q)| ≤ x d d
. Let us consider q ∈ Q such that ||q|| ∞ < s. Lemma 9.2 shows that there exists a run q σ -→ x with x(j) ≥ λ |J| for every j ∈ J such that π J (q) σ -→ π J (G) π J (x) and such that:

|σ| ≤ |J| n=1 λ d+1-n n
Since π J (G) is strongly connected there exists a path π J (x) u -→ π J (G) π J (q). We can assume that the length of u is minimal. In particular u = if J = {1, . . . , d} and |u| ≤ λ

d-|J| |J|+1 otherwise. In both case |σu| ≤ dx d d
. Since λ is an adapted extractor we deduce that x(j) ≥ |u| ||A|| ∞ for every j ∈ J and by applying Lemma 3.1 we deduce that there exists a run x u -→ y. Since π J (x) u -→ π J (q) we deduce that y(j) = q(j) for every j ∈ J. Moreover if j ∈ J\I since y(j) ≥ s and s > ||q|| ∞ we get y(j) > q(j). We deduce that q ≤ y and J\I = {i | q(i) = y(i)}. Therefore q is forward pumpable by the cycle π J (q) σu --→ π J (G) π J (q). Symmetrically we prove the backward case. We have proved Theorem 9.1.

Deciding The Reversibility Problem

In this section, the reversible reachability problem is proved to be EXPSPACE-complete. The proof is inspired by the Kosaraju ideas [START_REF] Kosaraju | Decidability of reachability in vector addition systems (preliminary version)[END_REF]. A word α ∈ A * is said to be reversible on a configuration c if there exists a word β ∈ A * such that c αβ --→ c and ∆(α) + ∆(β) = 0. Note that if c is a standard configuration the last condition is implied by the first one.

Theorem 10.1. Let α ∈ A * be a reversible word on a configuration c. There exists another word α ∈ A * reversible on c such that ∆(α) = ∆(α ) and such that:

|α | ≤ 17d 2 x 15d d+2 where x = (1 + 2||A|| ∞ ) (1 + ||p|| ∞ + ||∆(α)|| ∞ ).
Let us assume that α ∈ A * is a reversible word on a configuration c. There exists a word β ∈ A * such that the run p αβ --→ p satisfies ∆(α) + ∆(β) = 0. From this run we extract a unique witness graph G = (Q, T ) such that p αβ --→ G p is a total cycle. In particular the Parikh image of this cycle is a total Kirchhoff function proving that G is reversible by Lemma 7.2. Let I be the set of projected components of G. We introduce a = ||A|| ∞ and s

= 1+||p|| ∞ +||∆(α)|| ∞ . Let q = p+∆ I (α). We have ||q|| ∞ ≤ ||p|| ∞ +||∆(α)|| ∞ < s.
Let us introduce x = (1 + 2a)s. Theorem 9.1 shows that there exists a set of indexes J such that π J (G) has at most x d d states and such that p forward pumpable by a cycle π J (p) v -→ π J (G) π J (p) and q is backward pumpable by a cycle π J (q) w -→ π J (G) π J (q) such that |v|, |w| ≤ dx d d . In particular ∆ I (v) and -∆ I (w) are two vectors in {c ∈

N d I | c(i) = 0 ⇔ i ∈ J}.
We deduce that for every n ∈ N we have:

p v n -→ p + n∆ I (v) q -n∆ I (w) w n --→ q
Since the witness graph G is reversible, Lemma 7.2 shows that π J (G) is reversible. From Theorem 7.3 we deduce that the zero vector is the displacement of a total Kirchhoff function µ for π J (G) satisfying:

||µ|| ∞ ≤ (x d d (1 + 2a)) d(d+1) ≤ x 4d d+2 Note that |π J (T )| ≤ |π J (Q)| |A| ≤ x d d x d ≤ x 2d d
Lemma 10.2. There exists a cycle π J (q) u -→ π J (G) π J (q) such that ∆(v) + ∆(u) + ∆(w) = 0 and:

|u| ≤ 3d x 7d d+2
Proof. Let µ v , µ w be the Parikh images of π J (p)

v -→ π J (G) π J (p) and π J (q) w -→ π J (G) π J (q). We introduce the function λ = (1 + 2dx d d )µ -(µ v + µ w ). Observe that λ is a Kirchhoff function for π J (G) satisfying λ(t) ≥ (1 + 2dx d d ) -2dx d d ≥ 1 for every t ∈ π J (T ). The Euler's Lemma shows that λ is the Parikh image of a total cycle π J (q) u -→ π J (G) π J (q). Observe that ∆(u) = (1 + 2dx d d )0 -(∆(v) + ∆(w)). Hence ∆(v) + ∆(u) + ∆(w) = 0. The length of u is bounded by: |u| = t∈π J (T ) (1 + 2dx d d )µ(t) -(µ v (t) + µ w (t)) ≤ 3dx d d ||µ|| ∞ |π J (T )| ≤ 3dx 7d d+2
Lemma 10.3. There exists a path π J (p) α -→ π J (G) π J (q) such that ∆(α) = ∆(α) and:

|α| ≤ 2x 7d d+2
Proof. Since π J (G) is strongly connected, there exists a path π J (q) β -→ π J (G) π J (p). We can assume that | β| is minimal. In particular | β| < x d d . Moreover, we know that π J (p)

α -→ π J (G) π J (q). Observe that α β is the label of a cycle in π J (G). Hence z = ∆(α) + ∆( β) is the displacement of a Kirchhoff function for G. We have ||z|| ∞ ≤ ||∆(α)|| ∞ +||∆( β)|| ∞ ≤ s+| β|a we get ||z|| ∞ ≤ s+x d d a ≤ x d d (1+a). Theorem 6.3 shows that z is the displacement of a Kirchhoff function θ for G such that: ||θ|| ∞ ≤ ((x d d ) d+1 a(1 + 2a) d + x d d (1 + a)) d ≤ x 4d d+2
We introduce the Parikh image f of the path π J (q) β -→ π J (G) π J (p). Let us add to the strongly connected graph π J (G) an additional transition t • from π J (q) to π J (p) and let G • be this new graph and T • = π J (T )∪{t • } be its set of transitions. Functions θ, µ and f are extended over T

• by θ(t • ) = µ(t • ) = f (t • ) = 0. We also introduce the Parikh image f • of t • , i.e. f • (t • ) = 1 and f • (t) = 0 for every t ∈ π J (T ). Let us observe that g = θ + x d d µ -f + f • is a Kirchhoff function for G • . Since f (t) < x d d
we deduce that g(t) ≥ 1 for every t ∈ π J (T ). Euler's Lemma shows that g is the Parikh image of a total cycle. Since g(t • ) = 1 we deduce that g is the Parikh image of a cycle of the form (π J (p) α -→ π J (q)) t • . By definition of g we get

∆(α) = z + x d d 0 -∆( β). Hence ∆(α) = z -∆( β). Since z = ∆(α) + ∆( β) we get ∆(α) = ∆(α).
The following inequalities provide the lemma:

|α| ≤ |π J (T )| ||θ|| ∞ + x d d |π J (T )| ||µ|| ∞ ≤ 2x 7d d+2
Lemma 10.4. For every n ≥ |u|a we have:

q + n∆ I (v) u n --→ q -n∆ I (w)
Proof. Let n ≥ |u|a. We introduce the sequence (x k ) 0≤k≤n of configurations x k = q + (n -k)∆ I (v) -k∆ I (w). Since π J (x k ) = π J (q) we deduce that there exists a run from π J (x k ) labelled by u. Moreover as ∆ I (v)(j) ≥ 1 and -∆ I (w)(j) ≥ 1 for every j ∈ J, we deduce that x k (j) ≥ n ≥ |u p |a for every j ∈ J. Lemma 3.1 shows that there exists a run from x k labelled by u. Since ∆

(v) + ∆(u) + ∆(w) = 0 we get x k u -→ x k+1 .
Lemma 10.5. For every n ≥ |α|a we have:

p + n∆ I (v) α -→ q + n∆ I (v)
Proof. Observe that π J (p + n∆ I (v)) = π J (p) and π J (p) α -→ π J (q). Moreover for every j ∈ J we have (p + n∆ I (v))(j) ≥ n ≥ |α|a. From Lemma 3.1 we deduce that there exists a run from p + n∆ I (v) labelled by α. From p α -→ q we deduce that p + ∆ I (α) = q. Since ∆(α) = ∆(α) we deduce that p + ∆ I (α) = q. We deduce the run p + n∆ I (v) α -→ q + n∆ I (v).

Finally, let n = a max{|α|, |u|}. We have proved that p α -→ q where α = v n αu n w n . Note that ∆(α ) = ∆(α) since ∆( α) = ∆(α) and ∆(v) + ∆(u) + ∆(w) = 0. We deduce that ∆(α ) = ∆(α). As q β -→ p with ∆(α) + ∆(β) = 0 we deduce that α is reversible on p. Note that n ≤ a3dx 7d d+2 ≤ 3dx 8d d+2

. Hence we have:

|α | ≤ 2x 7d d+2 + 3dx 8d d+2 (2dx d d + 3dx 7d d+2 ) ≤ 17d 2 x 15d d+2
We have proved Theorem 10.1.

Corollary 10.6. Two standard configurations p, q are is the same strongly connected component of a standard subreachability graph if and only if there exist runs p α -→ q and q β -→ p such that:

|α|, |β| ≤ 17d 2 x 15d d+2 where x = (1 + 2||A|| ∞ )(1 + 2 max{||p|| ∞ , ||q|| ∞ }).
Theorem 10.7. The reversible reachability problem is EXPSPACE-complete.

During the execution of a VAS some actions are reversible and some not. More precisely, let D a be the set of standard configurations c such that there exists a word α satisfying c ||c|| ∞ ≤ (102d 2 a 2 ) (15d d+2 ) d+2

Proof. Observe that if a = 0 we are done since in this case c = 0. So we can assume that a ≥ 1. We introduce the extractor λ = (λ 1 , . . . , λ d ) defined by λ d+1 = a and the following induction for n ∈ {1, . . . , d + 1}: and from e d+2 ≤ (15d d+2 ) d+2 we are done.

λ n-1 = 17d 2 (6aλ n ) 15d d+2

Conclusion

The reversible reachability problem is proved to be EXPSPACE-complete in this paper. The proof is inspired by the Rackoff and Kosaraju ideas [START_REF] Rackoff | The covering and boundedness problems for vector addition systems[END_REF][START_REF] Kosaraju | Decidability of reachability in vector addition systems (preliminary version)[END_REF]. We have introduced the domain of reversibility D a of every action a ∈ A. Observe that the reflexive and transitive closure of the following relation R is a congruence and from [START_REF] Bouziane | Cyclic petri net reachability sets are semi-linear effectively constructible[END_REF] we deduce that this relation is definable in the Presburger arithmetic. That means there exist a Preburger formula φ that exactly denotes the pair (x, y) of standard configurations in the reversible reachability relation. As a future work we are interested in characterizing precisely the size of such a formula (we already derive an elementary bound from [START_REF] Bouziane | Cyclic petri net reachability sets are semi-linear effectively constructible[END_REF] and Theorem 11.1).

R = a∈A {(x, x + a) | x ∈ D a }
Such a formula will provide a first hint on the structure of the production relations introduced in [START_REF] Leroux | Vector addition system reachability problem: a short self-contained proof[END_REF] for solving the general vector addition system reachability problem.

  d I of vectors z ∈ Z d such that I = {i | z(i) = }. Operations on Z are extended component-wise into operations on Z d I by interpreting as a projected component. More formally we denote by z 1 + z 2 where z 1 , z 2 ∈ Z d I the vector z ∈ Z d I defined by z(i) = z 1 (i) + z 2 (i) for every i ∈ I. Symmetrically given z ∈ Z d I and an integer k ∈ Z, we denote by kz the vector in Z d I defined by (kz

The

  projection of a vector z ∈ Z d I over a set L ⊆ {1, . . . , d} of indexes is the vector in Z d I∪L defined by π L (z)(i) = z(i) for every i ∈ L. The projection of a set Z ⊆ Z d I over L is defined as expected by π L (Z) = {π L (z) | z ∈ Z}.

A

  Vector Addition System (VAS) is a finite set A ⊆ Z d . Vectors a ∈ A are called actions and vectors c ∈ N d with N = N ∪ { } are called configurations. A configuration in N d is said to be standard and we denote by N d I the set of configurations c ∈ N d such that I = {i | c(i) = }. Given a word σ = a 1 . . . a k of actions a j ∈ A we denote by ∆(σ) the vector in Z d defined by ∆(σ) = k j=1 a j . This vector is called the displacement of σ. We also introduce the vector ∆ I (σ) = π I (∆(σ)). A run ρ from a configuration x ∈ N d I to a configuration y ∈ N d I labelled by a word σ = a 1 . . . a k of actions a j ∈ A is a non-empty word ρ = c 0 . . . c k of configurations c j ∈ N d

Fig. 1 .

 1 Fig. 1. A subreachability graph G and the subreachability graph πL(G) with L = {2, 3}.

  Example 4.1. A standard subreachability graph G = (Q, T ) and the subreachability graph π L (G) projected over the set L = {2, 3} are depicted in Fig. 1.

Example 7. 1 .

 1 Witness graphs depicted in Fig. 1 are reversible. The witness graph G = ({ }, {( , 1, )}) is not reversible.

  d-|I| |I|+1 . By minimality of the length of σ we deduce that |σ| ≤ λ d-|I| |I|+1 .

a-→ c + a α -

 α → c. We observe that the set D a is an upward closed set for the order ≤. In fact c a -→ c + a α -→ c implies the same thing by replacing c with a standard configuration x ∈ c + N d . So D a is characterized by its finite set of minimal elements min(D a ) for ≤. As an application of Theorem 10.1, we obtain the following result. Theorem 11.1. Configurations c ∈ min(D a ) satisfy the following inequality where a = ||A|| ∞ .

  Let c ∈ min(D a ) and let d = c + a. Let us consider the minimal excluding set I for (λ, {d}). By minimality of I we have d(i) < λ |I|+1 for every i ∈ I and d(i) ≥ λ |I| for every i ∈ I. We consider the standard configuration y defined byy(i) = λ |I| if i ∈ I and y(i) = d(i) if i ∈ I. Let us consider q = π I (c) and p = π I (d). Since c ∈ D a there exists a run d α -→ c. In particular p α -→ q a -→ p with ∆(α) + ∆(a) = 0.We deduce that α is reversible on p and Theorem 10.1 shows that there exists a word α such that p α -→ q, ∆(α ) = ∆(α) and:|α | ≤ 17d 2 x 15d d+2 where x = (1 + 2a)(1 + ||p|| ∞ + ||a|| ∞ ). Note that ||p|| ∞ ≤ λ |I|+1 -1. We deduce that x ≤ (1 + 2a)(λ |I|+1 + a) ≤ 6aλ |I|+1 since 1 ≤ aand a ≤ λ |I|+1 . Hence a|α | ≤ λ |I| thanks to the induction defining λ. Since π I (y) = p we deduce that there exists a run from π I (y) labelled by α . As y(i) ≥ λ |I| ≥ a|α | for every i ∈ I, Lemma 3.1 shows that there exists a run y α -→ x. Since ∆(α ) = ∆(α) = -a we deduce that x = ya. From y ≤ d we get x ≤ c by subtracting a. Moreover as x a -→ y α -→ x we deduce that x ∈ D a . By minimality of c we get c = x. Hence c = ya. In particular ||c|| ∞ ≤ λ |I| + a ≤ λ 0 + a. Finally let us get a bound on λ 0 . We get the equality λ n-1 = cλ e n by introducing e = 15d d+2 and c = 17d 2 (6a) e . Hence λ 0 ≤ (ca) e d+1 ≤ (102d 2 a 2 ) e d+2


Dudley Carleton and 'the libertie of old fashioned poetrie' on 8 November 1596

Unpublished SP 12/260, #148, dated 8 Nov 1596, is one of the earliest extant letters from Dudley Carleton to his lifelong friend and correspondent John Chamberlain1 whose own earliest published letter to Dudley was written June 11 1597. 2 The transcription is diplomatic and angle brackets enclose authorial insertions.

Mr : Dudley Carlton Oxford 1596

To his verie louing frend Mr John Chamberlain at Doct : Gilbert 3 his house on S : Peters hill 4 geue these : 189 Sr, I thanck you for hauing me in so good remembrance as to send thes Sonetts which I did much desire, and for to acquainting me with your newes owt of France for which I did more then vsuallie long. The verses 5 please me the more in that they treat of vnaccosta= med matter , and doe make that the subiect of Poetrie to which loosenes which doth accompanie the best wittes cannot learne to frame yt self. For in this much writing age that Poett is in great 10 streites who tieth himself to such a matter that he cannot vse the libertie of old fashioned poetrie as to speake of Goddes , Goddisses , Muses and Cupids , and therfore is the more to be liked by how much the more he is debarred of common helper.

Dudley Carleton

In the letter Dudley thanks his friend for English sonnets and the 'French discourse of a Spanish patissier,' 5 a story he has shown to his university friends with great success. The second half of the letter is devoted to his career prospects as a diplomat in France. He hopes Mr Evers, Sir Peter Evers, 6 will help him get a position with Mildmay, the ambassador to France, and boasts he knows the French King far better than any other student. He recalls a recent unhappy experience on the Continent, when he failed to secure employment at Mildmay's service, and shows little motivation for academic exercises he has not practiced for long. Though the sonnets are not quoted, the letter offers significant literary criticism which throws light on poetic taste in late 1596.

Dudley Carleton came up to Christ Church from Westminster, 7 a school 5 Le Patissier de Madrigal en Espaigne, estimé estre Dom Carles, fils du roy Philippe. A Paris, par Jean Le Blanc, ruë Sainct-Victor, au Soleil d'or. 1596. In-8. Another edition was printed in Poitiers in the same year.

6 'of Lincolnshire, was knighted May 11, 1603', Letters 1861, 4, note d. 7 I am grateful to Judith Curthoys, the archivist of Christ Church college, Oxford, for the following information: Dudley Carleton came up to Christ Church from Westminster School in 1591. There were fourteen other boys who started here that year as well, including two more from Westminster. These were Thomas Lewis, who became a chaplain in the cathedral and then rector of Edlington parish in Yorkshire, and John Ireland who became the headmaster of a grammar school in Croydon, Surrey. His other contemporaries were: George Brook, about whom we know very little; Robert Drew, who became a Member of Parliament; Thomas James, who, like most graduates at Christ Church, became a clergyman; Robert Killigrew, who was an ambassador, and Member of Parliament; John Leigh, who became a fellow of All Souls College and then treasurer to the diocese of Salisbury; William Warmstry, who became registrar to the diocese of Worcester; Thomas White, the founder of Sion College; and George Brook, Philip Pratt, Edmund Turner, Edward Waring, and Edward Waterhouse about whom we know nothing. 'Killigrew was a cosmopolitan and cultured man. When the Dutch diplomat and poet Constantijn Huygens where Camden promoted the writing of verse in the vernacular. [START_REF] Mulcaster | John Dryden -Jonson benefited deeply from the school's traditions of rhetorical and classical training, and, in particular, from the exercise of rendering Greek and Latin verse and prose into their equivalent English forms. Camden, who[END_REF] Ben Jonson, Dudley's contemporary at Westminster, profited immensely from this early practice. 9 In another letter in Latin (SP 12/256, #122) addressed to Chamberlain, Dudley complains that Mars leaves little time to Mercury, 10 which suggests a keen interest in poetry. Many Jacobean and Caroline verse miscellanies in manuscript circulated at Christ Church, [START_REF] Hobbs | Early Seventeenth-Century Verse Miscellany Manuscripts[END_REF] and though no similar manuscripts from the 1590s survive, vernacular verse was already flourishing in college, as shown by the number of poets and playwrights writing in English enrolled at Christ Church -among them Wood singles out Philip Sidney, George Peele and Richard Carew in his history of the university. [START_REF][END_REF] The letter writer notes this is a much writing age, which seems to be a commonplace, judging by Donne's 'Satire 2' (l. 23), 'And they who write, because all write'. [START_REF] Donne | Major Works[END_REF] On 8 August 1596 (SP 12/259, #195), Dudley asked Chamberlain to return a manuscript copy of 'D. AEdes', i.e. Richard Eedes's or Edes's Iter Boreale, 14 'because it is not mine owne but borrowed'. Edes's work, which was never printed, enjoyed a high reputation at Oxford, it seems, for it occurs in a list of writers of the university in the early seventeenth century Bodleian MS misc Eng d 28, p. 647, an Oxford commonplace book, [START_REF] Coatalen | Shakespeare and other 'Tragicall Discourses' in an Early Seventeenth-Century Commonplace Book from Oriel College, Oxford' 120-64[END_REF] and was praised by Meres in his Palladis Tamia (1598) as one of the best for tragedy (p. 283). [START_REF] Bl Add | 41499 A, f.13 contains 'Epilogus Caesaris interfecti[END_REF] He too was educated at Westminster. SP 12/260, f.148 proves there was a strong demand at Oxford for new literary material from London. Interestingly, Carleton kept the English sonnets for himself, perhaps because he did not want other students to use them to catch a patron's attention. He is slightly patronising towards his university friends who are 'men of easye credit', i.e. of less refined literary tastes.

Carleton's correspondence contains a substantial amount of literary criticism. His remarks on Bastard's epigrams 17 and on the theatre 18 are wellknown. He praises the sonnets -sonnets in the modern sense of the word or short poems -for their 'vnaccostamed matter' or original topic. The letter suggests a change in poetic taste, from the 'libertie of old fashioned poetrie as to speake of Goddes, Goddisses, Muses and Cupids' to the deliberate exclusion of the 'common helper'. He notes a poet's reputation is now measured according to his ability to write verse without tapping into the reservoir of ancient myths. It is precisely because of their 'loosenes', or freedom from restraint, that the 'best wittes' cannot frame their verse to the subject of poetry. Dudley goes on by defining loosenes as the refusal to rely on mythological commonplaces, 'the libertie of old fashioned poetrie'. Thus, he opposes two forms of freedom, one negative -'loosenes'the other positive -the use of ancient myths. To find the relevant information, poets could go to an annotated Homer, Virgil or Ovid, but they were more likely to consult one of the handy compendiums assembled by Italian mythographers. 19 Paradoxically, Dudley implies poetic conventions are necessary to deal with 'vnaccostamed matter'. Early modern English writers, who followed Latin authorities in the matter -notably Lucius Annaeus Seneca's 84th of his Epistulae morales, 20 believed there was no contradiction between originality 165 (cf. Chambers, The Elizabethan Stage, iii, p. 84). f. ii b. The same ms, f. 14, has The second Woodstock Entertainment, dated in the margin '1592 September 20'. The first six sections are new, the last six correspond to artt. v-x in Chambers. As follows:-(1) 'The knight that had Charge of the groue', beg. 'Ladye or queene or both'. f. 12;-(2) 'The second knyghts Complaynt', beg. 'What troops are theise'. Attributed to Dr [Richard] Edes in Petyt MS. 538, 43, f. 300b, and there entitled 'The melancholie Knights complaint in the wood'= art. xi in Chambers, op. cit., iii, p. 406. f. 12. [British Library online Manuscripts Catalogue] 17 CSP dom., 1580-1625, addenda, 385. 18 See his letter from London, SP 14/12, #6, January 7, 1604/5 printed in Dudley Carleton to John Chamberlain 1603-1624, Jacobean Letters, ed. M. Lee, Jr. (New Brunswick, 1972), 66-7, in which he reports on Jonson's Masque of Blackness. 19 See Jean Seznec, The Survival of the Pagan Gods: The Mythological Tradition and Its Place in Renaissance Humanism and Art (Princeton, 1953), 312-13, Mindele Anne Treip, Allegorical Poetics & the Epic. The Renaissance Tradition to Paradise Lost (Kentucky, 1993), 28-41. Bocccacio's Genealogiae (Venice, 1494) was the first major compendium. Others included Vincenzo Cartari, Le Imagini con la spositione de i dei de gli antichi (Venice, 1571), Natalis Comes, Mythologiae sive explicationum fabularum libri decem (Venice, 1567), and Lilio Gregorio Giraldi, De deis gentium (Basel, 1548). 20 See B. Vickers, English Renaissance Literary Criticism (Oxford, 1999), 24-5.

  15 I imagine your liking towardes these to be as great as mine , wherfore I haue returned againe these English poemes , accompanied with your French discourse of a Spanish patissier . which discourse I haue communicated with some of my vniuersitie 20 frendes , men of easye credit which beleeue yt better then I doe and are exceedinglie delighted with the noueltie . yt is a hard thing for anie child to know his own father , else might I be brought to indiferent credence in this cause . I am France lookes then they . I praye you yf anie thing come by Mr Euers which concernes me in this cause lett me heare from you , yf nothing , yet lett me heare from you , and ben lett me entreate you not to be sparing of your aduise , for I relie more 50 vppon your iudgment then anie others. I haue heard you often say you did beare <take> small pleasure in writing but that you lou'd to read a long letter , yet I dowbt I haue trobled you so much at this present that yf I should be anye 55 longer I should trie the vttermost of your patience. Wherfore remembring my due com= mendations most hartelie vnto you, I wish you all wellfare. from Oxford. Nouember 8 1596.

	25 gladd to heare of Mr Euers so neere approche
	hoping vppon his arriuall to heare more con=
	cerning Mr Mildmay . for I know not how
	I am fallen into a more then earnest longing
	after his seruice whilst he is in France. And
	30 though I might be iudged to be distasted
	with such kind of course , by the vnhappie success
	of my last iorneye, yet that hath geuen me
	a greater edge, and made me like to those
	gamesters who account yt a good sighne to loose
	35 at first . Besides I haue reapt so much yt iorneye
	verso
	that though yt hath not sett me in such forwardness
	as to make me haue a good conceipt of my self of
	vnusuall fittnes to such kind of seruises, yet yt
	40 hath worked so much with me as to make me attmost
	vnfitt for anie other kind of course . for through
	dissuetude I find my self to be behind hand with
	diuerse of my old companions in ordinarie s<c>holers
	exersises , though I can better tell how the k. of
	45

60 yours allwaies most assuredlie

The earliest are SP 12/256, #12 (29 Feb 1595), SP 12/255, #74 (5 Aug 1595), SP 78/37, #105 (22 Mars [1596]), SP 12/259, #195 (8 Aug 1596).

Letters written by John Chamberlain during the reign of Queen Elizabeth, ed. Sarah Williams (London, 1861), 1-5.

William Gilbert (1540-1603), physician to Queen Elizabeth and author of the first treatise on magnetism. 'His will mentions one godson, and two 'good ffrends', a Mr Harwood and, more significantly, John Chamberlain. Chamberlain, the famous gossipy correspondent, lodged with Gilbert in Wingfield House between c.1595 and 1601, and mentioned him respectfully' Stephen Pumfrey, 'Gilbert, William (1544?-1603)', Oxford Dictionary of National Biography (Oxford, 2004).

'By 1595 Gilbert had acquired and moved into Wingfield House in St Peter's Hill, a substantial property near St Paul's Cathedral possibly inherited from his stepmother' Pumfrey, ODNB.

dissuetude ] An obscure word for which there are only two later occurrences in the OED on CD-ROM (Oxford, 1992): '1639 Spottiswood Hist. Ch. Scot. vi. (1677) 464 His long dissuetude of the Country-language made him unuseful at first. 1755 Johnson s.v. Disuse 1, Cessation of use, dissuetude; want of practice'.


Olivier Fruchart
email: olivier.fruchart@grenoble.cnrs.fr

Bernard Diény

Magnetostatics of synthetic ferrimagnet elements

We calculate the magnetostatic energy of synthetic ferrimagnet (SyF) elements, consisting of two thin ferromagnetic layers coupled antiferromagnetically, e.g. through RKKY coupling. Uniform magnetization is assumed in each layer. Exact formulas as well as approximate yet accurate ones are provided. These may be used to evaluate

various quantities of SyF such as shape-induced coercivity and thermal stability, like demagnetizing coefficients are used in single elements. Synthetic antiferromagnets (SAF, resp. ferrimagnets, SyF) [1,2] consist of two thin ferromagnetic films of moments of same (resp. different) magnitude, strongly coupled antiferromagnetically thanks to the RKKY interaction through an ultrathin spacer layer, typically Ru 0.6 -0.9 nm thick [START_REF] Parkin | Systematic variation of the strength and oscillation period of indirect magnetic exchange coupling through the 3d, 4d, and 5d transition metals[END_REF]. Hereon we consider only the case of in-plane magnetized layers. SyFs are widely used to provide spin-polarized layers displaying an overall weak moment. One benefit is to minimize cross-talk of neighboring (e.g. memory bits) or stacked (e.g. in a spin-valve) elements through stray-field coupling [1,2], such as in Magnetic Random Access Memory (MRAM) [START_REF] Sousa | Non-volatile magnetic random access memories (mram)[END_REF]. SyFs are also used to decrease the Zeeman coupling with external fields, e.g. to increase coercivity in reference layers [START_REF] Van Den Berg | Gmr sensor scheme with artificial antiferromagnetic subsystem[END_REF], decrease effects of the Oersted field in magneto-resistive or spin-torque oscillator pillars, or more recently boost the current-induced domain-wall propagation speed in nanostripes [START_REF] Pizzini | High domain wall velocity at zero magnetic field induced by low current densities in spin-valve nanostripes[END_REF][START_REF] Chanthbouala | Vertical-current-induced domain-wall motion in mgo-based magnetic tunnel junctions with low current densities[END_REF].

In practice SyFs are used as elements of finite lateral size. It has been shown [START_REF] Sun | Thermal activation-induced sweep-rate dependence of magnetic switching astroid[END_REF] and it is widely used [START_REF] Worledge | Magnetic phase diagram of two identical coupled nanomagnets[END_REF][START_REF] Fujiwara | Critical-field curves for switching toggle mode magnetoresistance random access memory devices[END_REF] that for flat and magnetically soft nanomagnets of lateral size smaller than a few hundreds of nanometers, the macrospin approximation (uniform magnetization) is largely correct. In this framework the coercive field equals the anisotropy field 2K/µ 0 M s and the energy barrier KV (V is the volume of the dot) preventing spontaneous magnetization reversal equals the magnitude of anisotropy of the total magnetic energy E, to which all the physics therefore boils down. Elongated dots are often used to induce or contribute to an easy axis of magnetization and an energy barrier ∆E, based on dipolar energy. Dipolar energy is a quadratic form and thus it is fully determined by its value along the two main in-plane axes. For single elements ∆E d = K d V ∆N with ∆N the difference between the two in-plane demagnetizing coefficients, and

K d = (1/2)µ 0 M 2
s . Analytical formulas have been known for a long time to evaluate the mutual energy of an arbitrary set of prisms [START_REF] Rhodes | Demagnetizing energies of uniformly magnetized rectangular blocks[END_REF]. However while simple expressions for N and thus ∆E d have been described, displayed and discussed for single-layer flat elements [START_REF] Rhodes | Demagnetizing energies of uniformly magnetized rectangular blocks[END_REF][START_REF] Aharoni | Demagnetizing factors for rectangular ferromagnetic prisms[END_REF], the analytical expressions and the evaluation of E d in SyFs have not been discussed in detail so far. Instead the studies requiring estimation of the dipolar energy in SyF, mainly pertaining to MRAM cells [START_REF] Worledge | Magnetic phase diagram of two identical coupled nanomagnets[END_REF][START_REF] Fujiwara | Critical-field curves for switching toggle mode magnetoresistance random access memory devices[END_REF][START_REF] Han | A new analytical/numerical combined method for the calculation of the magnetic energy barrier in a nanostructured synthetic antiferromagnet[END_REF], have in the best case made use of an effective socalled attenuation coefficient with respect to self-energy [START_REF] Fujiwara | Critical-field curves for switching toggle mode magnetoresistance random access memory devices[END_REF], which requires a numerical evaluation [START_REF] Han | A new analytical/numerical combined method for the calculation of the magnetic energy barrier in a nanostructured synthetic antiferromagnet[END_REF]. The meaning and scaling laws of this attenuation coefficient have never been discussed in detail, hiding the physics at play. As thermal stability, coercivity and toggle switching fields [START_REF] Worledge | Magnetic phase diagram of two identical coupled nanomagnets[END_REF][START_REF] Fujiwara | Critical-field curves for switching toggle mode magnetoresistance random access memory devices[END_REF][START_REF] Kim | Effects of induced anisotropy on the bit stability and switching field in magnetic random access memor[END_REF] depend crucially on the interlayer magnetostatic coupling, it is desirable to have a simple yet accurate analytical expression for interlayer dipolar fields. In this manuscript we report exact analytical expressions for the magnetostatics of SyFs uniformly-magnetized in each sub-layer. From the numerical evaluation we discuss the physics at play, while from the analytical formulas we propose an approximate yet accurate scaling law for their straightforward table-top evaluation.

We first consider SyF prisms and name F1 and F2 the two ferromagnetic layers (Figure 1), with magnetization aligned along z. This covers the case of both finite-size prisms as well as infinitely-long stripes with a rectangular cross-section. We apply formulas expressing the interaction between two parallel charged surfaces [START_REF] Rhodes | Demagnetizing energies of uniformly magnetized rectangular blocks[END_REF], and adopt the convenient notation of F ijk functions, the i, j and k-fold indefinite integrals along x, y and z of the Green's function F 000 = 1/r [START_REF] Hubert | Magnetic domains. The analysis of magnetic microstructures[END_REF]. The only such function needed here is

F 220 = 1 2 [x(v -w)L x + y(u -w)L y ] -xyP z + 1 6 r(3w -r 2 ) (1) with u = x 2 , v = y 2 , w = z 2 , r = √ u + v + w, L x = (1/2) ln[(r + x)/(r -x)] etc, P x =
x arctan(yz/xr) etc, and L x = 0 and P x = 0 for x = 0 etc.

The integrated magnetostatic energy of a single prismatic element of thickness t is:

E d = 2K d π δa,δt,δc∈{0,1} (-1) δa+δt+δc F 220 (aδ a , tδ t , cδ c ) (2)
which normalized to K d yields the demagnetizing coefficient N z . It can be verified that Eq. ( 2) coincides with the explicit formula already known [START_REF] Aharoni | Demagnetizing factors for rectangular ferromagnetic prisms[END_REF]. The magnetostatic energy of a prismatic SyF element may be calculated using the same formalism , may be written as:

E d = K d,1 N z (a, t 1 , c)V 1 + K d,2 N z (a, t 2 , c)V 2 +2 K d,1 K d,2 N m (a, t 1 , s, t 2 , c) V 1 V 2 (3) with N m (a, t 1 , s, t 2 , c) = 1 πa √ t1t2c δ1,δ2,δa,δc∈{0,1} (-1) δ1+δ2+δa+δc × F 220 (aδ a , s + t 1 δ 1 + t 2 δ 2 , cδ c
) is a mutual magnetostatic coefficient with a negative value, and

V i = at i c (resp. K d,i
) is the volume (resp. dipolar constant) of each single prism i. This equation of dipolar energy is a quadratic form of M 1 and M 2 , generalizing the definition of demagnetizing coefficients. above F1, considering or not the interaction between the two layers. In the latter case the energy increase nearly scales with t 2 2 , which is understandable because it is a self-energy (in F 2 alone). In the coupled case (a SyF) E d retains like for the uncoupled case an overall close-to-parabolic convex shape as can be verified with fitting, however with an initial negative slope. This can be understood as for low t 2 the extra edge charges induced by an infinitesimal increase δt 2 mainly feel the stabilizing stray field arising from F1, while for large t 2 they feel more the nearby charges induced by F2 itself. Notice that, contrary to what could be a first guess, the minimum of E d (t 2 ) occurs before the compensation of moment (t 1 = t 2 ). This stems from the same argument as above, which is that magnetic charges at an edge of F2 are closer to another than to the charges on the nearby edge of F1, thus for an identical amount δt 2 contribute more to E d .

Figure 2(b) shows the full plot of E d (t 1 , t 2 ) for s = 0.7 nm. The above arguments appear general. From this figure let us outline three take-away messages. 1. For a given t 1 the minimum of E d of a SyF is found for t 2 t 1 /2. 2. At this minimum E d is reduced by only ≈ 20-30 % with respect to a single-layer element of thickness t 1 considered alone.

3. E d roughly regains the value of the single layer at the moment compensation point

(t 1 = t 2 ).
This sheds light on results previously noticed empirically, however whose origin and generality had not been highlighted. Wiese et al. reported that the effective dipolar field anisotropy of a SyF basically scales with the inverse net moment [START_REF] Wiese | Switching of submicron-sized, antiferromagnetically coupled cofeb/ru/cofeb trilayers[END_REF], i.e. like the inverse strength of Zeeman energy. This suggests that ∆E d is essentially independent of the imbalance of moment, which goes against the widespread belief that magnetostatic energy nearly vanishes upon moment compensation. Our results clarify and quantify this: the dipolar energy does not differ more than 20-30 % from that of a single layer for t 2 t 1 (Figure 2a [START_REF] Parkin | Systematic variation of the strength and oscillation period of indirect magnetic exchange coupling through the 3d, 4d, and 5d transition metals[END_REF]. As explained in the introduction, we recall that thermal stability is determined by the energy barrier along the hard axis direction, with respect to the easy axis direction. In the case of anisotropy arising from dipolar energy and an elongated shape of the element, this barrier can be evaluated straightforwardly by calculating once E d along the short edge of the dot, and second along the long edge of the dot. Doing this we explain the findings of Saito et al.., whereas a reduction of 50 % would be expected on the basis of compensated moments (the numbers in brackets are thicknesses in nanometers). Our calculations may also be applicable to the cross-over of vortex versus single domain in flat disks [START_REF] Cowburn | Property variation with shape in magnetic nanoelements[END_REF] or vortex versus transverse domain walls in stripes [START_REF] Mcmichael | Head to head domain wall structures in thin magnetic strips[END_REF], whose scaling law t × a = Cte may be derived qualitatively by equaling the energy of a vortex ∼ t and that of a singledomain ∼ a 2 t(t/a) (here V = a 2 t is the volume, and t/a the demagnetizing coefficient).

Interestingly Tezuka et al. noticed that there is an optimum ferromagnetic film thickness at which SyAF can obtain a single-domain structure. This minimum (related to a minimum of demagnetization energy) is found for an imbalanced thickness in good quantitative agreement with Figure 2b.

With a view to promote the use of accurate magnetostatics for SyF while eliminating the need for numerical evaluation, we derived approximate yet highly accurate expressions for E d . Figure 3a shows that to a very good approximation, E d is proportional to the width of the element (along x) and is independent of its length (along z). This is already accurate for a single-layer (t 2 = 0), and is very accurate close to the compensation t 1 = t 2 because edges then behave as lines of dipoles, whose stray field quickly decays with distance (∼ 1/r 2 ). Thus E d boils down to a single line integral along its edge:

Energy(10 J)
E d = E λ (m.n) 2 ds (4) = E λ |dx| 1 + (∂ x f ) 2 (5) = E λ 2π 0 (r sin θ -∂ θ r cos θ) 2 (∂ θ r) 2 + r 2 dθ (6)
Eq. ( 4) is the general expression, expressed in the following two lines in cartesian and polar coordinates (Figure 4a). E λ is the density of magnetostatic energy per unit length of edge, a concept once discussed in the case of single layers [START_REF] Yuan | Size effects of switching fields of thin permalloy particles[END_REF]. Equations [START_REF] Sousa | Non-volatile magnetic random access memories (mram)[END_REF][START_REF] Van Den Berg | Gmr sensor scheme with artificial antiferromagnetic subsystem[END_REF][START_REF] Pizzini | High domain wall velocity at zero magnetic field induced by low current densities in spin-valve nanostripes[END_REF] apply to an arbitrary shape of perimeter (not simply rectangles for prisms) by considering the inplane angle ϕ between magnetization and the normal to the edge. It can be verified that for a SAF we have, with an accuracy better than 10 % for geometrical parameters relevant for practical cases, i.e. t 1,2 in the range of 2 -10 nm and sintherangeof 0.5 -1 nm:

E λ ≈ (1/2)K d t 2 (7)
The meaning of Eq. ( 7) is straightforward: due to the short range of interaction between dipolar lines, the density of dipolar energy is non-zero only in the vicinity of the edges, with a lateral range t. Thus a volume t 2 is concerned with a line density of energy of the order of K d . Expressions for non-compensated cases (including single elements) may also be evaluated. This provides us with analytical expressions for the magnetostatics of SyFs for the most usual shapes (Figure 4b).

A scaling law sometimes used as a first guess is based on the point dipole approximation. In this framework the energy gained by coupling F1 and F2 would roughly scale with K d a 4 /t, resulting from two point moments M s a 2 t interacting like 1/t 3 (for s ≪ t, and assuming lateral dimensions of the order of a). The scaling arising from our exact calculation is aE λ ∼ K d at 2 (Eq. ( 7) and Figure 4a). The point dipole approximation is thus clearly incorrect with an extra scaling (a/t) 3 (see Figure 4a) which largely overestimates the dipolar coupling. This is a general argument for any flat element, where dipolar fields are short-ranged [START_REF] Fruchart | Enhanced coercivity in sub-micrometer-sized ultrathin epitaxial dots with in-plane magnetization[END_REF] and thus the point-dipole approximation is clearly incorrect.

To conclude we derived exact formulas for the magnetostatics of prism SyF, and simple yet accurate forms for SyFs of arbitrary shapes. These simple forms may be used straightforwardly to derive scaling laws for all aspects of SyF physics pertaining with dipolar energy such as thermal stability, coercivity and anisotropy field. Notice that similar to the case of single flat elements edge roughness is liable to reduce significantly dipolar energy [START_REF] Cowburn | Lateral interface anisotropy in nanomagnets[END_REF][START_REF] Uhlig | Systematic study of the magnetization reversal in patterned co and nife nanolines[END_REF][START_REF] Moon | Experimental determination technique for magnetic anisotropy of individual nanowires[END_REF], so that the theoretical predictions need to be considered as upper bounds to the experimental values. The non-uniformity of magnetization is not expected to have a significant impact for lateral sizes below a few hundreds of nanometers [START_REF] Sun | Thermal activation-induced sweep-rate dependence of magnetic switching astroid[END_REF].

We acknowledge useful discussions with Y. Henry, IPCMS-Strasbourg.

Figure 1 :

 1 Figure 1: Geometry and notations of a prismatic SyF element comprising two ferromagnetic layers F 1 and F 2 .

Figure 2 :

 2 Figure 2: Magnetostatic energy of a SyF with c = 2a = 100 nm, M 1,2 = 10 6 A/m, s = 0.7 nm. (a) Sum of the energies of two prisms without mutual interaction, and when embedded in the SyF geometry. t 1 is kept constant at 2.5 nm, while t 2 is varied. (b) Energy of the general SyF. The curved lines are those of minimum energy for either constant t 1 or t 2 . The thick horizontal dotted line highlights the path for the SyF curve shown in (a).

Figure 2 (

 2 Figure 2(a) shows E d upon building a SyF via the progressive thickness increase of F2

Figure 3 :

 3 Figure 3: (a) Energy of a single layer (full symbols) and SyF (open symbols) as a function of dot length, i.e. along z, while a = 100 nm. (b) Energy of a single layer as a function of width (along x, open symbols), and length (along z, full symbols, same curve as in a), while the other in-plane dimension is kept constant at 100 nm. The lines are linear fits. For both plots the parameters are: M i = 10 6 A/m, t 1 = t 2 = 2.5 nm, s = 0.7 nm.

Figure 4 :

 4 Figure 4: (a) notations for the calculation of edge energy (b) integrated magnetostatic energy for various shapes. E is the elliptical integral of the second kind. See text for the definition of E λ .

  , dotted line). Saito et al. also reported that the thermal stability of Co 90 Fe 10 [3] /Ru[0.95] /Co 90 Fe 10 [5] is similar to that of Co 90 Fe 10