Ehtesham Zahoor
email: ehtesham.zahoor@loria.fr

Olivier Perrin
email: olivier.perrin@loria.fr

Claude Godart
email: claude.godart@loria.fr

Rule-based semi automatic Web services composition

In this paper we propose a rule-based approach for the semi-automatic Web services composition problem, giving end-user the control to guide the overall composition process. The end-user builds the composition flow by selecting known Web service instances or constrained Web service types, called nodes, and by connecting them using a set of control/data flow connectors. The specified nodes will then be bound to concrete Web service instances using a set of rule-based queries satisfying the associated constraints. When compared to the traditional approaches, our model is declarative, allows for specifying both the functional and non-functional requirements, provides connectors that include both the data and control flow aspects and aims to choose the one best matched Web service for a node instantiation.

Introduction

Traditional methods for Web services composition problem such as WSBPEL or WS-CDL have resolved the basic interoperability problem. However, in complex service oriented applications the services may need to be composed on the fly, with service instances not known in advance, and thus introducing the problem to automatically synthesize and adapt Web services composition process satisfying user request. There have been many approaches to the automatic composition problem but it is still considered highly complex task due to the rapid increase in the number of available services to choose from, the heterogeneity of the access protocols used and data formats they offer. Further, the proliferation of Web services may lead to a situation where we have many services with similar functionalities and thus we need to cater for the non-functional properties.

In this paper we propose a rule-based approach for Web services composition problem, putting the user in the control of the composition process. This leads to the semiautomatic Web services composition problem as the com-position flow is guided by the user. The motivation for our work comes from the growing usage of mashups that are defined in the literature [START_REF] Liu | Towards service composition based on mashup[END_REF][START_REF] Zahoor | Mashup model and verification using mashup processing network[END_REF][START_REF] Benslimane | Services mashups: The new generation of web applications[END_REF] as the new wave for composing Web services.

Our model allows user to select Web service instances and Web service types, called nodes, and connect them using the proposed set of connectors in order to define a process. When compared to the traditional approaches, our model has many differences: first, constraints on nodes include both the functional and non-functional specifications to be used for Web service discovery. Then, as mashups are the application level service composition and focus on composing the data from Web services [START_REF] Zahoor | Mashup model and verification using mashup processing network[END_REF], our proposal aims at providing a set of connectors that include both the data and control flow aspects. Further, in contrast to the procedural approaches, we propose a declarative approach to model the composition process and as opposed to the AI planning based approaches, we propose to select one best matched service (based on user specified criteria) as a result of node instantiation, this would be of critical importance due to the rapid increase in the number of available services. Our approach also handles the case when the service instantiation needs to be backtracked based on dependency between services and allows for propagation of newly chosen solution.

The paper is organized as follows. We discuss related work in section-2 and present the motivating example in section-3. We broadly discuss our proposal in section-4, while we detail the composition flow in section-5 and the concrete composition process in section-6. Implementation details are given in section-7 while section-8 concludes.

Related work

Web services composition is a highly active and widely studied research direction and there have been many approaches to automate the composition process. Most of these approaches can be divided into Workflow composition and AI planning based approaches, as discussed in [START_REF] Rao | A survey of automated web service composition methods[END_REF]. The composition result can be regarded as a wokflow because it includes the atomic Web services and the control and data flow between them. Static workflow composition approaches require an abstract composition flow to be specified and the selection and binding is performed automatically by the Web services composition process, while the dynamic workflow composition approaches require to both build the composition flow and select atomic service automatically based on user request as proposed in [START_REF] Schuster | Modeling and composing service-based and reference process-based multi-enterprise processes[END_REF]. The composition process can also be regarded as a AI planning problem by assuming that each Web service can be specified by its pre-conditions and effects. These approaches require the user to specify the process by a set of pre-conditions and effects and the AI planners can then generate a plan without any pre-defined workflow. These approaches are based on: situation calculus [START_REF] Narayanan | Simulation, verification and automated composition of web services[END_REF], rule-based planning [START_REF] Medjahed | Composing web services on the semantic web[END_REF], theorem proving [START_REF] Waldinger | Web agents cooperating deductively[END_REF] and other approaches including [START_REF] Sirin | Semi-automatic composition of web services using semantic descriptions[END_REF].

The problem of traditional approaches (such as WS-BPEL or WS-CDL) is that all what is not explicitly modeled is forbidden. In fact, WSBPEL and WS-CDL have in common that they are highly procedural, i.e., after the execution of a given activity the next activities are scheduled. Seen from the viewpoint of an execution language their procedural nature is not a problem [START_REF] Van Der Aalst | Decserflow: Towards a truly declarative service flow language[END_REF]. However, unlike a classical system, Web services tend to be rather autonomous and an important challenge is that all parties involved need to agree on an overall global process. Moreover, this way of modeling renders difficult to model complex orchestrations, i.e. those in which we need to express not only functional but also non-functional requirements such as cardinality constraints (one or more execution), temporal constraints, existence constraints, negative relationships between services, or security requirements on services (e.g. separation of duties). With current approaches, the designer should explicitly enumerate all the possible interactions and must either over-constrain or over-specify the orchestration. In case of multiple constraints (security and temporal for instance), it becomes very difficult to do that without declarative specifications. A more detailed discussion can be found in [START_REF] Pesic | A declarative approach for flexible business processes management[END_REF].

Our approach can be categorized as a composition framework (similar to the Astro approach [START_REF] Marconi | Automated composition of web services: the astro approach[END_REF]) and it provides the ability to dynamically discover the Web services by using the "service selection rule" to be processed. Our approach can also be considered as an extension to [START_REF] Monfroy | Dynamic web services provisioning with constraints[END_REF] but in this work we provide an extended set of connectors (to handle both control and data flow), introduce specification of non-functional properties, introduce concepts such as propagation and propose that some part of the composition may be static (with known Web service instances) while some other may require dynamic binding. Further, we argue the existence of private constraints for a service as proposed in [START_REF] Monfroy | Dynamic web services provisioning with constraints[END_REF]. Our approach proposes inferring the worksWith dependency using the service composability rules [START_REF] Medjahed | Composing web services on the semantic web[END_REF]. In addition, we have also proposed an implementation framework for our proposal using known Web service standards.

Motivating example

For the motivating example, we have chosen the case study of a SOA based Corporate Cash Management (CCM) solution 1 . Pierre has been hired as the treasury in an organization, the bigCo. One of his core responsibilities includes the CCM process, which is defined to be the process of managing a company's short-term resources, gathered for example from various financial institutions and ERP systems, to sustain its ongoing activities and to mobilize funds.

At bigCo, CCM is currently achieved by manually contacting different participating entities resulting in a tedious, less efficient and time consuming process. Pierre is willing to enhance this manual process of CCM by using the SOA principles, given that various financial institutions and internal systems being used at bigCo are exposing their functionalities using Web services.

In this context his responsibilities may include to compose cash positions held in multiple banks and internal ERP systems using the provided Web services; to determine investment or loan plans using the intelligent decision system Web service; to discover possible loan/investment options from various financial institutions based on some specified constraints (using the provided Web services); and to identify and execute Web services to get offer rating for the proposed investment or loan offers.

Proposed framework

Our proposal aims to provide a declarative framework for addressing the semi-automatic Web services composition problem, such as the one presented in the motivating example. In this section we will briefly discuss the main concepts related to our approach and will detail them in the sections to follow. The composition process starts when the user specifies the composition flow using a user friendly interface (see figure 1-1), allowing her/him to drag and drop components as similar to the Mashup creation tools such as Yahoo! Pipes. The user interface will be backed up by a declarative language, called the intermediate language, (see figure 12), though the end-user does not need to know the details of the intermediate language and works directly at the interface level. The various concepts introduced in the declarative language (that map directly to the components provided on the user-interface) include:

• Web services -The user can specify the Web services instances known in advance.

• Nodes -If the Web service instance is not known in advance, the user can specify the Web service node which has a unique type such as Bank or Credit Union. User can also add constraints to the Web service node to be satisfied when binding the node to some Web service instance of the same type.

• Connectors -Connectors link different nodes and Web service instances and specify the control and data flow between them.

The intermediate language will then be processed by the composition engine to transform it into a set of rule-based queries, called blocks (see figure 123).

Then, the instantiation process will bound the Web service nodes to the actual Web services (see figure 1234). Finally, the execution of query blocks will return the results (see figure 12345).

Composition flow

Connectors

Connectors link different Web service nodes or instances. Below we highlight some of the basic connectors, including a special form of data flow connectors known as operators.

Sequence is the most basic connector that executes the next Web service in sequence. It specifies both the invocation of some Web service specified in the target variable and also stores the invocation result in the output variable. In its basic form, sequence is a control flow connector but we can augment it to handle the data flow by specifying the data to be passed as the input variable, which is then forwarded to the target Web service for some processing. The role of input variable here is more than just specifying the input parameters of the service to invoke, by considering that the input may have been obtained by some processing earlier by some other service and/or connector (and thus the data flow aspect). Sequence connector takes the following form, the ?inputVariable is optional:

<sequence> <outputVariable>?resultVar</outputVariable> <inputVariable>?sourceVariable</inputVariable> <target>serviceName/node</target> </sequence>
The Split connector specifies the control (and data) split to multiple splitBlocks. The split decision can be based on contents of input data and this special case is called contentbased-split. Further, actual split can take one of three forms: same input data (or control) is forwarded to all splitBlocks, the AND-Split; to at-least one of the splitBlocks, OR-Split and to exactly one of the splitBlocks, XOR-Split:

<split scheme="AND/OR/XOR"> <inputVariable>?sourceVariable</inputVariable> <splitBlock> <condition>some condition</condition> ... </splitBlock> <!--other splitBlocks --> </split>
The split condition is optional and is needed in the case of content based split. Further, the split connector has no output variable to bound the results. The separation between split and aggregation is guided by the different split and aggregation schemes and to handle this, we introduce the aggregate connector below.

The Aggregate connector receives a collection of results, for example from different splitBlocks or output variables. Once a complete set of results has been received, it binds a single aggregated result to the output variable. In order to decide that a set is complete, we introduce the following aggregation schemes: all -all the results should be considered, exactly-one -one of the results should be considered, at-least-one -the first result that is received is considered, and subset -only a subset of results is aggregated. However, when the aggregate connector is coupled with the XOR based split connector, the only possible aggregation scheme is exactly-one.

<aggregate scheme="(all/exactlyOne/at-least-one/subset)"> <outputVariable>?resultVar</outputVariable> <!--some result variables or splitBlocks --> </aggregate> Data operators These operators provide operations such as data transformations and validations for the data to be passed between different components. This includes a large variety of data transformation operations ranging from string manipulation, basic mathematical calculation operations to advance operations such as enriching data from service nodes and others. Some commonly used data transformation and validation operations such as translator, enricher, filter, normalizer and others are discussed in [START_REF] Zahoor | Mashup model and verification using mashup processing network[END_REF].

The proposed set of connectors can be compared to the OWL-S control constructs used for the composite process definition. A major difference is that our connectors can handle both control and data flows. When compared to the sequence connector of OWL-S, our sequence connector is similar but it handles both control and data flows. For the split and aggregation process, two control constructs are introduced in OWL-S named split and split+join. Partial synchronization in OWL-S, i.e to split all and join some subbag, is similar to the proposed split/aggregate schemes. The choice OWL-S construct can be handled using the XOR based split connector while the if-then-else OWL-S control construct maps to the proposed if-then-else connector, which is not discussed due to space limitations. Further, the iterator connectors, similar to the proposed OWL-S iterators can be used, for example to process each of the results returned by some node instead of selecting the best match.

Constraints

For the nodes in composition flow, user can further add constraints that are not only to be satisfied during Web services discovery but also specify one specific path (solution) to choose from all available paths (solutions) for the Web services composition process. These constraints can be in the form of non-functional requirements such as security, reliability, quality requirements. They can also be in the form of some domain specific functional properties (loan duration, interest percentage for the motivating example). The constraints can either be local to some node, can be based on properties related to a fragment of the process or based on the overall composition process. They can also be modified and passed between different nodes.

