Jean-Franc ¸ois Condotta
email: condotta@cril.fr

Christophe Lecoutre
email: lecoutre@cril.fr

A Class of ⋄ f -consistencies for Qualitative Constraint Networks

In this paper, we introduce a new class of local consistencies, called ⋄ f -consistencies, for qualitative constraint networks. Each consistency of this class is based on weak composition (⋄) and a mapping f that provides a covering for each relation. We study the connections existing between some properties of mappings f and the relative inference strength of ⋄ f -consistencies. The consistency obtained by the usual closure under weak composition is shown to be the weakest element of the class, and new promising perspectives are shown to be opened by ⋄ f -consistencies stronger than weak composition. We also propose a generic algorithm that allows us to compute the closure of qualitative constraint networks under any "well-behaved" consistency of the class. The experimentation that we have conducted on qualitative constraint networks from the Interval Algebra shows the interest of these new local consistencies, in particular for the consistency problem.

Introduction

Qualitative Spatial-Temporal Reasoning (QSTR) is an area of computer science dealing with qualitative information about configurations of spatial/temporal entities. A calculus in QSTR introduces particular elements for representing the entities and a finite set of base relations on these elements. Each base relation is an abstraction of concrete metric information about the relative position of entities. For applications in domains such as e.g. geographic information systems and natural language understanding, a qualitative description can reveal to be far more appropriate than a metric description, in particular when precise information is not necessary or simply not available. In the past twenty years, numerous QSTR formalisms have been proposed and studied; see e.g. [START_REF] Randell | A spatial logic based on regions and connection[END_REF][START_REF] Pujari | INDU: an interval and duration network[END_REF][START_REF] Renz | Qualitative spatial reasoning using constraint calculi[END_REF].

In QSTR, Qualitative Constraint Networks (QCNs) are typically used to express information on spatial/temporal situations. A constraint represents a set of acceptable qualitative configurations between some variables (entities), and is then defined by a set of base relations. Given a QCN, the Copyright c 2010, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. main problem is to determine whether the information contained in the QCN is consistent. In the general case, this problem is NP-hard. However, because the worst-case only arises within a limited range of situations, many studies have been led to develop efficient practical approaches to solve this problem.

One such approach is backtrack search combined with a constraint propagation mechanism based on tractable subclasses of relations and the closure of QCNs under weak composition, which is an operation denoted by ⋄ and related to path consistency [START_REF] Mackworth | Consistency in networks of relations[END_REF]. More precisely, at each step of search, a constraint is split into relations belonging to a tractable class and closure under weak composition is an inference method applied to filter the search space (i.e. to reduce its size) by removing some inconsistent base relations. This effective approach, initiated by Nebel, has been adopted by most of the qualitative constraint solvers [START_REF] Condotta | A generic toolkit for n-ary qualitative temporal and spatial calculi[END_REF][START_REF] Gantner | GQR a fast reasoner for binary qualitative constraint calculi[END_REF], and in particular by GQR*, which is currently the fastest solver. On the other hand, some recent approaches [START_REF] Pham | Towards an efficient sat encoding for temporal reasoning[END_REF][START_REF] Westphal | Qualitative CSP, finite CSP and SAT: Comparing methods for qualitative constraint-based reasoning[END_REF][START_REF] Li | A divide-andconquer approach for solving interval algebra networks[END_REF] translate the consistency problem of QCNs into CSP (Constraint Satisfaction Problem) or SAT (propositional satisfiability) instances. Published results indicate that these approaches are promising.

Closure under weak composition is at the heart of the various approaches that directly handle qualitative constraint networks. It was the first inference method used to address the consistency problem of the temporal QCNs in the wellknown Interval Algebra [START_REF] Allen | An interval-based representation of temporal knowledge[END_REF]. Weak composition is currently recognized as an operation that offers a good balance between the execution overhead and the filtering benefit. Besides, it has been shown to be a complete approach for most of the identified tractable classes. Nevertheless, for the hardest QCNs it may be worthwhile to consider operations stronger than ⋄, i.e. stronger forms of local consistency.

In this paper, we propose a new class of local consistencies adapted to qualitative calculi. Each of them is defined from ⋄ and a mapping f that associates with every relation r of a qualitative calculus a set of sub-relations of r forming a covering of r. Intuitively, a QCN is ⋄ f -consistent if and only if after substituting any sub-relation defined by f for the relation associated with a constraint of the QCN, the obtained QCN is closed under ⋄. We prove that ⋄ corresponds to the weakest consistency of the class whereas a local consistency similar to SAC, Singleton Arc Consistency [START_REF] Debruyne | Some practical filtering techniques for the constraint satisfaction problem[END_REF] introduced for CSP, is the strongest one. Other consistencies of the class are situated between these two bounds since the class forms a complete lattice. We also characterize an important subset of the class of ⋄ f -consistencies that contains consistencies under which closure of QCNs exists, and we propose a general-purpose algorithm to enforce any of them. A preliminary experimentation carried out using the Interval Algebra shows promising results.

Preliminaries

A qualitative calculus is defined from a finite set B of base relations on a domain D. Without any loss of generality, we will only consider binary relations. The elements of D represent temporal or spatial entities, and the elements of B represent all possible configurations between two entities. B is a set that satisfies the following properties [START_REF] Ligozat | What is a qualitative calculus? a general framework[END_REF]): B forms a partition of D × D, B contains the identity relation Id, and B is closed under the converse operation ( -1 ). A (complex) relation is the union of some base relations, but it is customary to represent a relation as the set of base relations contained in it. Hence, the set 2 B will represent the set of relations of the qualitative calculus. The set 2 B is equipped with the weak composition operation, denoted by ⋄ and defined by: ∀a

, b ∈ B, a ⋄ b = {c ∈ B : ∃x, y, z ∈ D | x a z ∧ z b y ∧ x c y}; ∀r, s ∈ 2 B , r ⋄ s = a∈r,b∈s {a ⋄ b}. Note that r ⋄ s is the smallest relation of 2 B including the usual relational compo- sition r • s = {(x, y) ∈ D × D : ∃z ∈ D | x r z ∧ z s y}.
In some qualitative algebras (e.g. the Interval Algebra introduced below), r • s and r ⋄ s are identical.

A well known temporal qualitative formalism is the Interval Algebra, also called Allen's calculus [START_REF] Allen | An interval-based representation of temporal knowledge[END_REF]. The domain D int of this calculus is the set {(x -, x + ) ∈ Q × Q : x -< x + } since temporal entities are intervals of the rational line. The set B int of this calculus is the set {eq, p, pi, m, mi, o, oi, s, si, d, di, f, f i} of thirteen binary relations representing all orderings of the four endpoints of two intervals; see Figure 1.

A Qualitative Constraint Network (QCN) is a pair composed of a set of variables and a set of constraints. Each variable represents a spatial/temporal entity of the system that is modelled. Each constraint represents a set of acceptable qualitative configurations between two variables and is defined by a relation. Formally, a QCN is defined as follows:

Definition 1 A QCN is a pair N = (V, C) where:

• V = {v 1 , . . . , v n } is a finite set of n variables; • C is a mapping that associates a relation C(v i , v j ) ∈ 2 B , also denoted by C ij or N [i, j], with each pair (v i , v j ) of V × V . C is such that C ii ⊆ {Id} and C ij = C -1 ji . A partial solution of N on V ′ ⊆ V is a mapping σ de- fined from V ′ to D such that for every pair (v i , v j ) of vari- ables in V ′ , (σ(v i ), σ(v j )) satisfies C ij , i.
∈ C ij such that (σ(v i ), σ(v j )) ∈ b. A solu- tion of N is a partial solution of N on V .
N is consistent iff it admits a solution. Two QCNs are equivalent iff they admit the same set of solutions. A subQCN

N ′ of N , denoted by N ′ ⊆ N , is a QCN (V, C ′ ) such that C ′ ij ⊆ C ij , for every pair (v i , v j ) of variables. An atomic QCN is a QCN such that each constraint is defined by a base relation. A scenario S of N is an atomic consistent subQCN of N . A base relation for C ij is inconsistent iff there does not exist any scenario S of N such that S[i, j] = {b}. A QCN N = (V, C) is said to be ⋄-consistent or closed under weak composition if and only if C ij ⊆ C ik ⋄ C kj ∀v i , v j , v k ∈ V .
The closure under weak composition of N , denoted by ⋄(N ), is the greatest (w.r.t. ⊆) ⋄-consistent subQCN of N ; ⋄(N ) is equivalent to N . This (sub)QCN can be obtained by iterating the triangulation operation:

C ij ← C ij ∩ (C ik ⋄ C kj ), ∀v i , v j , v k ∈ V
until a fixed point is reached. This method can be implemented by an algorithm running in O(n 3 ) time. Weak composition admits the following properties:

• ⋄(N ) ⊆ N (⋄ is contracting), • ⋄(⋄(N )) = ⋄(N ) (⋄ is idempotent), • N ⊆ N ′ ⇒ ⋄(N ) ⊆ ⋄(N ′ ) (⋄ is monotonic). N [i,j]/r , with v i , v j ∈ V and r ∈ 2 B , is the QCN (V, C ′ ) defined by C ′ ij = r, C ′ ji = r -1 and C ′ kl = C kl ∀(v k , v l ) ∈ V × V \ {(v i , v j ), (v j , v i )}. The union of two QCNs N = (V, C) and N ′ = (V, C ′ ) is the QCN N ∪ N ′ = (V, C ′′ ) such that ∀(v i , v j ) ∈ V , C ′′ ij = C ij ∪ C ′ ij .
The Class of ⋄ f -consistencies

In this section, we introduce (for qualitative constraint networks) a general class of local consistencies, called ⋄ f -consistencies, where f is a mapping that associates a set of relations of 2 B with each relation of 2 B . Intuitively, a QCN is said to be ⋄ f -consistent iff for any constraint C ij of the QCN, after substituting any element r ′ of f (r) for the relation r associated with C ij and computing the closure under weak composition, the relation r ′ associated with C ij is let unchanged. Before proposing a formal definition of ⋄ fconsistencies, we introduce a set F that exactly contains the mappings f considered hereafter. More precisely, F is the set of mappings f defined from 2 B to 2 2 B associating a set of relations f (r) ∈ 2 2 B with each relation r ∈ 2 B such that f (r) = r, and ∅ ∈ f (r) when r = ∅. Note that f (r) is a covering of r and f ({b}) = {{b}}∀b ∈ B. Moreover, we have f (∅) = {∅}, which will be always implicitly assumed whenever we introduce a mapping later.

Definition 2 Let f be an element of F. A QCN N is ⋄ f - consistent iff for every pair (v i , v j ) of variables of N and for every s ∈ f (N [i, j]), ⋄(N [i,j]/s )[i, j] = s.
We obtain a new class (or family) of local consistencies since each mapping f ∈ F determines a new consistency denoted by ⋄ f . The class (set) of all ⋄ f -consistencies that can be built from elements of F is denoted by ⋄ F . The following result shows the practical interest of the new class of consistencies: when a QCN is not ⋄ f -consistent, some base relations said to be ⋄ f -inconsistent can be identified and safely removed.

