Virginie Gabrel
email: gabrel@lamsade.dauphine.fr

Maude Manouvrier
email: manouvrier@lamsade.dauphine.fr

Kamil Moreau

Écile Murat
email: murat@lamsade.dauphine.fr

QoS-aware Automatic Syntactic Service Composition problem: complexity and resolution

Keywords: Service composition, Web Service Challenge, AND/OR constraints, QoS optimization. ✦

Automatic syntactic service composition problem consists in automatically selecting services, from a registry, by matching their input and output data. The composite service, resulting from this selection, allows producing a set of output data, needed by a user, from a set of input data, given by the user. Many approaches resolving the aforementioned problem do experimentations on the well-known Web Service Challenge (WSC) standard benchmark, which provides synthetic services. Since 2009, this challenge has extended the syntactic service composite problem to a Quality-Of-Service (QoS) based one, by describing the synthetic services with execution time and throughput values. In this article, we propose an original formulation of the QoS-aware automatic syntactic service composition problem in terms of scheduling problem with AND/OR constraints, using a directed graph structure. For the WSC-09 benchmark (considering execution time and throughput QoS criteria), our exact algorithm outperforms the related work. We also analyse the complexity of optimizing other QoS criteria (cost and reliability) and exhibit polynomial cases.

INTRODUCTION

The QoS-aware automatic syntactic service composition problem consists in automatically composing services by matching their parameters (input and output data) such that the resulting composite service can produce a set of output data from a set of input ones while optimizing a Quality of Service (QoS) criterion.

Available services are grouped into a service registry. For example the Jena Geography Dataset 1 groups almost 200 geography services that have been gathered from different web sites. Moreover, it exists standard synthetic data benchmarks, as the Web Service Challenge (WSC) one. As shown in [START_REF] Weise | Semantic web service composition: The web service challenge perspective[END_REF], WSC proposes an incremental synthetic data benchmark. In 2005, it only focuses on syntactic web service composition, then it integrates OWL for Taxonomy in 2007, and structured data types in 2008 [START_REF] Bansal | WSC-08: Continuing the Web Services Challenge[END_REF], and finally it introduces QoS criteria (execution time and throughput) in 2009 [START_REF] Kona | WSC-2009: A Quality of Service-Oriented Web Services Challenge[END_REF]. These benchmarks are still used by recent approaches. For example, authors in [START_REF] Rodriguez Mier | An Integrated Semantic Web Service Discovery and Composition Framework[END_REF] experiment their approach on WSC-08, authors in [START_REF] Ma | A hybrid approach using genetic programming and greedy search for qos-aware web service composition[END_REF] on WSC-08 and WSC-09 and authors in [START_REF] Rodriguez Mier | A hybrid localglobal optimization strategy for qos-aware service composition[END_REF] on WSC09. In the last benchmarks, a WSDL standard file [START_REF] Booth | Web services description language (wsdl) version 2.0 part 0: Primer[END_REF] describes the input and output data of all the services available in the registry. Input and output data are hierarchically organized in terms of concepts using ontology recorded in a OWL [START_REF] Bechhofer | OWL Web Ontology Language Reference[END_REF] standard file. A WSLA [START_REF] Ludwig | Web Service Level Agreement (WSLA) Language Specification[END_REF] file describes the QoS criteria of all available services.

In this article, we propose an original formulation of the QoS-aware automatic syntactic service composition problem in terms of scheduling problem with AND/OR constraints. This formulation allows to apply very efficient exact algorithm for optimizing the execution time and throughput criteria (as shown by our experimental results on WSC-09). We analyse the complexity of optimizing other types of QoS 1. http://fusion.cs.uni-jena.de/professur/jgd/ criterion and exhibit polynomial cases.

This article is organized as follows. Section 2 presents the syntactic service composition problem. Related work is reviewed in Section 3. Considering execution time and throughput criteria, the service composition problem is modelled as a scheduling one with AND/OR constraints in Section 4. Section 5 analyses the theoretical complexity of service composition problem for cost and reliability criteria. Finally Section 6 concludes.

SYNTACTIC SERVICE COMPOSITION PROBLEM

Problem description: the feasibility part

As the syntactic description of functions in programming language, any (SOAP, RESTful or Web API) service s can be syntactically described by the set of its input data (i.e. the data needed by the service to be invoked), in(s), and the set of its output data (i.e. the data produced by the service invocation), out(s). We denote S the set of services and D the set of data. Example 1. Let us consider an example with 9 services and 9 data:

s 1 2 3 4 5 6 7 8 9 in(s) J K, P L, M M M P J N, P L out(s) M J, M N P P, Q R, Q L T N, P Table 1
An example of a service registry A service registry can easily be represented by a directed graph G = (X, U ), called in the following ServiceData graph:

• vertices represent services and data: X = D ∪ S,

• directed edges in U represent two kinds of relation:

(1) an edge from i ∈ S to j ∈ D represents the fact that service i produces data j (j ∈ out(i)), (2) an edge from i ∈ D to j ∈ S represents the fact that service j needs data i to be executed (i ∈ in(j)).

Let us remark that G is a bipartite graph (there does not exist any directed edge linking two vertices belonging to S or two vertices belonging to D).

Example 2. The ServiceData graph associated with the service registry given in Table 1 is represented in Fig. 1. Vertices representing data are represented with circles while vertices representing services are drawn with squares. For example, vertex P is a data produced by services represented by vertices 4, 5 or 9 and, is an input of services 2, 6 and 8. Service represented by vertex 3 needs data L and M to be executed and produces data N .

K 2 5 Q R M 4 P 6 J 1 7 3 N 8 T L 9
Figure 1. The ServiceData graph associated with registry of Table 1 Such graph can be, for example, easily built from the files provided by WSC-09 synthetic benchmark. This benchmark provides 5 test sets, each one containing one service registry described by 3 main files: services.wsdl describing services of the registry by their input/output, taxonomy.owl containing the ontology and Servicelevelagreements.wsla storing the QoS (response time and throughput) criteria values of each service. The first file, services.wsdl, contains all the services' identifier and their input and output, each one being defined as an instance of the ontology (i.e. as a leaf in a concept hierarchy) stored in the second file taxonomy.owl. A service is then represented in the ServiceData graph by a vertex s. Each input i of a service s is represented by vertex i. Each output o of a service s is represented by several vertices, as many as the concept of o has ancestors in the ontology.

A user query, denoted (I, O), is defined by a set I ⊆ D of data provided by the user and a set O ⊆ D of data required by the user. A service can be invoked only if all its input data are available. A data is available if it is computed by at least one service or if it is provided by user. In order to respond to a user query, the syntactic service composition problem is to select the set of services (representing the components of the resulting composite service) that provides, from the user input set I, the set O of all outputs needed by the user.

We can formulate this problem on the ServiceData graph transformed as follows:

• we add a fictitious vertex d 0 , representing an "empty" data, d 0 is included in D and I; for each service s which does not need any input to be executed, we add an arc (d 0 , s) ∈ U (d 0 is included in in(s)),

• we add a fictitious vertex denoted s 0 , which represents the beginning of the process; s 0 is included in S and for all i ∈ I, we add an arc (s 0 , i) ∈ U (thus out(s 0 ) = I),

• we add a fictitious vertex denoted End, which represents the end of the process; End is included in S and for all o ∈ O, we add an arc (o, End) ∈ U (thus in(End) = O).

A solution denoted C of the aforementioned composition problem can be expressed in terms of sub-graph. More precisely, given a query characterized by I and O, a sub-graph G C = (X C , U C ) of the ServiceData graph G corresponds to a composite service C if and only if:

• s 0 and End belong to X C , • if a vertex i ∈ D belongs to X C ,
at least one arc (j, i) ∈ U , with j ∈ S, belongs to U C (it is due to the fact that each data i has to be produced by at least one service),

• if a vertex i ∈ S belongs to X C , all arcs (j, i) ∈ U , with j ∈ D, belong to U C (it is due to the fact that each service i can be executed if and only if all its inputs data are available), Services can also be described by their Quality of Service (QoS) criteria. Among QoS criteria, we can find the execution time (i.e. the time needed by a service to produce output data from the input ones) and the throughput (i.e. the average rate of successful service execution). A service with the highest throughput and the lowest execution time represents a good performing service. In the following section, we present the most used criteria and the way to compute them.

Problems description: the optimality part

The QoS of a composite service C depends on the QoS of each service belonging to the composite service. In the following, we choose to present 4 famous QoS criteria which are representative of 4 different ways to aggregate individual QoS services:

• Execution time. Let us denote e(s) ≥ 0 the execution time of service s, P C the set of paths in G C from s 0 to End and v e (C) the value of the composite service C on the execution time criterion. We have:

v e (C) = max µ∈P C s∈µ e(s)
This criterion has to be minimized and the associated problem is denoted ESC for Execution time Service Composition.

• Throughput. Let us denote t(s) ≥ 0 the throughput of service s and v t (C) the value of the composite service C on the throughput criterion. We have:

v t (C) = min s∈C t(s) = min µ∈P C min s∈µ t(s)
This criterion has to be maximized and the associated problem is denoted TSC for Throughput Service Composition.

•

Cost. Let us denote c(s) ≥ 0 the cost of service s and v c (C) the value of the composite service C on the cost criterion. We have:

v c (C) = s∈C c(s)
This criterion has to be minimized and the associated problem is denoted CSC for Cost Service Composition.

• Reliability. Let us denote r(s), with 0 ≤ r(s) ≤ 1, the reliability of service s and v r (C) the value of the composite service C on the reliability criterion. We have:

v r (C) = s∈C r(s)
This criterion has to be maximized and the associated problem is denoted RSC for Reliability Service Composition.

The QoS values are modelized in the ServiceData graph as weight on vertices: a vertex representing a service has a weight equals to its QoS value, vertices associated to data and fictitious vertices (s 0 and End) have a neutral value (0 for the execution time and the cost values, 1 for the reliability value and +∞ for the throughput value).

For the first two criteria, the value of a composite service C is equal to the value of a particular optimal path in G C : the maximal path value for the execution time criterion and the minimal path value for the throughput criterion. The first criterion has to be minimized while the second one has to be maximized. That's why these two criteria, maxmin-type (or equivalently minmax-type) criteria, can be similarly processed by computing optimal path. Polynomial-time algorithm has been proposed in [START_REF] Jiang | Qos-aware automatic service composition: A graph view[END_REF], [START_REF] Jiang | QSynth: A Tool for QoS-Aware Automatic Service Composition[END_REF], [START_REF] Luo | An accumulated-qos-first search approach for semantic web service composition[END_REF] for solving the service composition problem with a maxmin-type criterion. This composition problem is the subject of the WSC-09 and a lot of papers have proposed different approaches to solve it. At the opposite, the last two criteria (sum-type and producttype respectively) cannot be expressed in terms of path value in G C . They induce much more difficult optimization problems. Indeed in [START_REF] Geyik | Robust dynamic service composition in sensor networks[END_REF], [START_REF] Oh | Effective web service composition in diverse and large-scale service networks[END_REF], authors show that the service composition problem is NP-hard when a sum-type criterion (e.g number of services or cost) is minimized. In [START_REF] Geyik | Robust dynamic service composition in sensor networks[END_REF], the proof is based on a reduction to the set cover problem. A composition problem with a sum-type criteria is the subject of WSC-08 which appears to be much more difficult than WSC-09.

In this article, we analyse the four optimality problems and the main results are:

• We show that the minimal ESC problem is a wellstudied project scheduling problem with AND/OR precedence constraints.

•

The minimal ESC and maximal TSC problems can be solved with a polynomial-time algorithm (already proposed in the project scheduling context) directly applied on the associated ServiceData graph. This algorithm is more efficient on WSC-09 instances than already published algorithms [START_REF] Jiang | Qos-aware automatic service composition: A graph view[END_REF], [START_REF] Jiang | QSynth: A Tool for QoS-Aware Automatic Service Composition[END_REF], [START_REF] Luo | An accumulated-qos-first search approach for semantic web service composition[END_REF].

•

We analyse the particular difficulty of the NP-hard minimal CSC problem and we exhibit a polynomial case (associated with a particular class of ServiceData graph).

•

We show that the maximal RSC problem is NP-hard and we exhibit also a polynomial case.

The next section presents the related approaches associated with the aforementioned problems.

RELATED WORK

QoS-aware automatic syntactic service composition problem has attracted a lot of attention from different fields in recent years. We choose to classify these approaches into four groups: search approaches, dependency graph approaches, planning graph approaches and integer linear programming ones.

Search approaches

In [START_REF] Huang | Effective Pruning Algorithm for QoS-Aware Service Composition[END_REF] and [START_REF] Jiang | QSynth: A Tool for QoS-Aware Automatic Service Composition[END_REF], the WSC-09 first run-up winners propose a polynomial-time algorithm to solve the minimal ESC and maximal TSC problems. Its worst case complexity, given in [START_REF] Jiang | QSynth: A Tool for QoS-Aware Automatic Service Composition[END_REF], is O(a|S| 2 ), with a the average number of services' input data. This algorithm proceeds in two steps: in the first one, a forward search aims to eliminate useless services for satisfying the user's query and, at the same time, computing optimal QoS values of useful services; in the second stage, a backtrack search is executed to determine the optimal composite service. In [START_REF] Luo | An accumulated-qos-first search approach for semantic web service composition[END_REF], authors propose a more efficient polynomial-time algorithm for solving the minimal ESC problem: the first part is a search procedure determining, at each iteration, the minimal accumulated execution time of one service (this search procedure stops when all user outputs are reached) and, the second part is a backtrack search in order to determine the optimal composite service. No theoretical complexity results are given. This algorithm is the closest one from ours. However, authors claim that the backtrack search can be rather long. From our point of view, this is due to the chosen data structures and we propose a more efficient graph-based data structure.