Example

Let us now review the motivating example and see how the composition flow can be specified. For the CCM scenario, the first part of composition requires Pierre to identify the current cash positions for the bigCo. As the Web service instances are known in advance, Pierre specifies the concrete instances for someBank, someOtherBank and for the ERP System Web services.

He specifies the AND-split as the connector which splits the user request to multiple Web service instances and then specifies the aggregate-all to get the results (see figure 2-1, for simplicity we have not shown the split operation of user request). The generated intermediate language code is shown below:

<aggregate scheme="all"> <outputVariable>?assets</outputVariable> <split scheme="AND"> <!--splitBlocks with sequence to Web services --> </split> </aggregate>

The aggregated information from banks and ERP system, i.e the ?assets variable, is then sequenced to the intelligent decision making system to either opt for investment or loan option (see figure 2-2, sequence is the default connector and is represented by an arrow). The information returned by the decision system will be then filtered to get only the relevant data (see figure 2-2), space limitation restrict us to discuss the generated intermediate language code. We assume that the filtered decision and amount information are bound to ?decision and ?invLoanAmount variables respectively.

The filtered information will then be splited using the XOR split scheme to different financial institutions for possible investment or loan offers. If the decision is to get loan, information is sent to the first splitBlock of the generated intermediate language code shown below. As the bank Web services providing loan offers are not known in advance, Pierre specifies the Web service node of type Bank and provides constraints such as loan period, expected interest percentage and others (see figure 23). For the investment decision, let us further consider that the company wants to invest with a specific priority level; the information is sent to the second splitBlock which will first sequence the data to the credit union service node and in case of no complete offer, some building society service can be contacted (see figure 234). Information returned will then be aggregated by using the aggregate-subset connector. For the credit union and building society nodes, user can also specify constraints such as investment period, and some other non-functional properties (omitted due to the space limitations). Finally the investment or loan offer is filtered and sent to the rating service, which provides rating for the financial institution providing the offer. Again, as the service instance is not known in advance, user specifies Web service node as of type Rating. User can also add a special constraint worksWith, which will allow to filter only the rating services that "work with" the offer service selected earlier (see figure 2345). We will discuss this special construct in section-6. Space limitations restrict us to discuss the generated intermediate language code.

Concrete composition

The generated intermediate language can then be used for the concrete composition process, which is divided into following three phases.

Translation

The concrete composition process starts by converting the intermediate language into a collection of rule-based queries, called blocks (see figure 123). These blocks act as the privacy control constructs as only the exposed results of some block will be available to the later blocks; whereas the unexposed internal details such as the constraints used by the block, will be hidden from other blocks. For each block, the associated query may have some local variables to operate on and possibly some constraints to be satisfied. It exposes its results by binding the output variables which are then available in the blocks to follow.

Instantiation

The translation process will be followed by the instantiation of all the Web service nodes specified by the user to some actual Web service instances (see figure 1234). The instantiation process may however decide to delay the instantiation of the nodes whose invocation is conditional as an attempt to improve performance. The instantiation query block will operate on the knowledge base containing Web service instances with associated properties and will first filter only the Web services of the specified node type. Then, it will further filter the Web services based on the userspecified constraints. The result may be a collection of Web service and in case of a loosely constrained node, the result set can be very large. Our proposal thus aims to choose the best matched Web service based on some user-specified criteria such as the quality rating for the Web service, by assuming that some trusted third-party has quality ratings assigned to services. This choice can also be based on some other non-functional requirements or as our proposal aims to put user in the control of composition process, the user can also manually select the Web service.

If the instantiation result set for a node is empty then we have following possibilities. If some constraint is unsatisfied, user can be given option if she/he wants to relax the constraint. For example the user can decide to relax the quality rating from high to some other level in an attempt to discover new instances. Further, if the worksWith relation is unsatisfied, we need to backtrack to the results of dependent block to select some other instantiation solution and then proceed to finding solution for the current block. The process continues until all backtrack solutions have been explored. Finally when none of above two situations hold, the composition process fails with notifying the user of the intermediate results and unbound node.

The worksWith dependency

We consider that a service worksWith some other service using the modified form of the composability rules discussed in [START_REF] Narayanan | Simulation, verification and automated composition of web services[END_REF]. These rules consider the syntactic and semantic properties of Web services. Syntactic rules include the rules for operation modes (one-way, request-response. . . ), and the rules for binding protocols and data formats of interacting services. However, we can relax the rule for data formats by considering that two services providing data in different formats can still work with each other, by using the translate transformation operation as discussed earlier in section 5-1.

The Semantic rules include the message composability rule which defines that two Web services are composable only if the output message of one service is compatible with the input message of another service. In case of semantic Web services described using OWL-S, it is important to consider that the input and output parameters are defined in the domain ontology as specifying them as datatypes add very little to semantics ([10] has a detailed discussion). Further, the operation semantic composability defines the compatibility between the domains, categories and purposes of two services while the qualitative composability defines the requester's preferences regarding the quality of operations for the composite service. Then, the composition soundness considers whether a composition of services is reasonable, see [START_REF] Narayanan | Simulation, verification and automated composition of web services[END_REF] for details.

Backtracking

The backtracking process involves finding an alternative to some previously chosen node instantiation solution. Backtracking is needed when the worksWith relation for some node is unsatisfied resulting in empty result set.

Propagation

Once the backtracking process execution terminates, resulting in a newly chosen solution (instance), the composition solution must be recomputed and may require the propagation of newly chosen solution. This would likely be the case when a (partial) solution to the composition process has already been determined and backtracking to some higher node (in hierarchal order) may result in propagating the new solution. Further, propagation may also be needed when the user fine tunes the solution by manually selecting some other Web service after the instantiation process.

The propagation process will require recomputing the composition and this may result in significant overhead to re-instantiate the service nodes. Our proposal aims to reinstantiate only the Web service nodes that have dependancy on the node to backtrack (either a worksWith dependancy or a data dependancy).

Execution

The instantiation phase will be followed by the execution phase, which will return the results of the Web services composition (figure 12345).

Implementation details

Architecture

In order to test our proposal, we have implemented a Java based application and tested it with multiple examples, including the motivating example. Below we briefly discuss various implementation related concepts.

Figure 3. Implementation Architecture

OWL-S is a OWL-based Web service ontology providing constructs for describing a Web service in terms of a service profile (which describes what a service provides and allows service classification using ServiceCategory attribute and specification of non-functional properties using Servi-ceParameter attribute), the process model (which describes how the service works) and the service grounding (which specifies concrete details such as message formats, network addresses used and others).

The Semantic Web Rule Language (SWRL) is intended to be the rule language for the semantic web. The SWRL rules are written in terms of OWL classes, properties and individuals. SWRL also provides a set of core built-ins for strings manipulation, basic mathematical operations. . . It also allows to extend the core built-ins to add user defined built-ins. An example of a SWRL rule to express that a person with a older female sibling has a older sister can be written as:

In the rule above, Person is a class with a sub-class named Woman and hasSibling and hasOlderSister are OWL properties with domain and range of the class Person. The rule also uses the hasAge property (with domain as Person and range of primitive datatype Integer) and the SWRL builtin (swrlb:greaterThan) to add hasOlderSister property to all individuals who have older female siblings. The Semantic Query-Enhanced Web Rule Language (SQWRL) adds querying capabilities to SWRL by providing primitives to select, count and perform other operations on the results of a SWRL rule. Finally, SQWRL queries (and so as SWRL rules) require a rule-solver and for that we have used the JESS rule-solver (see figure-3 for the overall implementation architecture).

Example

For the implementation, we have programmed Java based Web services to return sample data form different systems. We have also created their OWL-S descriptions which include the specification of the non-functional properties using the approach specified in DAML2 OWL-S examples. However, our proposal can also adapt the various QoS extensions to the OWL-S such as QoS-MO [START_REF] Tondello | The qos-mo ontology for semantic qos modeling[END_REF], QoSOnt [START_REF] Dobson | Qosont: a qos ontology for service-centric systems[END_REF] and other approaches that extend OWL-S for specifying QoS properties. For the CCM scenario, the concrete composition process starts with the translation of intermediate language code into a set of query blocks. Below we discuss the query blocks for various parts of the composition, for simplicity we will not discuss the node instantiation process separately and will highlight the instantiation blocks as they are encountered in the control flow of the composition process.

The first part of the composition (see figure 2-1), is static and although it does not require querying the rule base to search for Web services and invocation using rule engine; we here provide implementation of how such approach can be used.

service:Service(SomeBankService) ∧ service:supports( SomeBankService,?SBSGrounding) ∧ grounding:hasAtomic ProcessGrounding(?SBSGrounding, ?SBSAtProcGrnding)∧ grounding:wsdlDocument(?SBSAtProcGrnding,?SBSWsdl)∧ service:Service(SomeOtherBankService)∧... connectors:aggregateAll(?assets,?SBSWsdl, ?SOBSWsdl,?ERPSWsdl) → sqwrl:select(?assets)

We have created a SQWRL query which searches through the OWL-S service model to get the grounding information for the Web services (we have only presented the query for SomeBankService) and then passes the URI's to a custom SWRL built-in, aggregateALL. This custom builtin then calls the Web services to get results and aggregates/bounds them to the output variable, ?assets. We can then sequence the variable ?assets to the decision-SystemService again using the custom SWRL built-in sequence. The result of the operation will be available in the variable ?DSResult. We need to then filter the relevant message parts, such as decision and amount, from the result.

connectors:sequence(?DSResult,?assets,"decisionSystem Service") ∧ connectors:filter( ?InvLoanAmount, ?DSResult,"Amount") ∧ connectors:filter(...) → sqwrl:select(?decision, ?InvLoanAmount)

Next the contents of the ?decision variable, investment or loan decision, will be used to either opt for the loan or investment offer. Let us first consider the case that the loan offer decision is chosen. According to the composition flow, the loan request is sent to the bank service, not known in advance and which should be selected based on some constraints. service:Service(?loanBank) ∧ service:presents(?loanBank, ?lbProfile) ∧ profile:serviceCategory(? lbProfile, ?lbCategory) ∧ profile:code(? lbCategory, ?categoryCode) ∧ swrlb:equal(?categoryCode, "522110") ∧ profile:serviceParameter(?lbProfile,?SPReliability)∧ profile:sParameter(?SPReliability, HighlyReliable) ∧ profile:serviceParameter(?lbProfile, ?SPDuration) ∧ profile:sParameter(?SPDuration, 7_Years) ∧ ... other constraints ∧ service:supports(?loanBank, ?lbGrounding) ∧ grounding:ha sAtomicProcessGrounding(?lbGrounding,?lbAtProcGrnding)∧ grounding:wsdlDocument (?lbAtProcGrnding, ?loanBankWsdl) → sqwrl:select(?loanBank, ?loanBankWsdl)

The query first selects the loan bank services based on the Web service classification code specified in the service-Category attribute of the service profile. We have used NAICS 3 categorization for the Web services and the code value 522110 is for commercial banking. So the initial part of the query will select only the bank services. Next we specify the non-functional constraints such as reliability and some functional properties such as the loan duration and interest percentage. Finally, in the last part of query we get the selected Web service wsdl URI from its grounding. As our approach proposes to select only one best match service, for the implementation we select the first Web service instance we get after executing the query.

Running the above query on our services repository will return two Web service instances, someLoanBankService and someOtherLoanBankService and we will select the someLoanBankService to be used. Next, we get the loan offer from the someLoanBankService using the sequence operation, space limitation restrict to discuss the query. Finally, we send the offer we have received from the someLoanBankService to the rating service, and again as the Web service is not known in advance, we specify the constraints and use query to search for the rating service as below.