Proposition 1 Let f be an element of F, N be a QCN,

(v i , v j ) be a pair of variables of N and s ∈ f (N [i, j]). Any base relation b in s \ ⋄(N [i,j]/s )[i, j] is inconsistent for C ij . Proof. Let S be a scenario of N and b ′ be the base relation in S[i, j]. Either we have b ′ / ∈ s or b ′ ∈ s. If b ′ / ∈ s, necessarily b ′ = b. On the other hand, if b ′ ∈ s then b ′ ∈ ⋄(N [i,j]/s )[i, j] because ⋄ preserves scenarios. By hypothesis, b / ∈ ⋄(N [i,j]/s )[i, j],
which proves that b ′ = b. We conclude that v i b v j cannot be true in any scenario. ⊣

The following mappings will be useful to illustrate our purpose. ∀r ∈ 2 B \ {∅}:

• f B associates the set f B (r) = {{b} : b ∈ r} with r. • f = associates the set f = (r) = {r \ {b} : b ∈ r} with r iff |r| > 1; f = (r) = {r} otherwise. • f ⋄ associates the set f ⋄ (r) = {r} with r.
For example, if r = {p, m, o}, then f B (r) = {{p}, {m}, {o}} and f = (r) = {{p, m}, {p, o}, {m, o}}. Moreover, given a partition P = {r 1 , . . . , r k } of B, the mapping f P is defined as follows: for every relation

r ∈ 2 B , f (r) = {r ∩ r i : i ∈ {1, . . . , k}} \ {∅}. Note that ⋄
f B is a consistency that can be related to SAC (introduced for CSP) but ⋄ f = and partition-based consistencies ⋄ f P (as well as many other ⋄ f -consistencies) have no CSP counterpart. We will consider later the following (representative) partitions of B int :

• P 1 = {{p, m, o, f i, s, d}, {pi, mi, oi, f, si, di, eq}} • P 2 = {{p, m, o}, {f i, s, d}, {pi, mi, oi}, {f, si, di, eq}} • P 3 = {{p}, {m, o}, {f i}, {s, d}, {pi}, {mi, oi}, {f, eq}, {si, di}}
In order to compare the inference capability of different consistencies, we need to introduce a preorder. Let φ and ψ be two consistencies in ⋄ F , φ is stronger than ψ, denoted by φ ψ, iff whenever φ holds on a QCN N (i.e. N is φconsistent), ψ also holds on N ; φ is strictly stronger than ψ, denoted by φ ⊲ ψ, iff φ is stronger than ψ and there exists at least one QCN N such that ψ holds on N but not φ. Finally, φ and ψ are equivalent, denoted by φ ≈ ψ, iff both φ ψ and ψ φ.

First, we can show that a QCN N is ⋄ f⋄ -consistent if, and only if, N is closed under weak composition.

Proposition 2 The consistency ⋄ f⋄ is equivalent to ⋄. Proof. N is ⋄-consistent ⇔ ⋄(N ) = N ⇔ for every pair (v i , v j ) of variables of N , ⋄(N )[i, j] = N [i, j] ⇔ for every pair (v i , v j ) of variables of N and for every s ∈ f ⋄ (N [i, j]), ⋄(N [i,j]/s )[i, j] = s (because f ⋄ (r) = {r} for each relation r ∈ 2 B ) ⇔ N is ⋄ f⋄ -consistent ⊣
The finer the coverings of relations by an element f of F are, the stronger the consistency ⋄ f is. In particular, to relate ⋄ f -consistencies, we have the following result: Proposition 3 Let f, f ′ be two elements of F. If for every r ∈ 2 B and for every s ′ ∈ f ′ (r), there exists a set of relations

S ⊆ f (r) such that s ′ = S, then ⋄ f ⋄ f ′ . Proof. We suppose that we have a QCN N that is ⋄ f -consistent. Let v i , v j be two variables of N , r = N [i, j]
and s ′ be an element of f ′ (r). By hypothesis, there exists a set of relations S ⊆ f (r) such that s ′ = S. For every relation s ∈ S we have s ⊆ s ′ , and because

N [i,j]/s ⊆ N [i,j]/s ′ and ⋄ is monotonic, we have ⋄(N [i,j]/s )[i, j] ⊆ ⋄(N [i,j]/s ′ )[i, j]. We can deduce that {⋄(N [i,j]/s )[i, j] : s ∈ S} ⊆ ⋄(N [i,j]/s ′ )[i, j]. Since N is ⋄ f -consistent (by hypothesis), for every relation s ∈ S, we have ⋄(N [i,j]/s )[i, j] = s. Hence, S ⊆ ⋄(N [i,j]/s ′ )[i, j],
and as s ′ = S, we obtain

s ′ ⊆ ⋄(N [i,j]/s ′ )[i, j].
On the other hand, we also know that

⋄(N [i,j]/s ′ )[i, j] ⊆ s ′ because ⋄ is contracting. We can conclude that s ′ = ⋄(N [i,j]/s ′ )[i, j] and consequently that N is ⋄ f ′ -consistent. ⊣
For example, for the Interval Algebra, we have ⋄

f B ⋄ f P 3 ⋄ f P 2 ⋄ f P 1 ⋄ f⋄ . The following corollary stipulates that ⋄ f B is the strongest consistency (of ⋄ F ) and ⋄ f⋄ is the weakest one. Corollary 1 For every element f ∈ F, ⋄ f B ⋄ f ⋄ f⋄ . From this result, we can deduce in particular that ⋄ f B ⋄ f = ⋄
f⋄ . Now, let us consider the three QCNs of the Interval Algebra depicted in Figure 2. On each of these graphs, a variable is represented by a node, and a constraint by an arc labelled with the associated relation; note that, for simplicity, there is no arc going from v i to v j when either there is already an arc going from v j to v i or i = j. We can check that

N 1 is ⋄ f⋄ -consistent but not ⋄ f = -consistent because di / ∈ ⋄(N 1[0,1]/{di,m} )[0, 1], N 2 is ⋄ f = -consistent but not ⋄ f B - consistent because ⋄(N 2[1,3]/{f i} )[1, 3] = ∅, and N 3 is ⋄ f B - consistent.
From Corollary 1 and QCNs N 1 and N 2 , we deduce that (for the Interval Algebra)

⋄ f B ⊲ ⋄ f = ⊲ ⋄ f⋄ (note the strict order). v 0 v 2 v 3 v 1 {di, m, s} { o , o i} { o , f } { m , s , f i } {d, o, f i} { e q , d i, s , f i} (a) N1 v 0 v 2 v 3 v 1 { o , o i} { o , f } { m , s , f i } {d, o, f i} { e q , d i, s , f i} {m, s} (b) N2 v 0 v 2 v 3 v 1 {m, s} { o , o i} { o , f } {d, o, f i} { e q , d i, s } { m , s , f i } (c) N3 Figure 2: N 3 ⊂ N 2 ⊂ N 1 .
The equivalence classes of ≈ form a partition of ⋄ F ; the set of all equivalence classes is denoted by ⋄

F | ≈ . Note that ⋄ F | ≈ is a finite set since the set B of base relations is considered to be finite. The relation ≈ defined on ⋄ F | ≈ by ∀[φ], [ψ] ∈ ⋄ F | ≈ , [φ] ≈ [ψ] iff φ ψ
f as ∀r ∈ 2 B , f (r) = f 1 (r) ∪ f 2 (r).
First, we can observe that f ∈ F by construction. From Proposition 3, we deduce that

⋄ f ⋄ f1 and ⋄ f ⋄ f2 . Now, suppose that there exists f ′ ∈ F such that ⋄ f ′ ⋄ f1 and ⋄ f ′ ⋄ f2 . By definition, any ⋄ f ′ -consistent QCN N is ⋄ f1 - consistent and ⋄ f2 -consistent. Hence, for every pair (v i , v j ) of variables of N , s ∈ f 1 (N [i, j]) ⇒ ⋄(N [i,j]/s )[i, j] = s and s ∈ f 2 (N [i, j]) ⇒ ⋄(N [i,j]/s )[i, j] = s. So, for every s ∈ f 1 (N [i, j]) ∪ f 2 (N [i, j]), ⋄(N [i,j]/s )[i, j] = s. We deduce that N is ⋄ f -consistent, and ⋄ f ′ ⋄ f . [ ⋄ f ] is the least upper bound of [ ⋄ f1 ] and [ ⋄ f2
]. (Existence of binary meets) Let ⋄ f1 and ⋄ f2 be two elements of ⋄ F , and let us define the set

E as E = {f ′ ∈ F : ⋄ f1 ⋄ f ′ ∧ ⋄ f2 ⋄ f ′ }. Note that E = ∅ since f ⋄ ∈ E. Next, let us define f as ∀r ∈ 2 B , f (r) = {f ′ (r) : f ′ ∈ E}.
⋄ f1 -consistent QCN N that is not ⋄ f -consistent. Hence, there exist two variables v i , v j of N such that ⋄(N [i,j]/s )[i, j] = s with s ∈ f (N [i, j]).
From construction of f , we know that there exists a mapping

f ′ ∈ E such that s ∈ f ′ (N [i, j]). Hence, N is not ⋄ f ′ -consistent. On the other hand, as f ′ ∈ E we have ⋄ f1 ⋄ f ′ , and N ⋄ f ′ -consistent since N is ⋄ f1 -consistent. This is a contradiction, so ⋄ f1 ⋄ f does hold. Similarly, we can show that ⋄ f2 ⋄ f . [ ⋄ f ] is the greatest lower bound of [ ⋄ f1 ] and [ ⋄ f2 ]. ⊣
To conclude this section, let us prove the following result for atomic QCNs.

Proposition 5 Let f be an element of F, and N be an atomic QCN.

If N is consistent then N is ⋄ f -consistent. Proof.
For any element f of F and any base relation b, we know that f ({b}) = {{b}}. It means that all consistencies in ⋄ F are equivalent when restricted to atomic QCNs. As ⋄ f⋄ is equivalent to ⋄ (see Proposition 2) and as it is known that an atomic consistent QCN is necessarily closed under weak composition (i.e. ⋄-consistent), we deduce that an atomic consistent QCN is necessarily ⋄ f -consistent, whatever f is. ⊣

Closure of QCNs under ⋄ f -consistencies

