Feriel Daoudi
email: feriel.daoudi@malix.univ-paris1.fr

A framework to evaluate methods' capacity to design flexible business processes

The assumption done in this paper is that changing processes require specific methods for their design. The decision of adopting a method for modeling flexible processes depends on many criterions and situations. Accordingly, we propose a framework with a list of criterions. The user can use it as a decision support framework for the choice of a modeling method. We used two enterprise modeling approaches to illustrate the proposed framework.

I. Introduction

The flexibility of business processes passes by the way of managing and/or modeling them. Indeed the monitoring of those business processes can be facilitated by the use of adequate modeling techniques. The best way, from our point of view, is to ensure the modeling of business processes from organizational objectives they allow to reach, to the software components included in the supporting systems in a complete way (being top-down, bottom-up or mixed). This way of thinking is partially adopted by software publishers providing panoply of tools to model enterprises in a global and coherent way. It also underlies EAI solutions that aim to integrate enterprise applications in order to avoid discontinuity in business processes those applications support.

Today, many enterprises tend to adopt "knowledge management" type of organizational targets and constitute business process warehouses to use them as a support of their reflection. It seems obvious that some changes can be anticipated making simulations on enterprise models stored in those business process warehouses. In order to achieve that, it is also imperative to choose appropriate enterprise modeling techniques and to be sure that those techniques meet users' needs. Several modeling techniques exist and the choice of the one(s) being able to support the required flexibility is not easy. On the other hand, benchmarking should not be Selmin Nurcan In this paper, we propose a framework that permits to evaluate methods' capacities to facilitate the design of changing business processes. We have chosen two approaches, EKD-CMM and ARIS, and used them to illustrate the proposed framework.

II. Suggested framework

Process flexibility can be perceived differently. The meaning it takes determines (settle) the way to handle the flexibility topic. From our part, processes flexibility is the fast reactivity to internal and external changes that affects the enterprise and the easiness to modify business processes schemes and to set up the new enterprise activity. This flexibility is reflected by the ability that the information system (IS) has to take into account enterprise activity changes. This perception (vision) of process flexibility arises the need to get a structuring framework to explore the characteristics (behavior) of a method to cope with this issue.

In the information systems literature, a design method is generally viewed as a couple of a way of working (process model) and a way of modeling (product model) [START_REF] Harmsen | Situational Method Engineering for Information System Projects[END_REF], [START_REF] Prakash | On Method Statics and Dynamics[END_REF]. This definition of a method was also applied to business process design and development methods [START_REF] Hommes | Assessing the quality of business process modelling techniques[END_REF]. The product is a set of diagrams or schemes describing the new system to be constructed and the organization in which it will operate [START_REF] Loucopoulos | The ELEKTRA project: Enterprise Knowledge Modeling for change in the distribution unit of Public Power Corporation[END_REF], [START_REF] Scheer | ARIS architecture and reference models for business process management, Business Process Management[END_REF], [START_REF] Papazoglou | Configurable business objects for building evolving enterprise models and applications, Business Process Management[END_REF]. The process keeps track of how the product has been constructed. A process and its related product are specific to an application, to a domain or to the whole enterprise. The Product Model defines the set of concepts, their properties and relationships that are needed to express the outcome of the process. A Process Model is a description of processes at the type level. It defines how to use the concepts defined within a Product Model and may serve two distinct purposes: descriptive or prescriptive [START_REF] Curtis | Process Modeling[END_REF], [START_REF] Lonchamp | A structured conceptual and terminological framework for software process engineering[END_REF]. A descriptive Process Model aims at recording and providing a trace of what happens during the development process [START_REF] Gotel | An Analysis of the Requirements Traceability Problem[END_REF]. A prescriptive Process Model is used to describe "how things must/should/could be done". Prescriptive Process Models are often referred to as ways-of-working [START_REF] Seligmann | Analyzing the structure of IS methodologies, an alternative approach[END_REF].

In this paper, the framework proposed is the one depicted in Figure 1. It is inspired from the Seligman's framework for the description of information system development methods presented in [START_REF] Seligmann | Analyzing the structure of IS methodologies, an alternative approach[END_REF]. As shown in Figure 1, a business process design and development method is described according to four different aspects. Each of them is described using various criterions with explanations on their contributions for flexible business process management. The four aspects of the framework are:

• The way of thinking verbalizes the assumptions and viewpoints of the method on the kinds of problem domains, solutions and modelers. • The way of working structures the way in which business process models are designed. It defines the possible tasks to be performed as part of the design and development process. It provides heuristics on how these tasks should be performed.

• The way of modeling provides information on the modeling concepts, on their properties and on their relationships. It gives a formalism and notation to express business process models. • The way of supporting refers to the tools that support the design and development of business process models and offers a repository to store and to exploit them. To be efficient, a business process design and development method has to be supported by a tool because the results are exploited daily and have to be produced rapidly. • Completeness: it describes the various views covered by a method. Obviously, any modeling formalism has its own modeling views. Their number can determine the possible adoption of the method for a project. There are three main views. The objective (purpose) view is related to goals and strategies that the enterprise implements in its business processes. The dynamic view is related to events, activities and business processes describing the way of functioning of the enterprise. Finally the static view concerns the data, outputs and inputs

Way of thinking

Way of modeling Way of working

Way of supporting

produced/handled during the execution of business processes. All modeling formalisms don't necessarily offer concepts to describe the three views. Although to model flexible processes, a method must provide the necessary tool kit to model all the enterprise facets that are impacted by process changes. If it is not the case, the information modeled contains gaps and there is a risk of omitting important details in this design step. It means also that there is a risk of misalignment between new processes and the organization, staff, IS when those processes will be deployed.

• Targeted users: Usually a method is intended for a specific kind of users. Users' typology is a deterministic factor for multiple parameters such as formalism, development process, etc. As far as business process design is concerned, the method must be intended at the same time for IT engineers and business actors.

Processes flexibility is ensured when the enterprise updates rapidly its processes and the IS supporting them. Indeed the processes flexibility gives arise to the IS/processes alignment topic. Actually to handle this problem, the business staff and the IT staff should work together to design the new way of working of the enterprise. The method should address the two kinds of users offering then the autonomy to each team to design the diagrams concerning it with the possibility to communicate and/or validate its results with other teams.

II. 2. Way of working

• Arbitrariness/freedom: processes flexibility is synonymous to fast reactivity and the easiness to model changes in processes diagrams and in setting up the new enterprise's activity. The purpose of this characteristic is to not make diagrams too time consuming or requiring a large team. In this context, method's arbitrariness contributes in decreasing time and staff number. In fact, each design method offers a certain number of steps and a sequence of them. The degree of freedom offered to the designer concerning the execution of these steps varies (from one method to another). A high arbitrariness means possible parallelism of the steps so time decreasing. This means also the possibility to use some of the proposed modeling formalisms and to omit some others, according to the situation which is synonymous to time reduction and/or staff number restriction. This shows how the random side could be advantageous for a fast reactivity. However, an excess in the arbitrariness slows down the results or leads to a certain anarchy. It is essential to find the equilibrium between freedom and framing.

• Guidance: in the application of a method, the ideal is to have activities to be performed and guidelines relative to each situation. In the literature, various design methods offer only explanations related to the underlying modeling formalisms and the diagrams they allow to construct. However guidance concerning the steps to follow is seldom provided by them and it is deplorable. In fact, to easily design flexible business processes the enterprise needs guidelines specific to the context that it undergoes. In this case, guidance can be characterized by orientations relative to the changes (internal, external…) that are involved. Guidelines can refer also to the methodology that each kind of designer (business staff, IT staff …) should adopt. Guidelines should offer clear choices to the designer according to the modeling situations and his aims. The purpose of guidance is to optimize the designer time-split. Providing guidelines, increases designer's productivity by giving him strategies to follow for each situation or problem he faces. It's supposed to be a way to store situations of change and the way to handling them.

II. 3. Way of modeling

• Notation: it is the mean of expressing concepts via the formalism chosen. Notation can be formal, semi formal or informal. This criterion is an important mean to ensure flexibility. First, it is the guaranty of homogeneity of diagrams such as all concepts and all ways of connecting them are well known. Secondly, it may allow the designer to express all needed concepts without difficulty. If a design method does not offer those two conditions, flexibility seems difficult to ensure.