service:Service(?ratingService) ∧ service:presents(?.... ∧ profile:code(?rsCategory, ?categoryCode) ∧ swrlb:equal(?categoryCode, "561450") ∧ ... some constraints ... ∧ worksWith(?loanBank, ?ratingService)∧ → sqwrl:select(?ratingService, ?rsWsdl)

The query is similar to the one we mentioned earlier for the bank service, the NAICS code "561450" is for the rating services. In the constraints, we introduce the property worksWith, i.e we want to only search for the rating services that actually "work with" the someLoanBankService.

For the implementation we have created a OWL-S property named worksWith that specifies which bank, credit union and building society services work with which rating service. This property can be handled dynamically by adding SWRL rules for service composability rules discussed earlier. The selected someLoanBankService, does not work with any rating service and the result set of the above mentioned query will be empty. Thus we need to backtrack and select some other service from the results of previous query, that is the someOtherLoanBankService and then search for the rating services that work with it. This time we find the someOtherRatingService and next we get the offer rating from the service using the sequence operation query (as similar to the decisionSystemService query).

Let us also consider the case when investment decision is chosen by the decision system, as similar to the queries mentioned above; we first get the credit union service (using the NAICS code "522130" for credit unions) and the corresponding offer by the selected service. Further, let us consider that the selected Web service does not provide the investment option for the complete investment amount and thus some building society service must be contacted for the remaining amount. The query below handles this, assuming the credit union offer amount is bound to the variable ?cuAmount by some earlier query. service:Service(?buildingSociety)∧service:presents (?buildingSociety, ?bsProfile) ∧ .... swrlb:equal (?bsCategoryCode, "522294") ∧... swrlb:subtract (?amntRemaining,?InvLoanAmount,?cuAmount)∧ swrlb:greaterThanOrEqual (?amntRemaining, 10000) → sqwrl:select(?buildingSociety,?bsWsdl,?amntRemaining)

The above query only selects the building society service is the amount remaining, obtained after subtracting the credit union offer amount from the total amount, is greater than 10000. This serves as an example of how constraints can be modified and passed between nodes.

Conclusion

In this paper we have proposed a rule-based declarative framework for the semi-automatic Web services composition problem. Our approach requires the end-user to build the composition flow by specifying the Web service instances/types and data/control flow connectors to link them. The user interface is backed up with a declarative language, called intermediated language which is then used to instantiate the concrete composition process which involves translating the declarative language to rule based queries, called blocks, instantiating the Web service types and finally executing the process to get the results. We have also presented a sample Corporate Cash Management (CCM) scenario, that highlights our approach. A sample implementation to the sample scenario has been provided to discuss how our approach can be realized using the known Web services standards.

5 4 Figure 1 .

 541 Figure 1. Proposed model components

Figure 2 .

 2 Figure 2. Motivating Example

  <aggregate scheme="exactlyOne"> <!--Loan or Investment--> <outputVariable>?offer</outputVariable> <split scheme="XOR"> <inputVariable>?decision</inputVariable> <splitBlock> <!--Loan decision --> <condition>?decision=Loan<

http://www.oasis-open.org/presentations/security/KCronin.ppt

http://www.daml.org/services/owl-s/1.1/examples.html

http://www.census.gov/eos/www/naics/


K Hauschild

Preliminary simulations for the focal plane detection system of S 3 version 1.0

In this report preliminary Geant4 simulations for the focal plane detection system of S 3 using standard, off-the-shelf, germanium and silicon detectors are described and results for various proposed schemes are given.

1 Si detectors 1.1 Implantation detector These preliminary simulations are based around using a 100×100 mm 2 double sided Silicon 128-strip detector of 300 µm thickness which is currently available from Micron. This detector is mounted on a 133×128 mm 2 board (apparently Micron is able to make these boards such that only two adjacent sides are significantly larger than the Si). The board is assumed to be 1.5 mm thick.

While the 100×100 mm 2 geometry does not quite match the 140×60 mm 2 focal plane from the ion-optics simulations of Manikonda et al, it is a simple starting point to get an idea of the γ-ray and conversion-electron efficiencies to be expected. Furthermore, for the case of the 292 116 ion-optics simulations a 100×100 mm 2 detector would result in a transmission efficiency of 48.7% (collecting 4 charge states) instead of 55.1% (5 charge states) for the 140×60 mm 2 detector. Additionally, for most spectroscopic runs a dispersive mass analysing mode is unnecessary. If there is no other mode of operation possible the effect of an asymmetric focal plane on the γ-ray detection efficiency needs to be investigated.

Veto detector

A veto detector of the same size has been placed 10 mm downstream from the implantation detector. This gap is a guestimate, but the fact that the support boards can be made with the connectors on two adjacent sides should allow the two detectors to be reasonably close. There is an additional 10 mm gap between the Veto support board and the vacuum chamber back-plate.

Si tunnel

Four 1 mm thick Si detectors of 100 mm width perpendicular to the beam axis and varying length along the beam axis have been simulated. The support board has also been assumed to be 1.5 mm thick, but, unlike the implant and veto boards, it has not been simulated with a central hole. The support board extends 20 mm upstream of the tunnel as an indication of the position of a support/cooling frame.

Ge detectors

Simulations have been performed with standard Ge detectors : Eurogam Phase-I's, a Phase-I detector modified by the GABRIELA collaboration, EXOGAM clovers and larger clovers similar in size to those at GREAT. This conservative approach has been taken for two reasons :

• Simplicity : these detectors are well known and do not complicate commissioning of S 3

• Cost : until money is actually allocated for a focal plane using existing detectors is the only option

Visualisation

Figure 1 shows a representation of these focal plane detectors using Geant4. In the left panel, the central dark blue object is the implantation detector, which is surrounded by the blue coloured silicon tunnel. The beige objects are the support boards for the silicon tunnel, implant and veto detectors. In this example a ring of ten Phase-I Ge detectors (yellow) has been placed around the vacuum chamber.

The panel on the right of Figure 1 shows the same detector system, but this time looking along the beam-line axis directly at the implantation detector giving an indication of the space available either side of the support boards for cables, support frame, cooling lines etc. The inner radius of the vacuum chamber (coloured grey) is 103 mm and has a thickness of 2 mm. The ten Phase-I's are also visible : the germanium crystal is yellow and the end-cap is grey. (The green lines by the end-cap indicate the vacuum.) At this distance it would not be possible to use the BGO shields, nor would it be possible to use passive shielding.

Results

The simulated singles conversion-electron and gamma-ray detection efficiency using various detector arrangements are given in the following section. The electrons and gamma-rays were emitted from a distribution of points on the implantation detector using a recoil distribution calculated by Andrey Popeko for 22 Ne(E 1/2 = 115 MeV) on 238 U(0.2mg/cm 2 U in U 3 O 8 )→ 255 No+5n transmitted through the upgraded VASSILISSA : a 2D gaussian distribution with σ x = σ y =46 mm. For a specialised S 3 solution recoil distributions for S 3 are needed.

Conversion electrons

Simulations were performed with tunnel detectors of varying lengths along the beam-line axis. The width remained constant at 100 mm and thickness was 1 mm. Waely asked me to make an unrealistically long detector just to see what the asymptotic efficiency is. The results are shown in Fig. 4 for a 150-keV electron.

Length of tunnel along "beam" axis [mm]

Gamma-rays : Phase-I's only

Ten standard Phase-I Eurogam detectors were placed in a ring around the implantation detector at a radius of ∼110 mm. A modified (shortened end-cap) Phase-I was placed 2 mm from the focal plane vacuum chamber back-plate axially aligned with the beam-line. The simulated γ-ray efficiency curve is given in Fig. 5.

Gamma-rays : EXOGAM clovers

As above, but with 8 EXOGAM clovers (60 mm diam. crystals) in a ring (also at ∼110 mm) and a ninth EXOGAM clover facing upstream. The simulated γ-ray efficiency curve is given in Fig. 6.

-

Comments

• With the recoil distribution used little conversion electron detection efficiency is gained by having a tunnel ≥80 mm.

• Even an array of tried, trusted, but aging Phase-I detectors provides a reasonably efficient fallback option.

• Adding a modified (larger) EXOGAM clover in the up-stream position would increase the overall efficiency by ∼50% in relative terms.

• A close packed ring of 8 EXOGAM detectors provides the same efficiency as the modified (larger diameter crystal) EXOGAM detectors which have to be pushed further back (provides more space).

-A ring of 8 clovers is almost twice as efficient as a ring of 10 phase-I's. Therefore a relative increase of ∼35% in efficiency would occur if the larger Clover+Phase-I ring array was replaced by the larger Clover+Clover ring.

Additional information

• Chamber back-plate thickness = 1 mm

• NO add-back has been performed for the clover detectors. It's use must be on a case-by-case basis.

Figure 1 :

 1 Figure 1: Geant4 view of a simple S 3 focal plane. The viewpoint is from up-stream.

Figure 2 :

 2 Figure 2: A comparison of a modified Phase-I (left), EXOGAM (middle) and GREAT-like Clover in close geometry to the focal plane Si detectors.

Figure 3 :

 3 Figure 3: The "If I were a rich man" all Clover array.

Figure 4 :

 4 Figure 4: Simulated 150-keV electron detection efficiency for the tunnel as a function of tunnel length.

Figure 5 :

 5 Figure 5: Simulated γ-ray singles detection efficiency for a Phase-I Ge array.

Figure 6 :

 6 Figure 6: Simulated γ-ray singles detection efficiency for an EXOGAM clover array.

4. 4 Figure 7 :

 47 Figure 7: Simulated γ-ray singles detection efficiency for a modified EXOGAM clover array.


Alain Pham

Ngoc Dinh

Duc Dang

Pham Trong

Hoang Quan

Huy Nguyen

Tuan

Nguyen Hoang Quan

Tuan Huy

Trong

Pham Hoang Quan

A new stability results for the backward heat equation

Keywords: Backward heat problem, Ill-posed problem, Fourier Transform, Contraction principle Mathematics subject Classification 2000: 35K05, 35K99, 47J06, 47H10. 1

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Transient heat conduction phenomena are generally governed by the parabolic heat conduction equation and if the initial temperature distribution and boundary conditions are specified, then this, in general, leads to a well posed problem which may easily be solved numerically by using various methods.

However, in many practical situations when dealing with a heat conducting body it is not always possible to specify the boundary conditions or the initial temperature. For example, in practice, one may have to investigate the temperature distribution and the heat flux history from the known data at a particular time. In other words, it may be possible to specify the temperature distribution at a particular time, say t = T > 0, and from this data the question arises as to whether the temperature distribution at any earlier time t < T can be retrieved. This is usually referred to as the backward heat conduction problem (BHCP), or the final boundary value problem. The systematic study of the backward heat conduction problem is of rather recent origin, although isolated considerations have been given to such problems for several hundred years. In general no solution which satisfies the heat conduction equation, the final data and the boundary conditions exists. Further, even if a solution did exist, it would not be continuously dependent on the boundary and the final data, see Payne [START_REF] Campbell | Continuous dependence results for inhomogeneous ill-posed problems in Banach space[END_REF]. Thus the BHCP is an example of an ill-posed problem that is impossible to solve using classical numerical methods and requires special techniques to be employed, see Hadamard [START_REF] Campbell | Regularization of the backward heat equation via heatlets[END_REF]. Conditions for which the BHCP becomes well-posed have been investigated by Miranker [START_REF] Clark | Quasireversibility methods for non-well posed problems[END_REF] and Cannon and Douglas [START_REF] Denche | A modified quasi-boundary value method for ill-posed problems[END_REF]. These studies introduced additional hypotheses which restrict the class of functions to which the solution must belong, and which are seldom satisfied. Therefore numerical methods of solution appear more useful. Thus regularization techniques, see for example Cannon [START_REF] Feng | Numerical approximation of solution of nonhomogeneous backward heat conduction problem in bounded region[END_REF] and Han et al. [START_REF] Fu | On three spectral regularization method for a backward heat conduction problem[END_REF],

have been developed for solving the BHCP. Different methods, based on a perturbation of the original parabolic heat equation were proposed by Lattes and Lions [START_REF] Fu | A modified method for a backward heat conduction problem[END_REF] and Lesnic et al. [START_REF] Fu | Zhi Fourier regularization for a backward heat equation[END_REF]. These methods consist of replacing the operator by a perturbed higher order one that holds better invertibility features.

In this paper, we consider the following problem

   u t -u xx = 0, (x, t) ∈ R × (0, T ), u(x, T ) = ϕ(x), x ∈ R, (1)
where T > 0 be a given and ϕ(x) are given. We want to retrieve the temperature dis-tribution u(x, t) for 0 ≤ t < T. Of course, since the data ϕ(.) is based on (physical) observations, there will be measurement errors, and we would actually have as data some function ϕ ǫ ∈ L 2 (R) , for which ϕ -ϕ ǫ ≤ ǫ, where . denotes the L 2 -norm, the constant ǫ > 0 represents a bound on the measurement error. That is to say, practically, we need to consider the following problem,

   u t -u xx = 0, (x, t) ∈ R × (0, T ), u(x, T ) = ϕ ǫ (x), x ∈ R, (2)
Notice the reader that the problem ( 1) is investigated in some recent papers of ChuLiFu [START_REF] Fu | On three spectral regularization method for a backward heat conduction problem[END_REF][START_REF] Fu | A modified method for a backward heat conduction problem[END_REF][START_REF] Xiong | Error estimates of a difference approximation method for a backward heat conduction problem[END_REF] and of other authors such as Lien [START_REF] Duc | Regularization of a discrete backward problem using coefficients of truncated Lagrange polynomials[END_REF],Murniz [START_REF] Muniz | A comparison of some inverse methods for estimating the initial condition of the heat equation[END_REF], et al . To the authors knowledge, so far there are many papers on the backward heat equation, but theoretically the error estimates of most regularization methods in the literature are Holder type, i.e.,

u(., t) -v ǫ (., t) ≤ Cǫ k , k > 0. ( 3
)
where C is the constant depend on u, k is a constant is not depend on t, u . As we know, ǫ k converges to zero more quickly than the logarithmic term. So, the major object of this paper is to provide new regularization method to established the Holder estimates such as [START_REF] Campbell | Regularization of the backward heat equation via heatlets[END_REF]. We give a new approximation problem and investigate the error estimate between the regularization solution and the exact one.

The remainder of the paper is divided into three sections. In Section 2, we establish the approximated problem and show that it is well posed. Then, we also estimate the error between an exact solution u of Problem (1) and the approximation solution v ǫ (., t) with the Holder type. Finally, a numerical experiment will be given in Section 3.

2 Regularization and error estimates.

Let φ(ξ) = 1 √ 2π +∞ -∞ ϕ(x)e -iξx dx
be the Fourier transform of the function ϕ ∈ L 2 (R). We assume u(x, t) is the unique solution of (1). Using the Fourier transform technique to problem (1) with respect to the variable x, we can get the Fourier transform û(ξ, t) of the exact solution u(x, t) of problem

(1)    ût (ξ, t) = (iξ) 2 u(ξ, t), û(ξ, T ) = φ(ξ), ξ ∈ R, (4)
The solution to equation ( 4) is given by û(ξ, t) = e (T -t)ξ 2 φ(ξ). [START_REF] Denche | A modified quasi-boundary value method for ill-posed problems[END_REF] or equivalently,

u(x, t) = 1 √ 2π +∞ -∞ e (T -t)ξ 2 φ(ξ)e iξx dξ. (6)
Since t < T, we know from ( 6) that, when ξ becomes large, exp (T -t)ξ 2 increases rather quickly. Thus for û(ξ, t) ∈ L 2 (R) with respect to ξ, the exact data function φ(ξ) must decay rapidly as |ξ| → ∞. Small errors in high-frequency components can blow up and completely destroy the solution for 0 ≤ t < T .As for the measured data ϕ ǫ (x), its Fourier transform φǫ (ξ) is merely in L 2 (R).

Let p > 1 be a constant number. We approximated problem (3) by pertubing the Fourier transform of final value ϕ as follows

       ∂ ŵǫ (ξ, t) ∂t = (iξ) 2 ŵǫ (ξ, t), ŵǫ (ξ, T ) = e -T ξ 2 βe (p-1)T ξ 2 + e -T ξ 2 φ(ξ), ξ ∈ R, (7)
The formal solution of ( 7) is also easily seen to be ŵǫ (ξ, t) = e -tξ 2 βe (p-1)T ξ 2 + e -T ξ 2 φ(ξ), [START_REF] Fu | A modified method for a backward heat conduction problem[END_REF] or

w ǫ (x, t) = 1 √ 2π +∞ -∞ e -tξ 2 βe (p-1)T ξ 2 + e -T ξ 2 φ(ξ)e iξx dξ, (9)
where β is a positive number such that β > 0.

Let v ǫ (., t) be the approximated solution given by

v ǫ (x, t) = 1 √ 2π +∞ -∞ e -tξ 2 βe (p-1)T ξ 2 + e -T ξ 2 φǫ (ξ)e iξx dξ, (10)
Note that if β is chosen small, then for small |ξ|,

e -tξ 2
βe (p-1)T ξ 2 +e -T ξ 2 in ( 8) is close to e (T -t)ξ 2 in (5).

For ξ, x, β > 0, 0 ≤ a ≤ b, we prove the following inequality i).

