Guillaume Blin

Paola Bonizzoni

Riccardo Dondi

Florian Sikora

On the Parameterized Complexity of the Repetition Free Longest Common Subsequence Problem

Keywords: Repetition Free Longest Common Subsequence, Longest Common Subsequence, Parameterized Complexity

Longest common subsequence is a widely used measure to compare strings, in particular in Computational Biology. Recently, several variants of the longest common subsequence have been introduced to tackle the comparison of genomes. In particular, the Repetition Free Longest Common Subsequence problem (RFLCS) is a variant of the LCS problem that asks for a longest common subsequence of two input strings with no repetition of symbols. In this paper, we investigate the parameterized complexity of RFLCS. First, we show that the problem does not admit a polynomial kernel. Then, we present a randomized FPT algorithm for the RFLCS problem, improving the time complexity of the existent FPT algorithm.

Introduction

Longest Common Subsequence (LCS) has been widely used as a measure to compare strings in different fields [START_REF] Bergroth | A Survey of Longest Common Subsequence Algorithms[END_REF], in particular for the comparison of two (or more) genomes in Bioinformatics. Genomes are usually viewed as strings, where each symbol represents a gene, and the comparison of the strings associated with the genomes provides a measure of their similarities and differences. As the order in which genes appear in the genomes is considered relevant in the comparison, LCS provides a natural measure to compare genomes.

Different variants of longest common subsequence have been proposed [START_REF] Bonizzoni | Exemplar Longest Common Subsequence[END_REF][START_REF] Adi | Repetition-free Longest Common Subsequence[END_REF][START_REF] Bonizzoni | Variants of Constrained Longest Common Subsequence[END_REF] to compare biological strings, where, given two strings s 1 and s 2 , the computed longest common subsequence is required to satisfy some constraint. In particular, the Repetition Free Longest Common Subsequence (RFLCS) problem, proposed in [START_REF] Adi | Repetition-free Longest Common Subsequence[END_REF], requires that each symbol appears at most once in the common subsequence of the input strings. The use of such constraint is motivated by the exemplar hypothesis [START_REF] Sankoff | Genome Rearrangement with Gene Families[END_REF], that aims to identify the original copy of a gene that has originated all the copies of that gene in the genome through duplications. As a consequence, in the RFLCS problem, the input consists of two strings s 1 and s 2 , and the output consists of a longest common subsequence of s 1 and s 2 containing no repetition of symbols. The RFLCS is known to be APX-hard, even when each symbol occurs at most twice in each of the two input strings [START_REF] Adi | Repetition-free Longest Common Subsequence[END_REF]. Furthermore, the problem admits a k-approximation algorithm, where k is the maximum number of occurrences of each symbol in one of the two strings [START_REF] Adi | Repetition-free Longest Common Subsequence[END_REF]. Concerning parameterized complexity, if parameterized by the size k of the solution, the problem admits a deterministic FPT algorithm [START_REF] Bonizzoni | Variants of Constrained Longest Common Subsequence[END_REF], of time complexity O * (c k ), where c is a large constant, and space complexity O * (2 k )1 . The algorithm can be easily randomized, thus giving a randomized FPT algorithm of time complexity O * ((2e) k )) and space complexity O * (2 k ).

In this paper, we deepen the investigation on the parameterized complexity of the RFLCS problem. For details on parameterized complexity, we refer the reader to [START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF]. First, we investigate the kernelization complexity of RFLCS. Kernelization is a widely used technique in parameterized complexity [START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF], that aims to preprocess in polynomial time an instance of a problem, in order to produce an instance having size depending only on the considered parameter. Recently, several results [START_REF] Bodlaender | On problems without polynomial kernels[END_REF][START_REF] Bodlaender | Kernel Bounds for Disjoint Cycles and Disjoint Paths[END_REF] on the kernelization complexity have been introduced, in order to prove that a problem, although in FPT, does not admit a polynomial size kernel. Applying a technique of [START_REF] Bodlaender | On problems without polynomial kernels[END_REF], we show that the RFLCS problem does not admit a polynomial size kernel, unless N P ⊆ coN P/P oly. Notice that N P ⊆ coN P/P oly would imply a collapse to the third level of the polynomial time hierarchy.

On the positive side, we present a randomized fixed-parameter algorithm for the RFLCS problem parameterized by the size of the solution (denoted as k). Our randomized fixed-parameter algorithm has time complexity O * (2 k ) and polynomial space complexity, thus improving upon the existing algorithm proposed in [START_REF] Bonizzoni | Variants of Constrained Longest Common Subsequence[END_REF].

The rest of the paper is organized as follows. In Section 2, we give some preliminary definitions. In Section 3, we investigate the kernelization complexity of RFLCS, while in Section 4, we present the fixed-parameter algorithm for RFLCS.

Preliminaries

In this section we introduce some basic definitions. Let ∆ denote a finite alphabet and ∆ * the set of all finite length strings over ∆. Let Π ⊆ ∆ * × N be a parameterized problem and let 1 ∈ ∆. The derived classical problem Π C associated with Π is {x1 k : (x, k) ∈ Π}.

Let s be a string over alphabet Σ. We denote by |s| the length of s. The i-th symbol of s is denoted by s[i]. Given two positions i, j in s, with 1 ≤ i ≤ j ≤ |s|, we denote by s[i, j] the substring of s that starts at position i and ends at position j.

Consider two strings s 1 and s 2 . A common subsequence of s 1 and s 2 is a string s that can be computed by deleting some symbols (possibly none) in s 1 or s 2 . A longest common subsequence s of s 1 , s 2 is a common subsequence of s 1 and s 2 having maximum length. Given two strings s 1 and s 2 , we define s 1 s 2 as the concatenation of s 1 and s 2 .

The RFLCS problem is a constraint version of the longest common subsequence problem that has been introduced in [START_REF] Adi | Repetition-free Longest Common Subsequence[END_REF]. Given two strings s 1 , s 2 over alphabet Σ, RFLCS asks for a longest common subsequence of s 1 , s 2 where each symbol of Σ occurs at most once. Formally, the problem is defined as follows:

Problem 1. RFLCS Input: A pair of strings I = (s 1 , s 2 ) over alphabet Σ. Parameter: k. Output: A common subsequence s of s 1 and s 2 , such that each symbol σ ∈ Σ occurs at most once in s and |s| ≥ k.

The derived classic problem RFLCS C is known to be NP-hard [START_REF] Adi | Repetition-free Longest Common Subsequence[END_REF], even when each symbol occurs at most twice in each string.

Kernelization Complexity

In order to prove a lower bound on the polynomial kernel of RFLCS, we need to introduce in Section 3.1 some preliminary notions.

Preliminaries on Kernelization Complexity

In this section we introduce some preliminary notions about Kernelization Complexity, and in particular the notion of composition algorithm [START_REF] Bodlaender | On problems without polynomial kernels[END_REF].