• Simplicity: this element appears in this list because we believe that it is a way to reach flexibility. Simple business process models are easier to design, to understand and to update. Thus simplicity can be characterized by a moderate number of modeling formalisms. It can be characterized also by very significant symbols that have high expressiveness making models manageable. It will be then easy to introduce changes, to remove chunks, to detect inconsistencies, accelerating then new processes' design. Obviously, the principle of simplicity is often in opposition with the principle of richness, so the balance must be attempted.

• Richness: a Product Model includes the set of concepts intended to represent the enterprise knowledge. The richness of the formalism lies in the number and the power of expression of the underlying concepts. A representation language is considered as rich if it also offers possibilities of extension as it is the case of the stereotypes in UML. Despite the improvement in modeling techniques by representing several new concepts, some notions are still not represented. For this reason, it seems better to use an open formalism to ensure flexibility. Thus richness is an asset because it allows representing accurately enterprise knowledge. A judicious level of richness is required to represent easily changing processes. This level must permit the integration of specific enterprises' concepts and especially those related to its environment by adding them if they are not available in the product meta-model. Finally as said previously, richness must be controlled because too many concepts are a brake on straightforward comprehension of diagrams by all enterprise concerned staff.

• Granularity: it represents the level of decomposition of the designer's vision. All views of the enterprise are concerned by this principle. The granularity can be considered via the number of necessary diagrams to reflect a complete vision of the business. It can also be reflected by the levels of description of an enterprise diagram. For instance, an abstract diagram can be progressively detailed in more operational ones according to the modeling need. We argue that granularity affects process flexibility because it can facilitate or compromises the reader's comprehension. In fact, abstract diagrams (the first level) are the means to get a rapid and general idea of the enterprise's functioning. The detailed ones must permit the reflection of all the crucial details of the enterprise's ways of working and help managers take decisions and introduce desires and interesting changes. The granularity must be controlled because a large usage of decomposition is not always an ally of flexibility. Thus the designer must make the enterprise diagrams readable dice the first level, to facilitate the comprehension of the readers and their decision-making.

II. 4. Way of supporting

• Tool support: In our opinion, a method is more powerful when it has tool support. The level of tool support may vary from generic drawing and modeling tools (diagram editors) to integrated tool suites that even guide the developers through design and development processes. In the case of business flexibility, designers need processes warehouses to ameliorate continuously their activities. Without tool supporting, those changes are difficult to introduce because they are time and staff consuming which is in contradiction with the definition cited above. Tools also permit simulations and staff initiation which are essential to increase enterprise reactivity to change by implying its organization and whole staff.

• Connectivity: activities of business processes are supported by software components developed as parts of the enterprise information system. Those software components should match the requirements of the business process models. EAI technologies tend to ensure communication between them in tight (smooth) way. The aim is to keep the transversal integration from the design until the implementation. To ensure that a method should offer mechanisms to rock from business process modeling to IS development. Thus business processes will be translated accurately and at the same time can ensure efficient reverse engineering permitting then connection with software applications such as EAI and ERP.

III. Illustration

The list of criterions listed above was applied on two business modeling approaches: EKD-CMM [START_REF] Barrios | Model Driven Architectures for Enterprise Information Systems[END_REF], [START_REF] Nurcan | Enterprise Knowledge and Information System Modelling in an Evolving Environment[END_REF] and ARIS [START_REF] Scheer | ARIS architecture and reference models for business process management, Business Process Management[END_REF]. The following list shows how each approach tackles with business process change. This board summarizes this evaluation and reflects advantages and inconveniences that users can meet.

After reading those values, we notice that the gap between the two frameworks is due firstly to the lack of EKD-CMM to provide a tool support and to ensure connectivity with other kinds of applications. The second difference is materialized by the guidance offered by EKD-CMM and that is missing in ARIS. Finally, we observe that the richness of formalism offered by ARIS is caught up on formalism simplicity provided by EKD-CMM. This permits us to recommend EKD-CMM when users are not familiar with rich modeling paradigms and when a tool is not required to share out business process models. On the other hand, ARIS is better for modeling flexible business processes when business staff knows well logic connectors and when tool support is needed to store the produced business process models.

VI. Conclusion

By making a clear distinction between the different aspects of a method, we were able to find criterions for evaluating its capacity to contribute in business process flexibility. As suggested earlier, method evaluation is imperative before its selection for designing enterprise solutions. Benchmarking must be extended to design and development methods to help the enterprise in creating or maintaining flexible business processes. To attempt this target, users need a mean to position methods in the existing context and also to structure their problem.

The framework proposed in this paper permits that by decomposing a method in two layers. In the first layer, a method is dissected in four aspects: way of thinking, way of modelling, way of working and way of supporting. This layer is supposed to give a structure in order to position the method. Secondly, each aspect is detailed using several criterions in order to reflect situations or questions to which users are exposed in business process management projects. Thus, we offer a structured evaluation framework to study, in a detailed way, modelling capacities of business processes design and development methods. This was illustrated by EKD-CMM and ARIS to evaluate their adequacy to design flexible business processes. This framework is dedicated to be a decision support for the benchmarking of design and development methods. An extension can be considered by associating metrics to the criterions that can be exploited in simulations.

Fig. 1 .II. 1 .

 11 Fig. 1. Various aspects of a business process design and development method


A new approach for estimation of long-run relationships in economic analysis using Engle-Granger and artificial intelligence methods

Arshia Amiri, Ulf-G Gerdtham, Bruno Ventelou

To cite this version:

Arshia Amiri, Ulf-G Gerdtham, Bruno Ventelou. A new approach for estimation of long-run relationships in economic analysis using Engle-Granger and artificial intelligence methods. 2012. halshs-00606048v2


Selmin Nurcan

Mohamed Ben Ayed

Colette Rolland

Process of Mapping between User Centric Concepts and Lyee Internal Concepts

The overall objective of the research activity of the UP1 unit is to apply a method engineering approach to the Lyee methodology. This paper presents a formalization of the Lyee Process Model using the concept of Map. It develops also two methodological guidelines supporting (i) the mapping of the Lyee user-centric requirements, which have been previously specified using Design Patterns, into Lyee software requirements and (ii) the optimization of the latter. The motivation is the search for efficiency and effectiveness in the formulation of requirements in accordance with the two levels Lyee Product Meta-Model. The pay-off will be a more productive process of requirements formulation and a better quality result.

Introduction

LyeeALL is a CASE environment which aims at transforming software requirements into code. These requirements are expressed in rather low-level terms such as screen layouts and database accesses. Moreover they are influenced by the LyeeALL internals such as the Lyee identification policy of program variables, the generated program structure and the Lyee program execution control mechanism. As a consequence, it is difficult to get the Lyee customer away from the burden of Lyee internals instead of focusing his/her attention on the requirements. The Sorbonne group develops research towards meeting this need. The overall objective of the research activity of the UP1 unit is to apply a method engineering approach to the Lyee methodology. As a first step, the group is aiming at (1) defining a user-centric requirements model; (2) developing methodological rules to support the capture of these requirements in a systematic way; (3) generating the Lyee software requirements from these user requirements. In a second step, the objective is to provide an intelligent software support for the elicitation of user centric requirements and the automated generation of the Lyee software requirements.

Any method is defined as composed of a product model and a process model [Prakash 99]. The product model defines the set of concepts, their properties and relationships that are needed to express the outcome of the process. The process model comprises the set of goals, activities and guidelines to support goal achievement and action execution. Our research approach is driven by these two elements, the Lyee product and process models.

• The Lyee requirements product model

We used a meta modelling approach to model (i) the set of concepts underlying the Lyee software requirements and (ii) to abstract from them the user-centric requirements model. The result of this effort is a 2-layer meta model. The upper layer corresponds to the user-centric requirements model whereas the lower layer identifies the set of concepts required to express software requirements in Lyee terms. We refer to those as Lyee user requirements meta-model and Lyee software requirements meta-model respectively. These two meta-models constitute the Lyee product model that we propose in the Lyee project.

• The Lyee requirements process model

As far as we are concerned with the Lyee process model, our aim is threefold:

(1) to systematise the capture of user-centric requirements and their formulation in terms which comply with the upper layer of the meta-model thanks to the design patterns, (2) to define rules for mapping to transform the set of Lyee requirements expressed with the concepts of the upper layer of the meta-model into a set of equivalent requirements expressed in terms of the lower layer of the meta-model, (3) to implement software tools to support the capture and formulation of these requirements, being Lyee user requirements and Lyee software requirements.

This paper is organized as follows. Section 2 defines Lyee Requirements Process Model. In order to formalize this Process Model, we use the MAP formalism which helps identifying the key process intentions and the possible strategies to achieve them. Section 3 develops one of the two alternative methodological guidelines to perform the mapping between the concepts of the Lyee user requirements meta-model and the ones of the Lyee software requirements meta-model. Section 4 presents the methodological guideline supporting the optimization of a given Process Route Diagram (PRD). Some idea of future work is given in the conclusion.

The Lyee Requirements Process Model

This section describes the Lyee Requirements Process Model using the MAP formalism. We first recall the Lyee Requirements Product Model and than present the Lyee Map.

Lyee Requirements Product Model

As presented in [Rolland 02a], [Rolland 02b], [Rolland 02c] and [Souveyet 02], the result of the conception effort for the Lyee product model is the two layers meta-model shown in Figure 1. This shows the Product Meta-Model 1 and highlights the separation between the Lyee user requirements concepts and the Lyee software requirements concepts. The term meta-model is used in the report in the same sense as the term meta schema.

The Lyee Map

The Lyee Requirements Process Model is formalized as a Process Map with the key process intentions and the possible strategies to achieve them, and the associated guidelines. This section is organized as follows: Section 2.2.1 introduces the Process Meta-Model which allows us to specify the Lyee process model as a map. Section 2.2.2 describes broadly the Lyee process model, i.e. the Lyee Map. Section 2.2.3 introduces guidelines associated to the Lyee Map.

The Process Meta-Model

A map [Rolland 99], [Rolland 00], [Benjamen 99] is a process model in which a nondeterministic ordering of intentions and strategies has been included. It is a labeled directed graph with intentions as nodes and strategies as edges between intentions. As shown in Figure 2 2 , a map consists of a number of sections each of which is a triplet <source intention I3 i , target intention I j , strategy S4 ij>. There are two distinct intentions called Start and Stop respectively that represent the intentions to start navigating in the map and to stop doing so. Thus, it can be seen that there are a number of paths in the graph from Start to Stop. The map is a navigational structure that supports the dynamic selection of the intention to be achieved next and the appropriate strategy to achieve it whereas the associated guidelines help in the achievement of the selected intention. A strategy is an approach, a manner to achieve an intention. The strategy, as part of the triplet <I i ,I j ,S ij > characterizes the flow from I i to I j and the way I j can be achieved. The specific manner in which an intention can be achieved is captured in a section of the map whereas the various sections having the same intention I i as a source and I j as target show the different strategies that can be adopted for achieving I j when coming from I i . Similarly, there can be different sections having I i as source and I j , I k , ....I n as targets. These show the different intentions that can be achieved after the achievement of I i .

There might be several flows from I i to I j , each corresponding to a specific strategy. In this sense the map offers multi-thread flows. There might also be several strategies from different intentions to reach an intention I i . In this sense the map offers multi-flow paths to achieve an intention. The map contains a finite number of paths, each of them prescribing a way to develop the product (a Lyee program), i.e. each of them is a Lyee process model. Therefore the map is a multi-model. The approach suggests a dynamic construction of the actual path by navigating in the map. Because the next intention and strategy to achieve it are selected dynamically, guidelines that make available all choices open to handle a given situation are of great importance. The Lyee Map has such associated guidelines. A guideline is a set of indications on how to proceed to achieve an intention. A guideline embodies method knowledge to guide the Lyee engineer in achieving an intention in a given situation. The execution of each map section is supported by a guideline which can be atomic or compound. Some sections in a map can be defined as maps in a lower level of abstraction.

The Lyee process model or the Lyee Map

This section describes the Lyee process model by instantiating the concepts of the process meta-model presented in section 2.2.1. Figure 3 shows the Lyee process model, i.e. the Lyee Map. As shown in this figure, there are three key intentions in the Lyee process model, namely Capture Lyee User Requirements, Specify Lyee software requirements and Generate Lyee program. We refer to them as 'Process Intentions'. Capture Lyee User Requirements refers to all activities required to instantiate the upper level of the Product Model for a given application whereas Specify Lyee software requirements refers to all those activities that are needed to map the concepts of the upper level of the Product Model into the concepts of the lower layer. Eight strategies are used in the Lyee Process Model.

A Lyee program can be generated following different paths in the Lyee Map, in other words, using several methodological approaches. For instance, the Lyee engineer can first follow the section <Start, Specify Lyee Software Requirements, From scratch strategy>, and then <Specify Lyee Software Requirements, Generate Lyee program, LyeeAll generation strategy>. The path including these two sections was documented in [Nurcan 02]. In this paper, we focus on the two map sections drawn in bold in Figure 3.

The guidelines associated to the Lyee Map

The guideline corresponding to the map section <Start, Capture Lyee User Requirements, Design pattern driven strategy> was reported in [Rolland 02b], [Rolland 02d] and [BenAyed 03]. The two map sections <Capture Lyee User Requirements, Specify Lyee Software Requirements, Integrated mapping strategy> and <Capture Lyee User Requirements, Specify Lyee Software Requirements, N to M Mapping Strategy> describe two alternative ways to transform a PSG (concept of the upper layer of the Lyee Product Model) into a PRD (concept of the lower layer of the Lyee Product Model).

The execution of the map section <Capture Lyee User Requirements, Specify Lyee Software Requirements, Integrated mapping strategy> transforms each Node (related to a Defined) in a given PSG into a Scenario Function in the corresponding PRD. The guideline associated to this map section will be described and illustrated in §3.

The execution of the map section <Capture Lyee User Requirements, Specify Lyee Software Requirements, N to M Mapping Strategy> transforms N Nodes (with their related Defineds) in a given PSG into M Scenario Functions in the corresponding PRD. The methodological knowledge supporting this map section was formally defined and illustrated in [BenAyed 03].

The execution of the map section < Specify Lyee Software Requirements, Specify Lyee Software Requirements, Optimisation strategy> aims to perform a set of optimization operations on the Lyee Software Requirements which are described by instantiation of the concepts of the Lyee Product Model's lower layer. The guideline associated to this map section will be described and illustrated in §4.

The guideline supporting the map section <Capture Lyee User Requirements, Specify Lyee Software Requirements, Integrated Mapping strategy>

The aim of this section is to present the guideline associated to the map section <Capture Lyee User Requirements, Specify Lyee Software Requirements, Integrated Mapping Strategy> (see Figure 3), and the set of underlying mapping rules useful to establish the correspondence between the concepts of the two layers in the Lyee Product Meta-Model. Each mapping rule exploits the structural relationships between some concepts of the upper layer of the Product Meta-Model and some others in the lower layer (Figure 1). The guideline supporting the Map section <Capture Lyee User Requirements, Specify Lyee Software Requirements, Integrated Mapping Strategy> executes successively the following mapping rules for a given PSG in order to produce a PRD:

-Apply the mapping rule R0 to transform the PSG into a PRD, -For each intermediate Node of the PSG: Apply the mapping rule R1 S11 to transform the Node into a Scenario Function in the corresponding PRD, -For each Defined of the PSG: Apply the mapping rule R2 S11 to transform the Defined into one or several Logical Units in the Scenario Function; and to transform the items of the Defined into Domain Words shared by the Logical Units, -Apply the mapping rule R3 S11 to transform links between Nodes into InterSF Routing Words, -Apply the mapping rule R4 to add informations specific to the Lyee internal layer.

The Mapping Rule R0: Mapping a PSG into a PRD

In the Lyee process, each PSG is mapped into a PRD whatever the mapping strategy used. The mapping rule R0 performs the following actions: (i) Create a PRD corresponding to the PSG in hand and (ii) Define the PRD's name.

The Mapping Rule R1 S11 : Mapping a Node into a Scenario Function

