Mahamadou Belem
email: mahamadou.belem@mpl.ird.fr

Sansan Youl
email: youl@ird.bf

Jean-Luc Chotte
email: jean-luc.chotte@mpl.ird.fr

Bruno Barbier
email: bbarbier@cirad.fr

Christophe Lepage
email: christophe.l@chula.ac.th

Raphaël Manlay
email: manlay@engref.fr

MIROT: A multi-agent system model for the simulation of the dynamics of carbon resources of a West-African village territory

Keywords:

The decrease in carbon (C) resources in West African savannas falls within local agroecological and global environmental issues. Understanding how they are impacted by human activities at the village level is thus crucial. Multi-agent system (MAS) formalism can assist in representing the complex interactions between ecological and socio-economic dynamics. A MAS model (MIROT) was implemented into the CORMAS platform to simulate the dynamics of C resources of a

village in Burkina Faso. The representation of the environment was achieved by importing data from digital maps. Two bio-economic models (implemented with GAMS) were coupled with MIROT and used to simulate optimized farmer's strategies of decision at the farm level. Various scenarios were compared from simulations to assess the relative impact of climatic, demographic, economic or social factors on the viability of the village system as estimated by its carbon budget.

INTRODUCTION

In sub-Saharan Africa the availability in and cycling of carbon resources largely determine the viability of smallholders' low-input, farming systems. These rely on the soil organic carbon (SOC) content as well as the availability of wood, grain, fodder, all organic resources. Within the context of global change and within the Clean Development Mechanism of the Kyoto Protocol, developing countries may be funded by Annex-I parties to the United Nations Framework Convention on Climate Change for their efforts in mitigating the greenhouse gases content in the atmosphere (UNFCCC, 1997).

Carbon (C) resources are declining in West African savannas [START_REF] Ker | Farming Systems in the African Savanna. A Continent in Crisis[END_REF]. Improving their management is thus crucial from both local agroecological and global environmental points of view. Since carbon resources are renewable and, to a certain extent, shared between several decision-makers, particular attention should be paid to the level at which improvements are conceived and promoted. In West-African savannas, the village territory level must be considered, because of the functional connection between the land use systems and the communal control of fertility management practices and of land tenure (Manlay et al., 2004a).

Carbon dynamics of a village territory is complex. It involves interactions at several scales of time (day, month, season, year) and space (plot, farm, village territory and beyond). These interactions occur between actors in the system, and between actors and their environment. The environment drives the human activities: such as agricultural practices or breeding. Environmental conditions are subjected to complex external factors: climate change, global socio-economic context, etc. Through their activities human societies contribute to the transformation of the environment. In turn environment modifies the behaviour of human beings to adapt to the new conditions, and so on.

To understand such a complex system, tools simulating the state of the future environment and human behaviours along plausible scenarios are needed. Descriptive approaches can only assess past and present situations. At the plot level, forecasts can be made using real experiments. But at the farming system and regional levels the multiplicity of actors and scales of time and space makes computer modelling a better experimental tool to analyse the C cycle. This study aimed at developing a tool for the quantification of the carbon flows and stocks of a village territory. For this purpose a model that would represent the biophysic and socio-economic determinants of C dynamics in a territory was implemented and tested.

Our assumptions were the following:

1. Any relevant analysis about decisions on the management of organic (associated C and nutriments) resources must encompass the village territory level because of their communal regulation.

2. The multi-agent system (MAS) is a tool for prospective analysis which adequately supports the analysis by anticipation of the dynamics of the natural resources at the scale of the village territory. These analyses are made according to a range of scenarios of land management.

In the following section, multi-agents systems are defined and the study site is described. Then basic explanations about the functioning of carbon dynamics in the farming system and the conceptual framework of the MIROT model are provided. Finally simulations for some key variables under simple scenarios are shown and results are discussed.

MODELLING CARBON DYNAMICS IN HUMAN COMMUNITIES

The management of a renewable resource involves complex interactions between social and ecological dynamics. Models can help better to understand the mechanisms underlying these interactions and predict the likely impact of various collective rules and policies. Models apprehend the phenomenon studied through the representation of its principal factors. The understanding of the carbon dynamics requires considering the biological, social, physical, economic and political factors. However taking into account these major factors requires a study at a large scale such as the village, the region or the country.

Several studies simulated the organic stock management and carbon at the scale of the rural community in West Africa [START_REF] Reenberg | A hierarchical approach to land use and sustainable agricultural systems in the Sahel[END_REF][START_REF] Barbier | Induced innovation and land degradation: results from a bioeconomic model of a village in West Africa[END_REF][START_REF] Defoer | Participatory action research and quantitative analysis for nutrient management in southern Mali. A fruitful marriage?[END_REF][START_REF] Stephenne | A dynamic simulation model of land-use changes in Sudano-sahelian countries of Africa (SALU)[END_REF]Manlay et al., 2004c ;Manlay et al., 2004b ;[START_REF] Tschakert | The costs of soil carbon sequestration: an economic analysis for smallscale farming systems in Senegal[END_REF]) but these are theoretical, or strictly qualitative, or spatially non-explicit. Generally they do not take into account actors' diversity and restrict to an oversimplified set of their activities [START_REF] Thornton | Integrated crop-livestock simulation models for scenario analysis and impact assessment[END_REF].

This communication describes a multi-agents model that simulates the dynamics of carbon (and related nitrogen) resources at a village territory scale in the south-west of Burkina Faso: Touroukoro. The model integrates two types of farmers and the activities of cattle intervening in the spatial distribution of the organic matter. It integrates constraints related to resource use: equipment, cash, land, cattle, etc. Thus, we use two bio-economic models built with Gams (General Algebraic Modelling System) to optimize the rules of decisions of the farmers.

MULTI-AGENT SYSTEMS AND OPTIMIZATION

MAS have become a popular tool to simulate the dynamics of a renewable resources [START_REF] Axtell | Why agents? On the varied motivations for agent computing in the social sciences[END_REF][START_REF] Abrami | Niveaux d'organisation dans la modélisation multi-agent pour la gestion de ressource renouvelables: Application à la mise en oeuvre de règles collectives de gestion de l'eau agricole dans la basse-vallée de la Drôme[END_REF][START_REF] Barreteau | Suitability of Multi-Agent simulations to study irrigated system viability: application to case studies in the Senegal River Valley[END_REF][START_REF] Bousquet | Multi-agent simulations and ecosystem management : a review[END_REF]. Then, the MAS application domains go increasely: agronomy, economy, Internet, etc.

MAS come from the need to have heterogeneous agents able to coordinate their actions in order to solve a problem in the same system. An agent is considered here as an "autonomous entity capable of reacting to its environment, determining its most appropriate goals and actions in its world, and reasoning about deadlines and tradeoffs arising from those determinations" [START_REF] Vincent | An Agent Infrastructure to Build and Evaluate Multi-agent Systems : The Java Agent Framework and Multi-agent System Simulator[END_REF]. The capacity of an agent to modify its environment is determined by a set of actions assigned to him, thus defining its competences. A MAS is a set of agents representing the actors of the world studied. MAS are virtual laboratories controllable and observable by the operators. Because of its flexibility, MAS become a sustainable tool to represent and simulate complex systems [START_REF] Jennings | On agent-based software engineering[END_REF].

The dynamic of carbon considered at the scale of the territory village is a complex system. It is characterized by a great number of entities (e.g. vegetation, climate, soil, cattle, farmers which adopt different types of rotation) requiring an individual treatment. Also, the study of dynamics at the scale of the territory village is interested in flow of carbon in the soil, consequently its spatial distribution (Manlay et al., 2004c). The soil in this case, is carrying resources being the subject of a use by the various actors of the system. Thus, a spatial modelling will make it possible to take into account the interactions between social and spatial dynamic. We retained the MAS formalism, in order to represent the dynamic of carbon in all its complexity.

MAS agents evolve in a dynamic, complex and unforeseeable environment. It is difficult to predict correctly the behaviour of environment. To adapt and react to the various changes, the agents use individual or collective actions. A new organization can emerge [START_REF] Drogoul | Multi-agent Simulation as a Tool for Analysing Emergent Processes in Societies[END_REF][START_REF] Müller | Emergence of collective behaviour and problem solving[END_REF]) from these interactions. These characteristics are useful to clarify problems of coordination involved in the management of a resource.

Within the same model MAS can represent various levels of organization (from individual to groups) and make the articulations between these levels of organization explicit [START_REF] Servat | When agents emerge from agents: an introducing multi-scale Viewpoints in Multi-Agents Simulation[END_REF][START_REF] Hilaire | Vers une approche de spécification, de prototypage et de vérification de systèmes multi-agents[END_REF][START_REF] Amiguet | MOCA : Un modèle componentiel dynamique pour les systèmes multiagents organisationnels[END_REF][START_REF] Abrami | Niveaux d'organisation dans la modélisation multi-agent pour la gestion de ressource renouvelables: Application à la mise en oeuvre de règles collectives de gestion de l'eau agricole dans la basse-vallée de la Drôme[END_REF][START_REF] Tranouez | Contribution à la modélisation et à la prise en compte informatique de niveaux de descriptions multiples[END_REF]. By taking into account the various levels of organization of a system, MAS make it possible to study which a same model various points of view.

Space constitutes a central element in the interactions between the agents. Space carries the resources which are the subject of a common use by the various entities. Multi-agents models can take into account the spatial organization of resources and the spatial constraints of their management [START_REF] Bonnefoy | Modelling spatial practices and social representations of space using multi-agents[END_REF][START_REF] Bonnefoy | Modélisation d'une interaction individus, espace et société par les systèmes multi-agents: pâture en forêt virtuelle[END_REF][START_REF] Dumont | Multi-agent simulation of group foraging in sheep: effects of spatial memory, conspecific attraction and plot size[END_REF][START_REF] Lion | La modélisation comme outil d'aide à la gestion: Le cas de la colonisation forestière des pelouses sommitales du mont Lozère (Cévennes, France)[END_REF]. Thus, through spatial modelling and the modelling of the actions of the actors, the MAS highlight the impact of the various uses on dynamics of space. One of the major problems in environmental sciences is the representation of space on several hierarchical scales. Several platforms such as CORMAS provide utilities to represent the heterogeneity of space and the interactions which exist between social and spatial dynamic.

For the implementation of Mirot Model, CORMAS (Common-Pool Resources and System Multi-Agent) [START_REF] Bousquet | Cormas : Common-pool resources and multi-agents systems[END_REF] was used as a platform of simulations.

OPTIMISATION

The system studied is a semi-marketed agriculture where the main objective of the farmers is supposed to be the satisfaction of food and monetary needs. Farmers' decisions are influenced by a whole of constraints. To this end, Capillon in [START_REF] Herve | A modelling approach for analysis of agro pastoral activity at the one-farm level[END_REF]) defines an agricultural system as ''a decision-making chain within a set of constraints and assets, implemented to achieve one or more goals, that governs production processes and can be characterised by flux (money, material, information, and labour) within and outside of the farm.'' Roughly, farmers are constrained by the limitation of the resources and the state of the environment to produce and sell their production in an optimal way. Within such a view two bio-economic models were used to optimize two farmers' sets of decisions: (1) cropping strategy, and (2) programming of sale of agricultural production. The GAMS software was used for optimization steps.