Definition 1. [3] A composition algorithm for a parameterized problem Π ⊆ ∆×N is an algorithm that, given in input a sequence (x 1 , k), (x 2 , k), . . . , (x t , k) where each (x i , k) ∈ ∆ × N, runs in time polynomial in t i=1 x i + k, and outputs an instance (y, k ) ∈ ∆ × N such that 1. (y, k ) ∈ Π iff (x i , k) ∈ Π, for some 1 ≤ i ≤ t; 2. k is polynomial in k.
A parameterized problem is compositional if it has a composition algorithm.

We will apply the following fundamental result on kernelization complexity [START_REF] Fortnow | Infeasibility of instance compression and succinct PCPs for NP[END_REF]. Theorem 2. [START_REF] Fortnow | Infeasibility of instance compression and succinct PCPs for NP[END_REF] Let Π be a compositional parameterized problem whose derived classical problem Π C is NP-complete. If Π has a polynomial kernel, then N P ⊆ coN P/P oly.

Kernelization Complexity of RFLCS

In this section we prove that the RFLCS does not admit a polynomial kernel, unless N P ⊆ coN P/P oly. Since the derived classical problem RFLCS C is NP-complete [START_REF] Adi | Repetition-free Longest Common Subsequence[END_REF], we can prove the result applying the concept of composition algorithm given in Section 3.1.

Consider two instances

I 1 = (s 1,a , s 1,b ), k , I 2 = (s 2,a , s 2,b ), k of the RFLCS problem, such that s 1,a , s
Indeed assume that Σ 1 ∩ Σ 2 = ∅. Define a new alphabet Σ 1 such that for each α ∈ Σ 1 , there is a symbol α ∈ Σ 1 , where α / ∈ Σ 1 ∪ Σ 2 .
Then, define the string s 1,x , with x ∈ {a, b}, as follows: if • s a 1,2 = s 1,a s 2,a , that is s a 1,2 is the concatenation of s 1,a and s 2,a ;

s 1,x [i] = α, with 1 ≤ i ≤ |s 1,x |, then s 1,x [i] = α . By construction, s 1,a , s 1,b are over alphabet Σ 1 , with Σ 1 ∩ Σ 2 = ∅.
• s b 1,2 = s 2,b s 1,b , that is s b 1,2 is the concatenation of s 2,b and s 1,b . Example 1. Consider the instances I 1 = (s 1,a , s 1,b ), k and I 2 = (s 2,a , s 2,b ), k of RFLCS, where • s 1,a = abc • s 1,b = bca • s 2,a = def • s 2,b = ddf Then (s 1,a , s 1,b ) ⊗ (s 2,a , s 2,b
) produces the following strings:

s a 1,2 = s 1,a s 2,a = abcdef s b 1,2 = s 2,b s 1,b = ddf bca. Theorem 3.
The RFLCS problem does not admit a polynomial kernel unless N P ⊆ coN P/P oly.

Proof. Let (s 1,a , s 1,b ), k , (s 2,a , s 2,b ), k , . . . , (s t,a , s t,b ), k be t instances of RFLCS, defined over pairwise disjoint alphabets Σ 1 , . . . , Σ t . Let (s y,a , s y,b ) be a pair of strings defined as follows: (s y,a , s

y,b ) = (s 1,a , s 1,b ) ⊗ (s 2,a , s 2,b ) ⊗ • • • ⊗ (s t,a , s t,b ), that is s y,a = s 1,a s 2,a • • • s t,a , while s y,b = s t,b s t-1,b • • • s 1,b .
We claim that there is a solution for RFLCS over instance (s y,a , s y,b ), k if and only if there exists a j ∈ [t] such that RFLCS admits a solution over instance (s j,a , s j,b ), k) . First, assume that there is a solution of RFLCS over instance (s j,a , s j,b ), k , for some j ∈ [t]. Consider the substrings s j y,a , s j y,b of s y,a , s y,b respectively, consisting only of symbols in Σ j . Since by construction the instances (s 1,a , s 1,b ), k , (s 2,a , s 2,b ), k , . . . , (s t,a , s t,b ), k are over pairwise disjoint alphabets Σ 1 , . . . , Σ t , it follows by construction that s j y,a , s j y,b are identical to s j,a , s j,b respectively. Since there is a repetition free common subsequence of s j,a , s j,b of length at least k, then there is a repetition free common subsequence of s j y,a , s j y,b of length at least k, which implies that there is a solution for RFLCS over instance (s y,a , s y,b ), k .

Assume now that there is a solution s of RFLCS over instance (s y,a , s y,b ), k . Then we claim that s consists of symbols from exactly one alphabet Σ j , for some j ∈ [t]. Assume to the contrary that such a solution s contains a symbol α i ∈ Σ i and a symbol α j ∈ Σ j with i, j ∈ [t] and w.l.o.g. i < j. Recall that the instances (s 1,a , s 1,b ), k , (s 2,a , s 2,b ), k , . . . , (s t,a , s t,b ), k are defined over pairwise disjoint alphabets Σ 1 , . . . , Σ t . By construction α i appears on the left of α j is s y,a , while α i appears on the rigth of α j is s y,b . Hence s cannot contain both a symbol α i ∈ Σ i and a symbol α j ∈ Σ j . It follows that s is a string over alphabet Σ j , for some j ∈ [t], hence s is a repetition free common subsequence of s j y,a , s j y,b , which implies that s is a repetition free common subsequence of s j,a , s j,b .

By Theorem 2, it follows that RFLCS does not admit a polynomial kernel unless N P ⊆ coN P/P oly.

A Fixed-Parameter Algorithm

In order to present the fixed-parameter algorithm for RFLCS, we need to introduce in Section 4.1 some definitions and results concerning the multilinear detection technique.

Arithmetic circuits

Intuitively, the aim of this technique is to efficiently detect a multilinear monomial of a given degree in an arithmetic circuit, which is a compressed encoding of a multivariate polynomial.

More formally, let X be a set of variables {x 1 , x 2 , . . . , x z }. A multivariate polynomial is a sum of monomials. The degree of a monomial is the sum of the monomial variables degrees. A monomial is multilinear if the degree of all the variables is equal to 1. Thus, a multilinear monomial of degree k has exactly k different variables. For example, the degree of the monomial x 1 • x 2 2 is 3, and so is the degree of the multilinear monomial

x 1 • x 2 • x 3 .
An arithmetic circuit over X is a pair C = (C, r), where C is a labeled directed acyclic graph (DAG) such that each leaf (with an out-degree equal to zero) is labeled by a variable of X, each internal node is labeled either by + or ×, and r is a distinguished node of C (the root of C).

We can encode a polynomial with an arithmetic circuit. Recursively, the polynomial corresponding to a leaf is the label of the leaf, and the polynomial of an internal node labeled by + (resp. ×) is the sum (resp. the product) of its childrens' polynomials. Now, we can introduce the Multilinear Detection problem (MLD). Informally, given an arithmetic circuit C and an integer k, the Multilinear Detection problem asks if the polynomial P C encoded by C has a multilinear monomial of degree k. More formally, we give the definition of the Multilinear Detection problem. Problem 2. MLD Input: An arithmetic circuit C encoding a polynomial P C over a set of variables X. Parameter: k. Output: Does P C contains a multilinear monomial of degree k?