e

aξ 2 1 + βe bξ 2 ≤ β -a b . (11)
ii).

e aξ 2 ξ 2 (1 + βe bξ 2 ) ≤ b ln( 1 β ) β -a b (12)
Thus, we have

e aξ 2 1 + βe bξ 2 = e aξ 2 (1 + βe bξ 2 ) a b (1 + βe bξ 2 ) 1-a b ≤ e aξ 2 (1 + βe bξ 2 ) a b ≤ β -a b . For 0 ≤ t ≤ s ≤ T , denote A(ξ, t) = exp{-tξ 2 } β exp{(p -1)T ξ 2 } + exp{-T ξ 2 } , B(ξ, s, t) = exp{(s -t -T )ξ 2 } β exp{(p -1)T ξ 2 } + exp{-T ξ 2 } .
Using the inequality [START_REF] Lattès | Méthode de Quasi-réversibilité et Applications[END_REF], we obtain

A(ξ, t) = e (T -t)ξ 2 1 + βe pT ξ 2 ≤ β t-T pT (13) B(ξ, s, t) = e (s-t)ξ 2 1 + βe pT ξ 2 ≤ β t-s pT . ( 14
)
Theorem 1. Let ϕ ∈ L 2 (R). Then unique solution of the problem (6) depends on the final value ϕ,i.e, if w, v are the solution of the problem (6)corresponding to the final values ϕ and ω, then

w(., t) -v(., t) ≤ β t-T pT ϕ -φ .
Proof of Theorem 1.

Let w and v be two solution of the problem (6) corresponding to the final values ϕ and φ.

Using Parseval inequality, we have

w(., t) -v(., t) 2 = ŵ(., t) -v(., t) 2 ≤ +∞ -∞ A(ξ, t) φ(ξ) -φ(ξ) 2 dξ ≤ β 2t-2T pT +∞ -∞ φ(ξ) -φ(ξ) 2 dξ ≤ β 2t-2T pT φ -φ 2 ≤ β 2t-2T pT ϕ -φ 2 . Hence w(., t) -v(., t) ≤ β t-T pT ϕ -φ . Remark 1.
In [START_REF] Clark | Quasireversibility methods for non-well posed problems[END_REF][START_REF] Trong | Regularization and error estimates for nonhomogeneous backward heat problems[END_REF], the stability of magnitude is e T ǫ . In [START_REF] Fu | On three spectral regularization method for a backward heat conduction problem[END_REF][START_REF] Quan | A nonlinearly backward heat problem: uniqueness, regularization and error estimate[END_REF][START_REF] Dang Duc Trong | TuanA nonlinear case of the 1-D backward heat problem: Regularization and error estimate[END_REF], the stability estimate is of order

ǫ t T -1 .
In our paper, we give a better estimation of the stability order, which is

Cβ t T -1 T 1+ln( T β ) 1-t T .
It is easy to see that the order of the error, introduced by small changes in the final value g, is less than the order given in [START_REF] Quan | A nonlinearly backward heat problem: uniqueness, regularization and error estimate[END_REF][START_REF] Dang Duc Trong | TuanA nonlinear case of the 1-D backward heat problem: Regularization and error estimate[END_REF]. This is among of the advantages of our method.

Theorem 2. Let w ǫ and v ǫ defined by ( 9) and [START_REF] Dinh | Stability results for the heat equation backward in time, to appear[END_REF]. Then one has

w ǫ (., t) -v ǫ (., t) ≤ β t-T pT ǫ. ( 15
)
Proof of Theorem 2. Using Theorem 1, we get

w ǫ (., t) -v ǫ (., t) ≤ β t-T pT ϕ ǫ -ϕ ≤ β t-T pT ǫ. ( 16
)
Theorem 3. Let u be the exact solution of problem such that u(.,

0) ≤ E 1 . Then one has u(., t) -v ǫ (., t) ≤ ǫ t T (E 1 + 1).
Proof of Theorem 2. Using (11), we have

u(., t) -w ǫ (., t) 2 = +∞ -∞ |û(ξ, t) -ŵβ (ξ, t)| 2 dξ = +∞ -∞ (e (T -t)ξ 2 -A(ξ, t)) φ(ξ) 2 dξ = +∞ -∞ βe pT ξ 2 e (T -t)ξ 2 (1 + βe pT ξ 2 ) φ(ξ) = +∞ -∞ βe (pT -t)ξ 2 (1 + βe pT ξ 2 ) û(ξ, 0) 2 dξ ≤ β 2 β 2t-2T pT +∞ -∞ |û(ξ, 0)| 2 dξ ≤ β 2t pT E 2 1 .
Therefore u(., t) -w ǫ (., t) ≤ β t pT E 1 .

From β = ǫ p and using the inequality, we obtain u(., t) -v ǫ (., t) ≤ u(., t) -w ǫ (., t) + w ǫ (., t) -v ǫ (., t)

≤ β t pT E 1 + β t-T pT ǫ ≤ ǫ t T (E 1 + 1).
Remark 2. Notice that the convergence estimate in Theorem 1 does not give any useful information on the continuous dependence of the solution at t = 0. This is common in the theory of ill-posed problems, if we do not have additional conditions on the smoothness of the solution. To retain the continuous dependence of the solution at t = 0, instead of (2.5), one has to introduce a stronger a priori assumption.

We denote . k be the norm in Sobolev space H k (R), k > 0 defined by

u(., 0) k := +∞ -∞ (1 + ξ 2 ) k |û(ξ, 0)| 2 dξ 1 2
.

Theorem 3. Let u be the exact solution of problem such that u(., 0

) 2 ≤ E 2 . Let β = ǫ , then one has u(., t) -w ǫ (., t) ≤ pT ln( 1 ǫ ) ǫ t pT E 2 + ǫ t-T +pT pT . ( 17
)
Proof of Theorem 3.

u(., t) -w ǫ (., t) 2 = +∞ -∞ βe (pT -t)ξ 2 ξ 2 (1 + βe pT ξ 2 ) ξ 2 û(ξ, 0) 2 dξ ≤ +∞ -∞ ξ 4 û2 (ξ, 0)dξ ≤ pT β ln( 1 β ) β t-pT pT 2 +∞ -∞ ξ 4 û2 (ξ, 0)dξ ≤ pT β ln( 1 β ) β t-pT pT 2 u(., 0) 2 2 ≤ pT ln( 1 β ) β t pT E 2 .
From β = ǫ and using the inequality, we obtain u(., t) -v ǫ (., t) ≤ u(., t) -w ǫ (., t) + w ǫ (., t) -v ǫ (., t)

≤ pT ln( 1 ǫ ) ǫ t pT E 2 + ǫ t-T +pT pT . Remark 3.
1. In t = 0, the error (17) becomes