A consistency φ is well-behaved iff for any QCN N , there exists a (unique) largest φ-consistent QCN N ′ smaller than or equal to N (w.r.t. ⊆). N ′ is called the φ-closure of N , and denoted by φ(N ). In this section, we are concerned with the closure of QCNs under ⋄ f -consistencies. Are ⋄ f -consistencies well-behaved? In other words, given a QCN N and a consistency ⋄ f in ⋄ F , does the ⋄ f -closure of N exist? We first show that this is not always the case with an example taken from the Interval Algebra. We consider f ∈ F such that f ({p, eq, m}) = {{p, eq, m}, {eq}} and f (r) = {r} for every relation r ∈ 2 B int \ {{p, eq, m}}. Figure 3 shows three distinct QCNs. The first QCN N 4 is not ⋄ f -consistent because ⋄(N 4[0,3]/{eq} )[0, 3] = ∅. Now let us turn to the two distinct QCNs N 5 and N 6 : both QCNs are ⋄ f -consistent and (strictly) smaller than N 4 . Observing that there does not exist any ⋄ fconsistent QCN strictly greater than N 5 and N 6 and smaller than N 4 , we have just proved that ⋄ f is not well-behaved. Nevertheless, there exist some mappings f for which the consistencies ⋄ f are guaranteed to be well-behaved. This is the case for the elements of the set F * introduced below. Roughly speaking, for every relation r, f (r) cannot be finer than the set of f (r ′ ) with r ′ contained in r.

Definition 3 F * is the set of mappings f in F such that for every r, r ′ ∈ 2 B with r ′ ⊂ r and for every s ∈ f (r), we have

s ∩ r ′ = ∅ ⇒ ∃S ⊆ f (r ′ ) such that s ∩ r ′ = S.
For example, all mappings mentioned in our previous illustrations belong to F * , except the last one that has been introduced above to prove that some ⋄ f -consistencies are not well-behaved. We first show the following result.