Dependency graph approaches

In [START_REF] Geyik | Robust dynamic service composition in sensor networks[END_REF], [START_REF] Jiang | Qos-aware automatic service composition: A graph view[END_REF], authors represent the QoS-aware automatic syntactic service composition problem with another directed graph, called dependency graph. In the dependency graph, denoted H = (S, A), vertices only represent services. There is an arc in A from i to j if the intersection between the output of i and the input of j is not empty (i.e. service j needs a subset of the outputs produced by i to be executed, in(j) ∩ out(i) = ∅). The arc is tagged with the subset of data belonging to the intersection. Example 4. The dependency graph corresponding to the service registry given in Table 1 is represented in Fig. 3. Vertex s is drawn with a square divided into three columns: in(s) is given in the first column, s in the middle and out(s) in the latest one. For example, service 9 produces data N and P and service 6 needs data P , so there is an arc from 9 to 6 with tag P . 1 Remark 1. For building the dependency graph, one needs to read the service registry and, for each service, one has to match its inputs with the outputs of all the other services, inducing an O(|S|) complexity for each service (cf. [START_REF] Omer | A framework for Automatic Web Service Composition based on service dependency analysis[END_REF]). Consequently, the building step of the dependency graph is O(|S| 2 ).

J 1 M K P 2 J M L M 3 N M 4 P M 5 Q P P 6 Q R J 7 L N P 8 T L 9 N P L L M M M
In [START_REF] Jiang | Qos-aware automatic service composition: A graph view[END_REF], authors propose a new approach: to apply a Dijkstra-like algorithm on the dependency graph to solve the minimal ESC and maximal TSC problems. In their experimental results, we remark that the computational time is mainly due to the building step of the dependency graph (for example, for instances with 10000 services, the building time is 6000ms while the resolution time is 60ms). Moreover, this article includes inexact results: authors claim that their algorithm can be also applied to determine the optimal composite service on product-type criterion (reliability). We show in section 5.2 that it is not true since RSC problem is NP-hard. In [START_REF] Rodriguez Mier | A hybrid localglobal optimization strategy for qos-aware service composition[END_REF], authors mention the inexact result of [START_REF] Jiang | Qos-aware automatic service composition: A graph view[END_REF] to establish that the optimal QoS can be calculated in polynomial time, which is right only for throughput and execution time criteria.

Planning graph approaches

IA planning and graph-based approaches are also used for solving service composition problem. In [START_REF] Zheng | An efficient syntactic web service composition algorithm based on the planning graph model[END_REF], the planning graph model is applied for solving the following feasibility problem: does there exist a feasible composite service for satisfying the user's request, without considering any QoS criterion? Considering QoS-aware composition problem, Chen and Yan in [START_REF] Chen | QoS-aware Service Composition over Graphplan through Graph Reachability[END_REF] propose a three steps algorithm to determine the best composite service considering maxmin (for example execution time) or sum-type (for example cost) criterion. First, they represent the service composition problem by a labelled planning graph. Second, they transform the labelled planning graph into a layered weighted graph. Third, an optimal service composite is found by applying Dijkstra shortest path algorithm. Steps 1 and 3 can be done by polynomial-time algorithms; the complexity of step 2 is not presented in [START_REF] Chen | QoS-aware Service Composition over Graphplan through Graph Reachability[END_REF]. Since the QoS-aware service composition with sum-type criterion is NP-hard, the step 2 is the critical non-polynomial part of the algorithm. Thus, this approach is not interesting for solving the service composition with maxmin-type criterion since a polynomialtime algorithm has been already proposed in [START_REF] Huang | Effective Pruning Algorithm for QoS-Aware Service Composition[END_REF]. The same criticism can be done for the algorithmic study presented in [START_REF] Deng | Efficient planning for top-k web service composition[END_REF].

Integer linear programming approaches

Integer Linear Programming (ILP) model have also been proposed for QoS-aware service composition in [START_REF] Gabrel | Optimal and Automatic Transactional Web Service Composition with Dependency Graph and 0-1 Linear Programming[END_REF], [START_REF] Paganelli | A qos-aware service composition approach based on semantic annotations and integer programming[END_REF], [START_REF] Daniel | A web service composition framework using integer programming with nonfunctional objectives and constraints[END_REF]. In [START_REF] Paganelli | A qos-aware service composition approach based on semantic annotations and integer programming[END_REF], [START_REF] Daniel | A web service composition framework using integer programming with nonfunctional objectives and constraints[END_REF], a composite service is decomposed into stages: a stage contains one service or several services executed in parallel. The associated ILP represents the problem of selecting one or several services per stages. Thus, the number of variables and constraints can be huge since there are proportional to the number of services and data times the number of stages. Moreover, the number of stages is not known; only upper bounds can be chosen (the worst one is to set the number of stages equals to the number of services). The size of the model does not allow to solve big size instances. In [START_REF] Gabrel | Optimal and Automatic Transactional Web Service Composition with Dependency Graph and 0-1 Linear Programming[END_REF], authors propose a new ILP model containing a lower number of variables and constraints (proportional to the number of services and data). This model is able to optimize a QoS criterion while satisfying transactional requirements. In a large majority of the experimental instances of WSC-09, model of [START_REF] Gabrel | Optimal and Automatic Transactional Web Service Composition with Dependency Graph and 0-1 Linear Programming[END_REF] finds a better solution more rapidly than models proposed in [START_REF] Paganelli | A qos-aware service composition approach based on semantic annotations and integer programming[END_REF], [START_REF] Daniel | A web service composition framework using integer programming with nonfunctional objectives and constraints[END_REF].

In conclusion, for minimal ESC and maximal TSC problems, search approaches dominate. Planning graph and integer linear programming approaches become relevant for other QoS-aware problems. In this article, we show that the minimal ESC problem is exactly a well studied project scheduling problem with AND/OR constraints. In [START_REF] Link | Scheduling with AND/OR precedence constraints[END_REF] authors propose a Dijkstra-like algorithm to solve the project scheduling problem with AND/OR constraints. This algorithm is similar to the one proposed in [START_REF] Jiang | Qos-aware automatic service composition: A graph view[END_REF] but can be directly applied on a ServiceData graph (without computing a Dependency graph) as shown in the next section.

SERVICE COMPOSITION AS A SCHEDULING PROBLEM WITH AND/OR CONSTRAINTS

Scheduling with AND/OR precedence constraints