In [START_REF] Koutis | Limits and Applications of Group Algebras for Parameterized Problems[END_REF][START_REF] Williams | Finding paths of length k in O * (2 k ) time[END_REF], it is shown the following fundamental result for the MLD problem.

Theorem 4 ([14, 18]

). There exists a randomized algorithm that solves MLD in O(2 k |C|) time and in O(|C|) space.

In Section 4.2, we apply this result in order to obtain a new fixed-parameter algorithm for RFLCS.

A Fixed-Parameter Algorithm for RFLCS

In this section we present a randomized fixed-parameter algorithm for RFLCS of time complexity O * (2 k ) and of polynomial space complexity. The algorithm is based on the detection of multilinear monomials technique, presented in Section 4.1. Let s 1 , s 2 be the two input strings of RFLCS over alphabet Σ, we construct a circuit C as follows. C is defined over the set of variables {x a : a ∈ Σ}. Moreover, the circuit has a root P and a set of intermediary nodes P i,j,l , for 0 ≤ i ≤ |s 1 |, 0 ≤ j ≤ |s 2 | and 0 ≤ l ≤ |Σ|. Informally, the multilinear monomial P i,j,l encodes a repetition free common subsequence of the strings s 1 [1, . . . , i], s j [1, . . . , j], having length l. P i,j,l is defined as follows:

P i,j,l =          P i-1,j,l + P i,j-1,l + P i-1,j-1,l if i > 0, j > 0, s1[i] = s2[j] and l ≥ 1, P i-1,j,l + P i,j-1,l + P i-1,j-1,l-1 • x a if i > 0, j > 0, s1[i] = s2[j] = a and l ≥ 1, 1
if l = 0 and i, j ≥ 0, 0 if i = 0 or j = 0, and l > 0.

(1) Finally, define P = P |s1|,|s2|,k . The resulting instance of MLD is I = (C, k). Next, we prove the correctness of the reduction. Proof. We will prove that there is a RFLCS for the strings s 1 , s 2 of length k if and only if there is a multilinear monomial in C of length k. To do so, we prove by induction on i + j that there exists a repetition free common subsequence of s 1 [1 . . . i], s 2 [1 . . . j] containing the set of symbols {a 1 , . . . a l } (hence of length l) if and only if there is a multilinear monomial x a1 . . . x a l in P i,j,l .

When i = j = 1, assume that there is a repetition free common subsequence consisting w.l.o.g. of a 1 . Then s 1 [1] = s 2 [1] = a 1 , and, by Equation 1, P 1,1,1 = P 0,0,0 • x a1 = x a1 . Similarly, if P 1,1,1 = P 0,0,0 • x a1 = x a1 , then by construction it must hold s 1

[1] = s 2 [1] = a 1 .
Now, assume that the lemma holds for i + j = h, we prove that the lemma also holds for i + j = h + 1. Assume that there is a repetition free common subsequence s of s 1 [1 . . . i], s 2 [1 . . . j] consisting of the set of symbols {a 1 , . . . a l }. It follows, that either s

[l] = s 1 [i] = s 2 [j] = a z for a given 1 ≤ z ≤ l, or s[l] = s 1 [i], or s[l] = s 2 [j].
In the first case, by Equation 1, P i,j,l = P i-1,j-1,l-1 • x az . By induction, if there is a repetition free common subsequence s of s 1 [1 . . . i-1], s 2 [1 . . . j -1] consisting of symbols {a 1 , . . . , a l }\{a z }, then P i-1,j-1,l-1 contains a multilinear monomial of length l -

1 not including x az . If s[l] = s 1 [i] or s[l] = s 2 [j], then s is a repetition free common subsequence of s 1 [1 . . . i], s 2 [1 . . . j -1], or of s 1 [1 . . . i -1], s 2 [1 . . . j], or of s 1 [1 . . . i -1], s 2 [1 . . . j -1]
. By induction hypothesis, one of P i,j-1,l , P i-1,j,l , P i-1,j-1,l contains a multilinear monomial x a1 . . . x a l . By Equation 1, P i,j,l also contains such a multilinear monomial.

Assume that P i,j,l contains a multilinear monomial m x = x a1 . . . x a l . By construction (Equation 1) it holds that m x is either contained in one of P i-1,j,l , P i,j-1,l , P i-1,j-1,l or it is obtained from P i-1,j-1,l-1 • x a and P i-1,j-1,l-1 contains a multilinear monomial over the set of variables {x a1 . . . x a l } \ {x a }. In the first three cases, by induction hypothesis there is a repetition free longest common subsequence of s 1 [1 . . . i], s 2 [1 . . . j] consisting of symbols a 1 , . . . , a l . Hence, assume that the latter case holds, that is P i,j,l = P i-1,j-1,l-1 • x a . Hence P i-1,j-1,l-1 contains a monomial over the set of variables {x a1 . . . x a l } \ {x a }.

As a consequence, by induction hypothesis, there is a repetition free longest common subsequence s of s 1 [1 . . . i -1], s 2 [1 . . . j -1] over the set of symbols {a 1 , . . . , a l } \ {a}. But then s = s a is a repetition free longest common subsequence of s 1 [1 . . . i], s 2 [1 . . . j] over the set of symbols {a 1 , . . . , a l }, concluding the proof for the induction.

By applying Theorem 4 of Section 4.1, and by observing that |C| = k|s 1 ||s 2 |, we can solve RFLCS with a randomized algorithm with the claimed complexities.

Conclusion

We have investigated the parameterized complexity of the RFLCS, a variant of the LCS problem that, given two strings s 1 , s 2 , asks for a common subsequence s of s 1 , s 2 of length at least k such that s contains at most one occurrence of each symbol. We have proved that the RFLCS does not admit a polynomial size kernel, unless N P ⊆ coN P/P oly and we have given a fixedparameter algorithm for RFLCS of resp. O(2 k k|s 1 ||s 2 |) time and O(k|s 1 ||s 2 |) space complexities. To obtain these complexities, we used the multilinear detection framework, which seems to be quite powerful to improve algorithms based on dynamic programming and color-coding, widely used in computational biology. Indeed, some authors already gave improvements of some algorithms using this framework [START_REF] Guillemot | Finding and Counting Vertex-Colored Subtrees[END_REF] [START_REF] Fu | A Polynomial Algebra Method for Computing Exemplar Breakpoint Distance[END_REF].