u(., 0) -v ǫ (., 0) ≤ pT ln( 1 ǫ ) E 2 + ǫ -T +pT pT . ( 18
)
It follows from p > 1 that the right hand side of (18) converges to zero when ǫ → 0. This error is the same order as Theorem 3.1 in paper [START_REF] Fu | A modified method for a backward heat conduction problem[END_REF] (see page 566) and Theorem 2.1 in paper [START_REF] Fu | Zhi Fourier regularization for a backward heat equation[END_REF].

2.Since [START_REF] Tautenhahn | Optimality for ill-posed problems under general source conditions[END_REF], the first term of the right hand side of ( 17) is the logarithmic form, and the second term is a power, so the order of ( 17) is also logarithmic order. It is the same order as some results which is mentioned in Remark 2. This often occurs in the boundary error estimate for ill-posed problems. To retain the Holder order in [0, T ], we introduce a different priori assumption.

Theorem 4.

Assume that there exist a positive number γ ∈ (0, pT ) such that +∞ -∞ e 2γξ 2 û(ξ, 0)dξ < E 2 3 .

Let β = ǫ and h = min{γ, (p -1)T }. Then, one has

u(., t) -w ǫ (., t) ≤ ǫ t+h pT (E 3 + 1). ( 19
)
Proof of Theorem 4.

From , we get u(., t) -w ǫ (., t

) 2 = +∞ -∞ |û(ξ, t) -ŵβ (ξ, t)| 2 dξ = +∞ -∞ βe pT ξ 2 e (T -t)ξ 2 (1 + βe pT ξ 2 ) φ(ξ) = +∞ -∞ βe pT ξ 2 1 + βe pT ξ 2 û(ξ, t) 2 dξ = +∞ -∞ βe (pT -t-γ)ξ 2 1 + βe pT ξ 2 e γξ 2 û(ξ, 0) 2 dξ. (20)
Using the inequality (11), we have

βe (pT -t-γ)ξ 2 1 + βe pT ξ 2 ≤ ββ t+γ-pT pT . (21)
Combining ( 20) and ( 21), we get

u(., t) -w ǫ (., t) 2 ≤ β 2t+2γ pT +∞ -∞ e 2γξ 2 û(ξ, 0)dξ ≤ β 2t+2γ pT E 2 3 .
From β = ǫ and using the inequality, we obtain u(., t) -v ǫ (., t) ≤ u(., t) -w ǫ (., t) + w ǫ (., t) -v ǫ (., t)

≤ β t+γ pT E 3 + β t-T pT ǫ ≤ ǫ t+h pT (E 3 + 1). Remark 4.
1. In t = 0, the error (19) becomes u(., t) -w ǫ (., t) ≤ ǫ h pT (E 3 + 1).

2. Suppose that E ǫ = v ǫ -u be the error of the exact solution and the approximate solution. In most of results concerning the backward heat, then optimal error between is of the logarithmic form. It means that

E ǫ ≤ C ln T ǫ -m
where m > 0. The error order of logarithmic form is investigated in many recent papers, such as [START_REF] Clark | Quasireversibility methods for non-well posed problems[END_REF][START_REF] Fu | A modified method for a backward heat conduction problem[END_REF][START_REF] Denche | A modified quasi-boundary value method for ill-posed problems[END_REF][START_REF] Trong | Regularization and error estimates for nonhomogeneous backward heat problems[END_REF][START_REF] Dang Duc Trong | TuanA nonlinear case of the 1-D backward heat problem: Regularization and error estimate[END_REF][START_REF] Duc | A nonhomogeneous backward heat problem: Regularization and error estimates[END_REF].

To illustrate this, we can enumerate some more recent papers considering the errors of logarithmic order.

Let u and v ǫ be exact solution and the approximated solution respectively.

In [START_REF] Dang Duc Trong | TuanA nonlinear case of the 1-D backward heat problem: Regularization and error estimate[END_REF][START_REF] Duc | A nonhomogeneous backward heat problem: Regularization and error estimates[END_REF] , the error is given the form v ǫ (., t) -u(., t) ≤ C 1 1 + ln T ǫ .

In recently, Feng Xiao-Li and coauthors [START_REF] Feng | Numerical approximation of solution of nonhomogeneous backward heat conduction problem in bounded region[END_REF] gave the error estimates as follows From the discussed error, we can see that most of recent regularization methods established the logarithimic stability. The convergence rates in here is very slowly.

In Tautenhahn and Schroter [START_REF] Tautenhahn | On optimal regularization methods for the backward heat equation[END_REF], the authors proved that the best possible worst case error for identifying u(t) is given by E ǫ = Dǫ .

In [START_REF] Fu | Zhi Fourier regularization for a backward heat equation[END_REF], ChuLiFu and his coauthors esrablished the logarithimic order of the form u(., t) -u δ,ξmax

  v α,δ (.) -u(.)

1 (

 1 In 2007, Zhi Qian et al.[START_REF] Fu | A modified method for a backward heat conduction problem[END_REF] (See Remark 3.6, p.570)gave the error estimation in t = 0 for (2) as follows u(., 0 -v(., 0 ≤


Nicolas Jacon

CONSTRUCTIBLE REPRESENTATIONS AND BASIC SETS IN TYPE B

Constructible representations and basic sets in type B

Introduction

One of the main problems in the modular representation theory of Hecke algebras of finite Weyl groups is to find "good" parametrizations of the set of simple modules. There is a natural way to solve that problem by studying the associated decomposition matrices. In fact, in characteristic zero, using these matrices, it is possible to prove the existence of certain indexing sets called "basic sets" which are in natural bijection with the set of simple modules for the Hecke algebra. Once we have the existence of these sets, it is another problem to have an explicit characterization of them. This has been achieved in type A n-1 by Dipper and James [START_REF] Dipper | Representations of Hecke algebras of general linear groups[END_REF], in type B n combining works by M. Chlouveraki, M.Geck, and the author [START_REF] Chlouveraki | Schur elements and basic sets for cyclotomic Hecke algebras[END_REF], [START_REF] Geck | Canonical basic sets in type Bn[END_REF], in type D n by M. Geck [START_REF] Geck | On the representation theory of Iwahori-Hecke algebras of extended finite Weyl groups[END_REF] and the author [START_REF] Jacon | Sur les représentations modulaires des algèbres de Hecke de type Dn[END_REF] and for the exceptional types by Geck, Müller and Lux, [START_REF] Geck | The decomposition numbers of the Hecke algebra of type E 6[END_REF], [START_REF] Geck | The decomposition numbers of the Hecke algebra of type F 4[END_REF], [START_REF] Müller | Zerlegungszahlen für generische Iwahori-Hecke Algebren von exzeptionellem Typ[END_REF], [START_REF] Müller | Decomposition numbers for generic Iwahori-Hecke algebras of non-cristallographic type[END_REF]. Importantly, these results remain valid in positive characteristic under the assumptions of certain Lusztig conjectures. We refer to [START_REF] Geck | Modular representations of Hecke algebras[END_REF] for a survey of these results.

In the case of type B n , the theory of basic sets provides several natural ways to label the same set of simple modules. In this paper, we are mainly interested on the connections between these various basic sets. First, we show the existence of analogues of basic sets for other types of representation introduced by Lusztig: the constructible representations (see [START_REF] Lusztig | Hecke algebras with unequal parameters[END_REF]). In fact, given the matrix of the constructible characters for a choice of parameters (this includes the case where these parameters are negative), we show the existence of two different associated basic sets. As a consequence, we obtain two natural ways to parametrize the constructible characters, extending the work of Lusztig [START_REF] Lusztig | A class of irreducible representations of a Weyl group[END_REF], [START_REF] Lusztig | Characters of reductive groups over a finite field[END_REF], [START_REF] Lusztig | Hecke algebras with unequal parameters[END_REF]. In addition, we describe the bijection between these two basic sets. All these results use as a crucial tool the works of Lusztig, Leclerc and Miyachi [START_REF] Leclerc | Constructible characters and canonical bases[END_REF] and the combinatorics developed therein.

The last part of the paper is devoted to the study of the various bijections between the basic sets in type B n . It turns out that the bipartitions labelling these sets are difficult to describe in general (we only have in principle a recursive description of them). Then, in the same spirit as in [START_REF] Jacon | Crystal isomorphisms for irreducible Uv( b sle)-modules of higher level[END_REF], we show the existence of an action of the affine extended symmetric group S 2 on these basic sets. We observe the two following remarkable facts:

• there is an easy description of the basic sets lying in a fundamental domain associated with the above action, • the action of S 2 on the set of basic sets can be explicitly described combining our previous results with results obtained in [START_REF] Jacon | Crystal isomorphisms for irreducible Uv( b sle)-modules of higher level[END_REF]. It is then possible to describe the basic sets as orbits of the elements of the fundamental domain under this action. Finally, we remark that this action is in some sense controlled by the matrices of constructible representations. In particular the bijections between the various basic sets can be essentially read through these matrices.

We end the paper with an explanation of this phenomenon.

Decomposition matrices for Hecke algebras

Let (W, S) be a finite Weyl group. We assume that we have a decomposition S = S + ⊔S -where no elements of S + is conjugate to an element of S -. Let φ : S → Z be such that

φ(s) = φ(s ′ ) if (s, s ′ ) ∈ S 2 + and φ(s) = φ(s ′ ) if (s, s ′ ) ∈ S 2 -(⋆)
Let q be an indeterminate and choose q 1/2 a root of q. We then have an associated Iwahori-Hecke algebra H(W, S, φ) over A = Z[q 1/2 , q -1/2 ]. The basis is given by {T w } w∈W and the multiplication is determined by the following rules:

T w T w ′ = T ww ′ if l(ww ′ ) = l(w) + l(w ′ ) (T s -q φ(s) )(T s + 1) = 0
In this section, we study the representation theory of these algebras in both the semisimple and the modular case and give extensions of some definitions and properties which were previously only known when φ(S) ⊂ N 2.1. Decomposition matrices. Let K be the field of fractions of A. Then by [21, §9.3.5], the algebra H K (W, S, φ) := K ⊗ A H(W, S, φ) is split semisimple and by Tits' deformation theorem, we have a canonical bijection between Irr(H K (W, S, φ)) and Irr(W ). Let Λ is an indexing set for Irr(W ):

Irr(W ) = E λ | λ ∈ Λ .
We then have:

Irr(H K (W, S, φ)) = V λ φ | λ ∈ Λ Let k
be a field and ξ ∈ k × be an element which has a square root in k × . Then there is a ring homomorphism θ : A → k such that θ(q) = ξ. Considering k as an A-module via θ, we set H k (W, S, φ) := k ⊗ A H A (W, S, φ). As noted above, we have a canonical way to parametrize the simple modules for H K (W, S, φ). It is also desirable to obtain a "good" parametrization of the simple H k (W, S, φ)-modules. As H k (W, S, φ) is not semisimple in general, Tits' deformation theorem cannot be applied. However, following [15, §4.10], one can use the associated decomposition matrix to solve that problem. Let λ ∈ Λ and let

ρ λ : H K (W, S, φ) → M d (K) T w → (a ij (T w )) 1≤i,j≤d
be a matrix representation affording the module V λ φ ∈ Irr(H K (W, S, φ)) of dimension d. The ideal p = ker(θ) is a prime ideal in A and the localization A p is a regular local ring of Krull dimension ≤ 2. Hence, by Du-Parshall-Scott [9, §1.1.1], we can assume that ρ λ satisfies the condition

ρ λ (T w ) ∈ M d (A p )
for all w ∈ W . Now, θ extends to a ring homomorphism θ p : A p → k. Applying θ p , we obtain a representation

ρ λ k,ξ : H k (W, S, φ) → M d (k), T w → (θ p (a ij (T w ))) 1≤i,j≤d .
This representation may no longer be irreducible. For any M ∈ Irr(H k (W, S, φ)), let [V λ φ : M ] be the multiplicity of M as a composition factor of the H k (W, S, φ)-module affording ρ λ k,ξ . This is well defined by [9, §1.1.2]. Thus, we obtain a well-defined matrix

D φ θ = [V λ φ : M ] λ∈Λ,M∈Irr(H k (W,S,φ))
which is called the decomposition matrix associated with θ. Let R(H K (W, S, φ)) (resp. R(H k (W, S, φ))) be the Grothendieck group of finitely generated H K (W, S, φ)modules (resp. H k (W, S, φ)-modules). It is generated by the classes [U ] of the simple H K (W, S, φ)-modules (resp. H k (W, S, φ)-modules) U . Then we obtained a well defined decomposition map:

d φ θ : R(H K (W, S, φ)) → R(H k (W, S, φ)
) such that for all λ ∈ Λ we have:

d φ θ ([V λ φ ]) = M∈Irr(H k (W,S,φ)) [V λ φ : M ][M ]
The notion of basic sets of simple modules for Hecke algebras has first been considered by Geck in [START_REF] Geck | Kazhdan-Lusztig cells and decomposition numbers[END_REF]. The definition depends on the decomposition matrix and has been originally given in the case where φ is constant and positive and then in the case where φ is positive in [START_REF] Geck | Modular representations of Hecke algebras[END_REF]. Using the above discussion, we will be able to generalize these notions to all possible φ. 2.2. Basic sets. In this section, we adopt the following notations. Let φ : S → Z be a map satisfying

φ(s) = φ(s ′ ) if (s, s ′ ) ∈ S 2 + and φ(s) = φ(s ′ ) if (s, s ′ ) ∈ S 2 - (⋆).
We denote by |φ| : S → Z the map such that |φ|(s) = |φ(s)| for all s ∈ S. Note that this map satisfy (⋆). Set:

S -:= {s ∈ S | φ(s) < 0} . Let ε : W → Q × be the one dimensional representation of W such that ε(s) = 1 if s ∈ S + and ε(s) = -1 if s ∈ S -. For λ ∈ Λ, the module (E λ ) ε remains simple and we define λ ε ∈ Λ such that E λ ε ≃ (E λ ) ε .
We turn to the definition of basic sets associated with a specialization of the Hecke algebra.

Definition 2.1. We say that H(W, S, φ) admits a basic set B(φ) ⊂ Λ with respect to θ : A → k and to a map α φ : Λ → Q if and only if:

(1) For all M ∈ Irr(H k (W, S, φ)) there exists λ M ∈ B(φ) such that

[V λM φ , M ] = 1 and α φ (µ) > α φ (λ M ) if [V µ φ , M ] = 0 (2) The map Irr(H k (W, S, φ)) → B(φ) M → λ M is a bijection
Assume that H(W, S, φ) admits a basic set B(φ) ⊂ Λ with respect to θ and to a map α φ : Λ → Q. This implies that the associated decomposition matrix has a lower triangular shape with one along the diagonal for a "good" order on Λ induced by the map α φ . Hence, it gives a way to label Irr(H k (W, S, φ)).

It is now natural to ask if these basic sets always exist. The question has been considered in [START_REF] Geck | Filtrations on projective modules for Iwahori-Hecke algebras[END_REF], [START_REF] Geck | Kazhdan-Lusztig cells and decomposition numbers[END_REF], [START_REF] Geck | Modular representations of Hecke algebras[END_REF] (see [START_REF] Geck | Representations of Hecke algebras at roots of unity[END_REF] for a complete survey on this theory) and in [START_REF] Chlouveraki | Schur elements and basic sets for cyclotomic Hecke algebras[END_REF] (where the question of existence of basic sets in characteristic 0 and for any weight function is complete),

The first step is to define the canonical map a φ : Λ → N which will play the role of α φ . This can be done using the symmetric algebra structure of H(W, S, φ) We define a linear map τ : H(W, S, φ) → A by τ (T 1 ) = 1 and τ (T w ) = 0 for w = 1.

Then one can show that τ is a trace function and we have

τ (T w T w ′ ) = π(w) if w ′ = w -1 , 0 otherwise.
This implies that H(W, S, φ) is a symmetric algebra (see [START_REF] Geck | Characters of finite Coxeter groups and Iwahori-Hecke algebras[END_REF]Ch. 7] for a study of the representation theory of this type of algebras). The above trace form extends to a trace form τ K :

H K (W, S, φ) → K. Now since H K (W, S, φ) is split semisimple, we have τ K (T w ) = λ∈Λ 1 c λ trace(T w , V λ φ ), for all w ∈ W,
where c λ ∈ A is called the Schur element associated to λ ∈ Λ. For all λ ∈ Λ, we now have c λ = f λ q -a φ λ + combination of higher powers of q, where f λ and a φ λ are both integers such that f λ > 0 and a φ λ ≥ 0 (see [START_REF] Geck | Characters of finite Coxeter groups and Iwahori-Hecke algebras[END_REF]Ch. 20] for details.) The map

a φ : Λ → N λ → a φ λ is called the Lusztig a-function.
In the next theorem, we need the following definition: we say that k is good with respect to H(W, S, φ) if f λ 1 k = 0 for all λ ∈ Λ. The proof of the existence of basic set for Hecke algebras (in characretistic 0) with respect to the a-function has been given Geck and Geck-Rouquier (see [START_REF] Geck | Modular representations of Hecke algebras[END_REF]) whenΦ is positive. The following proposition obtained in [6, Prop 2.5] allows the extension of the result for arbitrary Φ. This result will also be crucial in the rest of the paper. Proposition 2.2. For all λ ∈ Λ, we have:

a φ (V λ φ ) = a |φ| (V λ ε |φ| )
The theorem of existence becomes then the following: Theorem 2.3. We keep the above notations. Assume in addition that Lusztig's conjectures P1-P15 in [33, §14.2] hold and that k is good with respect to H(W, S, φ). Then H(W, S, φ) admits a basic set B(φ) ⊂ Λ with respect to any specialization and to the map a φ , the Lusztig a-function. This basic set is called the canonical basic set and it only depends on e and φ.

Remark 2.4. Lusztig's conjectures are known to hold in the following cases:

(1) For all finite Weyl group, in the so called "equal parameter case", that is when there exists a ∈ N such that φ(s) = a for all s ∈ S by Lusztig (see [START_REF] Lusztig | Hecke algebras with unequal parameters[END_REF]Ch. 15].) (2) In type B n , in the so called "asymptotic case" by the works of Bonnafé-Iancu [START_REF] Bonnafé | Left cells in type Bn with unequal parameters[END_REF], Bonnafé [START_REF] Bonnafé | Two-sided cells in type B (asymptotic case)[END_REF], Geck [START_REF] Geck | Relative Kazhdan-Lusztig cells[END_REF] and Geck-Iancu [START_REF] Geck | Lusztig's a-function in type Bn in the asymptotic case[END_REF].