The strategy of the Lyee Map presented in Section 3 is called Integrated Mapping because each Node in a given PSG is mapped into a Scenario Function. In other words, Integrated Mapping means "One to One mapping" for all Nodes. Figure 4 illustrates graphically the 'One to One Mapping' strategy applied to two Nodes related to Defineds of type 'screen'.

W03 W02 W04 W03 W03 W02 W02 W04 W04 SF01 W03 W02 W04 W03 W03 W02 W02 W04 W04 SF02 END SW02 Sc2 SW02 Sc2 SR02 Sc2 SR02 Sc2 SW01 Sc1 SW01 Sc1 SR01 Sc1 SR01 Sc1

Physical Screen

Ok Ok

Defined Sc2

Ok Ok

Defined Sc1

Cancel Cancel

Figure 4: The illustration of the 'One to One Mapping' strategy

In order to illustrate the Integrated Mapping Strategy, we use the 'Split a Goal' example. Split a Goal is a functionality which, given a goal statement such as 'Withdraw cash from an ATM', automatically decomposes it into a verb and its parameters. For example, Withdraw is the verb, cash is the target parameter of the verb and from an ATM is the means parameter. For this example, we will consider only the two parameters exemplified above, target and means. Figure 5 shows the user screen designed for the 'Split a Goal' example. The Split button triggers the decomposition of the goal statement provided by the user in the Goal widget and the display of the result of this decomposition in the widgets verb, target and means. The Cancel button allows the user to stop the process at any moment.

Figure 6 presents the instance of the concepts in the upper layer of the Product Meta-Model created during the formulation of the user centric requirements for the given example. This instance is drawn using the UML object diagram notations. It shows that there is one PSG 'PsgSplit' which is composed of one Defined of type screen, namely 'Split', gathering the input and output items of the interaction. The 'Split' Defined comprises active items (cmdSplit and cmdCancel), output items (verb, target, means) and a passive item (Goal). Each output item in the Defined 'Split' is associated with a formula that is its calculation rule.

Mapping rule R1 S11 5 : An intermediate node in the upper layer is transformed into a Scenario Function in the lower layer.

The mapping rule R1 S11 performs the following actions for a given node in the PSG:

1. Create one SF for the intermediate node of the PSG; define SFID (concatenation of the string 'SF' and a sequential number), 2. Link the SF to the PRD (the one which has been created by the execution of the mapping rule) 3. Create the three pallets W04, W02 and W03, 4. Link the three pallets to the SF (Pallet belongs to SF) 5. For each pallet, define the PalletID (concatenation of SFID and the pallet name)

Example : The PSG 'PsgSplit' was previously transformed into the PRD 'PrdSplit' by the application of the mapping rule R0. The intermediate node 'Node2' is transformed into the Scenario Function 'SF01' linked to the PRD 'PrdSplit'. The three pallets 'SF01W04', 'SF01W02' and 'SF01W03' are created and linked to 'SF01', their PalletID are specified.

The Mapping Rule R2 S11 : Mapping a Defined into Logical Unit(s)

Mapping rule R2 S11 : A Defined is transformed into one or several Logical Units in the Scenario Function created by the application of the mapping rule R1 S11 . The items of the Defined become Domain Words shared by the Logical Units.

A Defined is mapped into one or several Logical Units according to the Defined type. An Item is mapped into one or several Domain Words. These Words can belong to Logical Units in the same or in different Scenario Functions.

Let us consider an instance of PSG called PSG i6 . The intermediate node of PSG i (corresponding to the Defined in hand) has already been transformed into an instance of Scenario Function by the application of R1 S11 . Let us call Defined j the Defined in hand. The Scenario Function corresponding to the intermediate node of PSG j related to Defined j is called SF j . The mapping rule R2 S11 performs the following actions:

• If the type of Defined j is 'Screen' :

1. Create two logical units SR j and SW j 2. Specify the LogicalID and the Device (Defined name) of SRj i and SW j 3. For each input item in Defined j : (i) Create one instance of domain word, we call it word k (ii) Specify the name (item name) and the domain (item domain) of word k (iii) Associate the domain word word k to the pallet W02 of the SF j and to the SR j logical unit using a ternary relationship 4. For each output item in Defined j : (i) Create one instance of domain word, we call it word m (ii) Specify the name (item name), the domain (item domain), the L4-formula (output item formula), and the L3-condition (item L3-condition), (iii) Associate the domain word word m to the pallet W04 of the SF j and to the SW j logical unit using a ternary relationship, (iv) Associate word m to the pallet W03 of the SF j and the to SW j logical unit using a ternary relationship.

•

If the type of Defined j is 'Database' :

1. If there are input items in Defined j :

-Create one logical unit FR j -Specify LogicalID and Device (Defined name) of FR j -For each input item in Defined j : (i) Create a domain word, we call it word k , (ii) Specify the name (item name) and the domain (item domain), (iii) Associate word k to the pallet W02 of the SF j and the FR j logical unit using a ternary relationship 2. If there are output items in Defined j :

-Create one logical unit FW j -Specify LogicalID and Device (Defined name) of FW j -For each output item in Defined j : (i) Create a domain word, we call it word m , (ii) Specify the name (item name), the domain (item domain), the L4-formula (output item formula), and the L3-condition (item L3-condition), (iii) Associate word m to the pallet W04 of the SF j and to the FW j logical unit, (iv) Associate word m to the pallet W03 of the SF j and to the FW j logical unit.

Example : Figure 7 shows the instances of the concepts of the Lyee internal layer of the Product Meta-Model created by the application of the mapping rule R2 S11 to the 'Split a Goal' example. The PSG 'PsgSplit' contains a single Defined 'Split' as shown in Figure 6. The Defined 'Split' will be transformed into one or several Logical Units by the application of R2 S11 . The SF 'SF01' and the three pallets 'SF01W02', 'SF01W03' and 'SF01W04' were created by the transformation of the 'Node2' by applying R1 S11 .

The Mapping Rule R3 S11 : transforming Links between Nodes into InterSF Routing Words

Links between PSG Nodes are of three different types: Continuous, Duplex and Multiplex.

Mapping rule R3 S11 : Continuous, Multiplex or Duplex links between two Nodes are transformed into InterSF Routing Words.

All links in the PSG becomes InterSF routing words in the corresponding PRD. The Multiplex link in the upper layer of the meta-model matches up with the PNTM routing word in the lower layer. The Duplex link in the upper layer of the meta-model matches up with the PNTD routing word in the lower layer. The Continuous link in the upper layer of the meta-model matches up with the PNTC, PNTA and PNTE routing words in the lower layer according to the situation.

Let us consider SF i and SF j , two Scenario Functions obtained by the transformation of two nodes N i and N j when the rule R1 S11 has been performed. Let us consider also that N i and N j are respectively the source and the target nodes for a link L ij . We distinguish five situations depending of the types of the link, of the source and target nodes in the PSG. According to the situation, the mapping rule R3 S11 performs the following actions: Situation 1: If the link L ij is of type Continuous and the target node is 'End':

-Create a PNTE i routing word, specify the WordID -Specify NextPalletID of PNTE i (NextPalletID = End) -Link PNTE i to the W03 pallet of SF i (corresponding to the source node)

Situation 2: If the link L ij is of type Continuous and the target node is related to a Defined of type database:

-Create a PNTA i routing word, specify the WordID -Specify NextPalletID of PNTA i (NextPalletID = Pallet W04 of SF j corresponding to the target node) -Link PNTA i to the W03 pallet of SF i (corresponding to the source node) Situation 3: If the link L ij is of type Continuous and the target node is related to a Defined of type screen :

-Create a PNTC i routing word, specify the WordID -Specify NextPalletID of PNTC i (NextPalletID = Pallet W04 of SF j corresponding to the target node) -Link PNTC i to the W03 pallet of SF i (corresponding to the source node) Situation 4: If the link L ij is of type Multiplex :

-Create a PNTM i routing word, specify the WordID -Specify NextPalletID of PNTM i (NextPalletID = Pallet W04 of SF j corresponding to the target node) -Link PNTM i to the W03 pallet of SF i (corresponding to the source node) Situation 5: If the link L ij is of type Duplex :