Proposition 6 Let f be a mapping of F * . If N 1 and N 2 are two ⋄ f -consistent QCNs defined on the same set of variables, then Proof. Let v i , v j be two variables of N (and consequently of N 1 and N 2 ), r = N [i, j] and s ∈ f (r). We have to show that ⋄(N

N = N 1 ∪ N 2 is a ⋄ f -consistent QCN. v 0 v 3 v 1 v 2 {p,
[i,j]/s )[i, j] = s. Let r 1 = N 1 [i, j], r 2 = N 2 [i, j]
and let s 1 and s 2 be the two relations defined as s 1 = s ∩ r 1 and s 2 = s ∩ r 2 . As s ∈ f (r), we have s ⊆ r and as

N = N 1 ∪ N 2 , we have r = r 1 ∪ r 2 . We can deduce s = s 1 ∪ s 2 , and also N 1[i,j]/s 1 ⊆ N [i,j]/s and N 2[i,j]/s 2 ⊆ N [i,j]/s . Because ⋄ is monotonic, we have ⋄(N 1[i,j]/s 1 ) ⊆ ⋄(N [i,j]/s ) and ⋄(N 2[i,j]/s 2 ) ⊆ ⋄(N [i,j]/s ).
On the other hand, as f ∈ F * there exist S 1 ⊆ f (r 1 ) and S 2 ⊆ f (r 2 ) such that S 1 = s 1 and S 2 = s 2 (if we assume that s 1 = ∅ and s 2 = ∅). From N 1 and N 2 being ⋄ f -consistent, we deduce that ⋄(N

1[i,j]/s ′ 1 )[i, j] = s ′ 1 , ∀s ′ 1 ∈ S 1 and ⋄(N 2[i,j]/s ′ 2 )[i, j] = s ′ 2 , ∀s ′ 2 ∈ S 2 . More- over, because ⋄ is monotonic, we have ⋄(N 1[i,j]/s ′ 1 )[i, j] ⊆ ⋄(N 1[i,j]/s 1 )[i, j], ∀s ′ 1 ∈ S 1 and ⋄(N 2[i,j]/s ′ 2 )[i, j] ⊆ ⋄(N 2[i,j]/s 2 )[i, j], ∀s ′ 2 ∈ S 2 . From this, we obtain s ′ 1 ⊆ ⋄(N 1[i,j]/s 1 )[i, j], ∀s ′ 1 ∈ S 1 and s ′ 2 ⊆ ⋄(N 2[i,j]/s 2 )[i, j], ∀s ′ 2 ∈ S 2 . Consequently, s 1 ⊆ ⋄(N 1[i,j]/s 1 )[i, j] and s 2 ⊆ ⋄(N 2[i,j]/s 2 )[i, j]. As ⋄ is contracting, we also have ⋄(N 1[i,j]/s 1 )[i, j] ⊆ s 1 and ⋄(N 2[i,j]/s 2 )[i, j] ⊆ s 2 . Finally, ⋄(N 1[i,j]/s 1 )[i, j] = s 1 and ⋄(N 2[i,j]/s 2 )[i, j] = s 2 .
From what precedes, we obtain

s 1 ⊆ ⋄(N [i,j]/s )[i, j] and s 2 ⊆ ⋄(N [i,j]/s )[i, j]. So, s = s 1 ∪ s 2 ⊆ ⋄(N [i,j]/s )[i, j].
The same result can be obtained when s 1 = ∅ or s 2 = ∅. Moreover, we also know that ⋄(N

[i,j]/s )[i, j] ⊆ s because ⋄ is contracting. We can conclude that ⋄(N [i,j]/s )[i, j] = s, and consequently that N is ⋄ f -consistent. ⊣
From the previous result, we can show that for every QCN N and every f in F * , the QCN {N ′ :

N ′ ⊆ N and N ′ is ⋄ f -consistent} is the largest ⋄ f -consistent subQCN of N , i.e. the ⋄ f -closure of N . Corollary 2 If ⋄ f is a consistency in ⋄ F * , then ⋄ f is well- behaved.
Observing that f = and f B do belong to F * , we can show that the QCNs from Figure 2 are such that ⋄ f = (N 1 ) = N 2 and ⋄ f B (N 2 ) = N 3 . Importantly, every consistency in ⋄ F * preserves the set of scenarios (the proof is omitted due to lack of space). This is not very surprising since Proposition 1 already indicates that identified base ⋄ f -inconsistent relations can be safely discarded.

Proposition 7 Let f be an element of F * . For every QCN N , ⋄ f (N ) is equivalent to N . Proof. Suppose that there exist two variables

(v i , v j ) of N and a base relation b ∈ B such that b ∈ N [i, j], b / ∈ ⋄ f (N )[i, j]
and a scenario S of N with S[i, j] = {b}. From Proposition 5, we know that S is ⋄ f -consistent, and from S being a scenario of N , we know that S ⊆ N . Hence, by closure definition, we have S ⊆ ⋄ f (N ). This leads to a contradiction since

S[i, j] = {b} and b / ∈ ⋄ f (N )[i, j]. ⊣

Generic Algorithm

In this section, we present a basic ⋄ f -algorithm, that is to say an algorithm that allows us to compute the ⋄ f -closure ⋄ f (N ) of any given QCN N . Such a closure is guaranteed to exist since f is assumed to belong to F * ; see Corollary 2. We introduce a constraint-oriented propagation scheme for enforcing the consistency ⋄ f . The constraint-oriented propagation scheme is characterized by revision of constraints that are successively picked from a dedicated set Q called the queue of the propagation.

The revision of a constraint C ij removes from C ij some base relations that are ⋄ f -inconsistent (if any). A revision is said to be effective if it removes at least one base relation. This is the role of function df-revise. For each element s of f (C ij ), a ⋄ f -check on s is performed, that is to say, N ′ = ⋄(N [i,j]/s ) is computed (line 3), which enables the identification of ⋄ f -inconsistent base relations, those in s \ N ′ [i, j] (line 4). The variable r collects ⋄ f -inconsistent base relations from C ij , and if r is not empty, C ij is updated (line 7) and true is returned.

The main function, called df-closure, performs one or several turns (passes) of the main loop. At each pass, all constraints are revised in turn: constraints are iteratively selected from Q (line 7) and df-revise is called to perform revisions (line 8). When an inference is performed (i.e. a revision is effective), the Boolean variable modif ied is set to true, which determines that a next pass is necessary. The algorithm stops when no inference is performed during a pass, or when an inconsistency is detected (lines 2 and 10). Note that when a QCN N is trivially inconsistent because there exists an empty constraint in N , we note N = ⊥. Initially (line 1), and after each effective revision (line 9), ⋄ (closure under weak composition) is applied on N . This We can prove that the algorithm df-closure is correct, i.e. enforce ⋄ f . Indeed, the algorithm is sound because every base relation removed in df-revise is ⋄ f -inconsistent. On the other hand, the algorithm is complete because, as soon as an inference is performed, a new pass is run (and all constraints are revised). However, it is important to note that the function df-revise removes at least one ⋄ f -inconsistent base relation from a given ⋄ f -inconsistent constraint. Consequently, this guarantess completeness although the function df-revise does not systematically render the given constraint ⋄ f -consistent.

Function df-revise(C ij ): Boolean in/out : C ij , a constraint of the QCN N output: true iff the revision of C ij is effective r ← ∅ 1 foreach relation s ∈ f (C ij ) do 2 N ′ ← ⋄(N [i,j]/s ) // ⋄ f -check on s 3 r ← r ∪ (s \ N ′ [i, j]) // ⋄ f -inconsistent 4 base relations are collected if r = ∅ then 5 r ′ ← N [i,j] \ r 6 N ← N [i,j]/r ′ // C ij becomes r ′ 7 return true 8 else return false 9 Function df-closure(N ,f ): Boolean in/out : N = (V, C), a QCN in : f , an element of F * output: true iff ⋄ f (N ) = ⊥ N ← ⋄(N ) // ⋄ enforced 1 if N = ⊥ then return false 2 repeat 3 modif ied ← f alse 4 Q ← {C ij ∈ C | i < j ∧ |f (C ij )| > 1} 5 while Q = ∅ do 6 select and remove a constraint C ij from Q 7 if df-revise(C ij ) then 8 N ← ⋄(N ) // ⋄ maintained 9 if N = ⊥ then
The worst-case time complexity of the function df-revise is O(sλ) where s is the greatest size (cardinality) of sets in {f (r) : r ∈ 2 B } and λ the worst-case time complexity of enforcing ⋄, i.e. O(n 3 ) for binary relations. Indeed, at most s ⋄ f -checks are performed. At each pass of the function df-closure, the number of calls to df-revise is O(n 2 ), so the worst-case time complexity of one pass of df-closure is O(sλn 2 ). Although the number of passes is bounded by O(|B|n 2 ) (only one base relation removed at each pass), we think that it is a small number in practice (this will be confirmed in our experimentations). Besides, we believe that the basic algoritm presented here can be refined so as to make it incremental (similarly to what is done for SAC [START_REF] Bessiere | Theoretical analysis of singleton arc consistency and its extensions[END_REF]).

Experiments

In our experimentation, we have focused on qualitative constraint networks from the Interval Algebra, randomly generated following Model A [START_REF] Nebel | Solving hard qualitative temporal reasoning problems: Evaluating the efficienty of using the ORD-Horn class[END_REF]. This model involves the generation of QCNs according to three parameters: n the number of variables, d the density and s the average number of base relations in each constraint. The set (or series) of QCNs that can be generated from n, d and s is denoted by A(n, d, s). The experimental results presented in this section concern QCN instances from series A(75, d, 6.5) and A(100, d, 6.5) for d varying from 2 to 24 with a step of 0.25. For these series, the hardest instances are located in a region where the density ranges from 8 to 11. For each series, we generated 100 instances.

The main objective of our experimental study is to compare both the filtering strength and the time efficiency of some ⋄ f -algorithms (those based on consistencies introduced in previous sections). The first criterion used for our comparisons is the number of QCNs detected as inconsistent, within the phase transition. This informs us about the relative filtering strength1 of different consistencies. Note that the exact number of inconsistent QCNs will be computed using a complete solving method: this represents the ideal filtering capability for a consistency. This method, called solver afterwards, is the solver proposed in [START_REF] Nebel | Solving hard qualitative temporal reasoning problems: Evaluating the efficienty of using the ORD-Horn class[END_REF]. Basically, it performs search by successively reducing each constraint relation to a tractable one (using a splitting of the initial relations) and maintaining the QCN closed under weak composition. In our context, we used the tractable sets of the Ord-Horn relations as split elements, and sought the best control parameters of solver to solve our instances. The second criterion used for our comparisons is the CPU time (given in seconds) taken by ⋄ f -algorithms (and solver).

When enforcing ⋄

f -consistencies, we may decide to ignore universal constraints so as to limit the computation effort of the algorithms. This means that when there is a constraint between two variables v i , v j such that C ij = B then no check on C ij is performed by means of f . Pragmatically, for every mapping f , we can introduce a related so-called reduced mapping f -defined as: f save time whereas limiting the loss of inferences due to the universal nature of these constraints.

-(r) = f (r) if r = B,
Figures 4(a) and 5(a) show the filtering capabilities of various ⋄ f -consistencies on series A(75, d, 6.5) and A(100, d, 6.5), respectively. A first observation is that consistencies based on reduced mappings are quite close to unreduced ones. For n = 75 variables, this was so striking that we decided (for clarity reasons) to not plot the curves corresponding to reduced mappings (except for f - B ). For n = 100 variables, a small difference is visible. This means that for a a given mapping f , the mapping f -allows us to detect almost the same number of inconsistent QCNs. However, we conjecture that this is less ans less true when n increases. A second observation is that ⋄ f B (theoretically shown to be the strongest local consistency in ⋄ F ) is very effective as it almost detects all inconsistent QCNs (as identified by solver) from series A(75, d, 6.5), and a lot of them from series A(100, d, 6.5). Other consistencies stronger than ⋄ = ⋄ f⋄ are, in order, P 3 , P 2 , P 1 and ⋄ f = . Interestingly, there is even so a significant gap between ⋄ f = and ⋄, which motivates us to further study each of these new consistencies. Finally, note that the number of passes executed by the function df-closure is very limited (around 3.5 on average).

Figures 4(b) and 5(b) show the CPU time taken by the ⋄ falgorithms on the same series. Note the use of a log scale on the y-axis in order to better distinguish between the behaviour of all algorithms. For n = 75 variables, the use of the strongest consistencies such as ⋄ f B , ⋄

f P 3 and ⋄ f P 2
involve a large overhead with respect to solver, but when reduced mappings are used the ⋄ f algorithms are far faster. For n = 100 variables, solver becomes clearly slower than all other algorithms, but recall that solver performs a complete search whereas ⋄ f -algorithms are incomplete since they can only perform some inferences. However, it is fair to compare solver and ⋄ f -algorithms on instances shown to be inconsistent by both approaches. This is the case for most of the instances of series A(100, d, 6.5) with d around 11.75 or higher; see Figure 5(a). For such instances, algorithms such as ⋄ f P 1 and ⋄ f = (and their reduced variants) are about two orders of magnitude faster than solver. Finally, ⋄ f⋄ = ⋄ is clearly the fastest algorithm as it is usually enforced within 0.1s (we did not plot its CPU curves because this flattens the figures) but remember that it is far weaker than other introduced ⋄ f -consistencies as shown in Figures 4(a To summarize, our (preliminary) experimentation shows how promising ⋄ f -consistencies may be, and in particular those based on reduced mappings that offer a good compromise between time overhead and filtering capability. Maintaining such consistencies during search is a perspective that we envision using a fast solver like GQR*.

Conclusion

In this paper, we have introduced the class of ⋄ f -consistencies for qualitative constraint networks. This class forms a complete lattice and contains original local consistencies (even when considering their CSP counterparts) such as ⋄ f = , all being stronger than weak composition. Looking for the ⋄ fconsistency that is the most appropriate to solve hard instances (from different qualitative algebras) is a pragmatic perspective of this work. On the other hand, we may imagine additional new classes built from coverings where ⋄ is substituted by another local consistency. Studying the connections between all these consistencies and the problems of (global) consistency and minimality of QCNs is an exciting theoretical perspective.

Figure 1 :

 1 Figure 1: Base relations of the Interval Algebra.

  From this definition and Proposition 3, we deduce that ⋄ f ⋄ f ′ for every f ′ ∈ E. We now prove by contradiction that ⋄ f1 ⋄ f and ⋄ f2 ⋄ f . Let us suppose that ⋄ f1 ⋄ f does not hold. This means that there exists a

Figure 3 :

 3 Figure 3: N 4 = N 5 ∪ N 6 .

  we know that for any f ∈ F * , ⋄ f (N ) ⊆ ⋄ f⋄ (N ) = ⋄(N ). When initializing Q (line 5), a constraint C ji with i < j is ignored because it can be deducted from C ij by means of the inverse operation. Also, a constraintC ij such that |f (C ij )| = 1 is ignored because it is necessarily ⋄f -consistent (recall that closure under weak composition is maintained during search).

Figure 4 :Figure 5 :

 45 Figure 4: Experimental results for series A(75, d, 6.5).

We could also assess the filtering strength of a given local consistency φ in terms of the number of base relations deleted when applying φ, but this information is closely related to our first criterion.


Audrey Maille

Amandine Chapelain

Laure Déruti

Philippe Bec

Catherine Blois-Heulin

Manual laterality for pointing gestures compared

Keywords: Broca', hemispheric specialization, red-capped mangabey

published or not. The documents may come

2

Vauclair 2010b; [START_REF] Esseily | Handedness for grasping objects and pointing and the development of language in 14-month-old infants[END_REF][START_REF] Cochet | Development of hand preference for object1directed actions and pointing gestures: a longitudinal study between 15 and 25 months of age[END_REF][START_REF] Cochet | Hand preference for pointing gestures and bimanual manipulation around the vocabulary spurt period[END_REF] or chimpanzees [START_REF] Hopkins | Hand use and gestural communication in chimpanzees (Pan troglodytes)[END_REF][START_REF] Hopkins | Gestural communication in chimpanzees (Pan troglodytes): the influence of experimenter position on gesture type and hand preference[END_REF][START_REF] Hopkins | From hand to mouth in the evolution of language: the influence of vocal behavior on lateralized hand use in manual gestures by chimpanzees (Pan troglodytes)[END_REF][START_REF] Meguerditchian | The sound of one-hand clapping: handedness and perisylvian neural correlates of a communicative gesture in chimpanzees[END_REF].

Studies on monkeys' gestures may have strong implications for understanding the evolutionary origins of hemispheric specialization for language. Currently, it is unclear whether communicative gestures also involve specific lateralized systems in monkeys. As far as we know, hand preferences for gestures have been investigated in only one species of Old World monkey, the olive baboon, Papio anubis. In this species, a right-hand bias was found for the production of a threat gesture, the 'hand slap', and the pattern of laterality differed from that reported for grasping actions and manipulative actions [START_REF] Meguerditchian | Baboons communicate with their right hand[END_REF][START_REF] Meguerditchian | Right-handedness predominance in 162 baboons (Papio anubis) for gestural communication: consistency across time and groups[END_REF]. To test whether the left-hemisphere specialization for communicative activities found in human and nonhuman apes is conserved in more distant relatives, there is a need to enlarge the investigation of laterality for manual gestures in several monkey species.

In the present study, we focused on requesting gestures, which are imperative manual gestures directed towards a desired item [START_REF] Leavens | Manual deixis in apes and humans[END_REF]) such as begging and pointing gestures, produced by nonhuman primates towards humans. On the one hand, one may hypothesize that monkeys' requesting gestures differ from those of apes in their communicative functions. Indeed, a gap divides monkeys from apes in their production of requesting gestures: apes often produce requesting gestures towards either conspecifics or humans (Call & Tomasello 2007b) whereas, to our knowledge, monkeys have never been observed to produce requesting gestures towards conspecifics. Moreover, in contrast to apes, captive monkeys must generally be trained to produce requesting gestures [START_REF] Gómez | Requesting gestures in captive monkeys and apes: conditioned responses or referential behaviours?[END_REF]).

Yet, we believe that requesting gestures of trained monkeys are efficient communicative signals since monkeys seem to be able to use requesting gestures to communicate intentionally with human recipients. Several studies indeed suggest that requesting gestures of monkeys would be mostly directed towards an attentive human audience (squirrel monkeys, Saimiri sciureus: [START_REF] Anderson | Flexibility in the use of requesting gestures in squirrel monkeys (Saimiri sciureus)[END_REF]; capuchin monkeys, Cebus apell a: [START_REF] Hattori | Tufted capuchin monkeys (Cebus apella) show understanding of human attentional states when requesting food held by a human[END_REF]; red-capped mangabeys, Cercocebus torquatus: [START_REF] Maille | To beg, or not to beg? That is the question: mangabeys modify their production of requesting gestures in response to human's attentional states[END_REF]; olive baboons: [START_REF] Meunier | Olive baboons communicate intentionally by pointing[END_REF]. On the other hand, one may argue that it is not relevant to investigate manual laterality within the scope of interspecific gestural communication. Manual laterality for communicative gestures may indeed differ according to whether the gesture is directed towards a conspecific or a human recipient. However, some studies have pointed out that chimpanzees exhibit a right-hand bias for the production of communicative gestures, regardless of whether they produce gestures towards conspecifics or humans (e.g. begging gestures: [START_REF] Meguerditchian | Captive chimpanzees use their right hand to communicate with each other: implications for the origin of the cerebral substrate for language[END_REF]clapping gestures: Meguerditchian et al. 2012). We thus assume that requesting gestures directed towards humans would be controlled by the same cerebral structures as communicative gestures directed towards conspecifics, in monkeys as in nonhuman apes.

The requesting gestures of monkeys consist of full arm extensions [START_REF] Gómez | Requesting gestures in captive monkeys and apes: conditioned responses or referential behaviours?[END_REF] but the existing literature has only compared requesting gestures of monkeys to grasping of items located near to the subjects, thus requiring low arm extensions (baboons: [START_REF] Meguerditchian | Contrast of hand preferences between communicative gestures and non-communicative actions in baboons: implications for the origins of hemispheric specialization for language[END_REF][START_REF] Meunier | Human infants and baboons show the same pattern of handedness for a communicative gesture[END_REF]. We aimed to compare manual laterality in monkeys for requesting gestures and for grasping actions requiring either full or low arm extensions. We hypothesized that (1) monkeys, like humans and nonhuman apes, would use their right hand more frequently for pointing gestures than for grasping actions, (2) right-hand use for pointing gestures would be greater in monkeys showing better communicative abilities and (3) hand preferences for pointing gestures and for grasping actions requiring full arm extensions would be similarly affected by the position of the items because these two arm movements share the same motor pattern.

To compare the respective patterns of hand preferences for pointing gestures and for grasping actions, we devised an experimental design in which the posture of the subject, the position of the items to request/grasp and the distance from the subject to the items were standardized. The 'quantification of hand preferences' task (QHP task: [START_REF] Bishop | The measurement of hand preference: a validation study comparing three groups of right-handers[END_REF] was first designed to measure handedness in human participants for grasping actions towards items that are presented in several locations in front of them. The QHP task has been successfully adapted for monkeys using food items [START_REF] Meunier | A new tool for measuring hand preference in non-human primates: adaptation of Bishop's Quantifying Hand Preference task for olive baboons[END_REF][START_REF] Chapelain | Hand preference and its flexibility according to the position of the object: a study in cercopithecines examining spontaneous behaviour and an experimental task (the Bishop QHP task)[END_REF]. Moreover, this task has been previously used to compare handedness for pointing gestures and for grasping actions requiring low arm extensions in humans (infants: [START_REF] Jacquet | Handedness for grasping objects and declarative pointing: a longitudinal study[END_REF][START_REF] Meunier | Human infants and baboons show the same pattern of handedness for a communicative gesture[END_REF]adults: Calvert & Bishop 1998) and baboons [START_REF] Meunier | Human infants and baboons show the same pattern of handedness for a communicative gesture[END_REF]. The QHP task thus appears suitable for investigating hand preferences for pointing gestures compared to grasping actions in human and nonhuman primates.

In this study, we investigated manual laterality for requesting gestures and for grasping actions in two genera of Old World monkeys that are closely related to baboons: Cercopithecus (guenons) and Cercocebus (one genus of mangabeys). We chose to study Campbell's monkeys, Cercopithecus campbelli, and red-capped mangabeys, Cercocebus torquatus, because, in contrast to humans and baboons, which are both terrestrial species, Campbell's monkeys are arboreal [START_REF] Oates | The distribution of Cercopithecus monkeys in West Afican forests[END_REF]) and red-capped mangabeys are semiterrestrial [START_REF] Gautier-Hion | Histoire Naturelle des Primates d'Afrique Centrale[END_REF]. These variations in habitat may affect manual laterality in nonhuman primates. [START_REF] Macneilage | Implications of primate functional asymmetries for the evolution of cerebral hemispheric specializations[END_REF][START_REF] Macneilage | Present status of the postural origins theory[END_REF] hypothesized that arboreal primates should be more left-handed than terrestrial primates because of a right-hand specialization for postural support in the trees. Moreover, [START_REF] Rogers | Hand preferences and other lateral biases in rehabilitated orang-utans, Pongo pygameus pygmaeus[END_REF] suggested that an arboreal lifestyle may induce a decrease in manual asymmetries because of a need to adapt to the architecture of the trees: to grasp food items safely in the trees, one hand must be used to hang on to the branches while the other hand grasps the food items.

In both guenons and mangabeys, we compared manual laterality for pointing gestures and grasping actions and we evaluated the influence of the position of the items on the hand used to request/grasp. Therefore, we used three versions of the QHP task to measure manual laterality for pointing gestures and for grasping actions requiring either full or low arm extensions. When the food items were located on the subject's body midline, we predicted that both guenons and mangabeys would be more right-handed for pointing gestures than for grasping actions and that there would be no relationship between the hand preferences exhibited for pointing gestures compared to grasping actions. Moreover, we predicted that the subjects showing the greatest skills for directing their pointing gestures towards hidden items located at one of five potential positions would be more right-handed for the production of pointing gestures than the other subjects. Finally, when the items were located away from the subject's body midline, we postulated that there would be a predominant use of the ipsilateral hand to the food items for both pointing gestures and grasping actions requiring full or low arm extensions.

METHODS
Subjects

Experimental subjects were 12 adult Campbell's monkeys (three males and nine females) and 16 adult or juvenile red-capped mangabeys (eight males and eight females; Table 1). All subjects were housed at the Station Biologique de Paimpont (Université de Rennes 1, France). They lived in social groups, in cages composed of indoor and outdoor enclosures of various sizes (indoor enclosures: minimum: 9 m² and 3.70 m high, maximum: 26 m² and 3.70 m high; outdoor enclosures: minimum: 12 m² and 4 m high, maximum: 330 m² and 4.50 m high). Food was given twice a day (fresh fruits and vegetables in the morning, monkey chows in the afternoon) and water was available ad libitum. Climbing furniture, ground substrates (woodchips and straw) and sunflower seeds were provided as enrichment on a daily basis. Experiments were conducted in cages adjacent to the home cages of subjects.

The subject being tested was isolated from dominant conspecifics and could move freely during the test. All of the subjects were habituated to being tested and isolated. Subjects were not deprived of food or water during testing. The experiment was conducted between February 2011 and May 2011 in guenons and between September 2010 and January 2011 in mangabeys.

The experiment was licensed by the departmental direction of veterinary services of Ille-et-Vilaine (licence no. 04672) in accordance with the European Communities Council Directive of 24 November 1986 (86/609/EEC). Animal facilities and animal care procedures were regularly monitored by the responsible local authorities, while animal husbandry and care were under management of the staff of the biological station in Paimpont, University of Rennes 1, France. During the experiments, animals were constantly monitored for signs of distress and care was taken to provide a stress-free experimental environment.

Experimental design

A semicircular board (guenons: PVC Celuka, diameter = 120 cm, thickness =1 cm; mangabeys: wood covered with zinc-plated steel, diameter = 160 cm, thickness = 2 cm; Fig. 1) was attached horizontally onto the wire-net mesh outside the cage (distance between the A2 2 board and the ground: guenons: 120 cm; mangabeys: 80 cm). Five positions were marked on the board, each separated by 30° from one another (Fig. 1). The positions were labelled according to their angle with the midline from the subject's point of view: leftward positions LL (-60°) and L (-30°), central position C (0°), rightward positions R (+ 30°) and RR (+ 60°).

Conversely to the original QHP task [START_REF] Bishop | The measurement of hand preference: a validation study comparing three groups of right-handers[END_REF], we did not use the two extreme positions (i.e. -90° and + 90°) because of physical constraints linked to the cage mesh.

A rectangular opening in the wire-net mesh at the board level (guenons: 28 × 6 cm; mangabeys: 44 × 8 cm) allowed the subjects to pass their arms through the mesh and move their arms freely over the board (Fig. 1). A stool (wood and zinc-plated steel: 47 × 42 × 3 cm) was fixed onto the wire-net mesh inside the cage, just in front of the board centre. When seated on the stool, the subjects were in a frontal position relative to the board. The stool was removable and the distance between the stool and the board varied according to the size of the subject so as to ensure that the elbows of the subjects were at the same level as the board (guenons: males: 28 cm; females: 24 cm; mangabeys: males < 5 years: 28 cm; males > 5 years: 36 cm; females < 4 years: 20 cm; females > 4 years: 28 cm).

Experimental procedure

For each trial, a food item was placed at one of the five positions that were marked on the board (Fig. 1); the hand used by the experimenter to place the food item was chosen at random. We used various food items (sunflower seeds, raisins, peanuts and pistachios) according to the preference of the subject. We exposed the subjects to three experimental tasks: the QHP-Pointing task (QHP-P), the QHP-Far Grasping task (QHP-FG) and the QHP-Nearby Grasping task (QHP-NG). For each of the three tasks, the trials began when the subject was sitting on the stool with its arms placed symmetrically. Two experimenters (E1 1B2 2 and E2) participated in the QHP-P task whereas only one experimenter (E1) was involved in the QHP-FG and the QHP-NG tasks.

Each test session consisted of a total of 25 trials, five trials in each of the five positions, which were presented in a random order (the same for all subjects and every experimental task). Every subject participated in 12 test sessions for each task, for a total of 300 trials per task (60 trials per position). The tasks were performed in the following order: QHP-NG, QHP-FG and QHP-P tasks in guenons, and QHP-NG, QHP-P and QHP-FG tasks in mangabeys. We performed only one session per day for each subject.

QHP-Pointing task

In the QHP-P task, the food items were out of reach for the subject. The distance between the centre of the board and the items varied according to the length of the arm of the subject (guenons: males: 45 cm; females: 38 cm; mangabeys: males < 5 years: 52 cm; males > 5 years: 65 cm; females < 4 years: 45 cm; females > 4 years: 55 cm). Five opaque tubes (zinc-plated steel: diameter: 4 cm, length: 7 cm; thickness: 0.1 cm) were placed vertically on the board, one tube per position (Fig. 1). The food items were hidden under the tubes to prevent the subject from seeing them. At the beginning of each trial, one experimenter, E1, stood with her back turned to the subject and the other experimenter, E2, stood facing the subject. The trials were divided into the following three phases.

(1) Baiting phase: E2 showed the food item to the subject. She then lifted an opaque tube (position chosen at random) to place and hide the item underneath it. She finally repositioned the tube in its original location. E1 remained blind to the baiting phase.

(2) Transition phase: E2 waited until the subject stopped producing pointing gestures and positioned its arms symmetrically. E2 then turned her back to the subject while E1 turned around to face the subject.

(3) Pointing phase: E1 looked at the subject. As soon as the subject extended one or both arms towards a tube (i.e. pointing gesture), E1 lifted the indicated tube. If the subject succeeded, that is, if it produced a pointing gesture towards the baited tube, E1 gave the food item to the subject. If the subject failed, that is, if it produced a pointing gesture towards an unbaited tube, E1 looked inside the other tubes and took away the food item from the baited tube. If the subject did not produce any pointing gestures within 30 s, E1 acted as if the subject had failed.

A training programme was conducted before the QHP-P task in both species because it was necessary to train monkeys to produce pointing gestures towards some tubes. During the training programme, whenever the subjects started to extend one or both arms towards the location of a food item, E1 immediately gave them the food item. At first (step 1), the food item was visible and later (step 2) it was hidden under one of two tubes. Each subject was trained during 15 min daily sessions. The training programme was considered completed for a subject when it was successful in at least five trials (i.e. pointing gesture directed towards the food item) per position in each step.

QHP-Far Grasping task

In the QHP-FG task, the food items were placed far from the subject (for both arms): subjects had to perform a full arm extension in order to grasp the items. The distance between the centre of the board and the food items varied according to the length of the arm of the subject (guenons: males: 30 cm; females: 23 cm; mangabeys: males < 5 years: 32 cm; males > 5 years: 45 cm; females < 4 years: 25 cm; females > 4 years: 35 cm). At the beginning of each trial, E1 stood facing the subject.

QHP-Nearby Grasping task

In the QHP-NG task, the food items were placed close to the subject (for both arms).

The distance between the centre of the board and the food items varied according to the length of the arm of the subject (guenons: males: 15 cm; females: 15 cm; mangabeys: males < 5 years: 20 cm; males > 5 years: 25 cm; females < 4 years: 15 cm; females > 4 years: 20 cm).

At the beginning of each trial, E1 stood facing the subject.

Data scoring

In the QHP-P task, we scored the first pointing gesture directed towards an opaque tube during the pointing phase of each trial (i.e. when E1 was facing the subject). We did not score the pointing gestures produced during the baiting and the transition phases of each trial (i.e. when E2 was facing the subject) because E2 knew where the food item was hidden and could thus provide information about its location to the subject during gesture production. We recorded (1) which arm (left or right arm, or both arms) was used to perform the pointing gesture and (2) the position of the opaque tube indicated by the pointing gesture. We usually recorded more or less than 60 trials per position because some pointing gestures were directed towards a tube other than the baited one.

In the QHP-FG and the QHP-NG tasks, we recorded which arm (left or right arm) was used to grasp the food item on each trial.

All test sessions were videotaped and later coded by E1. The videorecords were analysed by E1 using a VLC Media Player.

Data analysis

We calculated an individual handedness index (HI) per position and per subject in each experimental task. HI was calculated using the formula: HI = (number of right -number of left)/(number of right + number of left). HI varies between -1 and +1 and gives the direction of hand preference: negative values indicate a bias towards a preference for the left hand and positive values indicate a bias towards a preference for the right hand. When calculating HI values from the QHP-P task, (1) we did not consider trials in which pointing gestures were performed bimanually (mean ± SE per position: guenons: 1.0 ± 0.7; mangabeys: 6.1 ± 2.8) and ( 2) we considered trials in which pointing gestures were directed towards an opaque tube other than the baited one (mean ± SE per position: guenons: 9.7 ± 2.1; mangabeys: 11.8 ± 2.4) but we allocated these trials to the pointed tube's position rather than to the baited tube's position.

Manual laterality for pointing gestures compared to grasping actions

We determined whether subjects were left-handed or right-handed at each position and for each experimental task using the binomial test on the number of left and right actions. We assessed population-level biases in hand preference at each position using (1) the binomial test on the number of left-and right-handers and (2) the one-sample t test on HI values. We tested whether manual laterality at each position was consistent between the three experimental tasks using the Pearson correlation test with FDR (false discovery rate) correction on HI values.

Manual laterality in homogeneous and heterogeneous pointers

In the QHP-P task, we expected subjects to produce pointing gestures equally towards each of the five positions. Indeed, we performed an equivalent number of trials per position (i.e. each of the five opaque tubes was baited on 60 trials randomly distributed in the test sessions) and all the subjects were successfully trained to produce referential pointing, that is, pointing gestures directed towards the baited opaque tube. In each subject, we assessed homogeneity in the number of pointing gestures directed towards each of the five opaque tubes using the chi-square test: a statistical significance revealed a lack of homogeneity, i.e. under-or overrepresentation of trials for which the pointing gestures were directed towards a given container (usually referred to as 'position bias': e.g. [START_REF] Jolly | Choice of cue in Prosimian learning[END_REF]). We classified subjects into two pointer categories: heterogeneous pointers (chi-square significant) and homogeneous pointers (chi-square not significant); we assumed that homogeneous pointers exhibited the greatest skills for pointing referentially compared to heterogeneous pointers. We tested whether HI values differed between the two pointer categories using repeated measures ANOVA on HI values.

Influence of the position of items on manual laterality

We assessed whether manual laterality differed between the two species and whether it was affected by the task or the position of the food items using repeated measures ANOVA on HI values. We analysed the correlation between HI values and the numbers of the positions (LL = 1, L = 2, C = 3, R = 4, RR = 5) using Pearson correlation tests to evaluate more precisely the influence of the position on manual laterality.

Finally, we analysed the potential influence of the adult subjects' sex on the manual laterality exhibited for each of the three QHP tasks using repeated measures ANOVA and Pearson correlation tests on HI values.

We checked for equivariance and normality of the residuals of the ANOVAs. We used paired t tests with FDR correction as post hoc tests. Statistical tests were two tailed and type I error 1 was set at 0.05. All analyses were performed with R 2.14.2 (The R Foundation for 162 2

Statistical Computing, Vienna, Austria, http://www.r-project.org); when statistical tests yielded nonsignificant results, post hoc statistical power was calculated with GPower 3.1 [START_REF] Faul | G* Power 3: a flexible statistical power analysis program for the social, behavioral, and biomedical sciences[END_REF]).

RESULTS

The number of pointing gestures or grasping actions performed with either the left hand or the right hand by each subject as well as the individual hand preferences and the HI values are reported in Table 2 (data for the central position for the three tasks) and in Appendix Tables A1, A2 and A3 (data for the four lateral positions for the QHP-P task, QHP-FG task and QHP-NG task, respectively).

Manual laterality for pointing gestures compared to grasping actions
Hand preferences (central position)

For pointing gestures (QHP-P task) directed towards the central position C, the mean HI was 0.33 (SE = 0.22) in guenons and -0.12 (SE = 0.21) in mangabeys. The analysis of HI values showed no significant group-level biases for the production of pointing gestures in either guenons (one-sample t test: t 11 = 1.52, P = 0.158, effect size d = 0.44, power = 0.28) or mangabeys (one-sample t test: t 15 = -0.59, P = 0.567, d = -0.15, power = 0.09). Moreover, there were no significant differences in the number of left-and right-handed subjects in either species (binomial test: guenons: N = 12, P = 0.344; mangabeys: N = 16, P = 0.774; Table 2).

For grasping items placed at the central position C, the mean HI was 0.28 (SE = 0.15) in guenons and -0.21 (SE = 0.16) in mangabeys for the QHP-FG task, whereas the mean HI was 0.21 (SE = 0.13) in guenons and -0.22 (SE = 0.17) in mangabeys for the QHP-NG task. The analysis of HI values showed no significant group-level biases for the production of grasping actions requiring either full or low arm extensions in guenons (one-sample t test: QHP-FG: t 11 = 1.82, P = 0.096, d = 0.52, power = 0.38; QHP-NG: t 11 = 1.59, P = 0.140, d = 0.46, power = 0.22) and in mangabeys (one-sample t test: QHP-FG: t 15 = -1.28, P = 0.221, d = -0.32, power = 0.31; QHP-NG: t 15 = -1.21, P = 0.243, d = -0.30, power = 0.21). Moreover, there were no significant differences in the number of left-and right-handed subjects for the QHP-FG task (binomial test: guenons: N = 12, P = 0.180; mangabeys: N = 16, P = 0.581; Table 2) and the QHP-NG task (binomial test: guenons: N = 12, P = 0.289; mangabeys: N = 16, P = 0.388; Table 2).

Consistency in manual laterality

HI values from the QHP-P task and the QHP-FG task were not significantly correlated in the two species (Pearson correlation test: P > 0.05; detailed in Table 3), except at the two rightward positions R and RR in mangabeys ( Pearson correlation test: P < 0.05; detailed in Table 3). Moreover, there were no significant correlations between HI values from the QHP-P task and the QHP-NG task, for all positions and species (Pearson correlation test: P > 0.05; detailed in Table 3).

In contrast, there were significant positive correlations between HI values from the QHP-FG task and the QHP-NG task at positions L, C and R in mangabeys (and at position LL in guenons ((Pearson correlation test: P < 0.05; detailed in Table 3).

Manual laterality in homogeneous and heterogeneous pointers

In guenons, the chi-square test classified ten subjects (83.3%) as homogeneous pointers and two subjects (16.7%) as heterogeneous pointers (Table 1). In mangabeys, the chi-square 2 test classified seven subjects (43.8%) as homogeneous pointers and nine subjects (56.2%) as heterogeneous pointers (Table 1). We could thus compare manual laterality of homogeneous and heterogeneous pointers only in mangabeys.

A mixed ANOVA on HI values of mangabeys as a function of task and pointer category did not reveal a pointer category effect (ANOVA: F 1,15 = 0.18, P = 0.676, effect size f = 0.11, power = 0.07) but it detected a task*pointer category interaction (ANOVA: F 2,30 = 7.21, P < 0.001, f = 0.37). First, we conducted a mixed ANOVA on HI values as a function of pointer category for each task separately. This analysis showed that homogeneous pointers were more right-handed than heterogeneous pointers in the QHP-P task (ANOVA: F 1,15 = 4.68, P = 0.048, f = 0.58; Fig. 2) whereas manual laterality did not differ between the two pointer categories for the QHP-FG task (ANOVA: F 1,15 = 0.01, P = 0.924, f = 0.03, power = 0.05; Fig. 2) and the QHP-NG task (ANOVA: F 1,15 = 0.75, P = 0.402, f = 0.23, power = 0.14; Fig. 2). Second, we performed a mixed ANOVA on HI values as a function of task in each pointer category. We found a main effect of task in homogeneous pointers (ANOVA: F 2,34 = 11.61, P < 0.001, f = 0.49): homogeneous pointers used their right hand more often for the QHP-P task than for the QHP-FG task (paired t test: P = 0.021; Fig. 2) and the QHP-NG task (paired t test: P < 0.001; Fig. 2). In contrast, no task effect was detected in heterogeneous pointers (ANOVA: F 2,30 = 2.55, P = 0.083, f = 0.20, power = 0.07).

Influence of the position of items on manual laterality.

A mixed ANOVA on HI values as a function of species, task and position showed a significant main effect of the species (ANOVA: F 1,27 = 4.73, P = 0.039, f = 0.42): guenon subjects were more right-handed than mangabey subjects. However, we performed the following analyses in both species pooled together because there was no species*task interaction (ANOVA: F 2,54 = 0.52, P = 0.593, f = 0.05, power = 0.05) and no species*position interaction (ANOVA: F 4,108 = 2.01, P = 0.093, f = 0.15, power = 0.06) indicating that the species effect occurred similarly in the three tasks and among the five positions. The analysis revealed a task*position interaction (ANOVA: F 8,216 = 18.72, P < 0.001, f = 0.64).

We conducted a mixed ANOVA analysis on HI values as a function of task at each position separately to assess how manual laterality differed between the three tasks. The analysis did not reveal a task effect at the central position (ANOVA: position C: F 2,54 = 0.27, P = 0.766, f = 0.10, power = 0.06). However, it showed a significant main effect of the task at the four lateral positions (ANOVA: position LL: F 2,54 = 30.29, P < 0.001, f = 1.07; position L: F 2,54 = 7.31, P = 0.002, f = 1.07; position R: F 2,54 = 4.35, P = 0.018, f = 0.39; position RR: F 2,54 = 38.35, P < 0.001, f = 1.15). Subjects used their left hand more frequently for the QHP-FG task than for the QHP-NG task at the two leftward positions (paired t test: position LL: P < 0.001; position L: P = 0.030; Fig. 3) whereas they used their right hand more frequently at the more rightward position RR (paired t test: position R: P = 0.100; position RR: P < 0.001; Fig. 3). Similarly, subjects used their left hand more frequently for the QHP-P task than for the QHP-NG task at the two leftward positions (paired t test: position LL: P < 0.001; position L: P = 0.008; Fig. 3) whereas they used their right hand more frequently at the more rightward position RR (paired t test: position R: P = 0.100; position RR: P < 0.001; Fig. 3). In contrast, HI values did not differ significantly between the QHP-P and the QHP-FG tasks, regardless of the position (paired t test: position LL: P = 0.930; position L: P = 0.474; position R: P = 0.950; position RR: P = 0.710; Fig. 3).

We then assessed how the position of the food items affected manual laterality according to the task. First, we conducted a mixed ANOVA on HI values as a function of position in each task separately. The analysis revealed a significant main effect of the position 1A2 2

for the three tasks (ANOVA: QHP-P: F 4,108 = 39.86, P < 0.001, f = 1.22; QHP-FG: F 4,108 = 19.54, P < 0.001, f = 0.85; QHP-NG: F 4,108 = 47.10, P < 0.001, f = 1.33). Second, we performed Pearson correlation tests to evaluate whether there was a linear variation in the direction of manual laterality according to the location of the items. We found that HI values decreased significantly from the more leftward position LL to the more rightward position RR for both the QHP-P task (Pearson correlation test: r 139 = -0. 54, P < 0.001; Fig. 3) and the QHP-FG task (Pearson correlation test: r 139 = -0.61, P < 0.001; Fig. 3), but increased from position LL to position RR for the QHP-NG task (Pearson correlation test: r 139 = 0.28, P < 0.001; Fig. 3).

Influence of sex

In adult subjects from both species, we conducted a mixed ANOVA on HI values as a function of sex and task to assess whether manual laterality differed between males and females according to the task. The analysis showed neither a sex effect (ANOVA: F 1,20 = 3.39, P = 0.081, f = 0.47, power = 0.37) nor a sex*task interaction (ANOVA: F 2,40 = 0.15, P = 0.965, f = 0.04, power = 0.06). In both sexes, we found that HI values decreased significantly from the more leftward position LL to the more rightward position RR for both the QHP-P task (Pearson correlation test: males: r 34 = -0. 62, P < 0.001; females: r 69 = -0.50, P < 0.001) and the QHP-FG task (Pearson correlation test: males: r 34 = -0. 59, P < 0.001; females: r 69 = -0.62, P < 0.001). In contrast, HI values increased significantly from position LL to position RR for the QHP-NG task, but this was true of adult females only (Pearson correlation test: males: r 34 = 0. 07, P = 0.688; females: r 69 = 0.43, P < 0.001).

DISCUSSION

3B2 2

Our study had three main findings about manual laterality for pointing gestures in guenons and mangabeys. First, we found a lack of relationship between individual hand preferences for pointing gestures and for grasping actions to items located nearby. Second, homogeneous pointers believed to possess the greatest skills for pointing referentially were more right-handed for pointing gestures than for grasping actions to items located either nearby or far away, at least in mangabeys. Third, we showed that manual laterality for pointing gestures and for grasping actions to items located far away were similarly affected by the position of items: when the items were placed away from the body midline of the subjects, guenons and mangabeys used the hand contralateral to the items.

In guenons and mangabeys, we did not find any group-level right bias for the production of pointing gestures directed towards items located at the body midline in front of the subjects. In contrast to several studies that showed greater right-hand use for pointing gestures than for grasping actions in both human infants [START_REF] Bonvillian | Early sign language acquisition and the development of hand preference in young children[END_REF]Cochet & Vauclair 2010b;[START_REF] Esseily | Handedness for grasping objects and pointing and the development of language in 14-month-old infants[END_REF]) and chimpanzees [START_REF] Hopkins | The distribution and development of handedness for manual gestures in captive chimpanzees (Pan troglodytes)[END_REF], our results indicated no difference in manual laterality between pointing gestures and grasping actions. However, we found no relationship between individual hand preferences for pointing gestures and for grasping actions to items located nearby. This finding parallels those found in human infants (Cochet & Vauclair 2010b;[START_REF] Esseily | Handedness for grasping objects and pointing and the development of language in 14-month-old infants[END_REF][START_REF] Jacquet | Handedness for grasping objects and declarative pointing: a longitudinal study[END_REF]) and chimpanzees [START_REF] Hopkins | Gestural communication in chimpanzees (Pan troglodytes): the influence of experimenter position on gesture type and hand preference[END_REF][START_REF] Hopkins | From hand to mouth in the evolution of language: the influence of vocal behavior on lateralized hand use in manual gestures by chimpanzees (Pan troglodytes)[END_REF]. There was also no relationship between hand preferences exhibited for pointing gestures and for grasping actions to items located far away, except in the case of rightward items in mangabeys. Although this lack of consistency between hand preferences for pointing gestures and grasping actions may result from small sample sizes, mangabeys' hand preferences for grasping actions requiring full or low arm extensions were, by contrast, strongly and positively related when items were located either on the subject's midline or 30° from the midline.

As in humans and chimpanzees, manual laterality for pointing gestures seems to be relatively distinct from manual laterality for grasping actions in guenons and mangabeys: pointing gestures may rely on different cerebral structures to those involved in noncommunicative actions in monkeys as in humans and nonhuman apes. By contrast, a strong relationship exists between manual laterality for grasping actions requiring either full or low arm extension. Our study thus provides additional evidence that the cognitive processes underlying the production of requesting gestures in monkeys might be distinct from that involved in the execution of grasping actions, even if monkeys had to be trained to produce requesting gestures from a ritualization of reaching movements.

We found that the mangabey individuals possessing the greatest skills for pointing referentially were more right-handed for pointing gestures than for grasping actions (towards items located either nearby or far away). These seven individuals (i.e. homogeneous pointers) were more right-handed than the other nine individuals (i.e. heterogeneous pointers) for the production of pointing gestures whereas these two categories of individuals did not differ in their direction of manual laterality for grasping actions (requiring full or low arm extensions). Thus, we actually found a greater right-hand use for gestures compared to noncommunicative actions when we considered the mangabeys that were the best referential pointers. This predominant right-hand use for pointing gestures may reflect the activation of a specific leftlateralized communicative cerebral system involved in the production of communicative gestures which would be distinct from that involved in the production of purely motor actions.

One may note that the probability of detecting a significant group-level right-hand bias in mangabeys for gesturing was fairly low in the present study. No more than 16 mangabeys were available for testing and among them only those that possessed the greatest skills for pointing referentially were more right-handed for pointing gestures than for grasping actions.

We believe that an increase in sample size should allow the detection of a right-hand preference for the production of pointing gestures in mangabeys. Our findings suggest that the referential nature of the communicative signal may be a necessary condition for the activation of the left-hemispheric communicative system. In future laterality studies, we encourage investigations on interindividual differences in the referential abilities for the production of communicative signals.

Surprisingly, we did not find any increase in right-hand use for pointing gestures compared to grasping actions in guenons, although 10 of the 12 tested subjects exhibited considerable skills for pointing referentially. However, guenons were more right-handed than mangabeys for both pointing gestures and grasping actions. A simple explanation might thus be that the right-sided asymmetry was already too strongly marked in the tested group of guenons to increase it any further for the production of communicative gestures compared to grasping actions. Such an effect was indeed reported in strongly right-handed human adults [START_REF] Calvert | Quantifying hand preference using a behavioural continuum[END_REF][START_REF] Cochet | Hand preferences in human adults: non-communicative actions versus communicative gestures[END_REF].

Guenons and mangabeys produced pointing gestures using the hand contralateral to the items. Conversely, humans of various ages (infants: [START_REF] Butterworth | Dynamic aspects of visual event perception and the production of pointing by human infants[END_REF][START_REF] Esseily | Handedness for grasping objects and pointing and the development of language in 14-month-old infants[END_REF][START_REF] Jacquet | Handedness for grasping objects and declarative pointing: a longitudinal study[END_REF][START_REF] Meunier | Human infants and baboons show the same pattern of handedness for a communicative gesture[END_REF]children: Hill & Khanem 2009;adults: Calvert & Bishop 1998;[START_REF] Bryden | A performance measure of the degree of hand preference[END_REF], baboons [START_REF] Meunier | Human infants and baboons show the same pattern of handedness for a communicative gesture[END_REF]) and chimpanzees [START_REF] Krause | Chimpanzee (Pan troglodytes) pointing: hand shapes, accuracy, and the role of eye gaze[END_REF][START_REF] Hopkins | Gestural communication in chimpanzees (Pan troglodytes): the influence of experimenter position on gesture type and hand preference[END_REF] have been shown to use the ipsilateral hand to the items to make requests.

Additionally, guenons and mangabeys mainly performed grasping actions requiring low arm extensions using the hand ipsilateral to the items. Similarly, humans (infants: [START_REF] Jacquet | Handedness for grasping objects and declarative pointing: a longitudinal study[END_REF]children: Bishop et al. 1996;[START_REF] Gabbard | Attentional stimuli and programming hand selection: a developmental perspective[END_REF][START_REF] Gabbard | Lateralized effects on reaching by children[END_REF][START_REF] Carlier | Midline crossing: developmental trend from 3 to 10 years of age in a preferential card-reaching task[END_REF][START_REF] Leconte | Which factors affect hand selection in children's grasping in hemispace? Combined effects of task demand and motor dominance[END_REF]adults: Seltzer et al. 1990;[START_REF] Harris | Hand preference for visually-guided reaching in human infants and adults[END_REF][START_REF] Calvert | Quantifying hand preference using a behavioural continuum[END_REF][START_REF] Bryden | Preferential reaching into hemispace: an examination of performance, preference, and task complexity[END_REF][START_REF] Doyen | Measuring handedness: a validation study of Bishop's reaching card test[END_REF][START_REF] Rezaee | Which factors affect hand selection in adults? Combined effects of ocular dominance, task demand and object location[END_REF], macaques [START_REF] Cronholm | Situational factors in the lateral preference of rhesus monkeys[END_REF][START_REF] Lehman | The handedness of rhesus monkeys: I. Distribution[END_REF]Lehman , 1980a, b), b), baboons [START_REF] Meunier | A new tool for measuring hand preference in non-human primates: adaptation of Bishop's Quantifying Hand Preference task for olive baboons[END_REF]) and lemurs [START_REF] Forsythe | Posturally related variations in the hand preferences of the ruffed lemur (Varecia variegata variegata)[END_REF]) usually grasp using the hand closest to the items, although they more often perform midline crossing with the preferred hand rather than the nonpreferred hand. Surprisingly, guenons and mangabeys performed grasping actions requiring full arm extension using the hand contralateral to the items. Similarly, bushbabies, which are arboreal prosimian primates, have been shown to engage in contralateral grasping when they had to pick up items placed laterally and far away from them [START_REF] Ward | Patterns of lateralized behavior in Prosimians[END_REF]. Altogether, these results stand in contrast to many reports from human studies which show that manual laterality for grasping actions to items located laterally is not affected by an increase in the distance between the individual and the items (e.g. adults: [START_REF] Harris | Hand preference for visually-guided reaching in human infants and adults[END_REF][START_REF] Stins | A kinematic analysis of hand selection in a reaching task[END_REF].

Briefly, manual laterality for pointing gestures and for grasping actions directed towards items located laterally and far away were similarly affected by the position of the items in guenons and mangabeys. One could argue that the opening in the cage mesh was too small to allow subjects to produce movements requiring full arm extensions using the hand ipsilateral to the items located leftward or rightward. However, adult females from both species used the hand contralateral to the objects when they performed pointing gestures and grasping actions requiring full arm extensions to objects placed laterally, despite the fact that they were smaller than the adult males and consequently less constrained by the cage mesh. We propose that the use of the contralateral hand is preferred by guenons and mangabeys for pointing gestures and grasping actions requiring full arm extensions because these two activities are subject to the same biomechanical constraints. [START_REF] Mark | Postural dynamics and the preferred critical boundary for visually guided reaching[END_REF] suggested that contralateral movements involving multiple parts of the body may be more comfortable for movements directed towards items placed laterally and far away because none of the limb segments approach complete extension. In addition, differences in habitat may explain the controversial results between species: arboreal primates adapted to tree climbing, such as guenons, mangabeys and galagos, may not avoid postural instability in contrast to more terrestrial primates such as humans, chimpanzees and baboons. Arboreal primates would thus perform forward and lateral movements of the upper torso to produce a contralateral reaching whereas terrestrial primates would prefer to extend one shoulder to produce an ipsilateral reaching (humans: [START_REF] Mark | Postural dynamics and the preferred critical boundary for visually guided reaching[END_REF][START_REF] Westwood | Posture and target location effects on manual preference[END_REF]. Moreover, arboreal primates may use postural adjustments to secure sideway motions. They would hold on with the hand ipsilateral to the item to request/grasp to ensure their safety while leaning laterally, the contralateral hand remaining the only one free. In the present study, we indeed observed that sideway motions of guenons and mangabeys often co-occurred with holding on to the stool or to the cage mesh with the ipsilateral hand to the item. Our finding thus suggests that, when primates have to perform pointing gestures or grasping actions directed towards distant and laterally placed items, arboreal species but not terrestrial species may deal with the biomechanical constraints of these movements by using the contralateral hand to the items.

In conclusion, we showed that hand preferences for pointing gestures and grasping actions that required low arm extensions were not related in guenons and mangabeys. This finding suggests that communicative gestures do not rely on the same cerebral structures as noncommunicative actions in Old World monkeys. Importantly, we also revealed an interaction between referential abilities and hand preferences for pointing gestures in mangabeys: the monkeys possessing the greatest skills for pointing referentially were more right-handed for gesturing than for grasping. We propose that in Old World monkeys, as in chimpanzees, the production of intentional and referential gestures may involve the activation of specific regions of the left hemisphere specialized in the processing of intentional and referential communicative signals. Finally, we found that guenons and mangabeys used the hand contralateral to the items for the execution of both pointing gestures and grasping actions requiring full arm extensions. We postulate that the position of the items similarly affects manual laterality for these two types of arm movements because they are subject to the same biomechanical constraints in species adapted to tree climbing.

Figure captions Figure 1 .

 captions1 Figure captions

Figure 2 .

 2 Figure 2. Handedness index (HI) for the three experimental tasks in mangabeys. Presented

Figure 3 .

 3 Figure 3. Handedness index (HI) at each position and for the three experimental tasks in

Table 2 .

 2 Raw data and individual handedness index (HI) for pointing gestures (QHP-Pointing task) and grasping actions (QHP-Far Grasping task

	and QHP-Nearby Grasping task) directed towards the central position
		QHP-Pointing task		QHP-Far Grasping task	QHP-Nearby Grasping task
	Subject	Left Right	P	Bias HI	Left Right	P	Bias HI	Left Right	P	Bias HI
	Guenons
	Ecureuil	13	31	0.010 R 0.41	49	11 < 0.001 L -0.63	35	25	0.245 A -0.17
	Chili	55	0 < 0.001 L -1.00	10	50 < 0.001 R 0.67	3	57 < 0.001 R 0.90
	Amande	3	43 < 0.001 R 0.87	44	16 < 0.001 L -0.47	11	49 < 0.001 R 0.63
	Chilula	22	30	0.332 A 0.15	21	39	0.027 R 0.30	45	15 < 0.001 L -0.50
	Tilamook	11	38 < 0.001 R 0.55	10	50 < 0.001 R 0.67	11	49 < 0.001 R 0.63
	Maricopa	0	74 < 0.001 R 1.00	14	46 < 0.001 R 0.53	25	35	0.245 A 0.17
	Lowina	1	46 < 0.001 R 0.96	12	48 < 0.001 R 0.60	10	50 < 0.001 R 0.67
	Shawnee	0	50 < 0.001 R 1.00	7	53 < 0.001 R 0.77	30	30	1.000 A 0.00
	Plume	58	3 < 0.001 L -0.90	24	36	0.155 A 0.20	21	39	0.027 R 0.30
	Lombrik	59	13 < 0.001 L -0.64	35	25	0.245 A -0.17	41	19	0.006 L -0.37
	Lowi	12	50 < 0.001 R 0.61	35	25	0.245 A -0.17	34	26	0.366 A -0.13
	Arbok	0	78 < 0.001 R 1.00	0	60 < 0.001 R 1.00	20	40	0.013 R 0.33
	Mangabeys
	Lorette	24	33	0.289 A 0.16	16	44 < 0.001 R 0.47	23	37	0.092 A 0.23
	Many	45	0 < 0.001 L -1.00	18	42	0.003 R 0.40	2	58 < 0.001 R 0.93
	Chipse	7	10	0.629 A 0.18	26	33	0.435 A 0.12	42	18	0.003 L -0.40
	Julie	2	67 < 0.001 R 0.94	20	40	0.013 R 0.33	51	9 < 0.001 L -0.70
	Bell	21	11	0.110 A -0.31	31	29	0.897 A -0.03	30	30	1.000 A 0.00
	Goffrette	54	5 < 0.001 L -0.83	60	0 < 0.001 L -1.00	52	8 < 0.001 L -0.73
	Chipie	62	0 < 0.001 L -1.00	45	15 < 0.001 L -0.50	45	15 < 0.001 L -0.50
	Zunie	3	91 < 0.001 R 0.94	10	50 < 0.001 R 0.67	16	44 < 0.001 R 0.47

Table A3 .

 A3 Raw data and individual handedness index (HI) for grasping actions requiring low arm extensions (QHP-Nearby Grasping task) directed towards items placed at lateral positions

		Position LL (-60°)		Position L (-30°)		Position R (+ 30°)		Position RR (+ 60°)
	Subject	Left Right	P	Bias HI	Left Right	P	Bias HI	Left Right	P	Bias HI	Left Right	P	Bias HI
	Guenons
	Ecureuil	48	12 < 0.001 L -0.60	47	13 < 0.001 L -0.57	33	27	0.519 A -0.10	39	21	0.027 L -0.30
	Chili	5	55 < 0.001 R 0.83	7	53 < 0.001 R 0.77	3	57 < 0.001 R 0.90	5	55 < 0.001 R 0.83
	Amande	9	51 < 0.001 R 0.70	14	46 < 0.001 R 0.53	12	48 < 0.001 R 0.60	10	50 < 0.001 R 0.67
	Chilula	54	6 < 0.001 L -0.80	52	8 < 0.001 L -0.73	28	32	0.699 A 0.07	29	31	0.897 A 0.03
	Tilamook	17	43	0.001 R 0.43	13	47 < 0.001 R 0.57	7	53 < 0.001 R 0.77	10	50 < 0.001 R 0.67
	Maricopa	49	11 < 0.001 L -0.63	42	18	0.003 L -0.40	14	46 < 0.001 R 0.53	9	51 < 0.001 R 0.70
	Shawnee	20	40	0.013 R 0.33	17	43	0.001 R 0.43	8	52 < 0.001 R 0.73	21	39	0.027 R 0.30
	Lowina	43	17	0.001 L -0.43	46	14 < 0.001 L -0.53	31	29	1.000 A -0.03	32	28	1.000 A -0.07
	Plume	43	17	0.001 L -0.43	32	28	0.699 L -0.07	12	48 < 0.001 R 0.60	10	50 < 0.001 R 0.67
	Lombrik	40	20	0.013 L -0.33	43	17	0.001 L -0.43	38	22	0.052 A -0.27	41	19	0.006 L -0.37
	Lowi	38	22	0.052 A -0.27	37	23	0.092 A -0.23	29	31	0.897 A 0.03	19	41	0.006 R 0.37
	Arbok	17	43	0.001 R 0.43	23	37	0.092 A 0.23	17	43	0.001 R 0.43	17	43	0.001 R 0.43
	Mangabeys
	Lorette	1	59 < 0.001 R 0.97	2	58 < 0.001 R 0.93	2	58 < 0.001 R 0.93	0	60 < 0.001 R 1.00
	Many	35	25	0.245 A -0.17	25	35	0.245 A 0.17	34	26	0.366 A -0.13	42	18	0.003 L -0.40
	Chipse	47	13 < 0.001 L -0.57	42	18	0.003 L -0.40	42	18	0.003 L -0.40	52	8 < 0.001 L -0.73
	Julie	54	6 < 0.001 L -0.80	54	6 < 0.001 L -0.80	42	18	0.003 L -0.40	32	28	0.699 A -0.07
	Bell	53	7 < 0.001 L -0.77	48	12 < 0.001 L -0.60	32	28	1.000 A -0.07	16	44	1.000 A 0.47
	Goffrette	59	1 < 0.001 L -0.97	57	3 < 0.001 L -0.90	44	16 < 0.001 L -0.47	38	22	0.052 A -0.27
	Chipie	59	1 < 0.001 L -0.97	58	2 < 0.001 L -0.93	37	23	0.092 A -0.23	23	37	0.092 A 0.23
	Zunie	40	20	0.013 L -0.33	16	44 < 0.001 R 0.47	5	55 < 0.001 R 0.83	3	57 < 0.001 R 0.90
	Carillon	36	24	0.155 A -0.20	26	34	0.366 A 0.13	10	50 < 0.001 R 0.67	10	50 < 0.001 R 0.67
	Lenni	51	9 < 0.001 L -0.70	50	10 < 0.001 L -0.67	25	35	0.245 A 0.17	21	39	0.027 R 0.30

ACKNOWLEDGMENTS

We thank Arnaud Rossard for taking care of the monkeys and assisting in every step of the training, Lucie Engelhart for her participation in experiments on Campbell's monkeys and Claire Pettoello for helping in data scoring. We also thank Jacques Vauclair, Jacqueline Fagard, Hélène Meunier, Hélène Cochet, Adrien Meguerditchian, Marie Bourjade and James R. Anderson for helpful discussions about the methodology. We express many thanks to Pascaline Le Gouar, Eric Petit and Maxime Hervé for helpful advice on statistical analyses.

We are grateful to two anonymous referees for valuable comments on the manuscript and to Cléo Beaulieu for polishing the English. This study was supported by a French National Research Agency grant: reference ANR-08-BLAN-0.011_01.