An interesting open problem lies on the analysis of the approximation complexity of RFLCS: it is still open whether RFLCS admits a constant factor approximation algorithm or not.

  Furthermore, it is easy to see that RFLCS on input (s 1,a , s 1,b ), k admits a feasible solution if and only if RFLCS on input (s 1,a , s 1,b ), k admits a feasible solution. Given (s 1,a , s 1,b ) and (s 2,a , s 2,b ), the composition algorithm defines the operation (s 1,a , s 1,b ) ⊗ (s 2,a , s 2,b ), which starting from (s 1,a , s 1,b ) and (s 2,a , s 2,b ) outputs the strings s a 1,2 , s b 1,2 , defined as follows:

Theorem 5 .

 5 RFLCS is solvable by a randomized algorithm in O(2 k k|s 1 ||s 2 |) time and O(k|s 1 ||s 2 |) space.

  1,b (s 2,a , s 2,b respectively) are over alphabet

1 (Σ 2 respectively). We assume that Σ

1 ∩ Σ 2 = ∅, otherwise, starting from s 1,a , s 1,b , we can compute in time O(|s 1,a | + |s 1,b |) an instance I 1 = (s 1,a , s 1,b ), k of RFLCS such that (1) s 1,a , s 1,b are over alphabet Σ 1 , with Σ 1 ∩ Σ 2 = ∅; (2) RFLCS on input (s 1,a , s 1,b ), k admits a feasible solution if

and only if RFLCS on input (s 1,a , s 1,b ), k admits a feasible solution.

Email addresses: gblin@univ-mlv.fr (Guillaume Blin), bonizzoni@disco.unimib.it (Paola Bonizzoni), riccardo.dondi@unibg.it (Riccardo Dondi), sikora@univ-mlv.fr (Florian Sikora)Preprint submitted to ElsevierDecember 22, 2011

We recall that in the O * () notation, the polynomially bounded terms are suppressed.


Clarisse Didelon

Sophie De Ruffray

Executive summary -Main results -Table of content List of figures -Appendix

Outline and Results

Executive summary

This report aims to present and discuss the main findings obtained from the Work Package 2 "Mental map of students" (WP2) work package of the EuroBroadMap project 1 . This report follows the general plan of the questionnaire implemented in the survey. The introduction focuses on the general aims of the survey conducted in the WP2 and on the constraints imposed by our general hypotheses. It justifies the sample in terms of categories of population and places of survey, and also presents the main variations inside the sample regarding three categories of explanatory variables: 1) the material and symbolic capital of the student's family; 2) the spatial history of the student and their family; 3) personal awareness of the international and cultural diversity of the world. This general introduction to the report is quite important, and reviews the general objectives of the survey and stresses the potential influence of social and economic inequalities on the representation of Europe and on mental maps of the world.

The first part focuses on a specific question of Part A of the questionnaire: the feeling of belonging to a specific spatial-scale level. We formulated a strong hypothesis about the link between the student's perception of their spatial identity and their perception and representation of the world.

The second part of the report analyses in depth the countries and cities in which students declare they would like to live. As our sample does not cover the entire world, it does not allow measuring precisely the attractiveness of Europe in the world. It nevertheless provides interesting trends showing a coherent perception of the world according to the places of survey. This coherence between the answers of students in the same places of survey can also be observed in the following parts of the survey.

The third part of the report describes the results obtained on the mental maps of Europe and the words used to describe it. The first one shows that the vision of Europe is quite consensus throughout the sample and, at the same time, that the fuzziness of European borders is more important towards the east than towards the south: the Mediterranean Sea is a strong mental border of Europe in the minds of the students of all places surveyed. The vocabulary used to describe Europe also varies according to the places of survey, with a vision of "institutional" Europe in the European Union countries, an idealised and tourism based vision of Europe in Russia, China, and India, and a contrasted vision in African countries and Brazil: students surveyed in these countries pointed to both the development level of Europe, but also stress their impression of "rejection" using words such as "racism" and "xenophobia".

In the conclusion, we choose to place the results obtained in the WP2 of the EuroBroadMap project in a wider perceptive: it presents a benchmarking of our results with three previous studies realised between 2004

Main results

In order to avoid repetitions, we will focus the conclusion of the report on a benchmarking of our results with three previous studies realised between 2004 and 2009 on the external image of the European Union (EU) from three different points of view.

• The first one, made by the Academic Cooperation Association (ACA), is about the attractiveness of the EU to foreign students of six target countries (2004).

• The second one, prepared by the Garnet project, is about the external image of the EU combining individual, media and institutional visions (2007)(2008)(2009).

• The third one, made in ESPON Project 3.4.1, focuses on the place of Europe in the world according to European researchers and policy makers (2007).

The attractiveness of the EU for foreign students: Benchmarking of the EBM results with the ACA study (2004)

The ACA study (2004 [START_REF] Aca | Perceptions of European Higher Education in Third Countries[END_REF]) provides an analysis of the attractiveness of the EU to students, which is comparable in size to the EuroBroadMap survey, using the same target population (about 10,000 students). The difference is that only students located outside the European Union are analysed in the ACA study which prevents the comparison between internal and external perceptions in the EBM survey. The theoretical focus is also different as the aim of the ACA study was to measure the external attractiveness of the EU to foreign students rather than to develop a critical perspective on how the EU is seen from outside.

The ACA study was realised between November 2004 and December 2005, following a call for tender issued by the European Commission. The Academic Cooperation Association (ACA) carried out a major study, the purpose of which was to investigate the perception of European higher education in other parts of the world, and on this basis to identify some key messages for a "European brand" in the field of higher education and to reflect on possible instruments and mechanisms for its delivery. To this end, the ACA study sought to acquire an in-depth understanding of how European higher education is viewed by students and other stakeholders in "third countries", its perceived strengths and weaknesses, and its standing relative to that of other major destinations. The study was based on large-scale surveys in six target countries: China, India, Mexico, Brazil, Russia, and Thailand, as well as on interviews (with individuals and groups) and on desk research. For comparative purposes, it also included international students in the USA. Altogether, 11,471 students from the target countries filled in the paper questionnaires distributed at schools and institutions of higher education in the six target countries; 1,235 staff members filled in the paper questionnaires distributed at the same institutions; almost 9,000 students filled in the on-line questionnaire (a slight majority came from the six target countries, the rest were spread over different countries around the world); and over 400 international students in the United States participated in the US survey. This was by far the largest survey of worldwide perceptions of European higher education ever conducted.

Despite these differences of sample and objectives, some interesting comparisons can be made between the key findings obtained in the two projects.

Concerning Europe's share of international students worldwide, the ACA study concludes that "Europe has a reasonable share of non-European foreign students, but the United States is still the leading destination and the performance of Australia in attracting foreign students is remarkable, relative to its size. Despite considerable growth in recent years, Europe's relative disadvantage with regard to the USA and Australia as a destination for foreign students is predominantly with Asian students. Foreign students in Europe are unevenly spread, with the UK, Germany, and France hosting the lion's share. Other countries, particularly the new member states and southern Europe, are under-represented." Our study does not make it possible to compare the presence of foreign students in the same countries as the ACA study, but we can without any doubt confirm the fact that the places of survey located in the northwestern part of the EU (France, Belgium, Sweden) and, to a lesser degree, in Mediterranean countries of the EU (Malta, Portugal), are more open to foreign students than the places of survey located in the new member states from East-Central Europe (Hungary, Moldavia) and in neighbouring countries (Turkey, Tunisia). The highest share of foreign students in northwestern Europe is associated with a more important level of income and education (self-rated) and with a higher importance of foreign travel and of complexity of familial history (with parents born in different countries than students).