In a classical precedence-constrained scheduling problem, we have to determine the starting times of a set of jobs to be performed (with known execution time) while satisfying some precedence constraints of the form "a job i can be performed if and only if a job j is finished". Thus, a job is ready to be executed when all its precedence jobs are completed. The objective is to minimized the total execution time of all the jobs. This well-known problem can be solved in polynomial-time with critical-path algorithm (see e.g. [START_REF] Ahuja | Network Flows: Theory, Algorithms, and Applications[END_REF]). In a scheduling problem with AND/OR precedence constraints, two kinds of jobs are considered: jobs with AND precedence constraints are "classical" ones which can be executed when all their precedence jobs are finished, and jobs with OR precedence constraints can be performed when at least one of their precedence jobs is terminated. This scheduling problem can also be solved in polynomial time : several algorithms have been proposed in [START_REF] Adelson-Velsky | Project Scheduling in AND/OR Graphs: A Generalization of Dijkstra's Algorithm[END_REF], [START_REF] Dinic | The Fastest Algorithm for the Pert Problem with AND-and OR-Nodes (The New-Product-New-Technology Problem)[END_REF], [START_REF] Link | Scheduling with AND/OR precedence constraints[END_REF].

The minimal ESC problem is exactly a scheduling problem with AND/OR precedence constraints in a ServiceData graph:

• both data and services are jobs,

• services are AND-constrained jobs since each service can be executed if and only if ALL its input data are available,

• data are OR-constrained jobs since each data is available when AT LEAST one service produces it.

We adapt the algorithm given in [START_REF] Link | Scheduling with AND/OR precedence constraints[END_REF] to the service composition context and present it in the next subsection.

Polynomial-time algorithm for minimal ESC problem

In Algorithm 1, we denote nd(j): the number of nonavailable data expected by service j to be executed (at the beginning nd(j) = |in(j)|). Data and services are labelled with variables λ representing their starting time. The labels are initialized (lines 2-8) as follows:

• λ(s 0 ) = 0 (line 4)

• λ(i) = 0 for all data i in I (lines 5-8),

• λ(i) = +∞ for any other data and services (line 2).

For each data i, we have to record in p(i) the index of the service that produces i and p(i) is initialized by -1 (line 2).

At the beginning, all the labels are temporary. When the label of service j becomes definitive, it means that λ(j) is equal to its earliest starting time, while for the label of data i, it means that the data i is available at the earliest time λ(i). The set of vertices with definitive labels is denoted L in Algorithm 1. At the beginning, it only contains s 0 .

The temporary finite labels of data are recorded in a heap H: the root of the heap contains the data with the minimal value temporary label. In Algorithm 1, the classical heap functions are called:

• root(H): removes and returns the root of heap H • insert(λ(i), i, H): inserts data i with key λ(i) into heap H, • decrease(v, i, H): modifies heap H due to the decreasing of the label of data i, now equals to v.

In a current iteration of the algorithm, the three following steps are performed (lines 10-24):

Step 1. Data i with the smallest temporary λ(i) is chosen: its label becomes definitive (line 10).

Step 2. For each service j with data i as input, decrease nd(j) of one unit. If the counter nd(j) reaches 0, it means that the service j can be executed at the starting time of its latest available input data:

λ(j) = max i∈in(j)
λ(i). Thus, the label of service j becomes definitive (line 14). Step 3. For each service j whose label became definitive at the previous step, consider each data i belonging to out(j) and refresh its label as follows (lines [START_REF] Ludwig | Web Service Level Agreement (WSLA) Language Specification[END_REF][START_REF] Luo | An accumulated-qos-first search approach for semantic web service composition[END_REF][START_REF] Ma | A hybrid approach using genetic programming and greedy search for qos-aware web service composition[END_REF][START_REF] Link | Scheduling with AND/OR precedence constraints[END_REF][START_REF] Oh | Effective web service composition in diverse and large-scale service networks[END_REF][START_REF] Omer | A framework for Automatic Web Service Composition based on service dependency analysis[END_REF][START_REF] Paganelli | A qos-aware service composition approach based on semantic annotations and integer programming[END_REF][START_REF] Rodriguez Mier | A hybrid localglobal optimization strategy for qos-aware service composition[END_REF]:

λ(i) = min{λ(i), λ(j) + e(j)}
and update p(i).

When Algorithm 1 terminates, two cases have to be considered:

•

The fictitious vertex End has a definitive label. It means that all its input data (corresponding to set O) are available and, λ(End) is equal to the minimum execution time. Using p(i) (∀i ∈ D), we can easily obtain the solution composite service, with a very fast backtrack procedure.

•

The fictitious vertex End has not a definitive label and λ(End) equals +∞. It means that it does not exist any feasible composite service to satisfy the query.

Algorithm 1 is exact: the proof is given in [START_REF] Link | Scheduling with AND/OR precedence constraints[END_REF]. Concerning the complexity, we obtain

O(|D| log 2 |D| + s∈S |in(s)| + s∈S |out(s)| log 2 |D|).

Polynomial-time algorithm for maximal TSC problem

Algorithm 1 can be modified in order to optimize the throughput criterion. The entire algorithm is presented in the appendix and we present here the main modifications. First, the labels representing throughput are now initialized as follows: for all j ∈ S \ L such that i ∈ in(j) do 12:

nd(j) ← nd(j) -1

13:

if nd(j) == 0 then 14:

L ← L ∪ {j} and λ(j) ← max k∈in(

v ← λ(j) + e(j)

16: end for 25: end while 26: Return λ(End)

for all k ∈ out(j) \ L do 17: if λ(k) == +∞ then 18: λ(k) ← v, p(k) ← j and insert(v, k, H) 19: else if λ(k) > v then 20: λ(k) ← v, p(k) ← j, decrease(v, k, H)
Step 1. Data i with the maximal temporary λ(i) is chosen: its label becomes definitive. Step 2. For each service j with data i as input, decrease nd(j) of one unit. If the counter nd(j) reaches 0, it means that the service j can be executed with a throughput value equals to the minimal throughput of its input data: λ(j) = min i∈in(j) λ(i). Thus, the label of service j becomes definitive. Step 3. For each service j whose label became definitive at the previous step, consider each data i belonging to out(j) and refresh its label as follows:

λ(i) = max{λ(i), min{λ(j), t(j)}}
The temporary finite labels of data are recorded in a heap which root contains the maximal λ. We have to update the heap function by replacing the decrease function by an increase one.

When the service composition problem does not have any solution, Algorithm 2 cannot label End and terminates with λ(End) = 0. Property 1. When Algorithm 2 terminates with End ∈ L, we have: for all i ∈ S ∪ D, λ(i) = v t (µ * (i)) with µ * (i) the maximal throughput value path from s 0 to the vertex i.

Proof 1. The proof is by induction on the following property: Rank k. We denote D k (resp. S k ) the subset of data i (resp. service i) belonging to L at the kth iteration of the while loop (lines 9-25). For all i ∈ D k ∪ S k , λ(i) equals to the optimal path value from s 0 to i on throughput criterion denoted v t (µ * (i)).

Rank 0. We have S 0 = {s 0 } and D 0 = I. At the initialization step of the algorithm:

-λ(s 0 ) = +∞ ⇒ λ(s 0 ) = v t (µ * (s 0 )) -∀i ∈ I, λ(i) = +∞ ⇒ λ(i) = v t (µ * (i))
So, the property is satisfied at rank 0 and we assume that it is verified at rang k. Thus we have to show that the property is satisfied at rank k + 1.

Rank k + 1. The algorithm chooses the data d belonging to D \ D k such that λ(d) = max i∈D\D k λ(i). Let us suppose that this choice is wrong: the optimal path is µ * (d) = {s 0 , d 1 , . . . s q , d q+1 , . . . , s l , d l+1 = d} and we have v t (µ * (d)) > λ(d). If we scan µ * (d) from s 0 to d, one necessarily encounters a service, denoted s q with 1 ≤ q ≤ l, belonging to S k while d q+1 / ∈ D k . Since the property is verified at rank k and s q ∈ S k , we have λ(s q ) = v t (µ * (s q )). By construction of the algorithm, we also have: λ(d q+1 ) ≥ min{λ(s q ), t(s q )} implying:

λ(d q+1 ) ≥ v t (µ * (s q )) (1)
Moreover, since µ * (s q ) ⊂ µ * (d), we have: In the next sub-section, we present the computational time taken by Algorithms 1 and 2 on WSC-09.

v t (µ * (s q )) ≥ v t (µ * (d)) (2)

Experimental results

The experiments were carried out on a Dell PC with Intel (R) Core TM i7-2760, with 2,4 Ghz processor and 8 Go RAM, under Windows 7 and Python 2.7. We have tested our algorithm on the 5 Test Sets (TS) of WSC-09 2 [START_REF] Kona | WSC-2009: A Quality of Service-Oriented Web Services Challenge[END_REF] containing around 500, 4000, 8000 and 15000 WS (described by their response time and throughput QoS values) with respectively more than 1500, 10000, 15000 and 25000 data. Each test set corresponds to one query.

For each test set, in Table 2, we report:

• in the first line, the number of vertices associated with services, |S|,

• in the second line, the number of vertices associated with data, |D|,

• in the third line, the computational time (in ms) necessary for Algorithm 1 to compute the optimal solution on the execution time criterion and the computational time necessary to obtain the corresponding optimal solution with the backtrack procedure,

• in the fourth line, the computational time (in ms) necessary for Algorithm 2 to compute the optimal solution on the throughput criterion and the computational time necessary to obtain the corresponding optimal solution with the backtrack procedure.

Let us compare our results with the closest approaches already published. First, our results are better than those of [START_REF] Jiang | Qos-aware automatic service composition: A graph view[END_REF], since we don't have to build the dependency graph. Our results are also better than those of [START_REF] Luo | An accumulated-qos-first search approach for semantic web service composition[END_REF] (and consequently than those of [START_REF] Huang | Effective Pruning Algorithm for QoS-Aware Service Composition[END_REF], [START_REF] Jiang | QSynth: A Tool for QoS-Aware Automatic Service Composition[END_REF]) because our algorithm is based on a directed graph structure, which specially allows us to define a very efficient backtrack procedure. Unfortunately, as shown below, this polynomial-time algorithm can not be extended to other QoS criteria.

QOS-AWARE SYNTACTIC COMPOSITION PROB-LEM: NP-HARD CASES

Minimal CSC problem: the case of sum-type QoS citerion

General case

The minimal CSC problem is proved to be NP-hard in [START_REF] Geyik | Robust dynamic service composition in sensor networks[END_REF]. The service composite of Fig. 4 has a total cost v c (C sj ) c(s i ) + c(s j ). On the other hand, summing the cost values of s j 's inputs, we obtain:

v c (C K ) + v c (C L ) = 2c(s i )
When adding c(s j ), we do not obtain v c (C sj ) since c(s i ) is counted twice (forgetting that K and L are both outputs of the same service s i ).

In the second typical situation, a data is an input of several services.

The composite service of Fig. 5 has a total cost v c (C s l ) = c(s i ) + c(s j ) + c(s k ) + c(s l ). On the other hand, summing the cost values of the s l 's inputs, we obtain:

= v c (C Q ) + v c (C R ) = v c (C sj ) + v c (C s k ) = 2v c (C P ) + c(s j ) + c(s k ) = 2c(s i ) + c(s j ) + c(s k )
When adding c(s l ), we do not obtain v c (C s l ) since the cost of P is counted twice.

In general case, the cost of a composite service cannot be computed by summing the cost of its input data and Algorithm 1 cannot be updated for solving minimal CSC problem. However, in the following section, we can exhibit a polynomial case.

A polynomial case for solving CSC problem

If we assume the two following hypotheses, then the minimal CSC problem becomes polynomial: -(a) each service produces only one data, -(b) each data is an input of only one service. In this case, each feasible composite service is such that:

v c (C s ) = i∈in(s) v c (C i ) + c(s) (3)
since X Ci ∩X Cj = {s 0 }, ∀i, j ∈ in(s). If X Ci ∩X Cj = {s 0 }, then it exists a vertex v = s 0 , v ∈ C s such it exits a path from v to i and it exists a path from v to j. Then i ∈ in(s) and j ∈ in(s) imply that there exist two disjoint paths from v to s which contradicts hypothesis (a) or (b). In particular, equation 3 is useful for the minimum cost value and allows us to adapt the Algorithm 1 for solving the minimal CSC problem.

Maximal RSC problem: the case of product-type QoS citerion

In this section, we show that the maximal RSC problem is NP-hard. Therefore, both maximal RSC and minimal CSC problems are NP-hard.

In [START_REF] Jiang | Qos-aware automatic service composition: A graph view[END_REF], authors claim that their polynomial-time algorithm (similar to Algorithm 1 applied to the dependency graph) can be used for exactly solving maximal RSC problem. Theorem 1 implies that this claim is wrong. Here we give an example to illustrate that the algorithm provided in [START_REF] Jiang | Qos-aware automatic service composition: A graph view[END_REF] does not give the optimal solution. Example 5. In the dependency graph in Fig. 6, we consider the following reliability: At each current iteration, algorithm of [START_REF] Jiang | Qos-aware automatic service composition: A graph view[END_REF] chooses a maximal temporary label for becoming definitive: the first label concerns service 1 and the second one service 2. Thus, the algorithm determines the composite service with services 1 and 2 to obtain data M , N , P and Q with global reliability of 0.64. The optimal solution is clearly the service 3 with reliability of 0.7 which is better.

CONCLUSION

The QoS-aware syntactic service composition problem has been the subject of numerous studies. The well-known benchmark WSC, allows experimenting approaches for such problem using synthetic services. In this article, we recall that the theoretical complexity of the challenges of 2008 and 2009 are different: the service composition problem presented in WSC-08 (without QoS) is NP-hard, while for the problem presented in WSC-09 (QoS-aware service composition), we propose a polynomial-time algorithm. This algorithm is an extension of a Dijkstra-like project scheduling algorithm, with AND/OR constraints, for exactly solving the service composition problem. Our algorithm is based on a simple directed graph structure and does not need to construct any additional structure, like a dependency graph or a planning graph as usually used in the related work. Thanks to this simple graph structure, our approach is the most efficient one for exactly solving, in polynomial time, the service composition problem with a maxmintype criterion (like execution time or throughput criterion).

Unfortunately, for sum-type criterion (like cost QoS criterion), polynomial time approaches can not be applied, since this problem has been shown as NP-hard. In this article, we highlight the particular difficulty of such optimization problem and exhibit polynomial cases. We also show that the QoS-aware syntactic composition problem is NP-hard, when optimizing a product-type criteria like the reliability criterion. Approximate approaches can be defined for solving NP-hard composition problems. This is left for future research.

•GExample 3 .Figure 2 .

 32 Figure 2. A composite service and the associated sub-graph

Figure 3 .

 3 Figure3. The dependency graph associated with registry of Table1

•Algorithm 1

 1 λ(s 0 ) = +∞,• λ(i) = +∞ for all data i in I,• λ(i) = 0 for any other data and services.Moreover, current iteration has to be updated as follows: Minimal ESC.

1 :

 1 H ← ∅ 2: λ(i) ← +∞ ∀i ∈ S ∪ D and p(i) ← -1 ∀i ∈ D 3: nd(j) ← |in(j)| ∀j ∈ S 4: λ(s 0 ) ← 0 and L ← {s 0 } 5: for all i ∈ out(s 0 ) do 6: λ(i) ← 0 and p(i) ← 0 7: insert(λ(i), i, H) 8: end for 9: while End / ∈ L and H = ∅ do 10: i ← root(H) and L ← L ∪ {i} 11:

Equations 1 and 2

 2 and the hypothesis v t (µ* (d)) > λ(d) imply: λ(d q+1 ) > λ(d) which contradicts λ(d) = max i∈D\D k λ(i).Thus, if the algorithm chooses data d with the maximal λ(i), we have λ(d) = v t (µ * (d)). And at the end, λ(End) = v t (µ * (End))

Figure 4 .

 4 Figure 4. An example with a two-output data service

Figure 5 .

 5 Figure 5. An example with a same input data of two distinct services

Theorem 1 .Proof 2 .

 12 The maximal RSC problem is NP-hard. The proof is based on a reduction from the minimal CSC problem. Given an instance of the minimal CSC problem described by a graph G = (X, U ) and a cost c(s) ≥ 0 associated to each service s, we build an instance of the maximal RSC problem described by the same graph G and a reliability r(s) = e -c(s) associated to each service s, inducing that each r(s) belongs to [0, 1]. An optimal solution of such an instance of the maximal RSC problem is equivalent to an optimal solution of the minimal CSC problem since:

Figure 6 .

 6 Figure 6. A counterexample for the reliability measure

Corollary 1 .

 1 If the ServiceData graph G = (X, U ) verifies hypothesis (a) and (b), then the maximal RSC problem becomes polynomial.

  2. Available at http://www.it-weise.de/documents/files/wsc05-09.zip.

		TS01	TS02	TS03	TS04	TS05
	|S|	572	4129	8138	8301	15211
	|D|	1330	9599	16263	16364	28337
	ESC /back. (ms)	3/5	11/6	11/6	25/5	30/6
	TSC /back. (ms)	2/5	9/5	15/5	26/6	24/7
			Table 2
	Sizes and computing times on WSC-09

APPENDIX ALGORITHM FOR SOLVING MAXIMAL TSC PROBLEM

The updated lines of Algorithm 1 are shown by ⊲.

Algorithm 2 Maximal TSC.

1: H ← ∅ 2: λ(i) ← 0 ∀i ∈ S ∪ D and p(i) ← -1 ∀i ∈ D ⊲ 3: nd(j) ← |in(j)| ∀j ∈ S 4: λ(s 0 ) ← +∞ and L ← {s 0 } ⊲ 5: for all i ∈ out(s 0 ) do 6: λ(i) ← +∞ and p(i) ← 0 ⊲ 7:

insert(λ(i), i, H) for all j ∈ S \ L such that i ∈ in(j) do 12: nd(j) ← nd(j) -1

13:

if nd(j) == 0 then 14:

L ← L ∪ {j} and λ(j) ← min

for all k ∈ out(j) \ L do


Nathalie HEINICH WHAT DOES « SOCIOLOGY OF CULTURE » MEAN ? NOTE ON A FEW TRANSCULTURAL MISUNDERSTANDINGS ___

Last year, I decided to change the presentation of my English CV, turning "sociologie de la culture" into "sociologie de l'art". The reason is that, obviously, the first term is misleading for some anglo-american scholars, who seem to give it another meaning.

These differences between the French and the anglo-american academic world are what I would like to address in this short note, according to what we use to call "sociology of art" or (but this "or" is already a problem, as we shall see) "sociology of culture".

Sociology of art(s) or sociology of culture?

When I have to decline my speciality as a researcher, I use to say: "I study sociology of art" (sociologie de l'art), or "sociology of arts" (sociologie des arts): the plural is more and more used in our French world, in order to assert a more democratic interest for the whole spectrum of artistic activities, not only for the traditionally more "legitimate" ones (visual arts, literature, music) 1 .

I may also say "I study sociology of culture", which means a more extended spectrum of objects, including mostly what we call "cultural practices": museums, concerts, opera, ballets attendance, reading books, and also watching TV or reading comics, if not (but this still remains very controversial) leisure activities such as watching football or having picnics 2 . Though slightly different according to their extension, "Sociologie de l'art" and "sociologie de la culture" are both studied in the sociology departments of our universities.

As far as I understand the rather mysterious world of my colleagues working in the UK or in the US, they may also use the terms "sociology of art" or "sociology of culture" in quite a similar way as we do in France; and the discipline is also grounded in the sociology departments of their universities. But behind this apparent similarity, a first problem arises.

Sociology of art or aesthetic sociology and/or cultural history?

The problem is that a big deal of what they mean by "sociology of art" refers to what we would rather call "cultural history" ("histoire culturelle"), "aesthetic sociology" ("esthétique sociologique") or "social history of art". All three focus on art works, and belong to humanities: they do not actually need the concepts of sociological discipline (e.g. "social stratification", "professionalisation", "interaction", "frame", "anomy", "rationalisation", "civilisation process", "configuration", "field"…), nor its methods (e.g. statistical surveys, representative samples, in-depth interviews, observations, corpus analysis, typologies…) 3 . Cultural history is a global description of the collective set of representations governing the relationship to art in a certain society (e.g. Burckhardt, Panofsky); aesthetic sociology is a more or less theoretical reflection on the way "art" reflects "society" (e.g. Adorno, Hauser, Francastel); social history of art is a more empirical inquiry into the actual contexts in which art works are produced and appreciated (e.g. Antal, Baxandall, Haskell). 1 The first noticeable occurrence of this use could be found in the title of the international conference organized in Marseilles : cf. Raymonde Moulin (éd.), Sociologie des Arts, Paris, La Documentation Française, 1986. 2 For a discussion and commented results of the surveys on « cultural practices », cf. Olivier Donnat, Les Français face à la culture. De l'exclusion à l'éclectisme, Paris, La Découverte, 1994. 3 I tried to define and present the traditions of "cultural history", "aesthetic sociology, "social history" and "survey sociology" in N. Heinich, La Sociologie de l'art, Paris, La Découverte, collection Repères, 2002. In our present French academic world, the term "sociology of art" would rather bring out other expectations: that is, empirical surveys on art reception (cultural practices, categories of aesthetic perception and taste, modes of valuation, private collecting…), on art production (economic, social and juridical status of creators, artists' careers and curricula, role of age, gender, training, social origins etc. in the relationship to creation, collective representations of creators and creation…), or on art mediation (circles of recognition, role of gate-keepers such as publishers, gallery-owners or curators, critics, agents…). These three directions have been dramatically developed in the last generation of French researchers, in the path opened up by Pierre Bourdieu4 and, after him, Raymonde Moulin5 .

Sociology of culture or cultural sociology and/or cultural studies?

Although "sociologie de l'art" and "sociologie de la culture" differ but slightly in our French sociological world, I use to avoid the latter term in front of anglo-american colleagues, because I happened to realise that, when using the word "culture", one risks to be understood as a specialist either of "cultural sociology" or, more likely, of "cultural studies". Both are misleadingthe latter much more than the former.

As I understood through the interesting presentation offered by Janet Wolff in Inglis and Hughson's The Sociology of Art6 , the anglo-american "cultural sociology" is mostly taught in the departments of sociology and anthropology ; it has to do with education, law, habits etc.that is, the anglo-american meaning of "culture", which is not spontaneously associated to "arts" as it is in France. This does not mean that such issues are not present in our academic courses; but they rather appear as "histoire culturelle", at the crossroads of history, sociology and anthropology. It has been a leading trend in the last generation of French historians since the famous "École des Annales", owing to such authors as Alain Corbin, Antoine De Baecque, Arlette Farge, Pascal Ory, Jean-Pierre Rioux, Daniel Roche, Jean-François Sirinelli… But it is clearly grounded in history departments.

Actually, the higher risk would not to misunderstand "sociology of culture" as "cultural sociology" in present time anglo-american world: it would be to understand it as "cultural studies", given the dramatic increase of influence that such a trend obtained in the last generation. But, believe it or not: "cultural studies" does not exist in France -at least, not yet ("Thanks god!", I would add).

Three anecdotes

Here is an anecdote. Last time I was in the US (too long ago: about ten years), as well as last time I was in England (two weeks ago) I visited a few bookstores, as we all usually do abroad. There I desperately searched the shelve "sociology". As I could not find it, I asked the salesmen. "You mean cultural studies?", they said.

Here is another anecdote. A few months ago, I attended a conference organised by the sociology department in a French regional university. When driving me back to the station at the end of the day, the organiser told me that two new members of the department had proposed a teaching course entitled "études culturelles". It had been accepted without problem, since everybody in the department thought it would consist in the study of "cultural practices" (see above). They eventually realized (too late!) that "études culturelles" was the translation of "cultural studies" (gender studies, queer studies, post-colonial studies etc). They are now trying to dyke the wave… Here is a third anecdote. In 1999, when the Boekman Foundation in Amsterdam offered me its three years chair of sociology of art at the university, the staff wanted to know my teaching program. After hearing my presentation, they gently asked: "And don't you plan to teach French theory?" As politely -I hopeas I could, I immediately answered: "But I teach sociology, not philosophy!" And it was OK. But who was the most astonished: me, by their question; or them, by my astonishment at their question?

"French theory" as an American export commodity

As far as I know, in American campuses, "cultural studies" rather belong to the literature departments, together with what we, French people, call "philosophy" (but we use to restrict it to recent continental philosophy -Foucault, Derrida, Deleuze etc. -, merely including analytical philosophy). Our own literature departments teach history of literature, and sometimes (marginally) "sociologie de la littérature", which is mostly an application of Bourdieu's field theory.

The items covered by the term "cultural studies" seem to be finding a place in French campuses, but dispatched under a variety of issues, in sociology, anthropology, history, political science, philosophy, literature. They are closely akin to what some of us call Bourdieu's "critical sociology" ("sociologie critique"), since they share the same will to demonstrate that everything is "socially constructed", and that the sociologist's task is mainly to dismiss the actors' "illusions", their belief that the world as it goes is natural, universal and unchangeable. However it is difficult to assimilate "sociologie critique" and "cultural studies": not only because Bourdieu's fans use none of these two terms, but also because Bourdieu himself never considered himself a "cultural studies" or a "postmodern" scholar (he even strongly refused such a categorization) -no more than a philosopher, as he was very eager to demonstrate the superiority of sociology onto philosophy7 .

(By the way: "post-modernism" used to be a fashionable trend in french philosophy one generation ago, after Lyotard ; today, it seems quite outdated. If it may still be used in art theory, it is almost absent in the human and social sciences. When one hears "postmodernism" in France, one immediately thinks: "American", as for "MacDo" and "Cocacola")

French scholars are always astonished when hearing that Bourdieu is included in the so-called "French theory". First, such a thing as "French theory" does not exist in France : we know the structuralist trend of the 1960's, with the anthropologist Lévi-Strauss, the psychoanalyst Lacan, the philosopher Foucault ; we know Derrida's "deconstruction" and Deleuze's philosophy ; we know Bourdieu's "sociologie de la domination" or "sociologie des champs" -but nothing like "French theory", in spite of some recent efforts to import it from the US8 .

Second, the authors included in this category are either dead or very old (Lévi-Strauss is quietly going on his 100 years): their major works appeared in the 1960's, that is, more than forty years ago. For the presently working researchers, this is the past: so many new things and innovative authors appeared in our disciplines since the last thirty years! Should we ignore these new and exciting roads, in order to confine ourselves to authors that we used to read so long ago, when we were students? No: our debates are not there anymore.

Anglo-american vs French debates

Let me ask a last question: what are our present debates in both "cultures", concerning the sociology of art(s) and/or culture?

Seen from France, the main debate on the anglo-american scene appears to be that between post-modernism and positivist science (it was dramatically illustrated by the so called "Sokal case" -"affaire Sokal" in French). It partly pertains to the opposition between "theory" on one side, and empirical or fact-finding surveys on the other.

In France, the latter issue is rather addressed as an opposition between "humanities" and "social sciences"; in sociology, between qualitative and quantitative methods, and even sometimes between comprehensive and explicative sociology (very roughly said).

Another quite vivid opposition among French sociologists is that between those who practice and foster a politically involved social science (after Bourdieu), and those who plead in favour of Max Weber's "axiological neutrality", that is, the avoidance of any normative assessment, in order to limit the scientific discourse to a strictly descriptive and analytical level9 . The issue is all the more relevant that the model of the "intellectuel engagé" (the politically committed scholar) is very strong in our modern academic culture. Useless to say, "cultural studies" and "postmodernism" are, in the eyes of their opponents, but one of the most common ways to foster value-laden discourse, to confuse research with ideology, and to load social sciences with political or "critical" issues by repeatedly aiming at "deconstructing" and thus dismissing traditional hierarchies and categories (but only on campuses, which might somehow limit the efficiency of the program). This is why I disagree with Janet Wolff when she calls for "a growing dialogue between sociology and cultural studies"10 : as a fervent supporter of the "scientific", "neutral", unpolitical, empirically grounded (as well as qualitative and comprehensive) conception of sociological research, I do hope that "cultural studies", "post-modernism" and "French theory" will mostly remain an anglo-american speciality.

Our French sociology of art also includes two other still ongoing and rather acute debates. The first one has something to do with the said opposition between humanities and the social sciences: it opposes, on one side, the sociology of art works (mostly consisting in learned commentaries) and, on the other, the sociology of artistic producers, consumers, mediators (based on empirical surveys, be it through quantitative or qualitative methods) 11 . For the supporters of the former conception, the supreme goal of sociology should be to enlighten the social stakes of art works, whatever they are: a position which, in the eyes of their opponents (to which I belong), is but an old, pre-sociological way of thinking, which desperately tries to re-assemble "art" and "sociology" after having treated them as if they were two different entities, reproduces the academic privilege traditionally granted to art works, claims the hegemony of sociology over art history, and remains entangled in unending debates on whether one should focus on their "internal" or "external" determinants. In my eyes, the methodological and conceptual resources of sociology as a scientific discipline are much more appropriate to the study of activities, representations and values related to arts than to the works themselves, for which art historians and cultural historians provide quite interesting insights. The discussion is still on… Our last debate in the sociology of art pertains to the opposition between "legitimate culture" and "popular culture": should the sociologist focus on "major" arts, because they are considered as such by the actors, and thus more important in our societies? Or should he/she try to dismiss this hierarchy by privileging "minor" arts in his/her research agenda? Although Bourdieu himself seems to have been somewhat ambivalent, he was strongly accused to foster the first option by some of his previous collaborators, who referred to the "Birmingham school" (in particular to Richard Hoggarth's Uses of Literacy) in order to sustain their critics12 . There also, the debate is not closed yet.

Translation problems: the handicap of dominants

As for the present state of the sociology of art, there appears to be a certain dissymmetry between our two cultures: we, French people, seem to know a little more about you, anglo-american scholars, than you know about us (even if we may mistake or misunderstand a lot of things, as some readers of the present article might have probably deplored…). How could it be different, since we are forced to read and write in English (as I am just trying to do now -please forgive me -so clumsily) whereas you can rely on your native English without having to practice our language?

But the problem is not so much a matter of dissymmetry than a matter of temporal discrepancy, due to the delay in translations. Lets us take a well-known example: nowadays, no anglo-american bibliography in our disciplines (be it sociology of art, sociology of culture, cultural sociology, cultural studies…) ignores the name of Pierre Bourdieu. But he is quoted and discussed as if he were a today author, embodying the avant-garde of French production, whereas his major contributions to the field occurred between thirty and forty years ago. Among all the publications coming out of the younger generation, be it his/her followers or his/her challengers, very few have been translated yet in English. By the way, Bourdieu himself was translated in English long after many other languages: except one small book at the beginning of the 1960's, his major english translations started during the 1980's and exploded in the 1990's, that is, one generation after he began to publish; and most of his books and articles were translated in German, Spanish, Italian etc., long before English.

This last remark provides an interesting but somehow ironic contribution to the sociology of domination: to be a dominant may become a handicap in that it avoids the effort to go and see what happens among the dominated. Reshaped according to the temporal dimension, such a property may generate what is considered a major shortage in our intellectual world: that is, delay.

Nathalie HEINICH Centre National de la Recherche Scientifique (Paris) heinich@ehess.fr

See P. Bourdieu (éd.), Un art moyen. Essai sur les usages sociauxde la photographie, Paris, Minuit, 1965 ; P. Bourdieu, Alain Darbel, L'amour de l'art. Les musées d'art européens et leur public, Paris, Minuit, 1966, 1969 ; P. Bourdieu, « Eléments d'une théorie sociologique de la perception artistique », Revue internationale des sciences sociales, XX, 4, 1968 ; P. Bourdieu, « Disposition esthétique et compétence artistique », Les Temps modernes, n 295, 1971 ; P. Bourdieu, Le Marché des biens symboliques, L'Année sociologique, vol. 22, 1973 ; P. Bourdieu, « Les fractions de la classe dominante et les modes d'appropriation de l'oeuvre d'art », Information sur les sciences sociales, 13 (3), 1974 ; P. Bourdieu, « L'invention de la vie d'artiste », Actes de la recherche en sciences sociales, 2, mars 1975 ; P. Bourdieu, La Distinction. Critique sociale du jugement, Paris, Minuit, 1979 ; P. Bourdieu, Les Règles de l'art. Genèse et structure du champ littéraire, Paris, Seuil, 1992.

See R. Moulin, Le Marché de la peinture en France, Paris, Minuit, 1967 ; R. Moulin (éd.), Les Artistes. Essai de morphologie sociale, Paris, La Documentation française, 1965 ; R. Moulin, L'Artiste, l'institution et le marché, Paris,Flammarion, 1992.

J. Wolff, "Cultural Studies and the Sociology of Culture", in D. Inglis, J. Hughson (eds), The Sociology of Art. Ways of Seeing, Palgrave Macmillan, 2005.

See N. Heinich, Pourquoi Bourdieu, Paris, Gallimard, 2007.

See François Cusset, French Theory. Foucault, Derrida, Deleuze & Cie et les mutations de la vie intellectuelle aux Etats-Unis, Paris, La Découverte, 2003.

See N. Heinich, Ce que l'art fait à la sociologie, Paris,Minuit, 1998.

J. Wolff, "Cultural Studies and the Sociology of Culture", art. cit. p. 96.

The debate appeared in R. Moulin (éd.), Sociologie des Arts, op. cit., and was re-opened in the special issue of the journal Sociologie de l'art, "Sociologie des oeuvres", n° 10, 1997.

See Claude Grignon, Jean-Claude Passeron, Le Savant et le populaire, Paris,Gallimard-Le Seuil, 1989.