-Create a PNTD i routing word, specify the WordID -Specify NextPalletID of PNTD i (NextPalletID = Pallet W03 of SF j corresponding to the target node) -Link PNTD i to the W03 pallet of SF i (corresponding to the source node)

Example:

The user centric requirements shown in Figure 6 includes two Continuous links. The first Continuous link has 'Begin' as source node; this concept has not an equivalent in the lower layer, in fact the immediate start point of 'PrdSplit' is the pallet W04 of the Scenario Function SF01. The second continuous link has intermediate node 'Node2' as source and 'End' as target. SF i corresponds to 'SF01' according to R3 S11 . We are in the first situation identified in this rule. Then we create a PNTE routing word and we link it to the W03 pallet of SF01.

The Mapping Rule R4 : Adding information specific to the Lyee internal layer

Some concepts of the lower layer of the meta model have no direct correspondence with the upper layer. These concepts are related to the Lyee knowledge and are necessary to execute the Tense Control Function [Negoro01a], [Negoro01b], [START_REF] Benayed | Lyee Program Execution Patterns[END_REF], [START_REF] Nurcan | Scientific Report Sc1[END_REF]. Thus, the mapping rule supports the specifications of additional information specific to the Lyee Requirements of the Lyee Internal Layer.

Mapping rule R4: Add additional information specific to the Lyee Requirements of the Lyee Internal Layer

The elements of the Lyee Internal Layer involved in this rule are IntraSF Routing Words (PNTR, PNTN) and Action Words ( PCR1, PCR2, PBOX, PWT1, PCL1, POP1, PRD1). The rule R4 performs the following actions (see [BenAyed 03] for more details):

1. Add one PNTR routing word to the W03 pallet of each Scenario Function SF i in the PRD (the PRD was obtained by the transformation of the PSG in hand by the application of the mapping rule R0) 2. Add one PNTN routing word to the W04 pallet of each SF i in the PRD 3. Add one PNTN routing word to the W02 pallet of each SF i in the PRD 4. Add one or several Input Vectors to each Scenario Function SF i in the PRD 5. Add one or several Output Vectors to each Scenario Function SF i in the PRD 6. For each output Logical Unit LU i of the PRD (created by the transformation of the PSG in hand by applying the rule R0), add Structural Vectors

The guideline supporting the map section < Specify Lyee Software Requirements, Specify Lyee Software Requirements, Optimization strategy>

This section presents the guideline associated to the map section <Specify Lyee Software Requirements, Specify Lyee Software Requirements, Optimization strategy> (see Figure 3). The optimization of a PRD consists in transforming (merging) successively two or several Scenario Functions into single ones. Two merge tactics are proposed, respectively 'Father-Child Merge' and 'Brotherhood Merge'. For a given PRD, these two tactics can be used in an intertwined manner.

The Father-Child merge tactics

The 'Father-Child merge' term means that two Scenario Functions SF i and SF j related with a Continuous link are merged into a single Scenario Function. In addition, let us specify that the Scenario Function SF i is not the source of a backward link (multiplex or duplex). In this case, SF i is called the Father Scenario Function and SF j is called the Child Scenario Function. This tactics is applicable:

(i) in the situations where the external environment or the user requirements impose one physical screen to the Human Computer Interface; in this case the father and child Scenario Functions are related to Defineds of type 'screen';

(ii) in the situations where optimization considerations require a set of clustered database accesses and where database distribution considerations allow that; in this case the father and child Scenario Functions are related to Defineds of type 'database'.

W03 W02 W04 SF01 W03 W02 W04 SF02 END SW02 SR02 SW01 SR01 W03 W02 W04

END

The "father" (SF01) and its "child" (SF02) are merged into a single Scenario Function

SF01 SW01 SW02 SR01 SR02 W03 W02 W04 W03 W03 W02 W02 W04 W04 SF01 W03 W02 W04 W03 W03 W02 W02 W04 W04 SF02 END SW02 SR02 SW01 SR01 W03 W02 W04 W03 W03 W02 W02 W04 W04

END

The "father" (SF01) and its "child" (SF02) are merged into a single Scenario Function The tactics can be applied successively several times to perform the merging between several Scenario Functions which are in sequence in the PRD. Figure 9 presents two PRDs, respectively before and after the optimization strategy being applied using the 'Father-Child merge' tactics. This figure presents the two PRDs and the related SFs using the Lyee community notations. The 'father' Scenario Function 'SF01' and the 'child' Scenario Function 'SF02' are merged in a single Scenario Function called 'SF01'.

1 Example of Father-Child merge

In order to illustrate this optimization rule, we make use of a variant of the 'Split a Goal' example.

Goal Split

Stop Return

Screen "Sc2" The PRD corresponding to the 'Split a Goal' example is shown in Figure 11.

Let us suppose that, thanks to the Design Patterns, the user interactions have been initially designed as requiring two Defineds of type screens. Figure 10 shows the two screens of the adopted variant of the 'Split a Goal' example: the Split button triggers the decomposition of the goal statement provided by the user in the Goal widget and its display in the widgets verb, target and means. The Cancel button allows the user to stop the process at any moment. The Split button triggers the decomposition of the Goal. The Stop button ends the interaction with the user.

Let us now assume that user requirements impose the use of a single physical screen to support the 'Split a goal' example. Consequently, screens 'Sc1' and 'Sc2' should be merged in the single screen 'Split'. Figure 12 shows this screen. The application of the father-child optimization rule will produce the PRD shown in Figure 13.

Optimization rule for the 'Father-child merge' tactics

This rule performs the following set of actions for a given couple of Scenario Functions (SF f , SF c ) identified as candidate to the father-child merge in the given PRD i . We consider SF f as 'Father' Scenario Function and SF c as 'Child' Scenario Function. SF k is the Scenario Function produced by the application of the optimization rule.

1. Create one Scenario Function SF k , define SFID 2. Link SF k to the PRD i .

3. Create the three Pallets W04, W02 and W03 4. Link the three pallets to SF k 5. For each pallet, define the PalletID 6. Copy InterSF routing words related to the pallets W03 of SF f and SF c to the pallet W03 of SF k , The InterSF routing word corresponding to the continuous, multiplex or duplex link between SF f and SF c should be deleted. 7. Each InterSF routing word in the PRD having SF f or SF c as target should be modified :

-if routing word type is PNTC, PNTA or PNTM then NextPalletID = Pallet W04 of SF k -if routing word type is PNTD then NextPalletID = Pallet W03 of SF k 8. Logical units and words related to the Scenario Functions SF f and SF c are linked to the corresponding pallets of the Scenario Function SF k .

-Copy and link input logical units and the related words to the W02 pallet of the Scenario Function SF k using a ternary relationship -Copy and link output logical units and the related words to the W04 and the W03 pallets of the Scenario Function SF k using a ternary relationship. 9. Add additional information specific to the Lyee internal layer7 The application of this rule for the PRD of the 'Split a goal' example shown in Figure 11 produces the PRD shown in Figure 13. The Scenario Functions SF01 and SF02 are merged into a single Scenario Function 'SF01bis'. The input logical units 'SR01' and 'SR02' are added to W02 pallet of 'SF01bis'. The output logical units 'SW01' and 'SW02' are added to W04 pallet of 'SF01bis'.

The Brotherhood merge tactics

The 'Brotherhood merge' means that N scenarios functions having the same source Scenario Function SF i in N Continuous Links for which they are targets are merged into a single Scenario Function. In addition, let us specify that the source Scenario Function SF i is not the source of any backward link (multiplex or duplex). This tactics is applicable: (i) in the situations where the external environment or the user requirements impose one physical screen to the Human Computer Interface; in this case the brotherhood Scenario Functions are related to Defineds of type 'screen'; (ii) in the situations where optimization considerations require a set of clustered database accesses and where database distribution considerations allows that; in this case brotherhood Scenario Functions are related to Defineds of type 'database'.

Figure 14 illustrates graphically the 'brotherhood merge' tactics. The tactics can be applied successively several times to perform the merging of several set of brotherhood Scenario Functions. The "brothers" SF02 and SF03 are merged into a single Scenario Function