Concerning the differential perception of the EU countries in terms of higher education attractiveness, the ACA study noticed, firstly, that While there is a perception of Europe as an "entity" in general terms and as an economic union, when it comes to cultural aspects and higher education, most international students rather see Europe as a range of very different countries. The perceived differences relate to the quality of education provided in individual EU member states, and to some extent in costs (tuition fees and living costs) and the availability of student support. Knowledge of Europe is limited to a very few countries, namely the UK, Germany, and France. The number of students who were well informed about other countries was negligible. Especially, the knowledge of higher educational opportunities in the new member states was extremely limited. The interviews revealed little or no interest in cooperating with or going to the new member states or less "prominent" countries, though with regard to the Nordic countries and the Netherlands this appears to be starting to change.

Concerning the first key discovery made by the ACA study, our survey was not able to confirm directly the assumption that Europe is more perceived as a set of countries rather than as an "entity". But we have indirect confirmation of this fact through the analysis of question B, on countries and cities where students would like to live or not like to live in the near future. Obviously, students located in the most remote countries (India, China, Brazil) have mainly declared they would like to live in countries from northwestern Europe, i.e., the member states of the old EU15 plus Norway and Switzerland. France and the United Kingdom were generally the first declared destinations, but Germany did not always have the third position, it being often bypassed by other countries such as Spain, Italy, and eventually Switzerland. The new member states were generally ignored by students or mentioned mostly negatively as places where students would not like to live in the near future. The only exception was the Czech Republic, in relation with the high attractiveness of its capital city, Prague. Looking in more detail, we can notice that this low attractiveness of new member states is not only observed in remote countries but also in the old member states and southern Mediterranean countries (Tunisia, Egypt) and Sub-Saharan countries (Cameroon, Senegal). The situation is more complex on the eastern border of the EU where a local polarisation of attractiveness can be observed and where the opinion on neighbouring countries is more developed (even if it can be negative). For example, Romania is declared, in Hungary, as a place where students would not like to live, but it is the reverse in Moldova. Russian students declared they would not like to live in countries that were previously members of the Soviet empire but at least they mentioned them (Ukraine, Belarus, Baltic countries). And they also introduced more positive statements about countries such as Hungary, Slovakia, Croatia, Serbia, and the Czech Republic. The current European Union with 27 members is not perceived as an "entity" by the students, but this is probably the case with the EU15 plus Switzerland and Norway. This result is derived not only from the analysis of question B on attractive/repulsive countries, but also from the results of question D, regarding the limits of Europe. We have noticed that many students propose a restricted definition of Europe that excludes not only the more recent members (Bulgaria, Romania) and the candidate countries (Turkey, Croatia) but which tends in many cases to limit the extent of Europe to the old core of northwestern Europe.

The differential attractiveness of the European Union as compared to the USA or Australia for students in emerging countries has been pointed out by the ACA study:

Europe has a better standing in Russia and Latin America, while the US and Australia are favoured by students in the Asian target countries (which represent a considerably bigger share of the total international student population world-wide); Asian students rank the US above Europe in most academic and labor-market related issues (quality of laboratories, libraries, and other facilities; quality of education; most prestigious universities; reputation of degrees; chances of getting a job and staying on after graduation; work opportunities during studies); Europe and Australia are perceived as safe destinations, but not the US; Europe and Australia are regarded as more accessible than the US at least as far as visas are concerned. Free tuition is regarded as an asset, and in overall terms Europe is perceived as more affordable than the US, though less affordable than Australia. Especially Asian students thought that it was easier to obtain a scholarship in the United States. Interviews also showed that information about English-taught programs in non-English speaking countries was not widespread.

Once more, the conclusion of the EuroBroadMap survey supports nicely the observation made by the ACA, but with important differences in terms of the interpretation of the factors of explanation. On the one hand, we have noticed that Brazilian students were very close to EU students in terms of their vision of the world (attractive places, scales of belonging, words associated to Europe), and we have also pointed to the fact that Russian students were very attracted by Western European countries, as compared to Indian and Chinese students, who are more likely to identify the USA as an attractive destination and, more generally, the Pacific rim (Australia, Japan, Korea). We have also noticed, through the comparison of the attractiveness of countries and cities, that the choice of specific cities (and probably universities) could balance their opinion about countries such as the USA. But on the other hand, we do not take for granted that the explanation of this differential is only related to difference of quality in terms of education, reputation of universities, and jobs opportunities. In our opinion, geographical distance combined with common language and historical network (such as colonisation) or economic flows such as trade relations) remains a major factor of explanation of students' preferences. The ACA study is right when it points to the effect of language and visa facility. But the authors probably underestimate the trivial effect of geographical distance and transport network accessibility that appears in all parts of our study as a major factor of knowledge on the opportunities offered by distant places. Contrary to what is claimed by many gurus, the world is definitely not "flat" and the best opportunities for the European Union to attract the "creative class" are certainly to be found in the countries of its neighbourhood or in countries with a long common history of migration, such as Africa and Latin America.

The stereotype of Europe as a traditional historical and cultural museum more interesting for tourism or leisure than for professional activity or social innovation (as compared to the USA or Australia) was finally pointed to by the ACA study.

Cultural and linguistic diversity is mainly seen as attractive, especially in Latin America. However, a significant group of Asians see diversity of languages as a barrier to communication and diversity of cultures as confusing; Europe's single major disadvantage in the eyes of Asian students is that English is not the universal mother tongue. Students rank the US first for issues linked to innovation, competition and dynamism (both in labour and society in general); Europe is seen as the destination with the most traditional universities, the most interesting cultural heritage and traditions, and the most attractive arts, music and cultural offering; Europe is seen as lacking innovation, tolerance and joie de vivre, thus reinforcing the picture of a "traditional" Europe lacking dynamism; Europe is generally seen as being elegant, clean, organised and modern.