In fact, the results in [START_REF] Chlouveraki | Schur elements and basic sets for cyclotomic Hecke algebras[END_REF] show that the canonical basic set B(φ) ⊂ Λ can be deduced from B(|φ|). We illustrate this fact in type B n which is our main centre of interest in this paper. Hence, let W be a Weyl group of type B n .

B n i i i • • • i t s 1 s 2 s n-1
In this case, Λ can be defined to be the set Π 2 n of bipartitions of rank n. In the following, it will be useful to introduce a "more generic" Hecke algebra than the one defined in the introduction of this section.

Let V and v be indeterminates and consider the generic Hecke algebra H({V, v}) of type B n over Z[V ±1/2 , v ±1/2 ] with presentation as follows:

(T 0 -V )(T 0 + 1) = 0 (T i -v)(T i + 1) = 0 if i = 1, ..., n -1
Let K be the field of fractions of A. We set

Irr(H K ({V, v})) = {V λ | λ ∈ Π 2 n }. and Λ = Π 2
n . We assume that we have a specialization θ : Z[V ±1/2 , v ±1/2 ] → k where k is a field. By results of Dipper and James [START_REF] Dipper | Representations of Hecke algebras of type Bn[END_REF]Th. 4.17], one can restrict ourselves to the following case. We assume that θ(V ) = -q da and θ(v) = q a for (a, b) ∈ N 2 and for q ∈ k × . The resulting algebra H k ({q a , -q ad }) has a presentation as follows:

(T 0 + q da )(T 0 + 1) = 0 (T i -q a )(T i + 1) = 0 if i = 1, ..., n -1.
It is in general a non semisimple algebra and as in §2.1, we have an associated decomposition matrix.

D = ([V λ : M ]) λ∈Π 2 n ,M∈Irr(H k ({q a ,-q ad }))
By a deep theorem of Ariki [START_REF] Ariki | Representations of quantum algebras and combinatorics of Young tableaux[END_REF]Thm 14.49], this matrix is nothing but the (evaluation at v = 1 of the) matrix of the canonical basis for the irreducible highest weight U v ( sl e )module with weight Λ d + Λ 0 (where the Λ i with i ∈ Z/eZ denote the fundamental weights).

Applying [START_REF] Chlouveraki | Schur elements and basic sets for cyclotomic Hecke algebras[END_REF] to type B n leads the following proposition.

Proposition 2.5. Let (W, S) be the Weyl group of type B n . We assume that we have a map φ : S = {t, s 1 , ..., s n } → Z satisfying (⋆). We set |φ| :

S = {t, s 1 , ..., s n } → Z such that |φ|(s) = |φ(s)| for all s ∈ S.
Then, for all specialization θ, we have

B(φ) = (λ 0 , λ 1 ) ε | (λ 0 , λ 1 ) ∈ B(|φ|)
where

(1) (λ 0 , λ 1 ) ε = (λ 1 , λ 0 ) if S + = {s 1 , ..., s n-1 } and S -= {t}, ( 2
) (λ 0 , λ 1 ) ε = (λ 1 ′ , λ 0 ′ ) if S + = ∅ and S -= {s 1 , ..., s n-1 , t}, (3)
(λ 0 , λ 1 ) ε = (λ 0 ′ , λ 1 ′ ) if S + = {t} and S -= {s 1 , ..., s n-1 },
From now, we will denote κ(λ 0 , λ 1 ) := (λ 1 , λ 0 ).

U (i) = V [Ind S I (U ) : V ]V (sum over all V ∈ Irr(C[W ]) such that a φ (V ) = i).
Then the J-induction of a simple C[W I ]-module U is

J S I (U ) = U (a φ I (U))
Using this "truncated" induction, the constructible representations with respect to φ are defined inductively in the following way:

(1) If W = {1}, only the trivial module is constructible.

(

) If W = {1}, the set of constructible C[W ]-modules consists of the C[W ]- modules of the form J S I (V ) or sgn ⊗ J S I (V ) 2
, where sgn is the sign representation of W , and I some proper subset of S. One can define an analogue of the decomposition matrix for this type of representations: the constructible matrix D φ cons which is defined as follows. Remark 2.7. If φ is positive, the blocks of the matrix D φ cons are known as the families of characters. This notion plays an important role in the theory of reductive group. In fact, it is possible to generalize the definition of families of characters to any map φ (ie. not necessary positive) and to a wider class of algebras : the cyclotomic Hecke algebras, using the notion of Rouquier blocks. The associated families have been studied by Chlouveraki [START_REF] Chlouveraki | Blocks and families for cyclotomic Hecke algebras[END_REF]. When W is a Weyl group, one can easily see that for any map φ, the blocks of the matrix D φ cons corresponds to the families of characters as given in [START_REF] Chlouveraki | Blocks and families for cyclotomic Hecke algebras[END_REF].

Bijections of basic sets

We now focus on the case of the Hecke algebras of type B n . Before the study of the representation theory, we first give the formula for the Lusztig a-function in the case where φ(t) = b ≥ 0 and φ(s i ) = a ≥ 0 for i = 1, ..., n -1.

3.1. a-function in type B n . We first introduce a combinatorial object which will be useful in the following: the shifted symbol of a bipartition. Let β = (β 1 , ..., β k ) be a sequence of strictly increasing integers and let s be a rational nonnegative number. We denote by [s] the integer part of s. We set