W03 W02 W04 W03 W03 W02 W02 W04 W04 SF01 W03 W02 W04 W03 W03 W02 W02 W04 W04 END SW01 SR01 SR01 SW02 SW02 W03 W02 W04 W03 W03 W02 W02 W04 W04 SR02 SR02 SF02 SF03 SW03 SW03 SR03 SR03 W03 W02 W04 W03 W03 W02 W02 W04 W04 SW02 SR02 SF02 condition1 condition2 SW03 SW03 SR03
Figure 14 : The brotherhood merge

Example of Brotherhood merge

In order to illustrate the optimization rule we defined for the 'Brotherhood merge' tactics, we use the 'Room booking' example. Room Booking is a functionality of a traveller support system which helps the users of the system to make hotel room reservations for the customers according to their specific needs. The database includes information about customers and rooms offered for booking. The system shall let the user state his/her booking requirements in terms of date (beginning and ending dates of the booking period), as well as location of the hotel (name of the city in which the hotel shall be chosen), and category of the hotel (expressed as a number of stars).

Let us suppose that, for implementing the 'room booking' functionality, the user interactions have been initially designed as requiring three Defineds of type screens as shown in Figure 15. The user specifies the customer for which the booking is recorded, and the booking requirements for a room (booking dates, location, and desired hotel category). When the OK button is pressed, the system checks first if the customer exists. For an unknown customer, the 'customer error message' is displayed in an output screen. If the customer exists, the system checks the availability of a room satisfying the customer's requirements. If there is no available room which meets the customer's requirement, the 'Not Available Room' error message is displayed in a second output screen. The Cancel button allows the user to stop the process at any moment. The Stop button ends the interaction with the user. The PRD corresponding to the 'Room booking' example obtained by the execution of the map section <Capture Lyee User Requirements, Specify Lyee Software Requirements, Integrated Mapping Strategy> is shown in Figure 16. Let us now assume that user requirements impose the use of a single physical screen to support the 'error messages'. Consequently, screens 'Scase1' and 'Scase2' should be merged in the single screen. Figure 17 shows this screen.

W04 SF01 SW01 SR01 Sc1 W02 W03 W04 SF02 W02 W03 FR01 W04 SW02 SR02 Scase1 W02 W03 W04 SW03 SR03 Scase2 W02 W03 End CmdCancel=true ∃ ∃ ∃ ∃ Customer No Available room SF03 SF04 W04 SF01 SW01 SR01 Sc1 W02 W03 W04 SF02 W02 W03 FR01 W04 SW02 SR02 Scase1 W02 W03 W04 SW03 SR03 Scase2 W02 W03 End CmdCancel=true ∃ ∃ ∃ ∃ Customer ∃ ∃ ∃ ∃ Customer
The application of the optimization rule will produce the PRD shown in Figure 18.

Optimization rule for the 'Brotherhood merge' tactics

This rule performs the following set of actions for a given set of brotherhood Scenario Functions SF j identified as candidate to the brotherhood merge in the given PRD i . We consider SF i as the source Scenario Function in the N Continuous Links for which the brotherhood Scenario Functions SF j are targets. SF k is the Scenario Function produced by the application of the rule to the brotherhood Scenario Functions SF j .

1. Create one Scenario Function SF k , define SFID 2. Link SF k to the PRD i .

3. Create three Pallets W04, W02 and W03. 4. Link the three pallets to the SF k 5. For each pallet, define the PalletID 6. Copy InterSF routing words related to the W03 pallet of each SF j to the W03 pallet of SF k . The InterSF routing word corresponding to the continuous, multiplex or duplex link between SF f and SF c should be deleted. 7. Each InterSF routing words in the PRD which have SF f or SF c as target should be modified (same sub-actions than in the Father-Child merge) 8. Logical units and words related to each Scenario Function SF j are linked to the corresponding pallets of the Scenario Function SF k (same sub-actions than in the Father-Child merge) 9. Add additional information specific to the Lyee internal layer (same sub-actions than in the Father-Child merge) 10. Delete all Scenario Functions SF j and their related logical units and words.

The application of this rule for the PRD of the 'Room booking' example shown in Figures 15 and16 produces the PRD shown in Figure 18. The Brotherhood Scenario Functions 'SF03' and 'SF04' are merged into a single Scenario Function 'SF03bis'. The input logical units 'SR02' and 'SR03' are added to W02 pallet of 'SF03bis'. The output logical units 'SW02' and 'SW03' are added to W04 pallet of 'SF03bis'.

The guideline associated to the Map section

The guideline associated to the Map section <Specify Lyee Software requirement, Specify Lyee Software requirement, Optimization strategy> implements the following optimization rules:

For each set of Scenario Functions in a PRD describing an atomic interaction (see [Rolland02d])

For each set of SFs candidates to a brotherhood merge List the brotherhood SFs to the user If requested Apply the 'Brotherhood Merge' tactics for these SFs For each set of SFs candidates to a Father-child merge List the couple of SFs to the user If requested Apply the 'Father-Child Merge' tactics

Conclusion

We presented in this paper a formalization of the Lyee Process Model using the concept of Map. We also developed two methodological guidelines associated to two sections of the Lyee Map, respectively <Capture Lyee User Requirements, Specify Lyee Software Requirements, Integrated Mapping Strategy>, <Specify Lyee Software requirements, Specify Lyee Software requirements, Optimization strategy>.

For a given PSG, the mapping between the concepts of the Lyee user requirements meta-model and the Lyee software requirements meta-model can be performed in two alternative ways, following one of the two sections of the Lyee Map, namely <Capture Lyee User Requirements, Specify Lyee Software Requirements, Integrated Mapping Strategy> and <Capture Lyee User Requirements, Specify Lyee Software Requirements, N to M Mapping Strategy>. The guideline associated to the former allows us to generate automatically a PRD from a PSG. Experimentation with various examples shown that the mapping is possible by following the rules presented in Section 3. The result is however a PRD that could be transformed to support improvements. Furthermore, the second guideline presented in this paper implements the PRD optimization strategy.

Still now, we defined the guidelines which support the execution of the map sections. The Lyee process knowledge should be completed in order to guide the Lyee engineer to choose between two alternative sections from a source intention towards a target intention in the Lyee Map. This type of guideline, describing how other guidelines should be applied is required, for instance, to guide the selection of one of the two strategies, Integrated Mapping and N to M Mapping during the execution of the Lyee Map.

The future work includes the following tasks: (i) to develop a software support for the elicitation of the user centric Lyee requirements and the automated generation of the Lyee software requirements; (ii) to define the methodological guidelines supporting the navigation in the Lyee Map and to offer an automatic support for their execution.

Figure 1 :

 1 Figure 1: The Lyee Product Meta-Model

Figure 2 :

 2 Figure 2: The map meta-model

Figure 3 :

 3 Figure 3: The Lyee process model : the Lyee Map

Figure 6 :

 6 Figure 5: The user screen for the 'Split a Goal' example

Figure 7 :

 7 Figure 7 :The product resulting of the application of the mapping rule R2 S11 to the 'Split a Goal' Example

Figure 8 Figure 8 :

 88 Figure8shows the instances of the concepts of the Lyee internal layer of the Product Meta-Model created by the application of the mapping rules R3 S11 and R4 to the 'Split a Goal' example.

Figure 9 :

 9 Figure 9: The father-child merge

Figure 10 :Figure 11 :

 1011 Figure 10: The user screens for the 'Split a goal' example

  Figure 12 : The user screen for the 'Split a goal' example

  a) Add one PNTR routing word to the W03 pallet of the Scenario Function SF k , specify NextpalletID as Pallet W04 of SF k b) Add one PNTN routing word to the W04 pallet of SF k , specify NextpalletID as Pallet W02 of SF k c) Add one PNTN routing word to the W02 pallet of SF k , specify NextpalletID as Pallet W03 of SF k d) Add Input Vectors to the Scenario Function SF k e) Add Output Vectors to the Scenario Function SF k f) For each output Logical Unit LU i related to SF k add Structural Vectors 10. Delete the Scenario Functions SF F and SF C and their related logical units and words.

Figure 15 :

 15 Figure 15: The user screens for the 'Room booking' example

Figure 16 :

 16 Figure 16 : The PRD of 'Room booking' example