The results of our survey are generally in line with this conclusion, in particular when it comes to the analysis of the question D2 and the choice of five words associated with Europe. As the authors of the ACA study, we have been surprised by the importance of the words associated to an apparently positive (but in fact very disturbing) vision of Europe in large emerging countries such as China ("graceful, "mysterious", "romantic", "pretty", "classical"), India ("lifestyle", "chocolate", "sophisticated") or Russia ("Cathedral", "Ferrari", "Mercedes", "Eiffel Tower"). The vision of Europe as a wealthy, industrialised, and developed part of the world is more frequent in countries such as Brazil and the southern and eastern neighbourhoods, but in this case it is also more frequently associated with a vision of a part of the world characterised by "xenophobia", "racism", "imperialism" and "self interest", especially in sub-Saharan countries. The association of Europe with "human rights", "peace", or "freedom", is mostly quoted internally, or to some extent, in countries strongly associated with the EU economy such as Tunisia and Turkey. But, in this case, it is also balanced by negative statements on the external closure of the EU borders. As a whole, the external vision of Europe by students is based on a romantic illusion at long distances and pessimistic disillusion at short distances.

Benchmarking of EBM results with the surveys on the External Image of the EU (Garnet Project 5.2. 1, 2007 & 2009) The two reports delivered by Garnet's project "The External Image of the European Union" (Lucarelli, 2007[71]; Lucarelli and Fioramonti, 2009 [START_REF] Lucarelli | The external image of the European Union, phase two[END_REF]) deserve also an in-depth comparison because, unlike the ACA study which focused on competitiveness, this project shares the same theoretical background as EuroBroadMap about a critical approach to external visions of Europe seen from abroad. Of course, the methodology is very different, and the focus is not on students, as in our study. But many preliminary comparisons of results can still be made on the basis of the key findings of each project, keeping in mind that the present benchmarking is limited to discoveries made in WP2 of EuroBroadMap project, and should be further completed by other results of WP3 (qualitative survey on migrants perception of the EU), WP4 (political visions of the EU), and WP5 (functional situation of the EU in the world according to flows).

The survey The External Image of the European Union has been conducted in two steps in the framework of the jointly executed research project 5.2.1 (Normative issues) of the Network of Excellence GARNET Global Governance, Regionalisation and Regulation: the Role of the EU-(the EU Sixth Framework Programme 2005-2010; Call Identifier: FP6-2002-Citisens-3), with the financial support of the Italian Ministry of Foreign Affairs. The research had four main aims: (1) evaluate the degree of academic information already available on how the EU is perceived outside its borders; (2) combine this information with an analysis of the open sources (newspapers, websites, official documents, available opinion polls), so as to produce a more detailed investigation of how the EU is perceived from outside; (3) evaluate whether such perceptions vary across geographic areas of the world, countries, and target groups within countries; (4) gain information useful to assess the extent to which there is a gap between the EU's self-representation and outside views of the EU.

In order to reach these goals, the authors combined various methodology and deliverables:

• Country reports: the selection of a sample of countries in each continent: Canada, Brazil, Australia, China, India, Japan, Egypt; South Africa in the first step, then Israel, Iran, Mexico, Palestine, Russia, Lebanon, the United States, and Venezuela in phase two of the project;

• Target groups: the selection of four target groups within each country on which to focus attention: political elites, public opinion, the press, and organised civil society;

• Issue areas: the selection of a number of areas that appear to be crucial in the EU's representation of itself and in the scholarly literature on the EU's international role;

• Sources: the collection of information on the image of the EU within each target group by: (i) reviewing the very limited academic literature available and (ii) analysing the open sources available, with particular attention to the analysis of the press. Each researcher chose a research strategy targeted to the needs of the country being analysed;

• Transversal reports summarising the discoveries made and making recommendations.

The limited knowledge of the EU in external countries is the first major conclusion of the report realised by political scientists under the direction of Lucarelli (2007): "There is a rather limited knowledge of the EU (particularly among certain target groups, such as civil society and citizens at large). Furthermore, there exists a general perception of Europe (more than the EU) as a political actor, which is influenced by historical relationships with individual European countries (e.g. former colonial empires). Such a weight of historical and colonial ties is rather prominent also at the level of political elites and the media." Many results from our survey of students confirm this analysis. We have discussed before the existence of surprising "stereotypes" in the choice of the word associated with Europe, especially in countries located at long distances such as China and India. We can complete the demonstration by an analysis of the boundaries of Europe drawn by the students and the fact that students from remote countries are generally more likely than others to draw limits of Europe that do not fit with the political borders of the European Union. For example, students from China generally draw simple circles or ellipses that do not respect the limits of the European Union, except on the southern side where the Mediterranean Sea is generally used as border. Indian students are apparently more precise when they follow the coastline of Europe, but they are no more likely to follow the political limits of the EU and many of them forgot (intentionally?) to include Ireland and the United Kingdom within their boundaries of Europe. Cameroonian students offer another point of view as they frequently include Russia and more generally the former Soviet Union in their drawing of Europe, which can be interpreted as the fact that Europe is not limited to the European Union and involves as well the former Eastern Europe, socialist until 1989-1991. This trend is coherent with the way Europe is taught in the textbooks of these countries. It is only for countries located in the neighbourhood, or for remote countries with stronger historical and migratory relations, that the official limits of the European Union are more often used as the limits of "Europe", and that the eastern limit is likely to be consistent with the current limits of the European Union. Among neighbouring countries, many differences appear between those that will decide to enlarge more or less the limit towards the south (Maghreb countries), towards the southeast (Turkey, Romania), or towards the east. Inside the European Union, a clear division appears between the old member States, which are very reluctant to any enlargement towards the south or east, and the new member states, which generally support the limit of the Mediterranean Sea but are more or less open to the eastern side, including large spaces beyond them. Finally, it is visible that for many students all over the world, the limits of "Europe" are not the limits of the European Union but something fuzzier with a clear core located in the area covering the six initial members of the EU. This EU6 core is easily enlarged to the EU15 plus Switzerland and Norway, but not so easily to the new member states of the EU25 and with many hesitations in the case of the last round of enlargement (Romania, Bulgaria) and the candidate countries (Turkey, western Balkan countries). The European Union is more an element of identification of "concentric circles of Europe" (identification of a core, semi-peripheries, and peripheries) than a factor of definition of its external limits. of part A of our survey that the "scales of belonging" of students are, firstly, highly correlated with the places of survey (students feel more "global" or "supranational" in the European Union and in neighbouring countries, more "national" in Russia, more "provincial" in China, more "local" in Cameroon) but are also strongly related to their field of study (students in arts are more "global" and less "national" than others), gender (women are definitively more "global" than men), and with the levels of income and education of parents. Both social and geographical factors are combined through the effect of international mobility, which can be either inherited from familial history or derived from the personal experience of the students, but that produces in every case a movement up the scale of belonging toward "supranational" or "global", and a decrease of the identification with "local" or "national". We have also demonstrated through spatial interaction models that the choice of countries and cities where the students would like to live in the near future is strongly related to the size of countries, their wealth, and their relative distance (both geographical and linguistic) to the country of origin of the students. Colonial relations could be a candidate for the explanation, but with ambiguous effects and possible inversion. For example, the students from Cameroon are less attracted to France and the UK than to Canada or the USA if we take into account the other effects of size, distance, wealth and common language. France remains actually the most attractive destination for students from Cameroon, but the share of negative opinion is relatively high and, according to the literature, students from Cameroon are more and more attracted towards other destinations located in America or Africa (in particular southern Africa).

The gap between the EU's self perception and external perception seen from abroad is the major finding of Lucarelli's report, which is summarised as follows by the author: "There is a certain gap between the EU's self-representation and the various images based on external perceptions, particularly as far as countries from the global South are concerned. Southern images/criticisms are frequently shared by NGOs worldwide in Europe included. As a matter of fact, if it is true that the EU is perceived as: a "strategic opportunity" for the partner countries; a trade giant; a supporter of multilateralism or at least multipolarism; a model of regional integration; a possible counterbalance to US hegemony. It t is also viewed as: an actor whose policy is severely influenced by its own security concerns; a neo-liberal actor in its attitude to the abroad; a protectionist power. Most of these images call into question the EU's self-representation as a solidaristic actor. Surprisingly, we could not find much evidence of the EU being widely seen as a "normative power" exporting universal values of democracy and human rights. This image seems to be confined only to a small segment of the organised civil society in the South. Equally surprisingly, the EU does not seem to be regarded anymore as a social model to be imitated." As mentioned before, the lexical analysis of the five words associated to Europe by the students of the EuroBroadMap survey is strongly in line with this diagnosis, but we have to make clear the fact that the question asked was related to "Europe" and not to "the European Union", which makes an important difference. When we look at the most frequent words used to qualify "Europe" in all of our sample (without distinction between countries located inside and outside the EU), the general picture that we obtain is firstly characterised by the two dimensions of political construction ("European", "union") and economic level ("developed", "development", "rich"). Two secondary dimensions appear to be related to cultural dimension ("culture", "history", "civilisation") and human rights ("freedom", "democracy", "diversity"). But it is clear that Europe or the European Union are not mainly characterised by world influence if we consider that the words "world" and "power" appear only in fourteenth and sixteenth place. This general picture of words realised at the level of the whole sample of students is in fact subject to important variations and it is mainly inside the European Union that the vision of Europe as an economic power or a political union is the most frequently observed. As we have noticed before, remote countries are more likely to define the European Union by other criteria, which range from "xenophobia" and "racism" (Cameroon) to "luxury", "beauty" and "romantic" (China and India). These results support therefore the observation made by Lucarelli's report on the low perception of Europe as a normative power (both inside and outside) but also the fact that there exists a clear cognitive dissonance between external and internal perceptions.

Benchmarking of EBM results with Europe in the World study (ESPON Project 3.4.1, 2007)

Finally, we comment briefly on the results of the EuroBroadMap survey as to the conclusions of the ESPON Project 3.4.1, "Europe in the World (2007)", which was a direct ancestor of the current study. The crucial point of that 2007 report was the fact that the situation of the European Union in the world was not so bad, even if its influence was decreasing and if its weight was likely to decrease from an economic and demographic point of view. The key political recommendation of that report was the need for the European Union to develop a strategic vision for its relation with the world in general and neighbouring countries in particular. Different existing visions were analysed ("Continent", "Centre-Periphery", "Archipelago") all of which possessed some advantages but also important shortcomings. The report proposed a fourth vision called "North-South regionalism" that was considered as the most interesting option for the European Union in the long run. The report also admitted that this option would probably be difficult to implement in the short term because it was in contradiction with public opinion, especially in terms of mental maps:

The European countries have a crucial choice to make between two options: [START_REF] Aca | Perceptions of European Higher Education in Third Countries[END_REF] to remain a continental integrated area based on homogeneity: gathering comparable countries, with cohesion as the main goal, through a process promoted mainly by states through public policies, a sort of "convergence regionalism"; (2) to build a more ambitious regional entity along with southern and eastern neighbours: an "in-depth regionalism" gathering unevenly developed countries, with economic growth and environment protection as the main goals, through a process promoted also by firms such as in NAFTA or "ASEAN Plus Three". This second pattern of regionalisation would provide better economic results than the first one [52]. The problem with this North-South vision lies in the fact that it is not based on the usual mental visions of Europe-in-the-world shared by European citizens and political decision makers. It is therefore difficult to imagine that it could be politically implemented at the EU level in the near future. Security issues and the fear of terrorism have become the major points of the Barcelona process, which was initially based on a much wider vision of a joint economic, social, ecological and cultural development on both sides of the Mediterranean. In the short term, and any moral consideration apart, a "closed-continent" or "centre-periphery" strategy could appear realistic for an economically declining and ageing Europe. But in fact, constructing an island of prosperity surrounded by oceans of poverty would most probably have tragic consequences in the long run.

In the project "Europe in the World", a first study on mental maps had been realised with a limited sample of participants in an ESPON seminar (114 researchers and policy makers from all countries of the EU). As in the current EuroBroadMap project, the participants were invited to divide the world into regions and propose their own limits of Europe. Looking at the way participants divided the world, the authors of the survey noticed that " 'the strongest division of the world for the ESPON seminar participants is the one drawn through the Mediterranean between Europe and North African countries. Would that mean that they feel that the European countries are very much different from the North African ones? Could that mean that for the European researchers and policy makers who attended the seminar, the Mediterranean should be considered as the most evident frontier of the world, and consequently the frontier of Europe?" The existence of a strong mental barrier, the Mediterranean Sea, was confirmed by the further question of where people proposed the limits of Europe. One more time, the limit appeared very strong on the Mediterranean Sea, despite the fact that the participants of the survey had visited many countries surrounding Europe. "A better knowledge about a specific country could lead people to more easily consider it as belonging to Europe or the contrary. So the following question is: is there a relation between the number of people that visit a country and the number of people considering that this country belongs to Europe? The pattern of the correlation plots shows that in fact there is no relation at all. In consequence, the frequency of visit to a country cannot be considered as a means to explain the fact that people consider that a country belongs or not to Europe."

Looking at the results of the EuroBroadMap survey, we have confirmation that the Mediterranean Sea is perceived by the majority of students as a very marked limit of "Europe". And we have also learned that this limit is perceived as a limit of Europe not only by students from the EU but also by students from external countries. Of course, some students from Tunisia or Egypt are more likely to enlarge the limit of the Europe toward the south and to include the southern coast, but they remain a very small minority. The situation is certainly more complicated and fuzzier on the eastern side where we have noticed a lot of variation in the inclusion of the Balkans, Turkey, Ukraine, and even Russia. There are also some interesting differences in the northwest direction, where different limits are proposed, sometimes excluding Ireland and the UK, and sometimes including Iceland and Greenland.

At the moment of delivering this report (March 2011), it is difficult to say if the "Arab revolutions" from springtime 2011 will contribute to modifying the perception of the southern border of the EU. And if such a modification of mental maps occurs, which forms would it take on both sides of the Mediterranean Sea? It is certainly of interest for the EU to follow the analysis that was engaged in by EuroBroadMap and to examine whether modifications will take place in the next period following the political revolution in the arabo-muslim countries. And it is important to transmit these results to public opinion on both sides of the Mediterranean Sea. As stated by Lucarelli at the end of "The External Image of the European Union": "the analysis on the external image of the EU should not be limited to how the EU is perceived in non-European countries, but should develop research strategies to evaluate whether and how such external images influence the internal process of identity formation among Europeans. What do European citizens know of how others see them and their institutions? How do the European media depict such an external reputation of the EU? Those are questions which are usually neglected in both research on EU political identity and research on the external image of the EU. On the contrary, we believe that filling this gap is fundamental for the analysis of the process of formation of the EU as a full-fledged political actor." [START_REF] Lucarelli | The external image of the European Union[END_REF]

  and 2009 on the external image of EU from three different points of view: the ACA study on Perceptions of European Higher Education in Third Countries (2004), the Garnet project's study on The External Image of the EU (2007, 2009) and the ESPON project Europe in the World (2007).

Figure 1 :

 1 Figure 1: Limits of Europe according to ESPON survey (2007)

  p. 342) 2 Introduction 35 The Eurobroadmap survey . . . . . . . . . . . . . . . . . . . . . . . 35 Organisation of the questionnaire . . . . . . . . . . . . . . . . . . . 44 3 Variations in the scale of the feeling of belonging 61 3.1 Theoretical definition and empirical measure of the degree of the feeling of belonging . . . . . . . . . . . . . . . . . . . . . . 61 3.1.1 Human territoriality and the concept of "man's shell" . 61 3.1.2 The question of "feeling of belonging" as proxy for "man's shell" . . . . . . . . . . . . . . . . . . . . . . . 63 3.1.3 Overview of the distribution of answers by country . . 65 3.2 International and intra-national variations of the scale of belonging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.2.1 Three main oppositions . . . . . . . . . . . . . . . . . 71 3.2.2 Typology of places of survey . . . . . . . . . . . . . . . 74 3.3 Social factors of variation of scale of belonging . . . . . . . . . 77 3.3.1 Methodological background for the analysis of social factors . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.3.2 The effect of gender, field of study, and religion . . . . 78 3.3.3 The effect of income and education levels . . . . . . . 81 3.3.4 The effect of the mobility of students and their families 82 3.3.5 The effect of journeys abroad and number of languages spoken . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 3.4 Conclusion: From scale of belonging to mental maps of students 85 4 Knowledge and attractiveness of cities and countries 91 4.1 Rate of participation and other background information . . . 92 4.1.1 Level of participation by field and place of survey . . . 92 4.1.2 Number of answers by topic and place of survey . . . . 92 List of Tables 1 Scale of belonging by place of survey . . . . . . . . . . . . . . 70 2 Number of answers to the question about cities where students would like to live (horizontal) and not like to live (vertical) in the near future . . . . . . . . . . . . . . . . . . . . . . . . . . 94 3 Number of answers to the question about countries where students would like to live (horizontal) or not like to live (vertical) in the near future . . . . . . . . . . . . . . . . . . . . . . . . . 94 4 Structural factors of choice of countries where students would like to live in the near future . . . . . . . . . . . . . . . . . . 123 5 Structural factors of choice of cities where students would like to live in the near future . . . . . . . . . . . . . . . . . . . . . 124 6 Knowledge logit models . . . . . . . . . . . . . . . . . . . . . 125 7 Asymmetry logit models . . . . . . . . . . . . . . . . . . . . . 125 8 Specific vocabulary of women . . . . . . . . . . . . . . . . . . 163 9 Specific vocabulary of men . . . . . . . . . . . . . . . . . . . . 164 10 Specific vocabulary of Art students . . . . . . . . . . . . . . . 166 11 Specific vocabulary of Business students . . . . . . . . . . . . 168 12 Over-represented vocabulary of Engineering students . . . . . 169 13 Under-represented specific vocabulary of Engineering students 170 14 Over-represented specific vocabulary of Politics students . . . 171 15 Under-represented specific vocabulary of Politics students . . 172 16 Over-represented specific vocabulary of students in human and social sciences . . . . . . . . . . . . . . . . . . . . . . . . 173 17 Under-represented specific vocabulary of students in human and social sciences . . . . . . . . . . . . . . . . . . . . . . . . 174 18 Specific vocabulary of Health Sciences students . . . . . . . . 175 19 Over-represented specific vocabulary of students with a low level of income . . . . . . . . . . . . . . . . . . . . . . . . . . 178 20 Under-represented specific vocabulary of students with a low level of income . . . . . . . . . . . . . . . . . . . . . . . . . . 179 21 Specific vocabulary of students with a low-medium level of income . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 22 Over-represented specific vocabulary of students with a mediumhigh level of income . . . . . . . . . . . . . . . . . . . . . . . 182 23 Under-represented specific vocabulary of students with a mediumhigh level of income . . . . . . . . . . . . . . . . . . . . . . . 183 24 Specific vocabulary of students with a high level of income . . 184 25 Specific vocabulary of students with one language spoken . . 186 26 Over-represented specific vocabulary of students speaking two languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 27 Under-represented specific vocabulary of students speaking two languages . . . . . . . . . . . . . . . . . . . . . . . . . . 188