β(s) := (s -[s], s -[s] + 1, ..., s -1, β 1 + s, ..., β k + s).
Let r ∈ Q and let λ = (λ 0 , λ 1 ) be a bipartition of rank n. Let h 0 and h 1 be the heights of the partitions λ 0 and λ 1 and let h be a positive integer such that h ≥ max(h 0 , h 1 ) + 1. We say that h is an admissible size for λ. We define two sequences of strictly decreasing integers

β 0 = (λ 0 h -h + h, ..., λ 0 j -j + h, ..., λ 0 1 -1 + h) and β 1 = (λ 1 h -h + h, ..., λ 1 j -j + h, ..., λ 1 1 -1 + h) The shifted r-symbol of λ of size h is then the family of sequence B r (λ) := (B 0 , B 1 ) such that B 0 = β 0 (r) if r ≥ 0 β 1 (-r) otherwise.
and

B 1 = β 0 if r ≤ 0 β 1 otherwise.
The shifted symbol of size h is usually written as a two row tableaux as follows: Assume now that φ(t) = b ≥ 0 and φ(s i ) = a > 0 for i = 1, ..., n -1. Let λ ∈ Λ and let B b/a (λ) be the shifted b/a symbol of λ of size h. Let

B r (λ) := B 0 B 1 Note that B r (λ) = B -r (κ(λ)).
γ 1 ≥ γ 2 ≥ .... ≥ γ t ,
be the elements of this symbol written in decreasing order (with repetition). Then write

a φ,h 1 (λ) = t i=1 (i -1)γ i .
Then by Lusztig [33, §22.14], we have:

a φ (λ) = a φ,h 1 (λ) -a φ,h 1 (∅).
Regarding the above definition and the connection between Lusztig a-function when b < 0 and b > 0 given by Prop. 2.2, we deduce:

Proposition 3.2. Assume that φ(t) = b and φ(s i ) = a ≥ 0 for i = 1, ..., n -1. Let λ ∈ Λ and let B b/a (λ) = (B 0 , B 1 ) be the shifted b/a-symbol of λ. Let γ 1 ≥ γ 2 ≥ .... ≥ γ t
be the elements of this symbol written in decreasing order (with repetition). We denote γ h b/a (λ) = (γ 1 , ..., γ t ) the associated partition. We then write

a φ 1 (λ) = t i=1 (i -1)γ i
Then we have:

a b/a (λ) := a φ (λ) = a φ,h 1 (λ) -a φ,h 1 (∅) It does not

3.2.

Constructible representations in type B n . Let V and v be indeterminates and consider the Hecke algebra H({V, v}) of type B n over Z[V ±1/2 , v ±1/2 ] as in §2.2.

We have

Irr(H K ({V, v})) = {V λ | λ ∈ Π 2 n }. We assume that we have a specialization θ :

Z[V ±1/2 , v ±1/2 ] → Q(q 1
2 ) where q is an indeterminate such that θ(V ) = -q da and θ(v) = q a for (a, b) ∈ N 2 . For d ∈ Z. Then we have an associated decomposition matrix.

D θ = ([V λ : M ]) λ∈Π 2 n ,M∈Irr(H Q(q 1/2 ) (q a ,-q da ))
By Ariki's theorem, this decomposition matrix is the matrix of the canonical basis of the irreducible highest weight U v (sl ∞ )-module with weight Λ d + Λ 0 . Assume that d ≥ 0 then by [START_REF] Leclerc | Constructible characters and canonical bases[END_REF] it has another interpretation in terms of Kazhdan-Lusztig theory: this is the matrix D φ cons of the constructible representations for the algebra H(W, S, φ) where φ(t) = d and φ(s i ) = 1 for all i = 1, ..., n -1. Thus, we have D φ cons = D θ . In other words, the columns of this decomposition matrix give the expansion of the constructible representations associated to the map φ in terms of the simple H(W, S, φ)-modules V µ φ . It is natural to ask if a basic set as defined in Def. 2.1 can be found in this situation that is if one can order the rows and columns of the constructible matrix such that it has a unitriangular shape. The explicit determination of the matrix D θ has been given by Lusztig and by Leclerc-Miyachi using different technics when d ≥ 0. We here follows the latter exposition [START_REF] Leclerc | Constructible characters and canonical bases[END_REF] and extend it to the case d ∈ Z.

Hence we assume from now that φ is such that φ(t) = d ∈ Z and φ(s i ) = 1 for all i = 1, ..., n -1. First, we need some additional combinatorial definition. Let λ be a bipartition and consider its d-symbol B d (λ) = (B 0 , B 1 ). We say that λ is standard, or equivalently that B d (λ) is standard if

B 1
i ≥ B 0 i for all i ≥ 1. The set of standard bipartitions is denoted by Std(d).

Let B d (λ) be a standard symbol. We define an injection Ψ : B 1 → B 0 such that Ψ(j) ≤ j for all j ∈ B 1 . It is obtained by describing the subsets

B 1 l := {j ∈ B 1 | Ψ(j) = j -l}. We set B 1 0 = B 1 ∩ B 0
and for l ≥ 1, we put:

B 1 l = {j ∈ B 1 \ {B 1 0 , ..., B 1 l-1 } | j -l ∈ B 0 \ Ψ(B 1 0 ∪ ... ∪ B 1 l-1
)} the pairs (j, Ψ(j)) with Ψ(j) = j are called the pairs of the symbols B d (λ). Let C(λ) be the set of all bipartitions µ such that the symbol of µ is obtained from B d (λ) by permuting some pairs in B d (λ) and reordering the rows. We also define Inv d (λ) to be the bipartition in C(λ) whose symbols is obtained from the symbol of λ after all possible permutations of the pairs.

The following is a result by Lusztig and Leclerc-Miyachi when d ≥ 0 which is easily extend in the case where d ∈ Z by Prop. 2.6 and by the definition of symbols. Proposition 3.4. Assume that φ is such that φ(t) = d ∈ Z and φ(s i ) = 1 for all i = 1, ..., n -1. The constructible representations with respect to φ are labelled by the standard bipartitions. Moreover, if λ is a standard bipartition, the associated constructible representation with respect to φ is

µ∈C(λ) V µ φ .
Example 3.5. We consider the Weyl group of type B 3 . Let φ be such that φ(t) = 2 ∈ Z and φ(s i ) = 1 for all i = 1, 2. From above, one can check that the only non trivial constructible representations are:

V (∅,3) φ ⊕ V (1,2) φ , V (1,2) φ ⊕ V (1.1,1) φ , V (1.1,1) φ ⊕ V (1.1.1,∅) φ
In other words, we have:

D φ cons =                
1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0

                (∅, 3) (∅, 2.1) (∅, 1.1.1) (1, 2) (1, 1.1) (2, 1) (1.1, 1) (3, ∅) (2.1, ∅) (1.1.1, ∅)
Note that the constructible representations are labelled by the set of standard bipartitions which is in this case Π 2 3 \ {(1.1.1, ∅)}. Note also that the unique non trivial block of the above matrix is given by the following set of bipartitions {(∅, 3), (1, 2), (1.1, 2), (1.1.1, ∅)} which corresponds to the unique non trivial family of characters. Now, if we set φ ′ be such that φ ′ (t) = -2 ∈ Z and φ ′ (s i ) = 1 for all i = 1, 2. From above, one can check that the only non trivial constructible representations are:

V (3,∅) φ ′ ⊕ V (2,1) φ ′ , V (2,1) φ ′ ⊕ V (1,1.1) φ ′ , V (1,1.1) φ ′ ⊕ V (∅,1.1.1) φ ′
The unique non trivial block of the above matrix is given by the following set of bipartitions {(3, ∅), (2, 1), (1, 1.1), (∅, 1.1.1)} which corresponds to the unique non trivial family of characters.

3.3. Basic sets of constructible representations. The aim of this section is to show the existence of basic sets for the matrix affording the constructible representations. To do this, we have to study the matrix D φ cons of the constructible representations for the algebra H(W, S, φ) where φ(t) = d ∈ Z and φ(s i ) = 1 for all i = 1, ..., n -1. We denote by Cons(d) the set of constructible H(W, S, φ)-modules. The main result of this section is the following one. Theorem 3.6. We keep the above notations and we put r ∈ Q such that r = d.

(1) For all U ∈ Cons(d) there exists λ U ∈ Λ such that

[V λU , U ] = 1 and a r (µ) > a r (λ U ) if [V µ , U ] = 0 (2) Let B r ∞ := {λ U | U ∈ Cons(d)} Then the map Cons(d) → B r ∞ U → λ U is a bijection (3) We have B r ∞ = Std(d) if r < d Inv d (Std(d)) if r > d
Proof. Let us first assume that d ≥ 0. Let λ be a standard bipartition then by Prop 3.4, we have an associated constructible representation labelled by this bipartition. Assume that V µ φ appears as an irreducible constituent in the expansion of this constructible representation. Then µ can be constructed from λ by permuting some pairs in the shifted d-symbol of λ. Let h be an admissible size for λ. By construction, it implies that this size is admissible for µ. Let B d (µ) = (B 0 , B 1 ) be the shifted d-symbol of µ of size h. By §3.1, we have B 0 = β 0 (d) and a = β 1 .

• If r > d the shifted r-symbol of µ is B r (µ) = (B 0 (rd), B 1 ). By the definition of C(λ), It is easy to see that

γ h r (Inv d (λ)) γ h r (µ)
, for all µ ∈ C(λ). Hence by Cor 3.3, we obtain:

a r (Inv d (λ)) ≤ a r (µ) • if r < d, the shifted r-symbol of µ of size h is B r (µ) = (B 0 (d -r), B 1 ) if r is positive.
In this case, by the definition of C(λ) It is easy to see that

γ h r (λ) γ h r (µ)
, for all µ ∈ C(λ) such that µ = λ . Hence we obtain:

a r (λ) ≤ a r (µ). If r is negative, the shifted r-symbol of µ of size h + d is B r (µ) = (B 1 (d - r), B 0
). In this case, by the definition of C(λ) It is easy to see that

γ h+d r (λ) ⊲ γ h+d r (µ),
and we can conclude as above. To summarize, We know that an arbitrary column of the constructible matrix D θ is naturally labelled by a standard bipartition λ U with U ∈ Cons(d). The above discussion shows that the minimal bipartition λ with respect to a r such that [

V λ : M ] = 0 is λ = λ U if r < d, λ = Inv d (λ U ) otherwise. In addition by Prop 3.4, if [V λ : U ] = 0 then [V λ : U ] = 1. This proves the Theorem if d > 0.
The case d < 0 is deduced from the above one using Prop. 2.2 and the facts that

κ(Std(d)) = Std(-d), κ(Inv d (Std(d))) = Inv -d (Std(-d))
In the expansion of a constructible character, all the simple modules have the same value with respect a d . This follows from the definition of constructible representations and can also be easily seen in the formula above. Theorem 3.6 shows that modifying the a-function by adding an integer s to d leads to a natural way to order the rows and columns of the constructible matrix so that it is unitriangular. This induces the existence of a canonical basic set which only depends on the sign of s.

Let us now describe the consequences on the parametrisations of the simple modules for Hecke algebras of type B n in the modular case.

Basic sets in type

B n 4.1. Explicit determination in a special case. Recall that A := Z[q 1/2 , q -1/2 ]. Let φ such that φ(t) = b ≥ 0 and φ(s i ) = a > 0 for i = 1, ..., n -1, Let θ : A → Q(q 1/2 0 )
be a specialization such that θ(q) = q 0 ∈ C * . Let e ≥ 2 be the multiplicative order of η e := q a 0 . Assume that q b 0 = -q ad 0 for some d ∈ Z. We have an associated decomposition matrix D θ and a canonical basic set B(φ) which will, from now, be rather denoted by B b/a e . Consider now φ 1 such that φ 1 (t) = b + ae and φ 1 (s i ) = a for i = 1, ..., n -1. Applying the specialization θ, we obtain again the algebra H k (q a 0 , -q da 0 ). Hence we have another basic set denoted by B These basic sets have been computed in [START_REF] Geck | Canonical basic sets in type Bn[END_REF] without the assumptions of P1-P15 in characteristic 0. It has been shown that the bipartitions labelling these sets are given by the so called Uglov bipartitions. These bipartitions appear as natural labelling of the Kashiwara's crystal basis for irreducible highest weight-modules of level two. As several combinatorial definitions are necessary to introduce them, we have chosen to omit the definition of these bipartitions here. We refer to [START_REF] Geck | Representations of Hecke algebras at roots of unity[END_REF] or [START_REF] Jacon | Crystal graphs of irreducible Uv( b sle)-modules of level two and Uglov bipartitions[END_REF] for details on them.