Start End Capture Lyee User Requirements Specify Lyee Sotware Requirements Generate Lyee Program

	Scenario Driven	From Scratch Strategy
	Strategy
		Optimisation
	Design Pattern	Stategy
	Driven strategy
	N to M
	Mapping Strategy
		LyeeALL
		Generation
		Strategy
	Completness
	Strategy

Integrated Mapping Strategy Start End Capture Lyee User Requirements Specify Lyee Sotware Requirements Generate Lyee Program

	Scenario Driven	From Scratch Strategy
	Strategy
	Design Pattern	Integrated Mapping Strategy	Optimisation Stategy
	Driven strategy
	N to M
	Mapping Strategy
			LyeeALL
			Generation
			Strategy
	Completness
	Strategy

Customer Begindate Enddate Room Booking City Stars Ok Cancel Customer Begindate Enddate Room Booking City Stars Ok Cancel Customer existence error Message Return Stop Customer existence error Message Return Stop Customer Error Message No Available room error Message Return Stop No Available room error Message Return Stop

	Not Available Room Error
	Message

Customer existence error Message Return Stop No Available room error Message Return Stop Customer existence error Message Return Stop No Available room error Message Return Stop Figure 17 : The user screen For the two error messages W04 SF01

	Sc1 Sc1		SF01
	W04	W02 W02	W03 W03		SF02 SF02
	SW01 SW01	SR01 SR01
				W04 W04	W02 W02	W03 W03
			Scase Scase	FR01 FR01	SF03bis SF03bis
	∃ ∃ ∃ ∃ Customer or No Available room ∃ ∃ ∃ ∃ Customer or No Available room ∃ ∃ ∃ ∃ Customer or No Available room	W04 W04	W02 W02	W03 W03
				SW02 SW02	SR02 SR02
				SW03 SW03	SR03 SR03
		CmdCancel=true CmdCancel=true		End End
	Figure 18 : The 'Optimized PRD' for the 'Room booking'
			example

We use an E/R like notation. A box represents en Entity Type (ET), the labeled link represents a Relationship Type (RT) and the embedded box refers to an objectified RT.

Intention are in italics (I i , I j )

Strategies are in " arial narrow "(Sij)

This notation expresses that R1 S11 is the first rule corresponding to the 'Integrated mapping' strategy. In fact, the mapping rule R0 and R4 are also used when the 'N to M mapping' strategy is applied.

The sub-index letter is used to indicate an instance of a concept, for example Defined j is an instance of concept Defined.

See [BenAyed 03] for more details.


Ludovic Paulhac

Vinh-Thong Ta

Rémi Mégret

Relaxed Cheeger Cut for Image Segmentation

Motivated by recent advances in spectral clustering that show the relation between the non linear p-Laplacian graph operator and the Cheeger cut problem, we propose to study and apply this methodology for image segmentation. Based on a 1 relaxation of the initial clustering problem, we show that these methods can outperform usual well-known graph based approaches, e.g., min-cut/max-flow algorithm or 2 spectral clustering, for unsupervised and very weakly supervised image segmentation. Experimental results demonstrate the benefits and the relevance of the proposed methodology especially for noisy image or when very few pixels are labeled for interactive image segmentation.

Introduction

Graph cut methods consist in dividing a dataset into two or more clusters where the data relations are modeled as a similarity graph. Such approaches have found several applications, for instance in image segmentation, statistics or biology (see [START_REF] Schaeffer | Graph clustering[END_REF] and references therein). Solving balanced graph cut problems is wellknown to be NP-hard [START_REF] Luxburg | A tutorial on spectral clustering[END_REF]. One of the most popular approximation is to consider spectral graph clustering. These methods are usually based on a 2 relaxation of the initial problem [START_REF] Nascimento | Spectral methods for graph clustering -a survey[END_REF]. They reduce the initial cut problem to the computation and the thresholding of the second smallest eigenvector of the associated graph Laplacian operator. Different definitions of the Laplacian operator correspond to an approximation of different balanced graph cut criteria. We refer the interested reader to [START_REF] Luxburg | A tutorial on spectral clustering[END_REF] for an introduction on spectral clustering. Recently, [START_REF] Bühler | Spectral clustering based on the graph p-Laplacian[END_REF][START_REF] Hein | Beyond spectral clustering -tight relaxations of balanced graph cuts[END_REF][START_REF] Szlam | Total variation and cheeger cuts[END_REF] have proposed a relaxation method based on the general p-Laplacian and show that the relaxed problem provides an exact solution of the Cheeger cut [START_REF] Cheeger | A lower bound for the smallest eigenvalue of the Laplacian[END_REF] when p=1. The authors show the superiority of such approach in comparison with the 2 relaxation based methods to cluster complex data.

Paper contributions.

Inspired by these recent advances in graph clustering, we propose to study and apply such methods for image segmentation. We demonstrate the superiority of theses approaches in presence of noise and propose an extension for interactive segmentation, which requires very few labeled pixels to obtain correct segmentation results. To the best of our knowledge, these novel methods have not been used for image processing. Therefore, one of our contributions is to demonstrate the relevance of theses methods for image segmentation. Paper organization. Section 2 recalls the Cheeger cut and its spectral relaxation. Section 3 presents the application of this methodology to image segmentation. Results and comparisons with usual graph cut methods such as min-cut/max-flow algorithm or standard 2 spectral clustering for noisy and interactive image segmentation are also provided. Finally, Section 4 concludes and presents the perspectives of this work.

p-Laplacian and Cheeger Cut

We consider the general situation where a data set is modeled as a graph G = (V, E) where V is a set of vertices that represents the data points, and E : V ×V a set of edges weighted by a function w ij for all (i, j) ∈ E that captures similarity relationship between the vertices. A method to find the balanced clustering of V is to consider the following Cheeger cut (CC):

CC(A, A) = cut(A, A) min(|A|, |A|) = i∈A,j∈A w ij min(|A|, |A|) (1)
where A ⊂ V , A = V \ A and |.| denotes the cardinality of the considered set. One simple interpretation of CC is that the weighted length of the cut boundary is small relatively to the balanced constraint. Because of the balanced condition, finding the global minimum of (1) is NP-hard. The most well-known approach to approximate the solution of ( 1) is to consider a 2 relaxation reducing the initial problem to an eigenvector problem associated to the 2 graph Laplacian [START_REF] Luxburg | A tutorial on spectral clustering[END_REF].

Recently, [START_REF] Bühler | Spectral clustering based on the graph p-Laplacian[END_REF][START_REF] Hein | Beyond spectral clustering -tight relaxations of balanced graph cuts[END_REF][START_REF] Szlam | Total variation and cheeger cuts[END_REF] have introduced a stronger relaxation based on the p-Laplacian: let L p be the graph p-Laplacian operator defined as

(L p f ) i = j∈V w ij |f i -f j | p-1 sign(f i -f j ) (2)
where i ∈ V , sign(.) ∈ [-1, 1] and f : V → [0, 1].

In [START_REF] Bühler | Spectral clustering based on the graph p-Laplacian[END_REF], the authors have shown that the optimal Cheeger cut value h CC = inf A⊂V CC(A, A) can be approximated by a relaxation based on (2). They have proved that when p → 1 the solution of the relaxed problem tends to h CC . Inspired by these results, [START_REF] Szlam | Total variation and cheeger cuts[END_REF] and later [START_REF] Hein | An inverse power method for nonlinear eigenproblems with applications in 1-spectral clustering and sparse PCA[END_REF], have proved that when p = 1 the associated 1 relaxation problem leads to an exact solution of the CC minimization. Finally, they have proposed to optimize the following problem

f * = argmin f f, L 1 f f 1 = n i,j=1 w ij |f i -f j | f 1 (3)
s.t. m(f )=0 where m(.) is the median. To optimize (3), the split Bregman method is used in [START_REF] Szlam | Total variation and cheeger cuts[END_REF] whereas a primal-dual algorithm is used in [START_REF] Hein | Beyond spectral clustering -tight relaxations of balanced graph cuts[END_REF]. Finally, f * is thresholded (see for example [START_REF] Hein | An inverse power method for nonlinear eigenproblems with applications in 1-spectral clustering and sparse PCA[END_REF]) to obtain the final graph partitioning. In this paper, we will consider the split Bregman approach.