Mathematical-programming models are used to simplify the behaviour of the multi-agent model. Some of the results of the simulations of the MAS were used as parameters for the mathematical models and vice versa.

STUDY SITE: THE VILLAGE TERRITORY OF TOUROUKORO

The village of Touroukoro is located in the south-west of Burkina Faso in the Comoé province. The climate is of sudanian type with rainfalls higher than 1000 mm allowing to grow a wide variety of crops [START_REF] Bonkougou | Déterminants socio-économique de la gestion des ressources en carbone par les exploitants dans le terroir de Torokoro. Province de la Comoé (Burkina Faso[END_REF].

The population of Touroukoro is highly diverse with either indigenous or migrant coexisting ethnic groups [START_REF] Bonkougou | Déterminants socio-économique de la gestion des ressources en carbone par les exploitants dans le terroir de Torokoro. Province de la Comoé (Burkina Faso[END_REF]. It is growing fast because of high natality rate and high immigration flow.

Two major, contrasted farming systems can be distinguished:

1. an indigenous system of semi-continuous crops based on yam (Figure 1): practised by the natives with rotation of yam/maize/sorghum then grains during two (2) or three (3) years before returning the land into long fallow (for ten years or more); Crops cultivated in Touroukoro can be subdivided into two categories: cash crops (cotton, yam), and food crops (maize, sorghum, etc.). Cattle husbandry is the second source of income and cashew production is the third source of income. Cashew tree planting also aims at securing land.

A SIMPLIFIED DESCRIPTION OF CARBON DYNAMICS OF A VILLAGE TERRITORY

Description of carbon dynamics at the village territory scale answers at several levels of description: plot, farm and village territory.

THE PLOT LEVEL

Carbon is fixed in the ecosystem in an organic form primarily by photosynthesis in the arbour-ground biomass of plants. Through respiration a fraction of the carbon stored returns to the atmosphere. Plants fill the litter and soil compartments after senescence of their above and below-ground organs and humification. Animal dung deposition also contributes to SOC accretion. A portion of SOC is transferred by erosion and lixiviation. Finally, SOC content depends on soil characteristics (depth, texture, etc.) and human activities (e.g. management practices, wood harvest, bush fires, etc.)

THE FARM LEVEL

Carbon dynamics at the farm level is -to some extent-the aggregation/addition of the carbon dynamics occurring at the plot level, but not only. Farmer's main objective is the satisfaction of his needs of food, cash, and social recognition. Demand is driven by measurable features of the household (such as community size), but not only. It is constrained by money, labour availability and other means of production. Farmer's needs, among other things, define management schemes that drive carbon dynamics (accretion, uptake, turn-over) in each plot -individually or mutually with nearby plots-as well as livestockor harvest-mediated carbon flows set across the farm boundaries.

THE VILLAGE TERRITORY LEVEL

At village territory level, behaviour and decisions of a single actor are controlled by her/his community, other actors, and collective structures (committees, customary authority) operating at different scales. To achieve their goals actors interact through institutions (formal or abstract) such as the market. Interactions can be set through tenurial or manuring agreements that modify the carbon allocation and transfers.

Carbon dynamics at the village territory level is also influenced by the coexistence of contrasted types of socio-economical and cultural groups. One type can have contrasted access to, and practices for the management of resources (among which carbon) that may be synergistic or antagonists with those of other groups. These distinctions are often influenced by the social membership.

Additionally landscape patterns of rainfall, soil, vegetation and freshwater distribution drive the behaviour of decision-makers and constraint access to communal carbon pools. The complexity and instability of environment require permanent adaptation from local decision-makers.

MIROT, AN OPTIMIZING MAS

A MAS typically includes agents, objects, organization and structure of its environment. In MIROT, the agents Farmer and Cattle are the two active entities. The system mimics their behaviour and their dynamic.

FARMER

The Farmer agent is a cognitive agent. Its database determines its knowledge on the state of its environment, and a base of rules enabling it to determine the action to be carried out in a given situation.

It has the knowledge of the existence of the other agents. It exchanges information with them. Farmer's main features are household size, cash disposal, food and livestock stocks, and available land.

The Farmer tries to optimize its utility while satisfying its needs for food and cash (Figure 3). Needs for food and cash depend on the family size (Equation 1 and Equation 2). To achieve its objectives Farmer must set the surface needed for each crop. It defines an optimal plan of production according to the adopted strategy. The production plan depends on resources (land and labour) availability and biophysical factors requiring a rational behaviour from the farmer.

Exploitation of the plot (e.g. through fertility decrease) changes the environment of the farmer and yields an information feedback (production). This feedback will influence the Farmer's future behaviour. For instance positive feedback induces investment in cattle and equipment to improve production. Investments are made with the Farmer's cash income. Farmer establishes a selling plan for each crop while taking into account the constraint of satisfaction of food and money. If the farm production becomes too low, the Farmer can migrate or change its strategy. Farmer also adapts to the state of the environment.

Equation 2: Model of assessment monetary need

It uses past recent experience to minimize risks: year after year, the agent Farmer's memory is updated with yield achieved. The memory is limited to five years. From its memory, the Farmer defines lowest possible yields and productions and thus minimal surfaces for each crop. This rule guarantees an optimal level of satisfaction of its need. The satisfaction of the needs is a condition for the stability of the Farmer. When the needs are not satisfied and cash is not sufficient, a part of the household migrates towards a new farm or leaves the village. Given these descriptions the farmer is a rational entity able to act so as to improve his utility.

AGENT CATTLE

Agent Cattle is a located agent. It is characterized by its size and the quantities of organic matter ingested and deposited monthly. The representation of the cattle activity in the system makes it possible to take into account their role in the transfer of organic matter/fertility [START_REF] Landais | Système d'élevage et transferts de fertilité dans la zone des savanes africaines[END_REF]. It is a reactive entity which functions by stimulus.

In the MIROT model, the activity of the cattle is represented through the following elements: ingestion, excretion and mobility rules. The principal objective of the Cattle is the satisfaction of its requirement in fodder and water, some resources distributed on the environment. To access these resources, the Cattle must move. Plot attractiveness is a function of fodder availability. Cattle can not access some land use (orchards and crops). Thus, from its current place, the Cattle selects the best pastures.

The direction of moving determines the distance walked on a plot and the residence time of the agent Cattle. The residence time depends on the travel rate. Grass intake (Equation 3) and dung deposition (Equation 4) are calculated. The displacement of Cattle is limited by a maximum duration of daily moving and the satisfaction of Cattle needs.

THE OTHER OBJECTS OF THE SYSTEM

Other main objects in MIROT are:

-Climate, that evaluates monthly rainfall, -Time, which evaluates the year and month of simulation, -Month, which describes the evolution of data according to the month of the year. It is described by the name and average rainfall of the month, and the monthly fodder needs and excretion for an animal, -Crop, which describes the various types of crop used in the model. A Crop is characterized by its type, selling and purchase price, gross and direct margin and fertility requirements, -Cropping_Culture that describes the cropping system, each cropping system being characterized by its type, and crop rotation (treated as an ordered list of crops),

-Storage, which defines the quantity of grains stored in the household's loft.

SPATIAL ORGANIZATION

To carry out an explicit representation of the environment a multilevel organisational structure of space was adopted. Three levels were distinguished (Figure 4):

-Level 1 corresponds to the elementary spatial entities (that is, the plots) of the system, -Level 2 corresponds to the spatial entities formed by aggregates of the spatial entities of level 1 gathered according to a common characteristic. The entities of Level 2 are either (1) non appropriated, in which case they are covered by savanna/forest vegetation, or (2) they belong to one Farmer and as such define the boundaries of its cropping, planting and breeding activities.

-Level 3 represents the simulated landscape at the village territory.

SPACE CONFIGURATION

The space of simulation is reproduced thanks to an importation of data from a geographical information system (GIS) into CORMAS (Figure 5). This importation, based on the morphopedological map of Touroukoro increases the realism of the model by taking into account some actual spatial constraints on the behaviour of actors. The map consists in a grid of points, each point corresponding to a 1 ha cell. Five types of land are distinguished defining a vegetation cover for each plot.

After initialisation of vegetation cover the plots are gathered into sets of 25 plots at least to form one farm. In conformity with reality, initial farms establishment is set in specific areas of the grid depending on Farmer's social membership (migrant or native).

LAND USE AND LAND USE CHANGE

The initial vegetation cover of a plot is forest, but it then changes varies according to its land use (crop, fallow, plantation, compound, kraal) (Figure 6). The occupation of the cultivated plot changes according to the cropping system (Figure 7 and Figure 8). A plot whose fertility is insufficient for the cropping returns in fallow and is exploited when its fertility is sufficient. The fertility of a plot is represented by discrete scales of points of fertility. When the plot is cultivated, its fertility decreases according to the fertility required by the crop. But, it increases by one point when it is left into fallow.

BIOMASS GROWTH

Several pools of biomass are represented in the model: herbaceous layer, above-ground tree (AGT) layer roots, and crop residues. Their growth varies according to their occupation and from uptake by farmers or animals.

AGT biomass of non-cropped and cropped plots is estimated as logistic (Equation 5) and decreasing exponential (Equation 6) functions, respectively [START_REF] Youl | Dynamique du carbone d'un terroir de savane d'Afrique de l'ouest :Approche par modélisation multi agent[END_REF]. ) 0 ( Equation 6: Model of above-ground tree (AGT) biomass allocation in a cultivated plot. S AGT (0): initial amount of AGT biomass at t = 0; r: decrease constant; t: length of cropping Herbaceous biomass is modelled as a function of AGT biomass (which is a competitor for light) (Equation 7). Cultivated plots are weeded. The output of crop is evaluated according the rainfall and fertility of plot (Equation 8).

( ) ( ) ( ) ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - × ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - × + = + max max max

MAS COUPLING WITH GAMS OPTIMIZATION MODEL

To integrate optimization into the MAS the CORMAS platform is coupled to the GAMS software (Figure 9). The interaction is achieved using dynamic link library (DLL). Optimization modules are called through this DLL.

Since CORMAS was developed within Visual Works (VW). VW predefined methods enabling the execution of a C program from a SmallTalk program were used. The DLL was thus written in C. Two modules of optimization are developed in GAMS (Figure 9). The Production module builds the Farmer's production plan. The Sale module defines the Farmer's selling plan. The DLL comprises two principal methods production() and sale() intended respectively to call the production and sale module of Gams.

Optimization is made at the individual (i.e. Farmer) level only. Agents run in a concurrent way and use the same files of parameters and results. However, the parameters can differ from one agent to another. To avoid conflicting access to data, semaphores were used. Semaphores enable restricted access to the resources shared such as the input and output files. When an agent starts a call of optimization, any other access to the module of optimization is blocked until the end of the first call. As a result the sequential execution of optimization modules decreases the performance of the model. The production plan depends on food and monetary needs, labour, equipment availability, area for each crop, and output of each type of crop. These data are stored in a file of parameters. The Gams optimization module reads this file and then provides the optimal crop area distribution.

DLLMain

The selling plan takes into account the production of each crop, needs for food and money and commodities prices that are stored in a file too. The optimization module provides the quantity to be sold for each crop.

SIMULATION

Simulations were run in model implemented under contrasted scenarios to assess the value of the models, and possibly to identify new trajectories or development pathways (Le [START_REF] Bars | Un simulateur Multi-Agent pour l'Aide à la Décion d'un Collectif Application à la gestion d'une ressource limitée Agro-environnementale[END_REF].

The principal objective of MIROT model was to simulate the dynamics of carbon at the village territory scale. The various scenarios were selected to understand the effect of the human actions on the carbon cycle and the sensitiveness of human behaviour to environmental change. Human actions are driven by the satisfaction of food and money needs that are positive functions of the population size. Briefly, three sets of scenarios were explored ( Table 1): (1) population density as a driver of farmers' activities and carbon storage, (2) cash need and its influence on the global behaviour of the system, and (3) climatic change (as expressed by rainfall variation) and its impact on the viability of the system. In each scenario natives and migrants have similar population distribution at the beginning of simulations: 10 natives and 10 migrants. In economic and climatic scenarios, the growth rate is 5% per year.

"International Conference on Regional and Urban Modeling" -on June 1-2, 2006 -Brussels -Belgium

DEMOGRAPHIC SCENARIOS

Population growth rate has a strong impact on both population size and total amount of above-ground tree (AGT) biomass (Figure 10; Figure 11). Results suggest that increased population increases pressure on resources such as AGT biomass. Collapse of these resources in turn limit carrying capacity of the territory and thus lead to population decline after departure from the village. When growth rate is set to 2.5 % the area converted to cropping increases slowly between 120 and 620 months (Figure 12). When it is set to 10% the village is saturated after 620 months with simulation.

Although there is a similar proportion of migrants and natives at the beginning of simulation. After, the surface occupied by the natives increases faster than that of the migrants. A reason for this is that soil impoverishment by yam is faster than by cereal and cotton, which requires larger clearing of uncropped land.

ECONOMIC SCENARIOS

Drop in carbon resource and forest cover is increased when cash need increases (Figure 13; Figure 14); a threshold effect can be evidenced round 100 € inhab -1 y -1 since the E2 and E3 scenarios do not differ much in their effects. Increasing monetary need increases the need for cropped land, leading to higher deforestation rates. And since above-ground tree biomass is a major pool of carbon, increasing monetary need exhausts carbon storage. Additionally, the lower the monetary need, the larger the average farm population size beyond 450 months of simulation (Figure 15). The average is 35 persons after 575 steps (months) in scenario E1 (50 €). In scenario E2 (100 €), the maximum ( 26) is reached after 470 months. Again scenario E3 has little impact on population size as compared to E2. A reason for these trends is that high monetary need increases cropping intensity, decreases soil fertility and reduces the farm carrying capacity in human beings. As a result the farm splits and some of the household moves to another location to found a new farm. Crop distribution too varies depending on rainfall trends (Figure 18; Figure 19). Areas under yam first decrease and then increase to a steady level when rainfall increases (Figure 18). Conversely they decrease gradually until they disappear in scenario C2 (Figure 19). Maize is the dominant crop in scenario C1. Rainfall decrease (scenario C2) favours cereal expansion, with clear benefit to sorghum that even competes with maize. Such results can be interpreted by the general drop in crop performance. The yam requires more fertility and it is gradually abandoned because there are not sufficiently fertile plots for its cropping.

Share of the

Explanation:

The yam is less resistant to climatic precariousness; it is abandoned with the profit of maize-growing and sorghum-growing. To compensate for the reduction of yam-growing, the farmers cultivate more maize and sorghum. 7. DISCUSSION

MODEL STRENGTH

Organization is a fundamental property of a complex system. However the levels of organization of a system are multiple and require to be integrated in the model. The MIROT model integrates several levels of organization: (1) environment is represented at three scales (plot, farm and village territory), and (2) four levels of representation of social organisation (farmer, ethnic group, production system and village community) are proposed. Agent-Group-Role (AGR) formalism used in this last case improved expressivity and modularity of the system. The using of AGR constitutes a first step for the installation of a dynamic and evolutionary organization. Moreover, the model was coupled with a GIS. This interfacing allowed an explicit representation of the environment, and the taking into account of the physical, biological and human drivers of environmental features and spatial constraints put on individual behaviour. The spatial behaviour of cattle (straying trajectory) was also represented in the model. By coupling the MIROT model with an economic model, a first representation of economic motivations was carried out. This coupling also made it possible to take into account the constraints related to the availability of the resources such as equipment, labour available, the cash resources, etc.

SOME MODEL LIMITATIONS

MIROT has some limitations. A real ecosystem involves many entities and complex interactions. Representing a set of various ecosystems interacting with each other according to biophysical and socioeconomic drivers would be almost impossible in a single model. A model is a simplification of reality.

Finding the right level of abstraction is thus needed to allow its sound analysis and avoid building a complex tool with behaviour and outputs impossible to control and understand. MIROT does not escape this rule. For instance:

-only two farming systems were selected among the many ones existing in Touroukoro, -the tenurial market was not simulated due to lack of information about trading practices that are still considered as illegal, -the fertility is represented by a discrete scales of points of fertility. It varies according to the use of the plot (increase in the event of fallow and reduction in the event of setting in crop). In reality, the fertility of a plot is subjected to several factors which unfortunately we do not lay out.

COUPLING MAS AND MATHEMATICAL PROGRAMMING

This study illustrates the interest of MAS for the representation of the complex systems. Whatever its advantages multi-agents modelling is not the unique solution to any modelling problem. Other types of modelling exist; just like MAS, their use depends on the user's objective. Mathematical programming is another more conventional technique for the bioeconomic representation of the dynamic of a farm or even of a community "the behaviour of the actors [ y ] is generally simulated by an algorithm of maximization of a function of utility under constraint of plot, work, capital, food and monetary risk" [START_REF] Barbier | Induced innovation and land degradation: results from a bioeconomic model of a village in West Africa[END_REF]. In semi-marketed agricultures these models simulate the behaviour of a farmer who would maximize his monetary income after the food needs of the family, and having a reasonable knowledge of the local and regional context technico-economic necessary to the realization of this optimization. The study suggests that these two approaches can be complementary even if they meet apparently divergent aims. Individual modelling is a more realistic but complex representation generating a behaviour more difficult to interpret. The mathematical programming is unaware of part of the complexity of the decision-making process of the farmer but more easily makes it possible to analyze and interpret the various technico-economic scenarios.

DEALING WITH THE COMPLEXITY OF THE SYSTEM

The simulated environment is represented by a map exported in CORMAS. 24462 points composing the map generated 24462 cells in CORMAS. With a minimum size of 25 cells by farm, the model controls approximately 310 farms. A farmer can manage one farm. In consequence, the model controls 310 farmers if the territory is saturated. Supposing each farmer raises cattle, 310 herds or 620 active agents (farmers and herds) evolve in parallel. Each active agent has a thread and resource consumption is important. Heavy computation resource consumption reduces the performance of the system. In addition, the Gams execution by the agents decreases the performance of the system.

CONCLUSION AND PERSPECTIVES

The MIROT prototype can simulate the carbon dynamics at the village territory level. It integrates the major aspects of carbon dynamic: biological, physical and socio-economic factors. The model provides several types of output for a relevant analysis of the studied system. These outputs can be subdivided in three categories: (1) biological data (biomass and carbon, nitrogen, etc.) (2) demographic variables (population, density, etc.) and ( 3) economic performance indicators. Moreover, it is possible to define outputs for each production system (native and migrant). Simulations carried out made it possible to analyze the impact of the demographic pressure, the economic situation and the climatic change on the dynamics of the system.

Understanding and managing a complex system is highly dependant on the articulation of at least two levels of description: local (the components of the system), global (the collective behaviour which results from it). In a natural system, these various levels are indivisible [START_REF] Duboz | Scale transfert modeling: Using Emergent computation for coupling an ordinary differential equation system with a reactive agent model[END_REF], but they require consideration for a better understanding of the dynamics of the ecosystem. Concerning the resource management, the articulation between the options at the global level (regulation, taxes and subsidies) and impact on individual behaviours and what can result, is not clear and again requires articulation between different levels of description. Further effort will focus on the articulation between different levels of organisation within the issue of carbon dynamic. Additionally the genericity of MIROT will be worked out to develop a model able to simulate the dynamics of carbon resources of contrasted territories of West-African savannas.

Figure 1 :Figure 2 :

 12 Figure 1: Crop rotation in the indigenous semi-permanent cropping system 2. The migrant system crop is based on cotton (Figure 2): with the usual rotation of the maize/cotton/maize/sorghum;

Farmer

Figure 3 :

 3 Figure 3: UML diagram for Farmer's rules of decision for cropping

  Model for fodder uptake by agent Cattle. uptakeCapacity is the amount of fodder ingested per hour and residenceTime is the residence time of Cattle on the plot. Model for dung deposition. excretionPerHour is the quantity of organic matter deposited per hour and residenceTime is the residence time of Cattle on the plot.

  Figure 5: Map generation

  Figure 6: land use and land change dynamics

Figure 7 :

 7 Figure 7: land use and land change dynamics in native system

Figure 8 :

 8 Figure 8: land use and land change dynamics in migrant system

  Model of above-ground tree (AGT) biomass allocation in a non-cultivated plot. S AGT (t): amount of AGT biomass at time t; S AGTmax : maximum amount of AGT biomass; S AGT (0): initial amount of AGT biomass at t = 0; t: length of fallow

  output modelWhere normalOutPut is the output of the crop, rainFall the rainfall evaluated by the model and normalrainfall the average rainfall in Touroukoro and fertilityApport the impact of fertility on output of crops fertilityApport = 1 if plot fertility (plotFertility) is great than or equal to the fertility required (requiredFertility) by the crop else: impact of fertility on output of crops

Figure 9 :

 9 Figure 9: Structure and functioning of the MAS-Gams optimization model coupling

Figure 10 :Figure 11

 1011 Figure 10: Evolution of population size under three demographic scenarios

Figure 12 :

 12 Figure 12: Evolution of land use under three demographic scenarios

Figure 13 :Figure 14 :

 1314 Figure 13: Evolution of the share of the territory under forest under three economic scenarios

Figure 15 :Figure 16 :Figure 17 :

 151617 Figure 15: Evolution of the average farm population size under three economic scenarios

Figure 18 :Figure 19 :

 1819 Figure 18: Evolution of crop distribution under scenario C1 (rainfall increase)

Table 1 :

 1 Scenario description

	Scenario set	Scenario code Parameters (annual values)
	Demographic		Population growth rate (in %)
		D1	2.5
		D2	5
		D2	10
	Economic		Monetary need (in euros)
		E1	50
		E2	100
		E3	200
	Climatic		Rainfall annual variation (in %)
		C1	+10
		C2	-10

"International Conference on Regional and Urban Modeling" -on June 1-2, 2006 -Brussels -Belgium


Emilie Balland

Paul Brauner

Radu Kopetz

Pierre-Etienne Moreau

Antoine Reilles

Uhp & Loria

Tom: Piggybacking Rewriting on Java

We present the Tom language that extends Java with the purpose of providing high level constructs inspired by the rewriting community. Tom furnishes a bridge between a general purpose language and higher level specifications that use rewriting. This approach was motivated by the promotion of rewriting techniques and their integration in large scale applications. Powerful matching capabilities along with a rich strategy language are among Tom's strong points, making it easy to use and competitive with other rule based languages.

Introduction

Term Rewriting provides a theoretical framework that is very useful to model, study, and analyze various parts of a complex system, from algorithms to running software. During the last  years, there were many successful attempts in understanding, certifying, and proving properties of software, such as termination or confluence.

Term Rewriting is also a great tool for building software. Following the development of Lisp, the first equational interpreters, OBJ and EQI were introduced in  by J. A. Goguen and M. J. O'Donnell. Many tools have integrated the notion of term rewriting in their implementation, among them, let us mention Reve , ML , Clean , RRL , ASF+SDF , Spike , ELAN , Larch Prover , Caml , Otter , Maude , CafeOBJ , Ci ME , DMS , Stratego , Hats , Tom , etc. Some of them are not only tools which use the notion of term rewriting, but general purpose programming languages whose semantics and execution mechanism are fully based on the notions invented, defined, and studied by the rewriting community: term, pattern matching, equational theory, rewrite rule, strategy, etc. to mention just a few of them.

Throughout the course of  years we developed the ELAN system [START_REF] Borovanský | An overview of ELAN[END_REF]. We integrated some of the best algorithms to implement pattern-matching, rule based normalization, and non-deterministic computations. As a result, ELAN is certainly, along with Maude [START_REF] Clavel | The maude 2.0 system[END_REF], one of the most established term rewriting based implementations which efficiently compiles associative-commutative rewriting combined with non-deterministic strategies. This was a very fruitful experience and it taught us many lessons. One of them is that implementing a good term data-structure is difficult, data conversion (also known as marshalling) is often a bottleneck, integrating built-in data-types such as integers or doubles is not so easy, mutable data-structures, such as arrays, are essential for the implementation of efficient data-structures like hash-tables. But one of the most important things we learned is that even if efficiency is important to make our technology credible, integration capabilities are even more important to make our research widely used both in academic and industrial projects.

In  we started the design of a new language called Tom [START_REF] Moreau | A Pattern Matching Compiler for Multiple Target Languages[END_REF], available at http://tom.loria.fr/, whose goal was to pursue the promotion of term rewriting by making our concepts and techniques more easily available. One solution could have been to increase our implementation efforts by providing more data-structures, more libraries, more input/output facilities, more threads, more native interfaces, more graphical user interfaces, more, more, more. But we have to admit that these are difficult tasks and that many other languages already do that very well. In fact, this is not our main business. Therefore, we chose another approach: make our technology available on top of an existing language. This concept is called Formal Island [START_REF] Balland | Formal islands[END_REF].

In a first possible scenario, we start from an already existing application and our goal is to implement new functionalities, or re-implement some old ones, using rewriting. The expected result is a more concise and abstract description, and the possibility to reason about this new piece of code. In this case, the datastructure used by the application are already defined. We cannot translate them forth and back before and after each rewrite step, this would introduce unacceptable marshalling costs. Behind the notion of formal island there is the notion of formal anchor, also called mapping, which describes how a concrete datastructure can be seen as an algebraic term. This idea, related to P. Wadler's views, allows Tom to rewrite any kind of data structure, as long as a formal anchor is provided. In a second scenario, the application is both specified and implemented at the same time, using rewrite rules. In that case, the system should be easy to use: the definition of an algebraic signature, the definition of rules, and that's all! In this paper we focus on this second approach, which is exactly what Tom provides when the underlying host language is Java.

The paper is organized as follows. In Section 2, we present how term rewriting is implemented and integrated into Java. Section 3 focuses on the strategy language and its control mechanism. Section 4 exposes meta-programming features added to the strategy language for managing non-deterministic computations and for modifying strategies at runtime. The two following sections present respectively some key details of the Tom implementation and some significant applications. Section 7 and 8 present related work and conclude.

Implementing term rewriting

Term rewriting systems are mostly concerned with computing reduced forms of a ground term wrt. a set of rules. To this end, the Tom language allows the definition of many-sorted signatures that are used to generate correctly typed algebraic terms. Further on, a rewrite system based on syntactic or equational pattern matching can be defined and applied on these terms.

First order terms. Similarly to other rule based or functional languages, Tom provides a construct to define many-sorted algebraic signatures:

module Peano Nat = zero() | suc( Nat )
In this example, Peano is the name of the module, Nat is a sort, zero and suc are constructors. More generally, a module may import another module, such as Peano, or any other predefined one like String or int. Given a signature, a well formed and well typed term can be built using the backquote (') construct: 'zero(), 'suc(zero()) are correct, as opposed to 'suc(zero(),zero()) or 'suc(3) which are respectively not well-formed and not well-typed.

Due to the fact that Tom is built on top of Java, a term can be used in any Java expression such as System.out.print("t = " + 'suc(suc(zero()))).

To ensure that the type of a term can be statically checked by the underlying Java compiler, the implementation of 'suc(suc(zero())) should reflect the type defined by the signature. To solve this problem, we followed a different approach from other classical implementations such as ASF+SDF, OCaml, ELAN, Maude, ML, or Stratego.

Usually, the compiler checks that all term manipulations result in correctly typed terms, while at runtime level a generic untyped term implementation is used. In our case, we use a generator [START_REF] Reilles | Canonical abstract syntax trees[END_REF] that compiles the algebraic signature into a typed term structure that can be directly used by a Java programmer. The need for a typed term structure comes also from the fact that pure Java code, not handled by the Tom compiler, could create wrongly shaped terms. The generated structures are efficient, and provide types at the implementation level. As a consequence, for each sort a Java class with the same name is generated: Nat t = 'suc(suc(zero())) defines a variable t of sort Nat. By generating a statically typed implementation we provide a smooth and natural integration of the notions of signature and term into Java.

Pattern matching and rewriting. Implementing term rewriting may be considered a simple task. To know if a rewrite rule l → r can be applied for a ground term t, it is sufficient to have a pattern matching algorithm that computes, when it is possible, a substitution σ such that σl = t, and fails otherwise. The application of the rule consists in replacing t by σr. However, real cases are more complicated. The rules may be applied not only on top, but also to subterms; they may have conditions; the patterns may contain symbols that belong to an equational theory (such as associativity and commutativity for example) and the application order of several rules may be prioritized. Besides, one may be interested in not only getting a single result, but also getting the set of all possible reductions of a given term t. The combinations of all these variants are difficult to tackle with. In practice, each implementation considers only a subset of them.

A main objective of Tom is to be as generic as possible. Therefore, we provide a key primitive on top of Java that can be used to handle most of the situations described above: the %match construct. Its semantics is close to the match that exists in functional programming languages, but in an imperative context. A %match is parameterized by a list of subjects (i.e. expressions evaluated to ground terms) and contains a list of rules. The left-hand side of the rules are patterns built upon constructors and fresh variables, without any restriction of linearity. The right-hand side is not a term, but a Java statement that is executed when the pattern matches the subject. But thanks to the backquote construct (') a term can be easily built and returned. Similar to the standard switch/case construct, patterns are evaluated from top to bottom. In contrast to the functional match, several actions (i.e. right-hand side) may be fired for a given subject as long as no return or break is executed. To implement a simple reduction step, for each rule, we just have to encode the left-hand side by a pattern and consider a Java statement that returns the right-hand side. To encode a rewrite system, the notion of function that already exists in Java is fundamental. For example, the addition and the comparison of Peano integers may be encoded as follows:

public Nat plus(Nat t1, Nat t2) { %match(t1,t2) { x,zero() -> { return 'x; } x,suc(y) -> { return 'suc(plus(x,y)); } } } boolean greaterThan(Nat t1, Nat t2) { %match(t1, t2) { x,x -> { return false; } suc(_),zero() -> { return true; } zero(),suc(_) -> { return false; } suc(x),suc(y) -> { return 'greaterThan(x,y); } }}
The reader should note that anonymous variables (_) are allowed and that variables such as x or y do not need to be declared: they are local to each left-hand side and their type is automatically inferred.

List matching. In addition to free constructors, list operators can be also declared. They are a variant of associative operators with neutral element:

module Peano Nat = zero() | suc( Nat ) NatList = conc( Nat* )
The notation Nat* means that conc is a variadic operator where each subterm is of sort Nat. It can be seen as a concatenation operator over Nat lists: 'conc() denotes the empty list while 'conc(zero(),suc(zero())) corresponds to the list that contains zero() and suc(zero()). List operators can be used in the left-hand side of a rule in order to perform list matching:

Collection bag = new HashSet(); %match(list) { conc(_*,suc(x),_*) -> { bag.add('x); } } System.out.println("numbers: " + bag.toString());

In this example, one can remark the use of list variables, annotated by a '*', which intuitively corresponds to the Kleene star: such a variable is instantiated by a (possibly empty) list. Note that an action is fired for each pattern and substitution that matches the subject. Since list matching is not unitary, the action bag.add('x) is evaluated for each element of list that matches against suc(x). When applied to a list of Peano integers, this code stores each natural whose successor is in the list into the set represented by bag. This non-functional approach is very useful to encode non-deterministic computations such as the exploration of a search space. Combining list operators and conditions allows for the definition of complex algorithms in a concise manner, as illustrated by the following sorting algorithm:

public NatList sort(NatList list) { %match(list) { conc(X1*,x,X2*,y,X3*) -> { if(greaterThan(x,y)) { return 'sort(conc(X1*,y,X2*,x,X3*)); } } _ -> { return list; } } }
Given a partially sorted list, the sort function looks for two elements x and y such that x is greater than y. If two such elements exist, they are swapped and the sort function is recursively applied. When the list is sorted this condition cannot be satisfied and the next pattern is tried: the sorted list is returned. This example also shows how a conditional rule can be naturally encoded using the if construct provided by Java.

Normal forms. When manipulating non-free algebras, it is convenient to work with terms in normal form. These normal forms are defined by a confluent and terminating rewrite system that is systematically applied to each term. This was the purpose of unnamed rules in ELAN for example. Instead of relying on normalization functions that have to be explicitly called by the programmer, Tom proposes to integrate the computation of normal forms into the definition of the data structure. This approach is very close to the recently introduced OCaml private types [START_REF] Leroy | The objective caml system release 3.09[END_REF]. Normal forms are specified using the notion of hook which defines construction functions in the term signature. For instance, suppose that we want to work on Z/3Z. Then, we have to systematically apply the rule suc(suc(suc(x))) → x when creating new terms. This is specified by a hook attached to the suc operator.

module Peano Nat = zero() | suc( Nat ) suc:make(t) { %match(t) { suc(suc(x)) -> { return 'x; } } } Each time a suc is built, make(t) is called with t instantiated by the subterm of the considered suc. This is why the rewrite rule above only rewrites two suc. A default allocator is called when no rule can be applied

Controlling Rewriting

When using rewriting as a programming or modeling paradigm, it is common to consider rewrite systems that are non-confluent or non-terminating. To be able to use them, it is necessary to exercise some control over the application of the rules. In Tom, a solution would be to use Java to express the control needed. While this solution provides a huge flexibility, its lack of abstraction renders difficult the reasoning about such transformations.

Rewriting based languages provide more abstract ways to express control of rule applications, by using reflexivity and the meta-level for Maude, or the notion of rewriting strategies for ELAN, Stratego [START_REF] Visser | Building program optimizers with rewriting strategies[END_REF], or ASF+SDF [START_REF] Brand | The ASF+SDF Meta-Environment: a Component-Based Language Development Environment[END_REF]. Strategies such as bottom-up, top-down or leftmost-innermost are higher-order features that describe how rewrite rules should be applied. We have developed a flexible and expressive strategy language inspired by ELAN, Stratego, and JJTraveler [START_REF] Visser | Visitor combination and traversal control[END_REF] where high-level strategies are defined by combining lowlevel primitives. For example, the top-down strategy is recursively defined by TopDown(s) △ = Sequence(s,All(TopDown(s))).

Elementary strategies. An elementary strategy corresponds to a minimal transformation. It could be Identity (does nothing), Fail (always fails), or a set of rewrite rules (performs an elementary rewrite step only at the root position). In our system, strategies are type-preserving and have a default behavior (introduced by the keyword extends) that can be either Identity or Fail: %strategy R() extends Fail() { visit Nat { zero() -> { return 'suc(zero()); } suc(suc(x)) -> { return 'x; } } } When a strategy is applied to a term t, as in a %match, a rule is fired if a pattern matches. Otherwise, the default strategy is applied. For example, applying the strategy R() to the term suc(suc(zero())) will produce the term zero() thanks to the second rule. The application to suc(suc(suc(zero()))) fails since no pattern matches at root position.

Recursive and parameterized strategies. More control is obtained by combining elementary strategies with basic combinators such as Sequence, Choice, All, One as presented in [START_REF] Borovanský | Controlling rewriting by rewriting[END_REF][START_REF] Visser | Building program optimizers with rewriting strategies[END_REF]. By denoting s[t] the application of the strategy s to the term t, the basic combinators are defined as follows: An example of composed strategy is Try(s) △ = 'Choice(s,Identity()), which applies s if it can, and performs the Identity otherwise. To define strategies such as repeat, bottom-up, top-down, etc. recursive definitions are needed. For example, to repeat the application of a strategy s until it fails, we consider the strategy Repeat(s) △ = Choice(Sequence(s,Repeat(s)), Identity()). In Tom, we use the recursion operator µ (comparable to rec in OCaml) to have stand-alone definitions: µx.Choice(Sequence(s,x),Identity()).

Sequence(s1,s2)[t] → s2[t'] if s1[t] → t' failure if s1[t] fails Choice(s1,s2)[t] → t' if s1[t] → t' s2[t'] if s1[t] fails All(s)[f(t1,...,tn)] → f(t1',...,tn') if s[t1] → t1',. . . ,
The All and One combinators are used to define tree traversals. For example, we have TopDown(s) △ = µx.Sequence(s,All(x)): the strategy s is first applied on top of the considered term, then the strategy TopDown(s) is recursively called on all immediate subterms of the term.

Exploration strategies. Strategy expressions can have any kind of parameters. It is common to have a Java Collection as parameter to collect some information in a tree. For example, let us consider the following strategy which collects the direct subterms of an f . This program creates a hash-set, and a strategy applied to f(f(a())) collects all the subterms which are under an f: i.e. {a(), f(a())}.

Meta-programming

The strategy language presented in Section 3 is very expressive and powerful to control how a set of rules should be applied. This is very convenient to collect information or traverse a tree for example. But, there is no real support to perform non-deterministic computations as in the exploration of a search space, which is essential when implementing a model checker or a prover for instance. For this purpose, we have added two new extensions to the strategy language.

Reifying t |ω . Given a term t, suppose that we want to compute the set of all its possible successors wrt. a rewrite rule l → r. We have to find all possible redexes, and for each of them to compute all the substitutions that solve the matching problem. In other words, we want to compute {t[σ 1 r] ω1 , t[σ 2 r] ω1 , . . . , t[σ p r] ωn , . . . , t[σ q r] ωn }, where ω i denotes a redex position, and σ j is a substitution such that σ j l = t |ωi .

Solving this problem involves manipulating the notion of position in a term, and some associated operations: getting the subterm at position ω, and replacing this subterm. To the best of our knowledge, there is no rewriting based language where positions, which are internal to the implementation, can be explicitly manipulated. We introduce a new operation, getPosition(), which raises the notion of position at the object level, providing this global information to the level of strategies. To compute the set of all successors of t for example 4 , we consider the top-down application of a strategy parameterized by the term t itself and a collection bag. For each redex position ω (i.e. when a pattern matches), we store t[σr] ω in bag, using getPosition() to obtain ω and replace to perform the replacement: The resulting bag contains f(g(b())), g(a()), and f(c()). This reification of the position notion to the object level is new in the domain of rewriting based languages, and it adds expressiveness while keeping programs close to their specification.

Rewriting a strategy. Strategy expressions are terms, and thus can themselves be subject to pattern matching and reduction by strategies. This permits dynamical adaptation of a strategy depending on the environment.

For example, suppose that we have two strategies, s1 and s2 which can commute. If computing s2;s1 is more efficient than computing s1;s2, we can define a rule to reorder the sequences of s1 and s2: %strategy Reorder() extends Identity() { visit T { Sequence(s1(),s2()) -> { return 'Sequence(s2(),s1()); } } } This strategy can be further applied top-down to any strategy s with: Strategy optimized s = 'TopDown(Reorder()).apply(s).

Implementation

Since its first version in , Tom itself has been written using Tom. The system is composed of a compiler and a library which defines the strategy language and offers support for predefined data-types such as integers, floats, strings, collections, and many other Java data-structures. The compiler is organized, in a pure functional style, as a pipeline of program transformations (type inference, simplification, compilation, optimization, generation). Each phase transforms a Java+Tom abstract syntax tree (AST) using rewrite rules and strategies. At the end a pure Java AST is obtained. The system is composed of  %match constructs, and  user strategy definitions, totalizing more than  lines of code. The complete environment has been integrated into Eclipse5 providing a simple and efficient user interface to develop, compile, and debug rule based applications. Each component of the Tom environment is highly modular and has been designed with flexibility and reusability in mind, without introducing any performance overhead. Due to the lack of space, we mention here only a few key ingredients.

Data representation. The generator of data-structures is integrated in Tom but can be also used independently. Given a signature, it generates a set of Java classes that provide static typing. A subtle hash-consing technique is used to offer maximal sharing [START_REF] Van Den Brand | Efficient annotated terms[END_REF]: there cannot be two identical terms in memory. Therefore, the equality tests are performed in constant time, which is very efficient in many cases including when non left-linear rewrite rules are considered. In addition to the generation of lightweight data-structures, specialized hash-functions are generated for each constructor of the signature, making the generated implementation often more efficient than a hand-coded term data-structure.

Pattern matching. Thanks to the formal anchor approach, Tom is not restricted to a fixed term data-structure. We have designed a compilation algorithm where the data-structure is a parameter of the pattern matching algorithm. In particular, Tom can be used to match and rewrite XML documents. Moreover, the underlying host language is also a parameter, making possible the compilation (including list-matching) into different target languages such as C, Java, OCaml, and Python. This approach has been formally studied in [START_REF] Kirchner | Formal validation of pattern matching code[END_REF]. Besides, for each compilation of a set of patterns, Tom provides a Coq proof that the generated code is correct wrt. the semantics of pattern matching.

Strategies. Most of the strategy library is written in Tom, making its extension easy. Only a few of low-level elementary strategies (Sequence, Choice, All, One, etc.) are implemented in Java. However, the considered object design-patterns for these elementary strategies facilitate their extension also. To add a new probabilistic choice operator for example, less than 30 lines of code have to be written, without any re-compilation of the system. This makes Tom an ideal platform to experiment new paradigms. Once again, the methodology used to implement the strategy library is not restricted to a given term representation, being possible to switch to another one by properly applying the interface concept offered by Java.

Applications

The Tom system is no longer a prototype. It has been used to implement many large and complex applications, among them the compiler itself. It has also been used in an industrial context to implement a query optimizer for Xquery, a platform for transforming and analysing timed automata using XML manipulation, etc. In this section we focus on some applications where the key characteristics of Tom were particularly useful. Proof assistant. lemuridae is a proof assistant for superdeduction [START_REF] Brauner | Principles of superdeduction[END_REF] (a dynamic extension of sequent calculus). Proof trees benefit from maximal memory sharing which allows for the handling of big proofs while tactics are naturally translated into strategies. Besides, the expressiveness of Tom patterns makes the micro-proofchecker only one hundred lines long and therefore enables a high degree of confidence in the prover. NSPK. Tom has been used to implement the verification of the Needham-Schroeder public key protocol by model checking. Several strategies have been experimented. The resulting implementation can be compared favorably with state of the art rule based implementation such as Maude or Murϕ. Rho-calculus. An interpreter for the rho-calculus [START_REF] Cirstea | The rewriting calculus -Part I and II[END_REF] with explicit substitutions was developed using Tom. It is surprisingly short and close to the operational semantics of the calculus taking advantage of all the capabilities of Tom. The calculus itself is expressed using rewrite rules and parameterized strategies, while the interactive features and user interface operations take advantage of the underlying Java language. Calculus of structures. Tom is used to implement an automatic prover for the system BV in the calculus of structures [START_REF] Reilles | Canonical abstract syntax trees[END_REF]. Normal forms are used to implement the several associative-commutative operators with neutral elements while firstorder positions allow to manage the high level of non determinism introduced by deep inference.

On several classical benchmarks Tom is competitive with state of the art implementations like ASF+SDF, ELAN, or Maude6 . In the following, Fibonacci computes 500 times the 18 th Fibonacci number using a Peano representation. Sieve computes prime numbers up to 2000 using list matching to eliminate nonprime numbers: (c 1 * , x, c 2 * , y, c 3 * ) → (c 1 * , x, c 2 * , c 3 * ) if x divides y7 . Evalsym, Evalexp, and Evaltree are three benchmarks based on the normalization of the expression 2 22 mod 17 using different reduction strategies. These three benchmarks were first presented in [START_REF] Brand | Compilation and Memory Management for ASF+SDF[END_REF]. All these examples are available on the Tom source repository8 . The measurements were done on a MacBook Pro 2.33 GHz, using Java 1.5.0 and gcc 4.0.

Related work

The creation of Tom was motivated by the difficulty in integrating or reusing a term rewriting based language in an industrial context. The initial idea of piggybacking rewriting on a generalist host language was inspired by Lex and Yacc and generalized in the framework of formal islands. Tom is the result of a long term effort, on one hand integrating innovative ideas and concepts, and on the other hand combining and incorporating key notions and techniques developed in well reputed research teams. Regarding the data-structures, the implementation of the generator has been done in strong cooperation with the authors of ApiGen [START_REF] Van Den Brand | A generator of efficient strongly typed abstract syntax trees in Java[END_REF] and followed our experience with the ATerm [START_REF] Van Den Brand | Efficient annotated terms[END_REF] library used by ASF+SDF. The originality of our solution is to provide typed constructs resulting in a faster and safer implementation. Moreover, we introduce the notion of hook which is strongly related to OCaml private types. Concerning matching theories, Tom is similar to ASF+SDF by providing list-matching, that corresponds to associative matching with neutral element. Contrary to Maude and ELAN, the restriction to list-matching instead of more complex theories like associativecommutative makes the implementation simpler and powerful enough in many cases. The design of the strategy language has been inspired by ELAN, Stratego, and JJTraveler. Compared to ELAN, Tom does not support implicit nondeterministic strategies, implemented using back-tracking. But due to reification of t |ω , explicit non-deterministic computations are practical. ASF+SDF does not have a strategy language but provides traversal functions that can be used to control how a set of rule should be applied. By raising the notion of strategy to the object level, Tom offers meta-programming capabilities that may remind the meta-level of Maude. With regard to strategy languages, Stratego is certainly the language to which Tom is the most close, the main differences being strategies as terms and explicit non-deterministic computations.

Conclusion

In this paper we introduced the system Tom, which brings rewriting techniques to the world of mainstream programming languages. In addition to this original result, the contributions of Tom include: the notion of formal island ; the certification of pattern matching; a support for private types in Java; an efficient implementation of typed and maximally shared terms; user definable recursive strategies (in Java) using the µ operator; strategies considered as terms; reification of t |ω that makes non-deterministic computations explicit. We are currently working on two extensions. One is the formalization and the integration of the notion of anti-patterns [START_REF] Kirchner | Anti-pattern matching[END_REF], which enables the expression of negative constraints inside patterns. The second one concerns the integration of termgraph rewriting capabilities into the language and the extension of the strategy library.

%strategy

  Collect(c:Collection) extends Identity() { visit T { f(x) -> { c.add('x); } } } Collection bag = new HashSet(); 'TopDown(Collect(bag)).apply( 'f(f(a())) );

http://www.eclipse.org/

note that Maude is an interpreter. The experimental results are extraordinarily good compared to the compiled and highly optimized low-level C implementations

on this example, the performance of ASF+SDF may be explained by the lack of support for builtin integers

http://gforge.inria.fr/projects/tom/


Fayssal Charif

Abdelkader Mohamed Helal

Abdelkader Lakmeche
email: lakmeche@yahoo.fr

Chemotherapy models

Keywords: MOTS-CLÉS : Modèle de chimiothérapie, Equations différentielles impulsifs, Solutions périodiques, Stabilité exponentielle, Bifurcation de Lyapunov-Schmidt Chemotherapy model, Impulsive differential equations, Periodic solutions, Exponential stability, Lyapunov-Schmidt bifurcation

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Impulsive differential systems are found in the description of phenomena issued from applied sciences as physics, chemistry, biology and medicine. Recently interesting works in biomathematics have been published, we can cite those considering impulsive chemotherapeutic treatment of tumor diseases ( [START_REF] Boudermine | Bifurcation of nontrivial periodic solutions for pulsed chemotherapy model[END_REF], [START_REF] Lakmeche | Bifurcation of non trivial periodic solutions of impulsive differential equations arising in chemotherapeutic treatment[END_REF]- [START_REF] Lakmeche | Pulsed chemotherapy model[END_REF], [START_REF] Panetta | A mathematical model of periodically pulsed chemotherapy : tumor recurrence and metastasis in a competition environment[END_REF], [START_REF] Panetta | A mathematical model of drug resistance : Heterogeneous tumors[END_REF]), impulsive pest control strategies ( [START_REF] Liu | Complex dynamics of Holling type II Lotka Volterra predator prey system with impulsive perturbations on the predator[END_REF]), impulsive harvesting ( [START_REF] Negi | Dynamics in a Beddington DeAngelis prey predator system with impulsive harvesting[END_REF], [START_REF] Zhang | Optimal impulsive harvesting policy for single population[END_REF]), and impulsive vaccination ( [START_REF] Shulgin | Theoretical examination of the pulse vaccination policy in the SIR epidemic model[END_REF], [START_REF] Zeng | Complexity of an SIR epidemic dynamics model with impulsive vaccination control[END_REF]). In this paper, we consider a mathematical model for cell population under chemotherapy treatment by two drugs, one with instantaneous effect and the other with continuous effect. We study the stability of the tumor eradication and the consequences of the lost of its stability. In the last case we could have a bifurcation of positive nontrivial solutions which correspond to the persistence of the tumor. More specifically, we consider a cell population constituted by three subpopulations ; normal cells, sensitive tumor cells and resistant tumor cells, with mutation and resistance to the drug with instantaneous effect. The model is described by the following impulsive differential equations :

dx 1 dt = r 1 x 1 1 - x 1 k 1 -λ 1 (x 2 + x 3 ) -θ 1 x 1 , [1] dx 2 dt = r 2 x 2 1 - x 2 + x 3 k 2 -λ 2 (x 1 + x 3 ) -mx 2 -θ 2 x 2 , [ 2
]
dx 3 dt = r 3 x 3 1 - x 2 + x 3 k 3 -λ 3 (x 1 + x 2 ) + mx 2 -θ 3 x 3 , [3]
x 1 (t + i ) = T 1 x 1 (t i ), [START_REF] Lakmeche | Nonlinear mathematical model of pulsed-therapy of heterogeneous tumors[END_REF] x 2 (t + i ) = (T 2 -R)x 2 (t i ), [START_REF] Lakmeche | Pulsed chemotherapy model[END_REF] x 3 (t + i ) = T 3 x 3 (t i ) + Rx 2 (t i ), [START_REF] Liu | Complex dynamics of Holling type II Lotka Volterra predator prey system with impulsive perturbations on the predator[END_REF] where t i+1 -

t i = τ > 0, ∀i ∈ N, θ 1 < r 1 , θ 2 < r 2 + m and θ 3 < r 3 .
The variables and parameters are : τ : period between two successive drug with instantaneous effect, x j : normal (resp. sensitive tumor, resistant tumor) cells biomass for j = 1 (resp. 2,3), r j : growth rates of the normal (resp. sensitive tumor, resistant tumor) cells for j = 1 (resp. 2,3), k j : carrying capacities of the normal (resp. sensitive tumor, resistant tumor) cells for j = 1 (resp. 2,3), λ j : competitive parameters of the normal (resp. sensitive tumor, resistant tumor) cells for j = 1 (resp. 2,3), T j : survival fractions of the normal (resp. sensitive tumor, resistant tumor) cells, their values are completely determined by the quantity of injected drug with instantaneous effect. θ j : elimination rate of normal (resp. sensitive tumor, resistant tumor) cells by the drug with continuous effect. R : Fraction of cells mutating due of the dose of the drug with instantaneous effect, which is less than T 2 . m : acquired resistance parameter usually it is very small. Note that if θ i = 0, then we obtain the models studied in [START_REF] Boudermine | Bifurcation of nontrivial periodic solutions for pulsed chemotherapy model[END_REF] and [START_REF] Lakmeche | Pulsed chemotherapy model[END_REF].

Analysis of the model

In the following, we proceed to analyze our model. To this purpose, we shall use a fixed point approach. Let Φ(t, X 0 ) be the solution of the system (1)-( 6) for the initial condition X 0 . We define the mappings

F 1 , F 2 , F 3 : R 3 → R by F 1 (x 1 , x 2 , x 3 ) = r 1 x 1 1 -x1 k1 -λ 1 (x 2 + x 3 ) -θ 1 x 1 , F 2 (x 1 , x 2 , x 3 ) = r 2 x 2 1 -x2+x3 k2 -λ 2 (x 1 + x 3 ) -mx 2 -θ 2 x 2 , F 3 (x 1 , x 2 , x 3 ) = r 3 x 3 1 -x2+x3 k3 -λ 3 (x 1 + x 2 ) + mx 2 -θ 3 x 3 , and Θ 1 , Θ 2 , Θ 3 : R 3 → R by Θ 1 (x 1 , x 2 , x 3 ) = T 1 x 1 , Θ 2 (x 1 , x 2 , x 3 ) = (T 2 -R)x 2 , Θ 3 (x 1 , x 2 , x 3 ) = T 3 x 3 + Rx 2 . Let Θ := (Θ 1 , Θ 2 , Θ 3 ) and Ψ : R + × R 3 → R 3 be the operator defined by Ψ(τ, X 0 ) = Θ(Φ(τ, X 0 )), [7]
and denote by D X Ψ the derivative of Ψ with respect to X. Then ξ = Φ(., X 0 ) is a τ -periodic solution of (1)-( 6) if and only if

Ψ(τ, X 0 ) = X 0 , [8]
i.e. X 0 is a fixed point of Ψ(τ, .), and it is exponentially stable if and only if the spectral radius ρ(D X Ψ(τ, .)) is strictly less than 1 ([2]). A fixed point X 0 of Ψ(τ, .) is the initial state of (1)-( 6) which gives a τ -periodic solution ξ verifying ξ(0) = X 0 . We reduce the problem of finding a periodic solution of (1)-( 6) to a fixed point problem.

Here, ξ is a periodic solution of period τ for (1)-( 6) if and only if X 0 is a fixed point for [START_REF] Panetta | A mathematical model of periodically pulsed chemotherapy : tumor recurrence and metastasis in a competition environment[END_REF]. Consequently, to establish the existence of nontrivial periodic solutions of ( 1)-( 6), one needs to prove the existence of nontrivial fixed points of Ψ(τ, .).

REMARQUE. -

The problem (1),(4), obtained by taking x 2 = 0 and x 3 = 0, has a τ 0 -periodic solution x(t, x 0 ) = x s (t), where

x s (t) = k 1 r 1 -θ 1 r 1 (T 1 -exp(-(r 1 -θ 1 )τ 0 )) exp((r 1 -θ 1 )t) exp((r 1 -θ 1 )t)(T 1 -exp(-(r 1 -θ 1 )τ 0 )) + (1 -T 1 ) , 0 < t ≤ τ 0 , [9] with x 0 = k 1 r1-θ1 r1 (T1-exp(-(r1-θ1)τ0))
1-exp(-(r1-θ1)τ0) . We denote by ζ = (x s , 0, 0) which is a solution of ( 1)-( 6), we call it trivial solution.

Stability of ζ

In the case without tumor we have x 2 = x 3 = 0, then (1)-( 6) is reduced to (1),( 4) which has a unique non-trivial positive periodic solution x s given by [START_REF] Panetta | A mathematical model of drug resistance : Heterogeneous tumors[END_REF]. It is defined and stable for

T 1 > exp(-(r 1 -θ 1 )τ 0 ). That is τ 0 > 1 r 1 -θ 1 ln 1 T 1 . [10]
To determine the stability of the trivial solution ζ = (x s , 0, 0) in the three dimensional space, we must calculate D X Ψ(τ 0 , X 0 ) where X 0 = (x 0 , 0, 0). We have

D X Ψ(τ 0 , X 0 ) = D X Θ(Φ(τ 0 , X 0 )) ∂Φ ∂X (τ 0 , X 0 ) =    T 1 ∂Φ1(τ0,X0) ∂x1 T 1 ∂Φ1(τ0,X0) ∂x2 T 1 ∂Φ1(τ0,X0) ∂x3 0 (T 2 -R)) ∂Φ2(τ0,X0) ∂x2 0 0 R ∂Φ2(τ0,X0) ∂x2 + T 3 ∂Φ3(τ0,X0) ∂x2 T 3 ∂Φ3(τ0,X0) ∂x3    .
The solution ζ is exponentially stable if and only if the spectral radius is less than one, that is

T j ∂Φ j ∂x j (τ 0 , X 0 ) < 1, for j = 1, 2, 3.
Using the variational equation associated to the system (1)-( 6)

d dt (D X Φ(t, X 0 )) = D X F (Φ(t, X 0 ))(D X Φ(t, X 0 )), [11]
with the initial condition

D X Φ(0, X 0 ) = Id R 3 we obtain ∂Φ1(τ0,X0) ∂x1 = T -2 1 e -(r1-θ1)τ0 , ∂Φ2(τ0,X0) ∂x2 = T -r 2 λ 2 K 1 r 1 1 e (r2-θ2-m-(r1-θ1) r 2 λ 2 K 1 r 1 )τ0 , ∂Φ3(τ0,X0) ∂x3 = T -r 3 λ 3 K 1 r 1 1 e (r3-θ3-(r1-θ1) r 3 λ 3 K 1 r 1 )τ0 , ∂Φ3(τ0,X0) ∂x2 = me (r 3 -θ 3 -(r 1 -θ 1 ) r 3 λ 3 K 1 r 1 )τ 0 (1-e -(r 1 -θ 1 )τ 0 ) r 2 λ 2 K 1 r 1 T r 3 λ 3 K 1 r 1 1 (1-e -(r 1 -θ 1 )τ 0 ) r 3 λ 3 K 1 r 1 τ0 0 e (r2-θ2-(r3-θ3)-m)u I (r3λ3-r2λ2) K 1 r 1 (u)du, ∂Φ1(τ0,X0) ∂x3 = -(r1-θ1)λ1K1(T1-e -(r 1 -θ 1 )τ 0 )e -(r 1 -θ 1 )τ 0 T 2 1 (1-e -(r 1 -θ 1 )τ 0 ) 2- r 3 λ 3 K 1 r 1 τ0 0 e (r3-θ3)u I 1-r 3 λ 3 K 1 r 1 (u)du, ∂Φ1(τ0,X0) ∂x2 = -(r1-θ1)λ1K1(T1-e -(r 1 -θ 1 )τ 0 )e -(r 1 -θ 1 )τ 0 T 2 1 (1-e -(r 1 -θ 1 )τ 0 ) 2- r 2 λ 2 K 1 r 1 τ0 0 e (r2-θ2-m)u I 1-r 2 λ 2 K 1 r 1 (u)du + m τ0 0 e (r3-θ3)u I 1-r 3 λ 3 K 1 r 1 (u)( u 0 e (r2-θ2-(r3-3)-m)p I (r3λ3-r2λ2) K 1 r 1 (p)dp)du for 0 < t ≤ τ 0 where I(t) = (T 1 -e -(r1-θ1)τ0
)e (r1-θ1)t + (1 -T 1 ) (Fore more details, see [START_REF] Lakmeche | Pulsed chemotherapy model[END_REF]).

In view of the fact that λ 2 K 1 < 1 and λ 3 K 1 < 1 (see [START_REF] Panetta | A mathematical model of periodically pulsed chemotherapy : tumor recurrence and metastasis in a competition environment[END_REF]), we have

T 2 < T r 2 λ 2 K 1 r 1 1 + R [12]
and

T 3 < T r 3 λ 3 K 1 r 1 1 . [13]
ζ is exponentially stable as an equilibrium for the full system (1)-( 6) if and only if

ln( 1 T1 ) r 1 -θ 1 < τ 0 < min     ln T r 2 λ 2 K 1 r 1 1 (T 2 -R) -1 r 2 -θ 2 -m -(r 1 -θ 1 ) r2λ2K1 r1 , ln T r 3 λ 3 K 1 r 1 1 T -1 3 r 3 -θ 3 -(r 1 -θ 1 ) r3λ3K1 r1     .
[14] REMARQUE. -The trivial periodic solution (x s , 0, 0) represents the healthy equilibrium. So, our aim is to obtain its stability, this corresponds to the eradication of the tumor. We have the following result. If conditions ( 12), (13) are satisfied and

T 2 > T r 2 λ 2 K 1 r 1 - r 3 λ 3 K 1 r 1 r 2 -θ 2 -m-(r 1 -θ 1 ) r 2 λ 2 K 1 r 1 r 3 -θ 3 -(r 1 -θ 1 ) r 3 λ 3 K 1 r 1 1 T r 2 -θ 2 -m-(r 1 -θ 1 ) r 2 λ 2 K 1 r 1 r 3 -θ 3 -(r 1 -θ 1 ) r 3 λ 3 K 1 r 1 3 + R, [15]
we have min

    ln T r 2 λ 2 K 1 r 1 1 (T2-R) -1 r2-θ2-m-(r1-θ1) r 2 λ 2 K 1 r 1 , ln T r 3 λ 3 K 1 r 1 1 T -1 3 r3-θ3-(r1-θ1) r 3 λ 3 K 1 r 1     = ln T r 2 λ 2 K 1 r 1 1 (T2-R) -1 r2-θ2-m-(r1-θ1) r 2 λ 2 K 1 r 1 .
That is, the tumor eradication solution ζ is stable for

ln( 1 T1 ) r 1 -θ 1 < τ 0 < ln T r 2 λ 2 K 1 r 1 1 (T 2 -R) -1 r 2 -θ 2 -m -(r 1 -θ 1 ) r2λ2K1 r1
.

[16]

If conditions ( 12), ( 13) are satisfied and

T 2 < T r 2 λ 2 K 1 r 1 - r 3 λ 3 K 1 r 1 r 2 -θ 2 -m-(r 1 -θ 1 ) r 2 λ 2 K 1 r 1 r 3 -θ 3 -(r 1 -θ 1 ) r 3 λ 3 K 1 r 1 1 T r 2 -θ 2 -m-(r 1 -θ 1 ) r 2 λ 2 K 1 r 1 r 3 -θ 3 -(r 1 -θ 1 ) r 3 λ 3 K 1 r 1 3 + R, [17]
we have min

    ln T r 2 λ 2 K 1 r 1 1 (T2-R) -1 r2-θ2-m-(r1-θ1) r 2 λ 2 K 1 r 1 , ln T r 3 λ 3 K 1 r 1 1 T -1 3 r3-θ3-(r1-θ1) r 3 λ 3 K 1 r 1     = ln T r 3 λ 3 K 1 r 1 1 T -1 3 r3-θ3-(r1-θ1) r 3 λ 3 K 1 r 1
.

That is, we have stability of ζ for

ln( 1 T1 ) r 1 -θ 1 < τ 0 < ln T r 3 λ 3 K 1 r 1 1 T -1 3 r 3 -θ 3 -(r 1 -θ 1 ) r3λ3K1 r1
.

[18]

REMARQUE. -From Theorem 2.1, we deduce that we have stability of the trivial equilibrium if the treatment amplitudes and period between two successive administrations of the treatment satisfy ( 12)-( 14), in this case we have eradication of the tumor.

Bifurcation analysis

We use Lyapunov Schmidt bifurcation to find nontrivial periodic solution of the model (1)- [START_REF] Liu | Complex dynamics of Holling type II Lotka Volterra predator prey system with impulsive perturbations on the predator[END_REF]. A necessary condition for the bifurcation of nontrivial periodic solutions near ζ is det(D X M (0, (0, 0, 0))) = 0.

To find a nontrivial periodic solution of period τ with initial data X 0 = (x 0 , 0, 0), we need to solve the fixed point problem X = Ψ(τ, X).

[19]

Let τ and X such that τ = τ 0 + τ and X = X 0 + X. The equation ( 19) is equivalent to

M (τ , X) = 0, [20]
where

M (τ , X) = M 1 (τ , X), M 2 (τ , X), M 3 (τ , X) = X 0 + X -Ψ(τ 0 + τ , X 0 + X). If (τ , X) is a zero of M , then (X 0 + X) is a fixed point of Ψ(τ 0 + τ , .
). Since ζ is a trivial τ 0 -periodic solution ( 1)-( 6), then it is associated to the trivial fixed point X 0 of Ψ(τ 0 , .). Let

D X M (0, (0, 0, 0)) =   a 0 b 0 c 0 0 e 0 0 0 h 0 i 0   . [21]
It follows that (see [START_REF] Lakmeche | Pulsed chemotherapy model[END_REF] for details) :

a 0 = T -1 1 (T 1 -e -(r1-θ1)τ0 ), b 0 = (r1-θ1)λ1K1(T1-e -(r 1 -θ 1 )τ 0 )e -(r 1 -θ 1 )τ 0 T1(1-e -(r 1 -θ 1 )τ 0 ) 2- r 2 λ 2 K 1 r 1 τ0 0 e (r2-θ2-m)u I 1-r 2 λ 2 K 1 r 1 (u)du + m τ0 0 e (r3-θ3)u I 1-r 3 λ 3 K 1 r 1 (u)( u 0 e (r2-θ2-(r3-3)-m)p I (r3λ3-r2λ2) K 1 r 1 (p)dp)du , c 0 = (r1-θ1)λ1K1(T1-e -(r 1 -θ 1 )τ 0 )e -(r 1 -θ 1 )τ 0 T1(1-e -(r 1 -θ 1 )τ 0 ) 2- r 3 λ 3 K 1 r 1 τ0 0 e (r3-θ3)u I 1-r 3 λ 3 K 1 r 1 (u)du, e 0 = 1 -(T 2 -R)T -r 2 λ 2 K 1 r 1 1 e (r2-θ2-m-(r1-θ1) r 2 λ 2 K 1 r 1 )τ0 , h 0 = -RT -r 2 λ 2 K 1 r 1 1 e (r2-θ2-m-(r1-θ1) r 2 λ 2 K 1 r 1 )τ0 -T 3 me (r 3 -θ 3 -(r 1 -θ 1 ) r 3 λ 3 K 1 r 1
)τ 0 (1-e -(r 1 -θ 1 )τ 0 )

r 2 λ 2 K 1 r 1 T r 3 λ 3 K 1 r 1 1 (1-e -(r 1 -θ 1 )τ 0 ) r 3 λ 3 K 1 r 1 τ0 0 e (r2-θ2-(r3-θ3)-m)u I (r3λ3-r2λ2) K 1 r 1 (u)du and i 0 = 1 -T 3 T -r 3 λ 3 K 1 r 1 1 e (r3-θ3-(r1-θ1) r 3 λ 3 K 1 r 1 )τ0 .
From the stability of the solution x s in the one dimensional space we have a 0 > 0, it follows that e 0 i 0 = 0 is necessary for the bifurcation. Equality

τ 0 = ln T r 2 λ 2 K 1 r 1 1 (T 2 -R) -1 r 2 -θ 2 -m -(r 1 -θ 1 ) r2λ2K1 r1 , [ 22
]
corresponds to e 0 = 0 and equality

τ 0 = ln T r 3 λ 3 K 1 r 1 1 T -1 3 r 3 -θ 3 -(r 1 -θ 1 ) r3λ3K1 r1 , [ 23
]
corresponds to i 0 = 0. We have three cases : 1) Case 1 : e 0 = 0 and i 0 = 0. Suppose that ( 10)-( 13), ( 15) and ( 22) are satisfied. With the above notations, we deduce that M (0, (0, 0, 0)) = 0, dim(ker[D X M (0, (0, 0, 0

))]) = 1 with ker[D X M (0, (0, 0, 0))] = span{ c 0 h 0 a 0 i 0 - b 0 a 0 , 1, - h 0 i 0 }. Then equation (20) is equivalent to    M 1 (τ , αY 0 + Z) = 0, M 2 (τ , αY 0 + Z) = 0, M 3 (τ , αY 0 + Z) = 0, [ 24
]
where

Y 0 = c 0 h 0 a 0 i 0 - b 0 a 0 , 1, - h 0 i 0 , Z = (z 1 , 0, z 3 ), X = αY 0 + Z and (α, z 1 , z 3 ) ∈ R 3 .
From the first and last equations of (24), we see that det ∂M1(0,(0,0,0)) ∂z1 ∂M1(0,(0,0,0)) ∂z3 ∂M3(0,(0,0,0)) ∂z1 ∂M3(0,(0,0,0)) ∂z3

= det a 0 c 0 0 i 0 = a 0 .i 0 = 0.

From the implicit function theorem, we can solve M 1 (τ , αY 0 + Z) = 0 and M 3 (τ , αY 0 + Z) = 0 near (0, (0, 0, 0)) with respect to Z as a function of τ and α and find a unique continuous function

Z * , such that Z * (τ , α) = (z * 1 (τ , α), 0, z * 3 (τ , α)), Z * (0, 0) = (0, 0, 0), M 1 τ , c 0 h 0 a 0 i 0 - b 0 a 0 α + z * 1 (τ , α), α, - h 0 i 0 α + z * 3 (τ , α) = 0 and M 3 τ , ć0 h0 á0 í0 - b0 á0 α + z * 1 (τ , α), α, - h0 í0 α + z * 3 (τ , α) = 0,
for every (τ , α) small enough.

Moreover, we have ∂Z * ∂α (0, 0) = (0, 0, 0) and

∂Z * ∂ τ (0, 0) = ( (r 1 -θ 1 ) 2 k 1 (1 -T 1 )e -(r1-θ1)τ0 r 1 (1 -e -(r1-θ1)τ0 ) 2 , 0, 0).
Then M (τ , X) = 0 if and only if

f 2 (τ , α) = M 2 τ , ć0 h0 á0 í0 - b0 á0 α + z * 1 (τ , α), α, - h0 í0 α + z * 3 (τ , α) = 0.
[25] We now proceed to solve equation (25). We have f 2 (0, 0) = 0. From the Taylor development of f 2 around (τ , α) = (0, 0), we find that

∂f2(0,0) ∂ τ = ∂f2(0,0) ∂α = 0. Let A 2 = ∂ 2 f2(0,0) ∂ τ 2 , B 2 = ∂ 2 f2(0,0) ∂ τ ∂α and C 2 = ∂ 2 f2(0,0) ∂α 2 . It's shown that A 2 = 0. Further, for λ 2 = 0 we have B 2 = -(T 2 -R) (r 2 -θ 2 -m) e (r2-θ2-m)τ0 < 0 and C 2 = (T 2 -R) r 2 e (r2-θ2-m)τ0 k 2 (r 2 -θ 2 -m) (e (r2-θ2-m)τ0 -1) +(T 2 -R) 2r 2 me (r2-θ2-m)τ0 k 2 τ0 0 e (r3-θ3)u I -r 3 λ 3 K 1 r 1 (u) u 0 e (r2-θ2-(r3-θ3)-m)s I -r 3 λ 3 K 1 r 1 (s) ds du +2(T 2 -R) -h 0 i 0 r 2 e (r2-θ2-m)τ0 k 2 (1 -e -(r1-θ1)τ0 ) -r 3 λ 3 K 1 r 1 τ0 0 e (r3-θ3)u I -(r 3 -θ 3 )λ 3 K 1 r 1 (u)du ,
(for more details, see [START_REF] Lakmeche | Pulsed chemotherapy model[END_REF]). From conditions cited above, we have i 0 > 0 and h 0 < 0, then

C 2 > 0, therefore B 2 C 2 < 0. Hence f 2 (τ , α) = B 2 τ α + C 2 α 2 2 + o |α| 2 + |τ | 2 .
By taking τ = σα, we have

f 2 (σα, α) = α 2 2 g 2 (σ, α) where g 2 (σ, α) = 2B 2 σ + C 2 + o α 1 + σ 2 . Moreover ∂g2 ∂σ (σ, 0) = 2B 2 < 0 and g 2 (σ, 0) = 2B 2 σ + C 2 . So, for σ 0 = -C2
2B2 we have g 2 (σ 0 , 0) = 0 and ∂g2 ∂σ (σ 0 , 0) = 0. Using the implicit function theorem we find a function σ(α) such that for α small enough g 2 (σ(α), α) = 0 and σ(0) = σ 0 = -C2 2B2 . Then, for α near 0 and τ (α) = σ(α)α we have f 2 (τ (α), α) = 0. Theorem 2.2 If conditions ( 10)-( 13), ( 15) and ( 22) hold, then we have a bifurcation of one nontrivial τ (α)-periodic solution of ( 1)-( 6) with initial condition

x 0 + c 0 h 0 a 0 i 0 - b 0 a 0 α + z * 1 (τ (α), α), α, - h 0 i 0 α + z * 3 (τ (α), α
) and period τ (α) = τ 0 + τ (α) for α(> 0) and λ 2 small enough, where

τ (α) = -C2 2B2 α + •(α) and z * 1 (τ (α), α) = -C2 2B2 (r1-θ1) 2 k1(1-T1)e -(r 1 -θ 1 )τ 0 r1(1-e -(r 1 -θ 1 )τ 0 ) 2 α + •(α).
2) Case 2 : e 0 = 0 and i 0 = 0. Suppose that ( 10)-( 13), ( 17) and (23) are satisfied. We have M (0, (0, 0, 0)) = 0, dim(ker[D X M (0, (0, 0, 0))]) = 1 with

ker[D X M (0, (0, 0, 0))] = span{ -c 0 a 0 , 0, 1 }. Let Y 0 = -c 0 a 0 , 0, 1 , Z = (z 1 , z 2 , 0), X = αY 0 + Z and (α, z 1 , z 2 ) ∈ R 3 .
From the first and second equations of (24), we have det ∂M1(0,(0,0,0)) ∂z1 ∂M1(0,(0,0,0)) ∂z2 ∂M2(0,(0,0,0)) ∂z1 ∂M2(0,(0,0,0)) ∂z2

= det a 0 b 0 0 e 0 = a 0 .e 0 = 0.

From the implicit function theorem, we can solve M 1 (τ , αY 0 + Z) = 0 and M 2 (τ , αY 0 + Z) = 0 near (0, (0, 0, 0)) with respect to Z as a function of τ and α and find a unique continuous function Z * , such that Z * (τ , α) = (z * 1 (τ , α), z * 2 (τ , α), 0), Z * (0, 0) = (0, 0, 0),

M 1 τ , - c 0 a 0 α + z * 1 (τ , α), z * 2 (τ , α), α = 0 and M 2 τ , - c 0 a 0 α + z * 1 (τ , α), z * 2 (τ , α), α = 0,
for every (τ , α) small enough.

Moreover, we have ∂Z * ∂α (0, 0) = (0, 0, 0) and

∂Z * ∂ τ (0, 0) = ( (r 1 -θ 1 ) 2 k 1 (1 -T 1 )e -(r1-θ1)τ0 r 1 (1 -e -(r1-θ1)τ0 ) 2 , 0, 0).
Then M (τ , X) = 0 if and only if

f 3 (τ , α) = M 3 τ , - c 0 a 0 α + z * 1 (τ , α), z * 2 (τ , α), α = 0. [26]
We now proceed to solve equation (26).

We have f 3 (0, 0) = 0.

From the Taylor development of f 3 around (τ , α) = (0, 0), we find that ∂f3(0,0)

∂ τ = ∂f3(0,0) ∂α = 0. Let A 3 = ∂ 2 f3(0,0) ∂ τ 2 , B 3 = ∂ 2 f2(0,0) ∂ τ ∂α and C 3 = ∂ 2 f3(0,0) ∂α 2 . It's shown that A 3 = 0.
Further, for λ 3 = 0 we have B 3 = -(r 3 -θ 3 )T 3 e (r3-θ3)τ0 < 0 and C 3 = 2r 3 τ 0 K -1 3 T 3 e (r3-θ3)τ0 > 0. Hence

f 3 (τ , α) = B 3 τ α + C 3 α 2 2 + o |α| 2 + |τ | 2 .
Using the same arguments as in the case 1, we have the following results. Theorem 2.3 If conditions ( 10)-( 13), ( 17) and ( 23) hold, then we have a bifurcation of one nontrivial τ (α)-periodic solution of ( 1)-( 6) with initial condition

x 0 + -ć 0 á0 α + z * 1 (τ (α), α), 0, α and period τ (α) = τ 0 + τ (α) for α(> 0) and (i) If h 0 = 0, then A 2 = B 2 = C 2 = 0, which is an undetermined case, to study it we need to determine the higher derivatives of f 2 .

(ii) If h 0 = 0, then dim ker(E) = 2, in this case the approach above can not be applied.

REMARQUE. -From Theorems 2.2 and 2.3, we deduce that the lost of stability for some values of the treatment amplitudes and the period between two successive administration of the treatment we have the onset of the tumor.

Conclusion

In this work we have considered a model of chemotherapy treatment by two drugs for population with normal cells, sensitive tumor cells and resistant tumor cells, one with instantaneous effect and the other with continuous effect. We have studied the stability of the trivial solution corresponding to the eradication of the tumor, and we find necessary conditions to have eradication of the tumor. Otherwise, we lose stability and bifurcation of nontrivial periodic solutions will appear, it corresponds to the persistence of the tumor. We have treated two cases, for the third one we need an other approach. It will be interesting to consider the resistance with respect to the drug with continuous effect.

Theorem 2 . 1

 21 If (12)-(14) are satisfied, then ζ is exponentially stable.

λ 3

 3 small enough, wherez * 1 (τ (α), α) = -C3 2B3 (r1-θ1) 2 k1(1-T1)e -(r 1 -θ 1 )τ 0 r1(1-e -(r 1 -θ 1 )τ 0 ) 2 α + •(α) and τ (α) = -C3 2B3 α + •(α).3) Case 3 : e 0 = 0 = i 0 .

ARIMA -volume 23 -2016