Philippe Woloszyn
email: philippe.woloszyn@univ-rennes2.fr

Guillaume Faburel
email: guillaume.faburel@univ-lyon2.fr

THE FARM OF THE MILLERS' PARK: LOCAL EXPERIMENTATION OF AND FOR A SUSTAINABLE URBAN PLANNING

Keywords: Resilience, viability, community construction, participatory initiative, sustainable planning

System viability approach is analysing how a system reacts, resists, changes and evolves in order to enable its own survival with facing a variety of environmental challenges. Moreover, viability constitutes a way to identify sustainable politics and actions through defining operational constraints, in terms of vulnerability and resilience. This last describes individual and social systems property to face a catastrophic change by resisting, adapting or transforming (Walker & al.

Nevertheless, systems approaches have been criticised for their inability to identify "bottom--up" processes, mainly refeering to participatory engagement within territorial challenges; This obviouly leads to the following question: is system viability an easy framework to be applied by local communities ? As explaining and identifying distinct environmental conditions and community responses to the sustainability challenge constitutes a complex activity for both scientific researcher and community participants, could viability indicators easily beeing understood by non--academic people ? Therefore, what type of methodological tools should enable participants to collect information to ensure a communitary viable territorial construction ?

To provide answers to those questions, we'll present a participatory experimentation situated at Villeneuve le Roi, a 3--hectare pluriactive farm not far from Orly airport, Paris, France [START_REF] Vialan | L'habiter environnemental comme communauté politique : l'expérience de la Ferme du Parc des Meuniers[END_REF]. This dynamical--insertion site tries to status this local environment as a communautary project, implying farming and gardening know--how transmission, environmental acknowledgment and cooking--baking practice. With knowing the importance of food as part of our culture and survival, this last game of the "viable meal" should develop a way of working on fundamental environmental resources such as nutrition, well--being and health. Thus, this participatory initiative can be readed through the three main viability dimensions: resisting -with keeping traditions both in terms of cultural practices and environment protecting, adapting -which means here facing a highly different environment, namely in key areas such as food habits or farming techniques, and transforming - by introducing new consumation modes through cooking their own farmed meals and baking their own bread. This pragmatic initiative also enable Meunier Park inhabitants to rebuilt their identity, that means to process individual resilience through collective participation to farm's life. In that way, transmission of knowledge, but also communautary programmes and collective projects constitute the real sustainable added values for community territory, leading to a new conception of democracy and citizenship.

Introduction: a farming cooperative empowerment experience

As the territorial intelligence traduces the way of governing the local which the analytical and prescriptive concept of territorial questions, sustainability goals should be achieved through effective economic, social and ecological aims as a route to socio-ecological transition. However, transition can't be drived without a dialectical answer to the tensions between local monitoring and global gouvernance, with involving territorial cooperation action. To ensure the conditions of emergence of the sustainability, the following example of collaborative farming in France constitutes one sustainable answer to inductive eco-social convergence with the implementation of collective actions.

Located in the city of Villeneuve-le-Roi (France), not far from Orly Airport, the Farm of the Miller's Park is a field of 3ha that has been transformed into a multi-active Farm by committed inhabitants since 15 years. Apart from a few buildings, this place comprises cultivated lands, pleasure gardens, and places for animals. There are roughly 650 members at the Farm, and some of them (60-100) have appropriated the place insomuch that they feel and show solidarity with the employees of the Farm. They suggest new projects, constructions or activities, and consider the Farm as another home, with coming there to share coffee and chat. Therefore, the farm is considered as a « place-resource », for and from the inhabitants (figure 1).

-56 - As the amateur, in the first and noble sense of the word, is the main word of the farming collectivity, every one is in a double position of teacher and student, and has knowledge to share without disqualification: thus, the experience of the Farm allows each and every one to build and assert its identity, to gain recognition inside a group, and to shared ecological so as social values as a knowledge to be cultivated and transmitted [START_REF] Faburel | L'habitant dans l'évaluation de l'environnement et de ses territoires. Sens ou indécence du développement durable ?[END_REF]. Therefore, the proposed social responsiveness empowerment of Meunier Farm experiment is enabled through social, cultural, and ecological converging capitals reciprocal reinforcement with socio-economical converging benefits.

Converging inhabitants benefits : socio/eco/enviromental capitals increasing

Instead examining how the relevant combinations of social ties and resources are assembled to meet a given economic balance, social capital theory considers less distinction between exchange that is otherwise deemed « economic » or « social ». A fruitful perspective for developing a more coherent conceptual framework for incorporating social capital into economic development theory and policy is to extend the insights to environmental challenges. This exactly constitutes the project proposed by Meunier Farm experiment, in terms of sustainable eco/socio/environmental shared capitals development, as seen figure 2: A first benefit of Meunier Farm experiment is social-cultural capital increasing, proceeded by interdividual new forms of relationships through collaborative work and daily life sharing. In this multi-active Farm experiment, inhabitants empowerment is provided, should we say induced, by employees of the Farm: they help them to pursue their projects, with no link of expertise. So, daily activities, as diverse as they are, all have in common to increase the inhabitants' self-sufficiency in their environment, to expand their means and power of action, from the exchange of know-how. Thus, this experience constitutes a powertrade for cooperative action, through policies participation or collaborative intelligence (Bourdieu & al, 1992, Coleman, 90). at a farming production unit scale. « social capital refers to features of social organization, such as trust, norms, and networks, that can improve the efficiency of society by facilitating coordinated actions » [START_REF] Putnam | Making Democracy Work[END_REF]. This rural empowerment experiment modifies the sociocultural identification of the inhabitants that has been affected by previous "social default", so that farming experiment increase their social capital by work and life transactions. By exchanging facilities, inhabitants of the farm aims to recover their social capital, with developping citizenship responsibility, and collective management capacities in land coworking [START_REF] Fukuyama | Trust: the social virtues and the creation of prosperity[END_REF].

Second benefit of this collaborative experience is ecological (organic) capital increasing, through transformation of natural resources, implying a new way of cooperative and sustainable farming and food production, thus coping with a more dynamic conception of the environment. As this farm activity formalizes a sustainable transformation of natural resources to amenity productions, a talking example can be found in cooking classes where inhabitants can learn how to cook bread. That emphasis put on bread (if it is a coincidence) is not insignificant: to learn how to cook bread is to re-claim ownership over food, through what can be considered as a basic element of everyday diet. In an even more obvious way, gardening is widely spread in the Farm and is linked to reclaiming ownership over food supply. As bread vehicles symbol of food independance, this particular acknowledgement benefit traduces an increase of ecological capital, considered here as relationship between individual life, work environment and a way to transform natural resources into sustainable food. With conveying many kinds of environmental knowledge: how to marry this plant with that one or with that flower, to know the rhythm of seasons and observe the weather, what are the good timings to plant… farm inhabitants transform their environmental perception through acting in a very practical goal (feeding), through each and every one's actions. Those action strategies lead them to follow responsible pro-environmental behavior, to endorse individual sense of responsibility, and to get proenvironmental attitudes (Hines, Hungerford and Tomera 1986).

By converting "inputs", "stocks" from labour and production [START_REF] Bourdieu | Reproduction in Education[END_REF], into "outputs", flows of services, produced goods and services contribute to the farm micro-societal amenities. Thus, wellbeing attributes of those produced amenities can be understood in both ecological and social dimensions: if farm co-working intends to produce feeding and essential needs supply as an economic benefit, the essential benefits are both social, with cooperative relationships creation in land co-working and ecological, through conceiving another type of relationship to nature.

Stocks to flows: inductive capitals fruting

To describe this co-evolution process, Territorial Intelligence (TI) networking E(Economic)-S(Social)-O(Organic) vulnerability model is therefore articulated between the three passive components of energetical systems, as potential energy, kinetic energy, and energy dissipation [START_REF] Woloszyn | Territorial intelligence of vulnerability systems 2-Sustainable Modelling of Globalization Challenge[END_REF]. E.S.O. model therefore proposes an analogy that identifies the "stock" as the capacitive property of the system to maintain or develop its capital, the "flow" as the conductance processes of capital (re-)production, and the "benefit" (or loss) of the system driving as the inductance effect of stock to flow capital recovering (figure 3). Moreover, by converting capital stocks into service flows in the 3 dimensions of sustainable development, stocks are understood as constitutive of the "capacitance" property of the system, as "flows" constitute its conductance, leading to capital stocks growing or declining. This system evolution describes the "inductive" effect of the (stock/flow) conversion process during the time of the experiment [START_REF] Woloszyn | Territorial intelligence of vulnerability systems -A transitional viewpoint of sustainable development[END_REF].

During the "flows" motions, inductance supplies to both capacitance and conductance, with taking into account the systems transformation potential through their temporal activities (figure 4). As a complex combination between environmental and social life values, principal output that the farm inhabitants may benefit to upgrade their wellbeing is nature -society reconnection, far from any abstract conception, or any power exerted over nature, thus reciprocally extending their ecological and social capitals, as seen figure 5:

Capacitation as inductive socio-ecological capacitance increasing

As shown within this model, Meunier Farm inhabitants find there together the resources ("stocks") they need to pursue their wishes and projects ("flows"), as well as [START_REF] Hicks | The foundations of welfare economics[END_REF] conception of community wellbeing stated that maintenance of the wellbeing of a community is a function of income flow maintenance, the conductance process, from a done stock of capital, the community capacitance (figure 6). When a community's capital stocks is growing, its capacity to generate flows of goods and services will also grow, thus enabling the community's ability to improve its wellbeing in the future, or consolidate its resilience capability, as seen figure 7:

Conclusion: farming as a way of resilience

With increasing social capacitance of the inhabitants, experienced collaborative farming facilitate the access to the main "social body", civil society, with developping new ecological and economical meanings of social life. Growing individual stocks of socio-ecological capitals provided by this collaborative farming experiment may act as a buffer against forces that will occur when inhabitants will be reinserted into the "savage sociality" of common socialized environments. Thus, it contributes to the renewal of the "resilience potential, passing from resistance ("Input" social capital) to adaptation (social to eco-social capital circulation) and transformation (inductive effect of stock to flow conversion).

Stock to flow economical/ societal/environmental transformation during production/ consuption/ exchange processes are here once again observed, leading to an inductive process of people's "capacitation", through actor's socio-ecological capacitance enhancement, thus, resilience potential optimization. Therefore, "resilience capacities" socio-ecological enhancement, due to inductive effect of the social/environment capitals circulation between Meunier farmers, results not only from a social with ecological capital mixing, but essentially from capability emergence as eco/socio/environmental capacitance growing, for a more fare sustainable development process.

  centimètre-carré ne reste vide. Les limites de la feuille sont les limites de la Ferme, comme si le monde entier se trouvait dans la ferme et dans cette carte. Sur le même niveau, on trouve « arbre », « haie », « prairie », mais aussi « bâtiment accueil », « coin pour fumeurs », « bassin Léon » (le bassin a été conçu par un habitant appelé Léon), tout se trouve mêlé, entremêlé, accordé, et lié. Lié par le dessin qui fait du territoire de la ferme un magma compact où tout est lié : le labyrinthe est collé au potager, qui est collé à l'éolienne. Pas d'espace de pause, tout est assemblé.

Figure 2 -

 2 Figure 2 -Carte mentale réalisée par Monsieur C.

Fig. 1 :

 1 Fig.1: Mr. C's Mind Map of Meunier Farm environment

Fig 2 :

 2 Fig 2: Articulation and convergences between sustainable development capitals

Fig 3 :

 3 Fig 3: Combinated capitals between environmental and social life values: generalized social energy between capacitance, conductance and inductance

Fig 4 :

 4 Fig 4: Open-analogical model of sustainability This paradigmatic change of the process leads us to consider a thermodynamic approach of open-living systems, instead of mechanical-closed systems: stability key of those lasts closed systems, retro-action, is here considered as the open-systems evolution source[START_REF] Dumas | Modèle participatif d'évaluation de la résilience[END_REF].

Fig 5 :

 5 Fig 5: Social capital benefits from Miller's Farm experimentAs a consequence, association of potential, dissipative and kinetic energy concepts with the three pillars of sustainable development leads us to define the three dynamical notions of a general theory of social-eco-environmental entropy, also called "generalized social energy", thus developping people's "capacitation" attributes by social capital increasing.

Fig 6 :

 6 Fig 6: Inductive process of capacitance increasing: socio-ecological capital benefits of farming experiment

Fig 7 :

 7 Fig 7: Resilience consodilation by Meunier Farm socio-ecological action process

Cr CNRS, ESO UMR 6590 CNRS/Université Rennes2, Laboratoire Espaces et Sociétés Rennes, Université de Haute Bretagne, Maison de la Recherche en Sciences Sociales, 35043 Rennes, France

Pr, Université Lumière Lyon 2, UMR Triangle, CNRS/Ecole Normale Supérieure, coordinateur Bureau de recherches Aménités : Aménagement, Environnement, Territoires


P.-C Héam

O Kouchnarenko

J Voinot

J Voinot Thèmes

Towards Formalizing QoS of Web Services with Weighted Automata

Keywords: images, données, connaissances Projets CASSIS Web Services, Verification, Composition, Quality of Service Services Web, vérification, composition, qualité de service

Web services (WSs) are used more and more as components of distributed applications with a goal to resolve complex tasks that simple services cannot. This use of WSs is connected to the emergence of languages like WS-BPEL which allows describing the external behaviour of WSs on top of the service interfaces. The use of WSs as components of distributed applications implies the possibility to change a failing service for another which can do at least the same things as the replaced service. The composition issues are also of particular interest to WSs users. Different solutions have been proposed during the last years to check such properties, but, to our knowledge, none of them takes QoS aspects into account. This paper introduces underpinnings and a tool for verifying WSs substitutivity and well-formed composition while considering WSs costs such as the execution time of the different operations provided by WSs.

Introduction

This paper is dedicated to the verification of substitutivity and well-formed composition of Web services while considering a new factor -Quality of Service (QoS).

Web services are increasingly used as components of distributed applications with an aim to resolve complex tasks that simple services cannot. This use of WSs is connected to the emergence of language like WS-BPEL (Web Services Business Process Execution Language, previously known as BPEL4WS, BPEL for short) which allows describing the external behaviour of WSs on top of the service interfaces defined in their WSDL (Web Services Description Language) specifications. With the success of WSs compositions, a new factor -Quality of Service (QoS) -quickly appeared in their definitions [Tia05, D'A06]. However, current Web service standards do not provide mechanisms for specifying services with QoS requirements, such as execution time or financial cost.

To make up for this lack, the starting point of our work and the first contribution of this paper is BPEL and WSDL language extensions including several service cost notions. In [START_REF] Héam | How to Handle QoS Aspects in Web Services Substitutivity Verification[END_REF], we have proposed to extend BPEL with a notion of service costs. In this paper we go further and consider both BPEL and WSDL specifications for being closer to the WSs reality. The main purpose of these extensions is to be able to simply specify QoS aspects of WSs. Moreover, in this paper more verification problems, e. g. strong substitutivity, well-formed composition, etc., are studied for different models, and new decision results are presented, as detailed below.

Following the use of WSs as components, various research orientations have appeared. Of particular interest to us within the framework of this paper are those relating to the checking of properties starting from BPEL and/or WSDL processes, and more especially WSs substitutivity and composition. This research is motivated by the fact that the use of WSs as components of distributed applications requires the possibility for the user to change (possibly dynamically) a failing service for another, which at least performs the same tasks as the replaced service. Different solutions have been proposed during the last years to check such properties. Some of them consist of the translation of BPEL into different classes of automata, like guarded automata in [START_REF] Fu | Analys of Interacting BPEL Web Services[END_REF], or finite state machines in [BCD + 05] and [START_REF] Foster | A Rigourous Approach to Engineering Web Service Compositions[END_REF]. But, to our knowledge, none of them introduces a model that allows taking service costs of WSs into account. In this direction, the second contribution of the paper is a formal model, called WSs weighted automata (WSWA for short), and a theory underpinning the proposed languages extensions.

Weighted automata -an extension of max-plus automata -is a formalism widely used in computer science for applications in images compression [START_REF] Culik | Generalized weighted finite automata based image compression[END_REF][START_REF] Katritzke | Enhancements of partitioning techniques for image compression using weighted finite automata[END_REF], speech-to-text proceeding [START_REF] Mohri | Weighted automata in text and speech processing[END_REF][START_REF] Buchsbaum | An approximate determinization algorithm for weighted finite-state automata[END_REF] or discrete event systems [START_REF] Gaubert | Performance Evaluation of (max,+) Automata[END_REF]. These large application areas make them intensively studied from the theoretical point of view [START_REF] Krob | The Equality Problem for Rational Series with Multiplicities in the Tropical Semiring is Undecidable[END_REF][START_REF] Weber | Finite-valued Distance Automata[END_REF][START_REF] Hashiguchi | Decidability of the Equivalence Problem for Finitely Ambiguous Finance Automata[END_REF][START_REF] Klimann | Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton[END_REF]. See [START_REF] Berstel | Rational Series and Their Languages[END_REF] for more detail.

With the increasing importance of QoS in the design of WSs compositions, it is of great interest for users and providers of WSs to be able to say that a WS does the same things as another (possibly failing) service, with comparable/higher quality. This is why this paper gives formal definitions of substitutivity and (strong) well-formed composition problems

λ ∈ Q k WS1 descr. file WS2 descr. file Translation A 1 A 2 Verification A ⊗ ≤
WS1 and WS2 comparable? The third contribution of the paper is the verifications proceeding on WSWA thanks to an automatic tool we have been developing. This tool whose structure is given by Fig. 1 allows us to automate the translation from extended BPEL/WSDL specifications to WSWA and to automatically check WSs substitutivity and composition. The remainder of the paper is organised as follows. Section 2 defines WSWA and substitutivity/composition notions based on them. It introduces extensions of BPEL and WSDL, and explains how these extensions can be translated into WSWA. The verification issues on WSs substitutivity and composition are presented in Section 3, and the operation of the tool support is described in Section 4. Finally, Section 5 gives conclusions and future works.

Modelling Web Services and QoS aspects

In this paper WSs and composed WSs are modelled by weighted automata. Section 2.1 introduces the formalism of finite weighted automata and of Web services executions. Section 2.2 explains how to model the substitutivity and the composition properties in this theoretical framework. Finally, Section 2.3 presents BPEL/WSDL extensions to model QoS aspects of WSs, and the computation of weighted automata from extended specifications.

Modelling Web Services with Finite Weighted Automata

In this paper, Σ denotes a finite set of actions and k is a fixed positive integer. We first introduce the notion of weighted automata.

Definition 1 A finite weighted automata A is a quintuplet A = (Q, Σ, E, I, F ) where Q is the finite set of states, E ⊆ Q × Σ × Z k × Q is the set of transitions, I ⊆ Q is the set of initial states and F ⊆ Q is the set of final states.
Notice that there is a restriction on E: for every action a, every pair of states p, q there exists in E at most one transition of the form (p, a, c, q). For every pair of elements Definition 2 A partial execution of a finite weighted automaton A is a sequence π = (p 0 , a 0 , c 0 , q 0 ), (p 1 , a 1 , c 1 , q 1 ), . . . , (p n , a n , c n , q n ) of transitions of A such that for every 0 ≤ i < n, q i = p i+1 . If we add the conditions: p 0 is an initial state, q n is a final state, then we call π an execution. The label of the (partial) execution π is the word a 0 a 1 . . . a n and the cost of the (partial) execution π is the sum of the c i 's:

INRIA c = [c 1 , . . . , c k ], d = [d 1 , . . . , d k ] of Q k and
cost A (π) = n i=0 c i .
The cost of a word u which is the label of at least one execution of A is the maximum of all costs of executions of label u:

cost A (u) = max π is labelled by u cost(π).
Notice that since u is finite, there are finitely many path executions labelled by u. The cost of u presented above is so well defined. Classically we denote by L(A) the set of labels of executions of A. We say that two partial executions π 1 and π 2 of two weighted automata A 1 and A 2 are equivalent, denoted π 1 ∼ π 2 , if they have the same label. This relation is trivially an equivalence relation on partial executions inducing an order relation on weighted automata: we say that A 1 A 2 if for every execution π of A 1 there exists an equivalent execution

π 2 of A 2 . Notice that A 1 A 2 if and only if L(A 1 ) ⊆ L(A 2 ).
For the rest of the paper, if there is no special mention, all considered automata are finite weighted automata.

Modelling Substitutivity and Composition Managing QoS Aspects

A problem occurring while managing WSs is to replace a failed service by another. Formally, for two Web services given by their weighted automata A 1 and A 2 the question is to decide whether A 2 can have the same behaviour than A 1 with a similar quality. In this case we say that A 2 can substitute A 1 .

Definition 3 Let λ be a positive element of Q k , and A 1 and A 2 be two weighted automata. We say that A 1 is substitutable by A 2 if for every execution π 1 of A 1 there exists an execution π 2 of A 2 such that π 1 ∼ π 2 and cost A2 (π 2 ) ≤ λcost A1 (π 1 ). We say that A 1 is strongly substitutable by A 2 if for every execution π 1 of A 1 there exists an execution π 2 of A 2 such that e 1 ∼ e 2 and for all execution

π 2 of A 2 such that π 1 ∼ π 2 , cost A2 (π 2 ) ≤ λcost A1 (π 1 ).
The notion of substitutivity means that a service S 1 can be subsituated by a service S 2 if S 2 has a way to act as S 1 with a higher quality. The notion of strong substitutivity means that a service S 1 can be substituted by a service S 2 if S 2 has a way to act as S 1 and whatever the way chosen by S 2 to act as S 1 , its quality is higher.

The composition issue is also a central problem in the framework of Web services: considering a list of Web services, the problem is to decide whether they can be associated together Definition 4 Let λ be a positive element of Q k and A 1 and A 2 be two automata (A 2 represents a composition of Web services). We say that A 2 is (strongly) well-formed with respect to

A 1 if A 1 is (strongly) substitutable by A 2 .
Notice that in the definitions we choose that cost(π 2 ) ≤ λcost(π 1 ) modelling that the lower is the cost the better is the service, what is intuitive for connection time or financial cost. One can give a dual definition if the lower is the cost the worse is the service by changing cost(π 2 ) ≤ λcost(π 1 ) in cost(π 2 ) ≥ λcost(π 1 ). All notions, algorithms, etc. described in this paper may be trivially adapted to this dual definition. In order to not overload the reader, we do not consider that case.

From WSDL and BPEL to Finite Weighted Automata

Unfortunately current Web service standards do not provide mechanisms for specifying WSs with QoS requirements, such as execution time or financial cost. In [START_REF] Héam | How to Handle QoS Aspects in Web Services Substitutivity Verification[END_REF], we have proposed to extend BPEL with a notion of service costs. In this paper we go further and extend both BPEL and WSDL specifications. BPEL files are produced by WSs users while WSDL files are given WSs providers. Adding service costs in WSDL enables joining a WSs audit framework, and makes it possible to set dynamically service costs, and to produce new extended WSDL files from composed WSs to be able to provide those like new WSs.

In this section, QoS aspects are first introduced in WSs specifications, and second the new extended descriptions are translated into WSs weighted automata by extracting behaviours/costs from extended BPEL specifications and extended WSDL interface files.

Introducing QoS Aspects in Web Services Description

Our proposal consists in defining a description element called costs. As shown in Fig. 2, each costs element may contain several elements which represent the different QoS aspects to be taken into account. The types of the service costs that can be specified, for the moment, are:

INRIA executionTime, the minimal, maximal and average execution time of an operation expressed in number of time units (seconds, milliseconds, ...).

financialCost, the financial cost of the execution of an operation expressed in number of monetary units (USD, EUR, JPY, ...). This list can be easily extended by other valuable operation costs. In comparison with [START_REF] Héam | How to Handle QoS Aspects in Web Services Substitutivity Verification[END_REF], the QoS requirements we propose to consider here are more advanced. Indeed, the executionTime element allows considering time intervals in addition to the average execution time of an operation; the costs element can be added in BPEL (extension of invoke, receive and reply BPEL activities and of onMessage BPEL activity element) and in WSDL (extension of operation WSDL element). This last point directly concerns the applicability of our approach in a Web services audit framework. Indeed, BPEL files being produced by Web services users, they can be modified by those. However, for confidence reasons, WSDL files should be modified by an audit entity rather than Web services providers which produce them. These considerations are not in the scope of this paper.

To compute a WSWA representing a Web service from its specification, the translation has to do:

The extraction of the Web service behaviours to define the automaton transitions thanks to the basic activities (invoke, receive, ...), and the sequences of the automaton transitions thanks to the structured activities (sequence, while, ...) used in the corresponding BPEL description.

The extraction of the costs of each Web service operation to define the cost of each automaton transition from the costs element corresponding to the transition operation.

Though separated, these two parts are closely related since there are two possibilities to deal with costs in WSs specifications. In the case when the costs are only given in the WSDL files related to the considered BPEL file, for each transition its cost is defined from the operation costs element of the corresponding WSDL files. Otherwise, i.e. when the costs are given in WSDL and/or BPEL descriptions files (see Fig. 3), we give top priority to the values in the BPEL description because it is defined by the Web service user.

While extracting the Web service behaviours, the two cases above have no impact on the result of the translation. Because of lack of space, we only give the translation rules for invoke BPEL activities. Others translations are similar (see http://lifc.univfcomte.fr/∼heampc/wiselong.pdf for more detail).

The invocation of a Web service operation can be synchronous or asynchronous. Consequently, there are two different rules for the translation of an invoke activity into weighted automata. In an extended BPEL specification, an asynchronous invoke activity is of the following form: In the corresponding WSDL description file, the called operation is as follows.

<portType name="pT"> <operation name="op1"> <input message="msgType1" /> <output message="msgType2" /> <costs> <executionTime min="0.3" max="1.2" average="0.9" unit="milliseconds" /> <financialCost value="30" unit="EUR" /> </costs> </operation> ... </portType> >From the forms above the following piece of WSWA is generated where c is a vector of the cost element values from WSDL or BPEL files.

q i q j op1:pt:A/c
For the example above, the vector c contains the values from the WSDL description for the execution times of the operation, and from the BPEL specification for the financial cost. A synchronous invoke activity is of the following form: <invoke partnerLink="A" portType="pt" operation="op2" inputVariable="x" outputVariable="y"> <costs> <executionTime min="0.3" max="0.8" average="0.5" unit="milliseconds" /> <financialCost value="20" unit="EUR" /> </costs> </invoke> Notice that this operation is linked to the same WSDL description file as the one above. From this activity definition we generate the following piece of weighted automata where c is the vector containing cost element values.

q i q j q k op1:pt:A/c op1:pt:A/0
In this case the vector c contains only the values specified in the BPEL specification in order to give top priority to the user. The second transition have the nil cost since we consider the return of an invocation to be free.

Verifying Substitutivity and Composition

According to Definitions 3 and 4, once we have modelled Web services by weighted automata, the formal algorithmic problem for substitutivity and well-formation on one hand, and for strong substitutivity and strong well-formation are identical. Let λ be a positive element of Q k and C 1 and C 2 be two classes of finite weighted automata. We define the generic substitutivity/well-formed composition problems by P λ [C 1 , C 2 ] by:

Input: Two automata A 1 ∈ C 1 and A 2 ∈ C 2 .
Question: for every execution π 1 of A 1 does there exist an execution π 2 of A 2 such that π 1 ∼ π 2 and cost A2 (π 2 ) ≤ λcost A1 (π 1 )?

Similarly, we define the generic problem P λ strong [C 1 , C 2 ] related to the strong substitutivity/strong well-formed composition:

Input: Two automata A 1 ∈ C 1 and A 2 ∈ C 2 .
Question: for every execution π 1 of A 1 does there exist an execution π 2 of A 2 such that π 1 ∼ π 2 and for every π 2 of A 2 such that π 1 ∼ π 2 , cost A2 (π 2 ) ≤ λcost A1 (π 1 )? E,I,F ) be an automaton and α ∈ Q k . We define the automaton αA obtained from A by multiplying all transition costs by α; formally αA = (Q, Σ, E , I, F ) with E = {(p, a, αc, q) | (p, a, c, q) ∈ E}.

Preliminary Background and Notation on Weighted Automata

Let A 1 = (Q 1 , Σ, E 1 , I 1 , F 1 ) and A 2 = (Q 2 , Σ, E 2 , I 2 , F 2 ) be two automata. The product of A 1 by A 2 is the automaton on Σ, denoted A 1 × A 2 , whose set of states is Q 1 × Q 2 , set of initial states is I 1 × I 2 , set of final states F 1 × F 2 and set of transition is (p 1 , p 2 ), a, c 1 + c 2 , (q 1 , q 2 ) | (p 1 , a, c 1 , q 1 ) ∈ E 1 , (p 2 , a, c 2 , q 2 ) ∈ E 2 , a ∈ Σ . It is well-known that L(A 1 ×A 2 ) = L(A 1 )×L(A 2 ). Let A = (Q, Σ,
An automaton is deterministic if it has a unique initial state and if for every state and every action there exists at most one transition starting from this state and labelled by this action. The product of two deterministic automata is also deterministic. An automaton is -ambiguous ( ∈ N) if for every accepted word u there exists at most executions labelled by u. A 1-ambiguous automaton is called unambiguous. Deterministic automata are trivially unambiguous. An automaton is finitely ambiguous if there exists an integer such that the automaton is -ambiguous. An automaton is uniformly weighted if for every pair (p 1 , a, c 1 , q 1 ) and (p 2 , a, c 2 , q 2 ) of transitions labelled by the same action, c 1 = c 2 .

We denote by WA the class of all finite weighted automata. We also denote by D (resp. UA) (resp. FA) (resp. UW) the subclasses of WA of deterministic (resp. nonambiguous) (resp. finitely ambiguous) (resp. uniformly weighted) weighted automata. One has: D ⊆ UA ⊆ FA ⊆ WA.

We finish this section by recalling some results on decision procedures for finite (weighted) automata.

Theorem 5 Given an integer λ and two weighted automata A 1 and A 2 , it is INRIA undecidable to test whether for every u ∈ L(A 1 ), cost A1 (u) ≤ λcost A2 (u) [START_REF] Krob | The Equality Problem for Rational Series with Multiplicities in the Tropical Semiring is Undecidable[END_REF]; same problem is decidable if A 1 and A 2 are both finitely ambiguous [START_REF] Hashiguchi | Decidability of the Equivalence Problem for Finitely Ambiguous Finance Automata[END_REF][START_REF] Weber | Finite-valued Distance Automata[END_REF], undecidable to test whether for every u ∈ L(A 1 ), there exists an execution π of label u in A 1 such that cost A1 (π) ≥ 0 (resp. cost A1 (π) ≤ 0) [START_REF] Krob | The Equality Problem for Rational Series with Multiplicities in the Tropical Semiring is Undecidable[END_REF], decidable in polynomial time to test whether for every u ∈ L(A 1 ), cost A1 (u) ≤ λcost A2 (u) if A 1 and A 2 are both finitely ambiguous [START_REF] Hashiguchi | Decidability of the Equivalence Problem for Finitely Ambiguous Finance Automata[END_REF][START_REF] Weber | Finite-valued Distance Automata[END_REF], decidable in polynomial time to test whether Proof. Let A be in WA. Let A 1 be the automaton of D obtained from the minimal unweighted automaton of L(A) by adding the nil weight on each transition. By construction, one has A 1 A. We claim that A 1 and A satisfy P λ [D, WA] if and only if for every u ∈ L(A), there exists an execution π of label u in A such that cost A (π) ≤ 0. Assume first that A 1 and A satisfy P λ [D, WA]. Let u ∈ L(A). Since L(A 1 ) = L(A), there exists an execution π 1 in A 1 of label u. Furthermore, by construction of A 1 , cost A1 (π 1 ) = 0. Now, since A 1 and A satisfy P λ [D, WA], there exists an execution π in A such that cost A (π) ≤ 0.

A 1 is in UA or if A 1 is in FA [WS91]. PSPACE-complete to decide whether L(A 1 ) ⊆ L(A 2 ) [AHU74].

On the

Assume now that A 1 and A are such that for every u ∈ L(A), there exists an execution π of label u in A with cost A (π) ≤ 0. Let π 1 be an execution of A 1 , and u 1 the label of π 1 . By hypothesis, there exists an execution π in A of label u 1 such that cost A (π) ≤ 0. Since cost A1 (π 1 ) = 0 by construction, A 1 and A satisfy P λ [D, WA], proving the claim.

It follows that if P λ [D, WA] is decidable, then the problem to decide whether for every u ∈ L(A), there exists an execution π of label u in A such that cost A (π) ≤ 0 is decidable; a contradiction (Theorem 5).

2

Proposition 9 One has

P λ [C 1 , D] = P λ strong [C 1 , D] and P λ [C 1 , UA] = P λ strong [C 1 , UA]
Proposition 10 The problem P λ [WA, FA] is PSPACE while the problem P λ [FA, FA] is decidable in polynomial time.

Using the inclusions D ⊆ UA ⊆ FA ⊆ WA, the previous results on the complexity of P λ [C 1 , C 2 ] may be synthesised in the following table.

P λ [C 1 , C 2 ] C 1 = D C 1 = UA C 1 = FA C 1 = WA C 2 = D P P P P C 2 = UA P P P PSPACE C 2 = FA P P P PSPACE C 2 = WA
undecidable undecidable undecidable undecidable If we consider weighted automata generated by WSDL files, with no moderation by BPEL specifications, all considered automata are in UW. Indeed, WSDL files describes each action with a cost. This cost does not depend on where the action is called in the composed service.

Proposition 11 For every pair of classes of automata C 1 , C 2 , the problems

P λ [C 1 ∩ UW, C 2 ∩ UW] and P λ strong [C 1 ∩ UW, C 2 ∩ UW] are equals.
So using the results of Section 3.2, one has:

P λ [C 1 ∩ UW, C 2 ∩ UW] C 1 = D C 1 = UA C 1 = FA C 1 = WA C 2 = D P P P P C 2 = UA P P P PSPACE C 2 = FA P P P PSPACE C 2 = WA PSPACE PSPACE PSPACE PSPACE-complete

Implementation

A tool for verifying different kinds of substitutivity based on weighted automata has been implemented. Its structure is shown in Fig. 1.

INRIA

The translation module is used to translate extended BPEL specifications and WSDL descriptions into weighted automata. Applied to the result of the specification files parsing, the corresponding algorithm is based on the set of rules introduced in Section 2.3.1. This algorithm is a recursive algorithm in which the automaton is built activities after activities.

The verification module is then used to verify substitutivity between two WSs following Definition 3. The inputs of this module are the WSWA produced by the translation module. First, an abstraction of each automaton is computed. This abstraction consists in removing the τ -transitions covering the assign and empty activities. Those transitions can be removed without loosing behaviours since they do not take part in services exchanges. Second, the verification process starts by the computation of the product of the two abstract automata. Third, all the verification algorithms are applied to the result of this product. Those algorithms are based on well-known graph theory algorithms like depth-first search or minimum spanning tree algorithms.

This implementation has been tested on a Dell Latitude D600 with an Intel Pentium M 1.4Ghz and 512Mo of RAM. The increase of the time to build automata is due to the presence of flow activities to put in parallel more activities in the book store example than in the loan approval example, and not to the size of the state space of the produced automaton. Also, this table shows that the costs location is not a factor to increase the time. Currently the verification module allows us to check whether two WSs are substitutable following Definition 3. The table presents the time needed to check the WSs substitutivity on some of the handled examples.

Conclusion

Awaiting a new standard including QoS aspects, this paper presented an approach to model WSs, provided as extended BPEL/WSDL specifications, and to decide the substitutivity and composition problems while considering QoS aspects. The tool developed enables us to automate the different steps of the verification process from extended BPEL4WS/WS-BPEL specifications or from extended WSDL interface files.

Annexes 6 Translation rules

Translation rule for a recursive call of activities. This rule corresponds to the translation of a while activity into cost automata. In a BPEL specification, a while activity is of the following form:

<while condition="booleanCondition"> activity </while> where activity can be a basic or structured activity like a sequence of activities. >From this activity definition we generate the following pieces of weighted automata:

q i q j √ , 0 activity
The transition labelled with √ represent the exit of the loop. This transition is introduced to verify some properties easier while allowing to detect the state which is the origin of a loop.

Translation rule for parallel activities. This rule corresponds to the translation of a flow activity into cost automata. In a BPEL specification, a flow activity is of the following form:

<flow> activity 1 activity 2 ... activity n </flow> where activity 1 , activity 2 , ..., activity n can be basic or structured activities. >From this activity definition we generate the following piece of weighted automata: Notice that this translation rule produces a piece of WSWA containing (n * ((n -1)! + n)) + 2 states where n is the number of activities. This number of states is reduced if some links between activities are defined thanks to the source and target elements of BPEL activities.

INRIA q i q 1 qn q k
7 Omitted proofs

Proof of Theorem 6

Proof. The proof will is divided into two parts.

Assume that A 1 and A 2 satisfy P λ strong . By definition, for every execution of A 1 there exists an equivalent execution in A 2 . Thus A 1 A 2 . Consider now an execution π in xA 1 × (-yA 2 ), π = (p 0 , a 1 , α 1 , p 1 ), (p 1 , a 2 , α 2 , p 2 ) . . . (p n-1 , a n , α n , p n ).

By definition of xA 1 × (-yA 2 ), there exist p 0 , p 1 , . . . , p n states of A 1 , q 0 , q 1 , . . . , q n states of A 2 , integers c 1 , c 2 , . . . , c n , d 1 , d 2 , . . . , d n such that -π 1 = (p 0 , a 1 , c 1 , p 1 ), (p 1 , a 2 , c 2 , p 2 ), . . . , (p n-1 , a n , c n , p n ) is an execution in A 1 , -π 2 = (q 0 , a 1 , d 1 , q 1 ), (q 1 , a 2 , d 2 , q 2 ), . . . , (q n-1 , a n , d n , q n ) is an execution in A 2 , -for every 1 ≤ i ≤ n, α i = xc i -yd i , -for every 0 ≤ i ≤ n, p i = (p i , q i ).

One has π 1 ∼ π 2 . Therefore, since A 1 and A 2 satisfy P λ strong , the following inequality holds:

n i=1 d i ≤ x y n i=1 c i . Consequently, n i=1 α i ≥ 0.
Assume now that A 1 and A 2 satisfy A 1 A 2 and for every execution π of (xA 1 × (-yA 2 )), cost(π) ≥ 0.

Since A 1 A 2 , for every execution in A 1 there exists an equivalent execution in A 2 .

Finally consider two executions

π 1 = (p 0 , a 1 , c 1 , p 1 ), (p 1 , a 2 , c 2 , p 2 ), . . . , (p n-1 , a n , c n , p n )
in A 1 and π 2 = (q 0 , a 1 , d 1 , q 1 ), (q 1 , a 2 , d 2 , q 2 ), . . . ,

(q n-1 , a n , d n , q n ) in A 2 such that π ∼ π 2 .
By definition there exists an execution π in yA 1 × (-xA 2 ),

π = (p 0 , a 1 , α 1 , p 1 ), (p 1 , a 2 , α 2 , p 2 ) . . . (p n-1 , a n , α n , p n ).
such that

-for every 1 ≤ i ≤ n, α i = yc i -xd i , -for every 0 ≤ i ≤ n, p i = (p i , q i ).
Moreover, by hypotheses, one has cost(π) ≥ 0:

cost(π) = n i=1 α i ≥ 0. Consequently, n i=1 d i ≤ x y n i=1 c i .
It follows that cost A2 (π 2 ) ≤ λcost A1 (π 1 ), which concludes the proof.

2

Proof of Corollary 7

Proof. Deciding whether A 1 A 2 is equivalent to decide whether L(A 1 ) ⊆ L(A 2 ) which is classically PSPACE-complete [START_REF] Aho | The design and analysis of computer algorithms[END_REF] in the general case and polynomial if either A 2 is deterministic [START_REF] Hopcroft | Introduction to automata theory, languages, and computation[END_REF] or if both A 1 and A 2 are finitely ambiguous [START_REF] Weber | Finite-valued Distance Automata[END_REF]. Now deciding whether for every execution π of c 2 A 1 × (-c 1 A 2 ), cost(π) ≥ 0 is a classical polynomial problem on weighted graphs which can be solved for instance by Bellman-Ford algorithm (see any graph algorithms book).

The PSPACE-completeness of the general case is trivially obtained by Theorem 6 using automata with zero weights and the PSPACE-completeness of testing whether L(A 1 ) ⊆ L(A 2 ). 2

INRIA

Proof of Proposition 9

Proof. Since for every word u ∈ L(A 2 ) there is a unique execution in A 2 labelled by π, the result is obvious. 2

Proof of Proposition 10

Proof.

Let

A 1 = (Q 1 , Σ, E 1 , I 1 , F 1 ) ∈ WA and A 2 = (Q 2 , Σ, E 2 , I 2 , F 2 ) ∈ FA. Set A 3 = (Q 1 , Σ × Q 1 × Q 1 , E 3 , I 1 , F 1 ) and A 4 = (Q 2 , Σ × Q 1 × Q 1 , E 4 , I 2 , F 2 )
where:

E 3 = {(p, [a, p, q], c, q) | (p, a, c, q) ∈ E 1 }, E 4 = {(p, [a, r, s], c, q) | (p, a, c, q) ∈ E 2 , ∃x ∈ Q k , (r, a, x, s) ∈ E 1 }.
Notice that A 3 is unambiguous and that A 4 are finitely ambiguous. Indeed if u = [a 1 , q 1 , q 2 ][a 2 , q 2 , q 3 ] . . . [a n , q n , q n+1 ] is accepted by A 3 , then there is a unique execution (q 1 , a 1 , c 1 , q 2 ) . . . (q n , a n , c n , q n+1 ) labelled by u (remind that in Section 2.1 that for each pair of states and each action there exists at most one transition between these two states label by this action). Now assume that A 2 is -ambiguous and that the word u = [a 1 , q 1 , q 2 ][a 2 , q 2 , q 3 ] . . . [a n , q n , q n+1 ] is accepted by A 4 . Since there are at most executions in A 2 accepting a 1 a 2 . . . a n , there is at most card(Q 1 ) 2 executions in A 4 accepting u. Thus A 4 is finitely ambiguous.

Let B = xA 3 × (-yA 4 ). We claim that A 1 and A 2 satisfy P λ [WA, FA] if and only if A 1 A 2 and for every u ∈ L(B), there exists an execution π in B such that cost B (π) ≥ 0.

(⇒) Assume first that A 1 and A 2 satisfy P λ [WA, FA]. Then A 1 A 2 . Now let u ∈ L(B).

This part of the proof is represented on Fig. 7.4.

By definition of the product, one also has u ∈ L(A 3 ). Consequently, there exists an execution π 3 in A 3 of label u of the form π 3 = (q 1 , [a 1 , q 1 , q 2 ], c 1 , q 2 ), (q 2 , [a 2 , q 2 , q 3 ], c 2 , q 3 ) . . . (q n , [a n , q n , q n+1 ], c n , q n+1 ).

Consequently, by construction of A 3 , π 1 = (q 1 , a 1 , c 1 , q 2 ), (q 2 , a 2 , c 2 , q 3 ) . . . (q n , a n , c n , q n+1 ) is an execution in A 1 (Step 1 of Fig. 7.4).

Since A 1 and A 2 satisfy P λ [WA, FA], there exists an execution π 2 in A 2 of label a 1 a 2 . . . a n such that (Step 2 of Fig. 7.4 ): cost A2 (π 2 ) ≤ λcost A1 (π 1 ).

(1) Set π 2 = (p 1 , a 1 , d 1 , p 2 ), (p 2 , a 2 , d 2 , p 3 ) . . . (p n , a n , d n , p n+1 ).

π 1 π 3 u π 2 π 4
Step 1 By construction of A 3

Step 2 Since A 1 and A 2 satisfy P λ [WA, FA]

Step 3 By construction of A 4 Now, by construction of A 4 , π 4 = (p 1 , [a 1 , q 1 , q 2 ], d 1 , p 2 ), (p 2 , [a 2 , q 2 , q 3 ], d 2 , p 3 ) . . . (p n , [a n , q n , q n+1 ], d n , p n+1 ) is an execution of A 4 (Step 3 of Fig. 7.4 ). Since cost A2 (π 2 ) = cost A4 (π 4 ) and cost A1 (π 1 ) = cost A3 (π 3 ) and by (1), the execution π in B corresponding to π 3 and π 4 has label u and a positive cost (the detailed proof of this last claim is quite similar to the one of Theorem 6 and is left to the reader).

A 1 A 2 A 3 A 4
(⇐) Let assume now that A 1 and A 2 satisfy A 1 A 2 and for every u ∈ L(B), there exists an execution π in B such that cost B (π) ≥ 0. This part of the proof is sketched in Fig. 7.4.

Let π 1 = (q 1 , a 1 , c 1 , q 2 ), (q 2 , a 2 , c 2 , q 3 ) . . . (q n , a n , c n , q n+1 ) be an execution of A 1 . By construction of A 3 , one has in A 3 the following execution (Step 1 in Fig. 7.4):

π 3 = (q 1 , [a 1 , q 1 , q 2 ], c 1 , q 2 ), (q 2 , [a 2 , q 2 , q 3 ], c 2 , q 3 ) . . . (q n , [a n , q n , q n+1 ], c n , q n+1 ).

Consequently, u = [a 1 , q 1 , q 2 ][a 2 , q 2 , q 3 ] . . . [a n , q n , q n+1 ] is in L(A 3 ). Since A 1 A 2 and by construction of A 3 and A 4 , u ∈ L(A 4 ). Consequently, by hypothesis, there exists an execution π in B of label u such that cost B (π) ≥ 0.

(2)

INRIA π 1 π 3 π 2 π 4 π
Step 1 By construction of A 3

Step 2 By hypothesis on A 1 and A 2

Step 3 By construction of B

Step 4 By construction of A 4 Therefore, since A 3 is unambiguous, π 3 = π 3 and one has: cost A4 (π 4 ) ≤ λcost A3 (π 3 ).

A 1 A 2 A 3 A 4 B
(3) Set π 4 = (p 1 , [a 1 , q 1 , q 2 ], d 1 , p 2 ), (p 2 , [a 2 , q 2 , q 3 ], d 2 , p 3 ) . . . (p n , [a n , q n , q n+1 ], d n , p n+1 ).

By construction of A 4 , there exists an execution π 2 of A 2 of the form (Step 4 in Since cost A4 (π 4 ) = cost A2 (π 2 ) and by (3) one has: cost A2 (π 2 ) ≤ λcost A3 (π 3 ).

Since π 2 ∼ π 1 , the proof of the claim is completed.

Figure 1 :

 1 Figure 1: Automata-based WSs verification tool

  for every ⊗ ∈ {+, -, * , /, max}, we denote by c ⊗ d the element [c 1 ⊗ d 1 , . . . , c k ⊗ d k ] of Q k . Now we formally define what is an execution of a weighted automaton and related notions.

  Figure 2: Syntax of the costs element

  cost not in BPEL file (b) Costs in WSDL and BPEL description files

Figure 3 :

 3 Figure 3: Translation process schema

Figure 4 :

 4 Figure 4: Proof of Proposition 10, part 1.

Figure 5 :

 5 Figure 5: Proof of Proposition 10, part 2.

  Fig 7.4): π 2 = (p 1 , a 1 , d 1 , p 2 ), (p 2 , a 2 , d 2 , p 3 ) . . . (p n , a n , d n , p n+1 ).

  Complexity of theP λ strong [C 1 , C 2 ] and P λ [C 1 , C 2 ] Problems Set λ = xy where x and y are two positive relatively prime numbers. C 1 and C 2 be two classes of finite weighted automata. Omitted proofs are given at http://lifc.univfcomte.fr/∼heampc/wiselong.pdf. Two automataA 1 ∈ C 1 and A 2 ∈ C 2 satisfy the problem P λ strong [C 1 , C 2 ]if and only if they satisfy A 1 A 2 and for every path execution π of xA 1 × (-yA 2 ), cost(π) ≥ 0.

	Theorem 6 P λ strong [C 1 , C 2 ]	C 1 = D C 1 = UA C 1 = FA	C 1 = WA
	C 2 = D	P	P	P	P
	C 2 = UA	P	P	P	PSPACE
	C 2 = FA	P	P	P	PSPACE
	C 2 = WA	PSPACE PSPACE PSPACE PSPACE-complete
	Theorem 8 The problem P

Corollary 7 The problems P λ strong [WA, WA] and P λ strong [WA, D] are respectively PSPACEcomplete and polynomial. The problem P λ strong [UA, UA] is polynomial too. Using the inclusions D ⊆ UA ⊆ FA ⊆ WA, previous results on the complexity of P λ strong [C 1 , C 2 ] may be synthesised in the following table. λ [D, WA] is undecidable.

  The tests have been achieved on different versions of several examples like a book store example provided by Oracle 1 or the classical loan approval example. Different versions of those examples have been developed in order to test the different possibilities to compute automata from description files. The following table shows some examples of the approximative computing time needed for building automata from BPEL and WSDL description files.

	Example	Costs location	State space Time to build Time to check
	Loan approval	WSDL	10	< 1 sec.	< 1 sec.
	Loan approval WSDL + BPEL	10	< 1 sec.	< 1 sec.
	Book store	WSDL	50	< 3 sec.	< 1 sec.
	Book store	WSDL + BPEL	50	< 3 sec.	< 1 sec.

RR n 6218

http://www.oracle.com/technology/pub/articles/matjaz_bpel2.html RR n 6218

This work was partially granted by the ARA-COPS project

In the future we intend, on one hand, to extend WSWA with guards on transitions, close to what is done in [START_REF] Fu | Analys of Interacting BPEL Web Services[END_REF]. This extension should enable modelling WSs more finely. In addition, this should allow us to consider conditional service costs. By conditional service costs we mean service costs which are dependent of the message (or the number of messages) received by the concerned WS. These evolutions should make it possible to use our framework and the dedicated tool in the realistic context with the proviso that it is possible to discern two functionally equivalent services (i.e. to rename operations which performs the same task to obtain equivalent WSWA).

On the other hand, we plan to consider other relations between WSWA, e.g. semicommutative relations or different kinds of simulation relations. Unfortunately, within these settings the problems of the substitutivity/well-formation might become undecidable.

We are grateful to Ines Klimann and to Sylvain Lombardy for their help. This finishes the proof of the proposition, the polynomial time decidability resulting from Theorem 5. 2

Proof of Proposition 10

Proof. By definition, one has

then for every execution π 1 of A 1 there exists an equivalent execution π 2 of A 2 such that cost A2 (π 2 ) ≤ λcost A1 (π 1 ). Let π 2 be an execution of A 2 equivalent to π 1 . By transitivity, π 2 and π 2 are equivalent. Moreover since A 2 ∈ UW, cost A2 (π 2 ) = cost A2 (π 2 ). It follows that


Zeyang Li

Qi-Tao Cao

Pai Peng

Martina Hentschel

Heming Wang

Mesoscopic Regulation of Atoms System via Optical Microcavity

Keywords: numbers: 00, 00, 00

The atom with fine structure is widely studied in the area of nuclear physics, atomic physics and condensed matter physics. The traditional way to manipulate them relates to static magnetic field; however, the scale area of a typical magnetic field is always macro. In this letter, we proposed a method to control atoms via vector the polarizability at mesoscopic scale by optical microcavity. The linear quantum control of optical microcavity, at the same time, is achieved, which could be a significant for on-chip device engineering. In addition, by applying magnetic field, a nonlinear phenomenon of transmission spectrum is observed, which could be used as a test pool for many fancy nonlinear dynamics.

I. INTRODUCTION

Modern research on cavity quantum electrodynamics (CQED) obtains great results about strong interactions between light field and single atom. To obtain the interaction a promising method is by increasing the energy density, where using optical cavity to spatially confine photons is a promising approach. The strong interaction has two remarkable consequences: on the one hand the atom is governed by the light field, and on the other hand the cavity modes are also modulated by the atoms. The former one is widely studied in numerous CQED systems such as graphene plasmonics [1], cavity polariton [2,3], quantum dot [4] and WGM cavity [5,6]. In addition, perfect circular WGM cavities, though exhibit great quality factor, are hard to couple with fiber, while asymmetric WGM cavities are always good substitution in reality. For single atom's coupling with light field, the later phenomenon can hardly be observed at ordinary light intensity level for experiments; however, things are different for an atom ensemble interacts with light field. What makes atom ensemble unique in this interaction form rather than individual atom arises from the interaction between atoms. Ordinarily, the interaction could be tuned by magnetic field via Feshbach resonance [7][8][9]. In general the Feshbach resonance occurs accompanied with zero energy bound state. Magnetic field tune the Zeeman shifting to create a bound state, and it could also be done via optical field by a so-called optical control of Feshbach resonance [10][11][12][13][14][15][16][17]. In the optical microcavity coupling to atom ensemble setup, this could also be important and have exotic phenomena both in cavity modes side and in atom's dynamics side.

In this work, we propose a system which for the first time can directly couple WGM cavity with atom's spin level. To achieve the necessary power, an asymmetry is * introduced to WGM cavity due to its strong near-field intensity. We assume the atoms are set in the mesoscale region, which is acme of both cavity mode intensity and the coupling strength. Due to the conversation of angular momentum, different cavity mode which has its unique orbital angular momentum could couple to each other via each order of spin flipping process.

In Sec. II we establish a description of the system, and discuss simplification which suits the ordinary experimental condition. In Sec. III we discuss the influence of this interaction to cavity mode where an interesting nonlinear behavior is observed. In Sec. IV we then discuss how this universal interaction matters on atoms, and two aspects are analyzed: first the population of spin as a function of input power and frequency is studied, and second we based on recent approach of deriving effective large scattering length via time-dependent modulated external field, where we extend it to light field rather than magnetic field to get better time-domain control.

II. MODEL CONSTRUCTION

Circular WGM cavity has a rotation symmetry, and its eigenmodes are all TM or TE polarized, i.e., have no circular polarizability. These properties would not be useful in a strong light-matter interaction for our study. By introducing asymmetry, such as deformation [18][19][20] or defects to make annular cavity [21,22], the near-field intensity is increased at some particular positions, and the eigenmodes of the cavity have circular polarization. Set atom ensembles in the regions where field intensity is large would therefore establish effective coupling between the cavity modes and atom. A fine-structured atom could interact with small detuning monochromic light via a form as

H eff = iu v (E × E * ) • S ( 1
)
where S is spin of an atom, and for the ideal two-level atom, u v = -1 12∆e α | l = 1|d|l = 0 | 2 is the so-called vector polarization which is derived in textbooks and literatures [23][24][START_REF] Cohen-Tannoudji | Atom-photon interactions: basic processes and applications[END_REF][START_REF] Cohen-Tannoudji | [END_REF][27][28] as the coupling strength of dipole interaction, and the ∆ e is the detuning of light frequency from energy gap between the atom's ground state and first excited state: ∆ e = E e -ω. This particular form of interaction is remarkable for artificial gauge field in ultracold atom areas, considering it produces a vector shift of atom and explores new form of light-matter interaction, and could disappear only when the total angular momentum F = 0. 4), (e) energy level demonstration, where the left shaded region and right shaded region couple to each other based on the conservation of angular momentum. The coupling strength proportional to the overlapping of cavity mode within the area of atomic ensemble.

For a symmetric optical microdisk, it could not exhibit any sort of property of this interaction, for the emission of a single resonance mode always has unitary distribution of E × E * . However, when asymmetric is introduced into the microcavity, such as deformed microcavity or annular microcavity, the TE mode electric field could be extremely different. In this letter, we take consideration of annular cavity to make the cavity asymmetrical. Fig. 1 (a-d) shows an example for annular cavity and related light intensity and |E×E * | distribution. For a TM mode, the field component perpendicular to the plane is magnetic field [22], therefore the TM mode's electronic field can be derived as

E ⊥ = - i r 2 kẑ × ∇ ⊥ B z , ∇ ⊥ = (∂ x , ∂ y , 0) (2)
within cylinder coordinates, it's

E ⊥ = - i r 2 kẑ × ∂B z ∂r e r + 1 r ∂B z ∂θ e θ (3)
and for a circular cavity this effect annihilates for θ symmetric and E is in same direction as E * .

For a TM mode, E × E * is pure imaginary and has no components on x, y direction, so we can suppose that E × E * = iΩe z /u v , an illustration see Fig. 1. We then derive the effective Hamiltonian as

H eff = -ΩS z (4)
which causes the splitting of the alkali atom's single outmost electron's two spin degeneracy eigenstate.

The physical process at resonance is important, for it obeys the conservation of energy and angular momentum at the same time, and hence the phenomenon is remarkable. The extra term we add into Hamiltonian is described as the following process: 1. the microcavity mode |m, 1 is excited by taper, with annihilation operator a m . Its emission, when treat as classical light, interacts with the atoms outside; 2. the spin-up atom absorbs photon with orbital momentum m , then emit a photon with orbital momentum (m + 1) and falls into spin-down atom; 3. the interaction could be described as coupling between atom electron spin and photon, i.e., gb † ↓ b ↑ a † m+1 a m + h.c; 4. the interaction happens because the photon spin is transferred into electron spin, however, with even weak spin-orbital interaction of photon, this could happen. Hence, full Hamiltonian without input at resonance is given by

H = H modes + H spin + H int (5a) H modes = j=m,m+1
(ω j -iΓ j )a † j a j (5b)

H spin = (ca † m a m + da † m+1 a m+1 )b † ↑ b ↑ (5c) H int = (gb † ↓ b ↑ a † m+1 a m + h.c) (5d)
where in the Hamiltonian, H modes , for the energy of photons; H spin , for the splitting due to the contribution of the two optical modes (as in Fig. 1, the two mode has basically same strength of E × E * , and hence the efficient is chosen to be same). The interaction between atoms is not taken into account for simplicity. The crossing of two electric field components is actually phenomenologically described via the extra interaction term: H int , for the interaction between integrated state |m + 1, ↓ and |m, ↑ . At large N limits, which means the number of photons and atoms are large enough, we can apply a meanfield approach where all the operators could be treated as numbers. By adding input term, we can write down the dynamics of cavity mode precisely as

b † ↑ b ↑ + b † ↓ b ↓ = N tot
i d dt a m = (ω m -iΓ m + cb † ↑ b ↑ )a m + g * b * ↑ b ↓ a m+1 + i √ κ m P e -iωt , (6a)
i d dt a m+1 = (ω m+1 -iΓ m+1 + db † ↑ b ↑ )a m+1 + gb * ↓ b ↑ a m + i √ κ m+1 P e -iωt , (6b)
and also the of spin population is given by

i d dt b ↑ = (ca † m a m + da † m+1 a m+1 )b ↑ + g * b ↓ a * m a m+1 , (6c)
i d dt b ↓ = gb ↑ a m a * m+1 . (6d)
with all these four equations, one can exactly solve the dynamical evolution of cavity mode and spin population. However, on the other hand, knowing the exact dynamics is relatively useless for the physics behind the whole framework. Therefore we might need other way to treat these equations, as in Sec. III.

III. REGULATION ON MICROCAVITY

In the first two sub-equations in (6a), (6b), the b † ↑ b ↑ term actually contributes a rather small effect, for firstly the c is relatively a small number, and secondly the number of atom is not large enough to influence the frequency of light, compare to the high optical frequency we are interested in. Based on this analyze, in principle we could omit this extra term due to each spin number.

We suppose that the input source set the frequency, i.e., a m , a m+1 , b ↑ , b ↓ are both in a harmonic oscillating way as a m,0 e -iω1t , a m+1,0 e -iω2t , b ↓,0 e -iω3t and b ↑,0 e -iω4t . An obvious result for this is that ω 1 = ω 2 , ω 3 = ω 4 , and due to the input as compulsory driven force,

ω 1 = ω 2 = ω. Define G 1 = g * b * ↑,0 b ↓,0 / , G 2 = g * a *
m,0 a m+1,0 / ; y ≡ a m+1,0 /a m,0 , z ≡ b ↓,0 /b ↑,0 as some parameters. Based on the condition that the number of total spin is conserved, i.e., |b ↓,0 | 2 + |b ↑,0 | 2 = N tot , the equations (6a) could be transformed that the amplitude obeys the following coupled algebraic equations:

z = 1 2G 2 -(c|a m,0 | 2 + d|a m+1,0 | 2 ) ± (c|a m,0 | 2 + d|a m+1,0 | 2 ) 2 + 4|G 2 | 2 (7a) ω 3 = ω 4 = 1 2 (c|a m,0 | 2 + d|a m+1,0 | 2 ) ± (c|a m,0 | 2 + d|a m+1,0 | 2 ) 2 + 4|G 2 | 2 (7b) a m,0 = √ κ 1 (ω -ω m+1 + iΓ m+1 ) + √ κ 2 G 1 iP (ω -ω m+1 + iΓ m+1 )(ω -ω m + iΓ m ) -|G 1 | 2 (7c) a m+1,0 = √ κ 2 (ω -ω m + iΓ m ) + √ κ 1 G 1 iP (ω -ω m+1 + iΓ m+1 )(ω -ω m + iΓ m ) -|G 1 | 2 (7d)
At this level, the phenomenon is purely linear: for scaling input power, the a m , a m+1 scales linearly which make the z, ω 3 = ω 4 unchanged. The effective coupling strength is therefore a function of total atom number N , as illustrated. We can show that at the experimental practical region, where cN ω, the effective coupling strength is linear increase of N tot . This would result in a linear quantum control of cavity mode, as a useful tool for quantum engineering based on on-chip device. However, the control is determined exclusively by the atom number and cavity shape (g), both hard to vary during experiments, and hence is not efficient for practical use. The following approach provides a solution to this dilemma.

In addition, by adding a constant magnetic field around, i.e., adding additional term µ B B|↑ ↑|, the system shows a very complicated behavior of transmission spectrum, and begin regularized by the input power. In other words, the system enters nonlinear region with nonzero magnetic field. In this region, the quantum control over microcavity is derived: by controlling the input power P , one would slightly control the peak position in transmission spectrum, which is defined as

T = |P - √ κ m a m,0 - √ κ m+1 a m+1,0 |/|P |.
Numerically calculated spectrum is shown in Fig. 2, where a sensitive relation of spin population to the frequency around the first major absorb, i.e., the ω ∼ 150 -160 could be read out. This is actually due to the mode beating, where the two optical mode are mixed together and the dominant one would rule which spin direction has more population. It's the same reason that the two spin orientations dominant at different input power, as in Fig. 3. The transmission spectrum has a shape much different from the traditional Lorentzian result. The spin plays a role of regulating the transmission. Due to it's nonlinear effect, the Fig. 2 only presents a low-power case, and the strong power situation would causes more results, as in Fig. 3. When the power is too strong where the photon number is remarkably high, the coupling between spin up and down is remarkable. This leads to a far deviation from half-half population at resonance, and on the other hand results in the power hard to permit inside the cavity, which in the spectrum means a transmission transparency. This kind of transparency has a dramatically sharp shape and small width, mainly because it happens when the spin population experience a nonlinear bifurcation. It's a sudden phenomenon, results in a discontinuity in physical quantity, and hence the transmission spectrum would only exhibit a sharp peak.

There are two things should be discussed carefully. One is about T > 1 for some particular frequency region. This could be understood as atoms gain energy from magnetic field, and the transfer this energy into photons and flip back into low energy state, and not violate energy conservation law, as expect. The other is the regularization of peak position by this approach is actually limited by the total number of atoms, and hence it saturates at high input energy.

IV. OPTICAL FESHBACH RESONANCE, ATOMIC INTERACTION AND FLOQUET COLLECTIVE EXCITATION

Each atom could interact with each other where the interaction could be described well by contact potential

U I = gδ(r) where g = 4π 2 a s m (8)
and a s is s-wave scattering length. The scattering length could be tuned by magnetic field due to the emergence of zero energy bound state or αI = B 0 , indicating a strong interacting. However, around these resonance place, the atoms got heated very fast, results in a remarkable atom loss. Recently a floquet approach [29] showed a modulated magnetic Feshbach resonance which means that a time periodic driven magnetic field could effectively reach higher scattering length so that might solve the atom loss issue when reaching strong interaction. However, even though the required frequency for driving the magnetic field is not high for 87 Rb, this could limit a potential application to other species of atom. Considering the driven frequency of light intensity could be really high, this approach could also be used in an optical control of Feshbach resonance, where all procedures are exactly the same.

a(B) = a bg 1 - ∆ B -B 0 (9)
However, to obtain a same form of time-dependent scattering length a(t), the control of input power is not simple. The light intensity has a nonlinear dependency of input power, due to the interacting between cavity mode and atom. We here can show a direct mapping from [29] the magnetic field approach to our optical approach that if the input power is a function of time I(t) = I 0 + ∆I cos(Ωt), the scattering length exhibits following behavior

1 a(Ω) = 1 ā Ω -Ω 0 Ω -Ω 0 -δ + iγ
and therefore being able to tune the scattering length and at the same time avoid heating and atom loss due to resonance, i.e., it can enhance the real part of scattering length while still having small imaginary part. The advantage for this setup is that the controlling of light intensity is much more flexible than the controlling of magnetic field, for the latter one always involves complicated current control due to large inductor. The light intensity is quite simple to control even at high frequency.

V. SUMMARY

In this work we briefly introduce circular polarization to the annular microcavity, which absences in circular microcavity. This on the other hand could perform a vector polarization on atom and therefore could regularize both the cavity's and the atom's behavior. We then analyze both sides, and find some nontrivial behavior and potential application. In particular, this could be useful for controlling the interaction between atom. The previous difficulties in controlling interaction between atoms are either the loss due to resonance or the technique in magnetic field precise control. In our setup both difficulties are solved.

This project was supported by Ministry of Science and Technology of the People's Republic of China (MOST) (2016YFA0301302, 2013CB921904, and 2013CB328704); National Natural Science Foundation of China (NSFC) (61435001 and 11474011).

FIG. 1 .

 1 FIG. 1. (a) -(d): Comsol simulation of the distribution of an annular microcavity's scar-like m = 16, 17 modes: (a, c) light intensity |E| 2 (b, d) imaginary part of E×E * 's z component, i.e., Ω/uv in eq. (4), (e) energy level demonstration, where the left shaded region and right shaded region couple to each other based on the conservation of angular momentum. The coupling strength proportional to the overlapping of cavity mode within the area of atomic ensemble.

  for the number of atoms. The Heisenberg equation gives the dynamics equation for modes and spin population. The coupling coefficient is determined by the overlapping of mode |m and |m + 1 around a given position, say around the place with high |E × E * | as in Fig.1. Physically one would expect the g as a function of the size and center displacement of annular cavity. The way to determine the coupling constant g is by calculating the mode overlapping of |m , |m + 1 modes at one maximum place.

FIG. 2 .

 2 FIG. 2.Numerically calculated transmission spectrum (rescaled by T → (T -0.8)/0.2) and spin population for the effective two mode system. The frequency of the two optical mode is set at ωm = 205 and ωm+1 = 210. The coupling on the one hand causes expel of peak position, on the other hand give rises of bistable modes.

FIG. 3 .

 3 FIG.3. Transmission spectrum and corresponding spin population at different power. In Fig.2the power is P0, and here is 50/100/200/300P0. As power increases, the frequency where the spin population first present near saturated occupation (50/100P0: spin down; others: spin up) tends to be lower, and the saturation's frequency range tends to broaden; besides, the similar saturation is arose at second dip.

0 FIG. 4 .

 04 FIG.4. Illustration of scattering length as a function of light intensity. Shaded region for scattering length exceeds the area of near field light spot and therefore the description of system is no longer valid.


L De Mesnard

THE Bl PROPORTIONAL FACTORIAL ANALYSIS

Keywords: Biproportion, RAS, Factorial Analysis. 1. RECALL: THE FACTORIAL ANALYSIS

Beyond the Factorial Analysis of Correspondences, the paper presents a new method of data analysis: the Biproportional Factorial Analysis. In the Factorial Analysis of Correspondences, the matrix to be diagonalised is the product of the two matrices of profiles, row and columns: this matrix is not symmetrical. In the Biproportional Factorial Analysis, the matrix to be diagonalised is the symmetrical product of an intermediate matrix over itself; this intermediate matrix is calculated as the biproportion of the data matrix over normalised margins. This provides a full symmetry between rows and columns. After recalling the Factorial Analysis of Correspondences, the paper recall what it is biproportion and then presents the Biproportional Factorial Analysis and discuss it,

At this point, the method is similar to the simple Principal Components Analysis Method.

However, it is not necessary to have centred data2 . Suppose that data are not centred. The vector of coordinates of the gravity center of the set of points X R = N R N, weighted by (NJN\ (\\

P R =^, is g R =X^P R l = -l-N R 1 NN R l-
, where 1 is the sum vector: 1:

1 The variance matrix of the points is V = X R P R X R -g g'. Then M R X R P R X R = M R V + M R gg' =>g'M R X R P R X R = g'M R V + g'M R gg'
As the vector Og is orthogonal to the set of points, it is a principal axis: g is eigenvector of the matrix M R V, with the eigenvalue A = 0: Note that Factorial Analysis of Correspondences looks like a particular case of the general Principal Components Analysis (with metric not unitary and with weights). Also, the matrix to be diagonalised is the product of the two matrices of profiles.

M R V = 0. Then g'M R XiP R X R = 0+||g||^g' = g'. The diagonaKsation of M R X R P R X R = N^1 N' N R
X Ci . = , or X c = NN C ! (this matrix is called the matrix of column profiles). The column

THE BIPROPORTIONAL FACTORIAL ANALYSIS

The starting problem of Correspondence Analysis appears to give unitary margins to the data table N, alternatively to rows and to columns. The result depends on that fact: the correspondence between these double result is studied. However, when the row margins are equal (unitary), they are not equal (unitary) in columns, and reciprocally. As there is duality between these double results, in fact they brings the same information seen on a different point. The information obtained when row and column margins are simultaneously equal could be interesting and it eliminates simultaneously the effect of the size of the margins of rows and columns. Then it looks to be interesting to give the same margins to rows and the same margins to columns simultaneously, that is to say to give such margins to N using a biproportion and then to make a "Correspondence-like Analysis".

Recall: biproportion

A biproportion of a matrix N on the margins of a matrix L is the matrix X = A N B .

n m

Note that margins respects a global equilibrium: ^ /. = ^ /..

i=l ;=1

Different algorithms may be used to calculate A and B. For example:

/ h a = , V/ and 6, = ^ , V/ j=l i=l [A = EMag(A*) IB = Diag(fi*) 01 ' J A* = [DiagfNB*)]" 1 L R 1 ^ jfi* = [Diag(N' A*)]"' L c 1
where Diag is the matrix operation who transforms a vector into a diagonal matrix3 , L R is the diagonal matrix of the terms /,._ and L c is the diagonal matrix of the terms / • . This algorithm is convergent, the solution of is unique. Moreover, we proved that, whatever be the algorithm, the result is the same: biproportion is so unique than proportion is [ de MESNARD ].

Remark: to apply a biproportion, data must not be negative, what excludes centred data: it is not a problem because diagonalisation may be done over not centred data, as shown.

The new method

1) First step. There are two cases.

a) The data matrix is square (n,n). We calculate a biproportion of the matrix N on any matrix L with unitary margins, that is to say, we calculate a matrix It is possible to go back to the original data. Classically, the reconstruction of the matrix X from the eigenvalues and the eigenvectors remains possible. And it is possible to retrieve the matrix N from the matrix X, making a biproportion of X on the margins of N. So, the only condition is to know the margins of N.

About metric and weights

Here For the same reason, there is no need to weight data before applying biproportion.

•

The metric is used after applying biproportion, or data are weighted after applying biproportion. The matrix to be diagionalised isMX'PX .

It is not logical to weight after applying biproportion because biproportion on N replaces the weighting on either rows or columns of N : every rows takes the same importance, every columns takes the same importance.

To use a non unitary metric is more logical. However, the £ metric used by Factorial Analysis of Correspondences is a little artificial. An argument is that unitary distance between rows (reciprocally columns) gives more importance to the bigger columns (reciprocally rows). Another and good argument is the "distributional invariance" of the j? metric. Biproportion allows to take into account the first argument but not the second: if this "distributional invariance" is essential, then one must get the £ metric.

Advantages and disadvantages of the new method

1. In Biproportional factorial Analysis, there is only one matrix X to calculate the symmetric matrix X' X to be diagonalised. In the Factorial Analysis of Correspondences, there are two matrices X R = N R N and X c = NN C ! , and no symmetry.

In the biproportional factorial analysis, there is not such a strict duality (the classical duality between 9? w and SSK N remains), but there is an absolute symmetry between rows and 2. With this new method, we shall lost the "distributional invariance" characterising the metric: if we replace two rows or columns by only one, we must recalculate the biproportion. It will be a disadvantage. However, we shall get a better analyse of data, because of the absolute symmetry between rows and columns.

columns. The new method does not requires to study correspondences: its interpretation is simple as in Principal Components

ANNEXE

The diagonalisation in factorial analysis

When data are centred, minimising the sum of squares of Euclidean distance is equivalent to maximise the sum of projections of points along the axis of regression. Generally, in the space of 5R W , if X is the matrix of data, and if u is the unitary vector supported by this axis (with m elements), X u is the projection of the points along the axis. Then, we must solve, r Max(Xu) (Xu) = u'X'Xu , under constraint: u' u = 1 .

The Lagrangian is L-u'X'X u-l(l-u'u) = 0

Deriving the Lagrangian with respect of u and X , we obtain:

du ÔX = x'Xu-;iu = o = l-u'u = 0
The second equation verifies the constraint, and the first equation provides: X'Xu = iu. >î is the eigenvalue and u is the eigenvector associated to it. As we maximise, we select eigenvalues Xfrom the greater to the smaller. The associated eigenvector gives the direction of the axis. The cosine of the angle between a variable X t and the axis is the correlation coefficient for this variable.

Example

We shall construct a small example with a 7x5 matrix.

  obtain the principal components c (the projection of the n individuals upon the m principal axis), we calculate c -X R v.

  calculus can be made in the space of 9? n (when points are columns), the terms N }J of the columns of this matrix are divided by the margins of the columns JV ; giving margins of X c are unitary. The metric is M c = Af N R . The distances are are the same than in the preceding case.

  data matrix is rectangular (n,m). We calculate a biproportion of the matrix N on any matrix L with unitary margins in one side and with equal margins in the other side. Suppose "l/m l/m] that m < n (without loss of generality); then L is a constant matrix: L -We are obliged to do so to respect the global equilibrium m ]T l u = ]T / ; • However, the important is that each rows have the same margins and each columns have the same margins, and not a unitary value of margins (multiplying every margins by £ multiplies by k 1 the eigenvalues of the diagonalised matrix 4 quasi normalisation simultaneously in rows and columns.2) Second step. We diagonalise the matrix X'X in the space of 9i m (or X X' in the space of 9T: classically, first eigenvalues are the same in one case and in the another case). A trivial eigenvalue is found: X = -, associated to the eigenvector g, the gravity center . If d = -g ; thus X = -with g as eigenvector.

  in rows and one time in columns, that is to say, divided by N L in one case and by N tj in one another case. In the Biproportional Factorial Analysis, data are simultaneously (quasi) normalised in rows and columns.

  =1In this example, results are enough close to those of Correspondence Analysis.

We follow here [ SAPORTA pp. 200-204 j.

This compact and easy-to-read writing is not efficient in computing: one must use a special algorithm to inverse diagonal matrices without using the standard matrix inversion routine.

See later.