Theorem 4.1 (Geck-Jacon). We keep the above notations. Let e ≥ 2 be the multiplicative order of q a and let p 0 ∈ Z be such that is defined in [START_REF] Geck | Canonical basic sets in type Bn[END_REF]Def. 4.4].

Without loss of generality, one can (and do) assume that p 0 = 0. By the results in the second section, the datum of φ ′ such that φ ′ (t) = ε 1 b and φ ′ (s i ) = ε 2 a (for i = 1, ..., n -1) with (ε 1 , ε 2 ) ∈ {±1} 2 also yields the existence of a basic set B(φ ′ ). By Prop. 2.5, they can be easily computed using the above theorem. In particular, the case ε 2 = 1 and ε 1 = -1 implies the existence of a basic set B -b/a . In fact, considering all the basic sets we have already obtained:

Now recall the specialization

θ : A → Q(q 1/2 0 )
such that θ(q) = q 0 . Looking at the Hecke algebra H({q -b , q a }) and applying the specisalization θ, we obtain a decomposition matrix which can be identify with D θ by [6, §3.1] . Keeping the above notations, we have: q -b+ae 0 = -q -ad 0 . Note that -b + ae and a are both positives. We then obtain a basic set B -b/a+e . Actually, using the same arguments as above, one obtain several basic sets: Following [START_REF] Jacon | Crystal isomorphisms for irreducible Uv( b sle)-modules of higher level[END_REF], we set

F = {±b/a + te | t ∈ Z}
Let S 2 be the extended affine symmetric group with generators σ and y 0 , y 1 and relations y 0 y 1 = y 1 y 0 , σ 2 = 1, y 0 = σy 1 σ.

One can define an action of S 2 on F determined by the following identities. For all t ∈ Z, we set:

σ.B γ e = κ(B γ e ) = (λ 0 , λ 1 ) | (λ 1 , λ 0 ) ∈ B γ e
Hence, to describe the action of S 2 on F , it suffices to understand the action of y 0 on an arbitrary basic set. By the results in [START_REF] Jacon | Crystal graphs of irreducible Uv( b sle)-modules of level two and Uglov bipartitions[END_REF] (see also the generalizations in [START_REF] Jacon | Crystal isomorphisms for irreducible Uv( b sle)-modules of higher level[END_REF]) together with Thm 4.1, the action of y 0 corresponds to a crystal isomorphism. Using the combinatorial study of this isomorphism in this paper, It can be expressed using the map Inv D defined in the previous section. This is given by the following theorem which uses the combinatorics developed in [START_REF] Jacon | Crystal graphs of irreducible Uv( b sle)-modules of level two and Uglov bipartitions[END_REF]. • if q b 0 = 1 then q ad 0 = -1 implies that e is even and d = e/2 which is impossible because then q b 0 = q ae/2 0 = -q ae/2 0 . • if q b 0 = -1 then q ad 0 = 1 implies d = e and d = 0. In this case, note that Φ Let H(W, S, {Q, q a }) be the generic Hecke algebra with parameters Q and q a (where Q and q are indeterminates). We consider a first specialization: T R(H Q(q 1/2 0 ) (W, S, {-q Da 0 , q a 0 })) R(H Q(q 1/2 ) (W, S, {-q Da , q a }))

d θ
5 5 j j j j j j j j j j j j j j j j j j

In other words, we have:

D θ1 = D θq D θ
The following gives a first consequence of this result which can be also easily checked using the results of the previous sections and the properties of Uglov biartitions. Corollary 4.6. We have:

B γ e ⊂ B γ ∞ . Proof. This follows directly from the above theorem. which is naturally defined using D θq . Consider a constructible character and the expansion of it in the standard basis. This is given by a column of D θq . Let λ be the element appearing in this column with non zero coefficient and with minimal value with respect to a γ . Then λ ∈ B γ ∞ . Let µ be the element appearing in this column with non zero coefficient and with minimal value with respect to a γ+e . Then µ ∈ B γ+e ∞ . We then set Ψ(λ) = µ. Combining this with the above result we get Ψ(B γ e ) = B γ+e e .

2. 3 .

 3 Constructible representations. From the above definitions and the results in[START_REF] Bonnafé | Semicontinuity properties of Kazhdan-Lusztig cells[END_REF], it will be easy to extend known results of constructible representations as defined by Lusztig [33, §22.1]. Let (W, S) be a Weyl group and let φ be a map φ : S → Z satisfying (⋆). Let I ⊂ S and let (W I , I) be the corresponding parabolic subgroup. Let φ I be the restriction of φ to I. Each simple C[W ]-module E λ can be seen as a specialization of a simple H(W, S, φ)-module V λ φ . By §2.2, each simple C[W ]-module U comes equipped with an associated invariant a φ (U ) depending on the choice of φ. Let U be a simple C[W I ]-module. Then we can uniquely write: Ind S I (U ) = U (0) ⊕ U (1) ⊕ .... where for any integer i

Example 3 . 1 .

 31 Let r = 1/2 and λ = (2.1, 3.3.2). We have h 0 = 2 and h 1 = 3. Then the associated shifted r-symbol of size 4 Let r = -5/2 and λ = (2.1, 3.3.2). We have h 0 = 2 and h 1 = 3 then the associated shifted r-symbol of size 4 is 1/2 3/2 1/2 7/2 11/2 13/

Corollary 3 . 3 .

 33 depend on the size of the symbol. Proof. When b ≥ 0, this is a result of Lusztig. Assume that b < 0, then we have by Prop. 2.2, a b/a (λ) := a -b/a (κ(λ)) and B b/a (λ) = B -b/a (κ(λ)) so the result followsThe following result is a direct consequence of the formula of the a-function. Assume that φ(t) = b and φ(s i ) = a ≥ 0 for i = 1, ..., n-1. Let λ ∈ Λ and µ ∈ Λ. Let h be an admissible size for λ and µ. Assume that γ h b/a (λ) ⊲ γ h b/a (µ) then we have a b/a (λ) < a b/a (µ).

  with respect to the a-function a b/a+e . Continuing in this way we obtain several basic sets B b/a , B b/a+e e , ..., B b/a+te e , ... and one can assume that 0 ≤ b/a < e.

d

  + p 0 e < b a < d + (p 0 + 1)e.(Note that the above conditions imply that b/a ≡ d mod e.) Then for all t ≥ 0, we have B

B

  b/a , B b/a+e e , ..., B b/a+te e , ... we obtain several other basic sets B -b/a , B -b/a-e e , ..., B -b/a-te e , ...

BCorollary 4 . 2 ., 2 .B

 422 -b/a+e , B -b/a+2e e , ..., B -b/a+te e , ... Keeping the notation of thm 4.1 (recall that p 0 = 0), note that we have -d < -b a + e < -d + e.The above theorem gives also the explicit determination of these basic sets: Keeping the above notations, for all t > 0, we haveB -b/a+te e = Φ (-d+(t-1)e,0) e,nwhere Φ(-d+(t-1)e,0) e,nis defined in[START_REF] Geck | Canonical basic sets in type Bn[END_REF] Def. 4.4]. Finally, as above, the existence of basic sets B -b/a+e , B -b/a+2e e , ..., B -b/a+te e , ... yields the existence of basic sets: B b/a-e , B b/a-2e e , ..., B b/a-te e An Action of the affine Weyl group S 2 .Let us summarize the different basic sets we have obtained and the parametrizations by the Uglov l-partitions. The results in[START_REF] Jacon | Crystal graphs of irreducible Uv( b sle)-modules of level two and Uglov bipartitions[END_REF] allow to change the parametrization of the sets. First by[START_REF] Jacon | Crystal graphs of irreducible Uv( b sle)-modules of level two and Uglov bipartitions[END_REF] Prop. 3.1 (2)] For all (s 0 , s 1 ) ∈ Z 2 , we haveκ(Φ (s0,s1) e,n ) = Φ (s1,s0+e) e,nMoreover, by[START_REF] Jacon | Crystal graphs of irreducible Uv( b sle)-modules of level two and Uglov bipartitions[END_REF] Prop 3.1 (1)], for all m ∈ Z, we have:Φ (s0,s1) e,n = Φ (s0+m,s1+m) e,nTo summarize, the following tabular gives the basic sets and the parametrizations by the Uglov bipartitions.Basic set withAssociated set Basic set with Associated set positive parameters of bipartitions negative parameters of bipartitions .-b/a-te e Φ (0,d+(t+1)e) e,n ... ... ... ...

  σ.(b/a + te) = -b/ate, y 0 .(b/a + te) = b/a + (t + 1)e, y 0 .(-b/a + te) = -b/a + (t + 1)e One can easily check that this action is well defined. The above dicussion yields the existence of an action on the basic sets by setting for all w ∈ S 2 and γ ∈ F: w.B γ e = B w.γ e By Prop 3.6, we have:

Theorem 4 . 3 .

 43 Assume that γ ∈ F. Then there exists D ∈ Z such that: B γ e = Φ (D-e,0) e,n To describe the action of y 0 , one can assume that D ≥ 0, then we have y 0 .B γ e = Inv D (B γ e ) Proof. Let γ ∈ F. By Thm 4.1, there exists D ∈ Z such that B γ e = Φ (D-e,0) e,n . Since we know that σ.B δ e = κ(B δ e ) for all δ ∈ F, one can assume that D ≥ 0. Let (λ 0 , λ 1 ) ∈ B γ e = Φ (D-e,0) e,n . Then by [28, Prop. 3.1], we have (λ 1 , λ 0 ) ∈ Φ (0,D) e,n . Using [28, Prop. 4.1], we deduce that (λ 0 , λ 1 ) ∈ Std(D). Again, by [28, Prop. 4.1], we have κ(Inv D (λ 0 , λ 1 )) ∈ Φ (0,D+e) e,n which implies that Inv D (λ 0 , λ 1 ) ∈ Φ (D,0) e,n . The map sending (λ 0 , λ 1 ) ∈ Φ (D-e,0) e,n to Inv D (λ 0 , λ 1 ) ∈ Φ (D,0) e,n is a bijection.Hence, remarkably, this action does not depend on e but only on D ! This will be developed in the following section.

Remark 4 . 4 .

 44 Assume that b/a = -b/a + e then 2b = ae and we have q 2b 0 = 1. Then we have two cases to consider

  (d,0) e,n = Φ (0,d) e,n and then B b/a e = B -b/a+e e . Hence the above result is coherent with this case.

4. 3 .

 3 Factorization of the decomposition map. The aim of this section is to give an interpretation of Prop. 4.3 in terms of constructible representations. We here keep the notations of this proposition.

Proposition 4 .

 4 [START_REF] Bonnafé | Semicontinuity properties of Kazhdan-Lusztig cells[END_REF] and the above result show that the bijection between y 0 .B γ e and B γ e is "controlled" by the matrix of the constructible representations through the above factorization in the following sense.Note that γ < D < γ + e. We have a bijectionΨ : B γ ∞ → B γ+e ∞

  Keeping the above notations λ∈Λ α λ V λ φ is a constructible C[W ]-module with respect to φ if and only if λ∈Λ α λ V λ ε |φ| is a constructible C[W ]-module with respect to |φ| Proof. The result follows directly from Prop. 2.2 and the definition of the constructible representation.

• The rows are labelled by Λ, • the coefficients in a fixed column give the expansion of the corresponding constructible representation in terms of the irreducible ones.

Proposition 2.6. Let φ : S → Z be a map satisfying (⋆).