Image Segmentation via Cheeger Cut

In this section, we describe and apply the previous graph cut methodology in the context of image segmentation and we compare the performance of theses methods for unsupervised and interactive cases.

Methodology

Graph construction. An image is represented as a 4adjacency grid graph where each vertex is associated to an image pixel and edges encode the 4-adjacency spatial relationship. The segmentation is performed only by using the pixel grayscale value as image feature in order to demonstrate the relevance and the efficiency of CC. For the same reason, the weight function uses only the pixel grayscale value. A weight

w ij = exp(-I(i) -I(j) 2 /2β 2 ij
) is defined for two adjacent pixels i and j where I(.) is a pixel grayscale value and β is a bandwidth parameter. In the rest of this paper, β will be set to the mean value over all I(i) -I(j) , ∀i, j ∈ I.

Obviously, incorporating higher level information that capture more complex image features in the graph structure and weights could improve the results but are out of the scope of this paper.

Unsupervised segmentation algorithm. Unsupervised image segmentation consists in extracting objects from images without any human intervention. Algorithm 1 describes the optimization of relaxed CC which is applied on the graph constructed on the image.

First, the solution f * of ( 3) is computed in steps 2 to 6, where R(.) and S(.) correspond to the numerator and the denominator of (3) respectively. Then, the final partitioning (A, A) is obtained with

: ∀i ∈ V , i ∈ A if f * i ≤ 0.5, i ∈ A otherwise.
Algorithm 1 Approximation of (3) and h CC .

1:

f 0 = random, f 0 = 1, λ 0 = R(f 0 )/S(f 0 ) 2: repeat 3: f k+1 = argmin R(f k ) -λ k S(f k ) s.t. m(f k+1 ) = 0 and f k+1 2 ≤ 1 4: λ k+1 = R(f k+1 )/S(f k+1 ) 5: until |λ k+1 -λ k |/λ k < 6: f * =f k+1 7: (A, A) = thresholding of f * 8: return (A, A)
The inner problem in step 3 of Algorithm 1 is transformed into the following constrained minimization problem [START_REF] Bresson | Multiclass transductive learning based on 1 relaxations of cheeger cut and mumford-shah-potts model[END_REF][START_REF] Szlam | Total variation and cheeger cuts[END_REF]

min f,g∈[0,1],d d 1 -λ g 1 s.t. d = Df, g = f and i∈V g i < |V |/2. ( 4
)
D is a linear operator with Df 1 = n i,j=1 w ij |f if j |. The last constraint on g ∈ [0, 1] corresponds to a linear approximation of the non linear constraint m(g) = 0 (see [START_REF] Bresson | Multiclass transductive learning based on 1 relaxations of cheeger cut and mumford-shah-potts model[END_REF]). Optimization of (4) can be performed with an augmented Lagrangian method where three sub-minimizations w.r.t f , g and d are considered. Due to the lack of space, we refer the reader to [START_REF] Bresson | Multiclass transductive learning based on 1 relaxations of cheeger cut and mumford-shah-potts model[END_REF][START_REF] Szlam | Total variation and cheeger cuts[END_REF] for a detailed description of this split Bregman approach and the sub-minimizations resolution.

Adaptation to weakly supervised image segmentation. Interactive segmentation has received a lot of attention in recent years. In its binary version, it consists in separating the image foreground from the background using initial labels (strokes) defined by the user for both objects to detect. One objective of this approach is to perform the segmentation with the fewest user interaction as possible. Moreover, most of such methods use prior information on images: for example, color likelihood, boundary prior or geometric constraints (see [START_REF] Vicente | Graph cut based image segmentation with connectivity priors[END_REF] and references therein).

In order to incorporate user provided initial labels, we slightly modify the optimization of (4). Let V f and V b be the initial foreground and background labeled pixel sets. Function f 0 in Algorithm 1 is initialized as

f 0 i = 0 if i ∈ V b , f 0 i = 1 if i ∈ V f
and f 0 i = 0.5 otherwise. Throughout the optimization process, the values of g at the labeled pixels are maintained to their initial value at the end of each sub-minimization w.r.t. g, i.e., g i = 0 and g i = 1 if i ∈ V b and i ∈ V f , respectively.

Results

In this section, we apply the previously describe methodology for unsupervised and interactive segmentation. In the following results, boundaries of obtained segmentations (presented in Figures 1, 2 and3) are superimposed on initial test images and are artificially dilated to increase the visibility.

Unsupervised image segmentation. We first compare CC with the popular min-cut/max-flow algorithm (MC) [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF] and 2 spectral methods: the Ratio Cut (RC) [START_REF] Hagen | Fast spectral methods for ratio cut partitioning and clustering[END_REF] and the Normalized Cut (NC) [START_REF] Shi | Normalized cuts and image segmentation[END_REF]. Results for MC are obtained by using publicly available C code from authors where the sink and source vertices are set to a pixel within the partitions to segment. Since we use [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF] to optimize the min-cut problem, the data fidelity term involving in [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF] energy is not used. For RC and NC, different 2-Laplacian operators are used, and the cut is obtained by thresholding the associated second smallest eigenvector [START_REF] Luxburg | A tutorial on spectral clustering[END_REF].

Figure 1 shows unsupervised segmentation results with two synthetic examples where different additive Gaussian noise level are applied on binary images to illustrate the effect of noise. The σ parameters presented in these results are chosen in order to illustrate the noise level at which these methods begin to fail. The green, yellow, blue and red colors in Figure 1 correspond to MC, RC, NC and CC, respectively. To give a quantitative evaluation of the segmentation results, an error rate is computed. It is defined as a percentage of misclassified pixels with respect to the ground truth. Table 1 presents the corresponding measures computed for each segmentation in Figure 1 where best results are presented in bold.

Regarding the measures obtained in the first part of Table 1 that correspond to segmentation results of Figure 1(a)-(d), one can see that CC outperforms the other methods whatever the noise level. We can observe that MC fails up to σ = 0.07 where segmentation results correspond to the initialization involving in the algorithm (Figures 1(b) to 1(d)). As shown in Figures 1(c) and 1(d), RC and NC are not able to provide correct segmentation when the noise level increases. The second part of Table 1 Table 1. Error rates for segmentations of Figure 1 (see text for more details) the same behaviors. Nevertheless, we can notice that for σ = 0.25, CC results are better on the first image than on the second one where objects are not of the same size.

and Figures 1(e)-(h) show approximately

The previous results clearly demonstrate the efficiency of CC for unsupervised noisy image segmentation. They also show the benefit of the 1 relaxation as compared to 2 one for balanced cuts approximations.

Very weakly supervised image segmentation. We show how CC can be applied to interactive image segmentation where very few labels (some pixels) are used as initialization and without any data fidelity or prior term while obtaining satisfying qualitative results.

Figure 2 shows results and comparisons of CC and MC. the boundaries of the segmentation results and the initial labels are superimposed on the initial images where white color are used for boundaries, red and blue colors for initial foreground and background labels, respectively (initial labels are artificially dilated to increase the visibility). Figures 2(a

Conclusion and Future Work

In this paper, we have presented a novel methodology based on 1 relaxation of Cheeger cut problem for image segmentation. Our study shows the potential and the relevance of this novel approach in a noisy context and for interactive segmentation where very few initialization is needed to obtain comparable result with the state of the art.

Due to the iterative optimization process, methods presented in this work are less efficient in term of computation time compared to, for instance, the mincut/max-flow algorithm. Nevertheless, due to the locality of computations, it could be implemented on CPU/GPU platforms.

Finally, the ability of the proposed method to handle a very sparse initial labeling could be leveraged by allowing automated initialization by non dense interest point detectors. This opens new possibilities in the initial phase of the segmentation, when only little information is known about the objects to extract.

Figure 1 .

 1 Figure 1. Qualitative comparison. MC: green, RC: yellow, NC: blue, CC: red (see text for more details)

  ) and 2(c) show interactive CC segmentation results on natural images where

Figure 2 .Figure 3 .

 23 Figure 2. Results of interactive segmentation. At left CC with very few labeled pixels. At right MC with large number of labeled pixels (see text for more details)