Except for Part C of the questionnaire, which focused on world representations: it will be presented within the framework of the WP6 (synthesis) in close connection with other work package results, mainly the WP5 (flows and networks).

Both geographical and sociological factors define the vision of the world (in general) and Europe (in particular). Contrary to the ACA study, the research on the External Vision of the EU has examined in detail the geographical and social variation of perception through the benchmarking of many country studies, but also many types of actors. On the basis of these results, the authors conclude that: "The degree of knowledge of the EU seems to be very much dependent on the level of education and societal position. Furthermore, the knowledge of Europe is frequently related to the relationship with individual European countries, particularly in the case of former colonies, as we have seen in the case of India, for instance. In other cases, the limited attention to the EU can be clearly explained in terms of its geographic distance and the limited visibility of the EU policy with respect to that of other core powers such as the US. In general, there is a closer knowledge of some core European states than the EU as such, particularly in the case of former colonies (e.g. in India of the UK)" (Lucarelli, 2007, pp. 330-331). Following the same approach, we arrived at the same conclusion, that the level of education and societal position on the one hand, geographical position and historical-cultural distance between countries on the other hand, are two complementary factors to be introduced in the explanation of the attitudes of students towards globalisation, the knowledge and attractiveness of countries or cities, or the definition of "Europe". Concerning the first point, we have clearly demonstrated on the basis

Acknowledgments

We would like to thank the researchers in the 18 countries involved in the EuroBroadMap Project who contributed to the realisation of the global survey, especially C. Didelon (CNRS, France), G. Van Hamme (ULB, Belgium), E. Marques da Costa (CEG, Portugal), A. Dubois (Nordregio, Sweden), A. Spiteri (IRMCo, Malta), O. Groza (UAIC, Romania), O. Zengingonul (DEU, Turkey), N. de Mello (USP, Brazil), A. Bopda (CAUPA, Cameroon), Y. Ning (ECNU, China), M. Thapan (Univ. of Delhi, India), A. Bennasr (Univ. of Sfax, Tunisia), and V. Kolossov (Russian Institute of Geography, Russia).