Dr Paula Teixeira
email: pcteixeira@esb.ucp.pt

G Almeida

A Morvan

I Santos

A Leclercq

R Magalhães

T Hogg

Team G Research

R Almeida

I Magalhães

T Santos

P Hogg

Teixeira

Keywords: Listeria monocytogenes, listeriosis, diversity, typing Listeria monocytogenes, listeriosis, diversity, typing

In recent years the number of cases of listeriosis has increased worldwide. Ninety-five isolates of Listeria monocytogenes recovered from Portuguese human cases of listeriosis have been characterized by biotyping (cadmium and arsenic sensitivity), PCR grouping and by pulsed field gel electrophoresis (PFGE) applying the enzymes AscI and ApaI. Isolates were classified into one of three PCR groups; IVb (71.6%), IIb (17.9%) and IIa (10.5%). Four biotypes were differentiated: sensitive to arsenic/cadmium (48.4%), arsenic sensitive and cadmium resistant (25.3%), resistant to arsenic and sensitive to cadmium (18.9%) and resista t to both h avy metals (7.4%). Combined analyses of AscI and ApaI patterns yielded a total of 58 PFGE types with fi e sets (G, Jb, KKa, Me and U) of Portuguese strains each of which were indistinguishable by PFGE typing. In the present study it was demonstrated that there are recurrent pulsotypes and that some were the same pulsotypes linked to outbreaks in France. In addition, there are some pulsotypes spread throughout the country while others only appear in a restricted region. This study allowed the assembly of a first large pulsotype database of Portuguese clinical strains.

Introduction

-Some statements are incorrect. Pag3, lines 15. A disease can be defined underreported only when it is notifiable.

Modified accordingly to: In Portugal, listeriosis is not a notifiable disease and has thus been underestimated.

-A laboratory surveillance system can contribute to more reliably estimate listeriosis incidence, but a systematical typing -pag. 3, lines 25-26 -per se does not.

Previous lines 19-25 ("The absence of adequate....of this disesase") were omitted.

-Lines 40 and following. There are a number of outbreaks that have been occurring in Europe and, in my opinion, could be more suitable to be cited. New references were added as suggested.

-Lines 48 and following. Again, typing of L. monocytogenes isolates is a very useful tool to be used in the aim of a better understanding of a complex disease from both clinical and epidemiological points of view, but is not a prerequisite in the implementation of a surveillance system.

Previous lines 48-53 were omitted.

-Traditional serotyping has not been so largely replaced by PCR "grouping or geno-serotyping" as the authors affirm in lines 55 and 56.

Modified to: The characterization of L. monocytogenes strains can be based on its molecular subtyping by PCR grouping or geno-serotyping [START_REF] Doumith | Differentiation of the major Listeria monocytogenes serovars by multiplex PCR[END_REF] and by macrorestriction pulsotype analysis of its DNA using the PulseNet protocol [START_REF] Graves | PulseNet standardized protocol for subtyping Listeria monocytogenes by macrorestriction and pulsed-field gel electrophoresis[END_REF].

-Geno-serotyping is less discriminatory than traditional serotyping and this observation is confirmed by the data presented in the manuscript.

We agree but it is true that the use of conventional serotyping has been replaced by geno-serotyping in several laboratories.

-Pag. 4, lines 1 to 14. This paragraph has to been rewritten for clarity.

Rewritten as suggested: "The use of subtyping methods to differentiate strains (or subtypes) of L. monocytogenes has important epidemiological applications: rapid, precise, and efficient foodborne listeriosis surveillance can minimize outbreaks and track sources of L. monocytogenes contamination throughout the food system. Moreover, molecular subtyping in listeriosis surveillance would allow the detection of clusters of cases that could be erroneously considered as sporadic cases. The association between a particular pulsotype and specific virulence traits is another possibility offered by molecular subtyping [START_REF] Franciosa | Characterization of Listeria monocytogenes strains involved in invasive and noninvasive listeriosis outbreaks by PCR-based fingerprinting techniques[END_REF]".

-Pag. 4, line 24. I suggest to replace "hypothetical" with "apparently". Modified as suggested.

-Pag. 4, lines lines 18 to 28. I would suggest to invert the position of the two paragraphs.

Modified as suggested.

Materials and Methods -Pag. 4, line 58 and pag.5, lines 1-2. I don't understand how the lack of information could be justified by the non notifiable status of this disease. Unfortunately, It is true that epidemiological information is often difficult or impossible to obtain, but this information should be routinely present in the databases of the diagnostic microbiology laboratories.

We are totally in agreement but this is the Portuguese reality concerning listeriosis. Unfortunately in many institutions the information in not centralized in the diagnostic microbiology laboratories being difficult to gather. Anyway, "in recognition of the fact that this illness is still a non-notifiable disease in Portugal" was omitted.

-Pag. 5, line 60 and pag. 6, lines 1 to 11. The Simpson's index of diversity can be cited only, without further details that should be deleted. Modified as suggested.

Results

Pag. 6, lines 43 and following. A section entitled "epidemiological data" is inconsistent with the repeated statements about the frequent lack of information. The descriptive data should not be emphasized.

Modified accordingly to: "Data collected from human episodes. " Lines 49 and following: 90% and 10% are incorrect and have to be recalculated. Moreover, percentages should be expressed with one decimal.

-Corrected -Pag. 6, line 57. Replace "sex" with "gender" Modified accordingly -Pag. 6, line 59. Delete "old" Modified accordingly -PFGE results. This is perhaps the most confuse part of the manuscript. Pag. 7, line 54 and following: this is a comment and has to be displaced in the Discussion.

The sentence was omitted.

-There is not an unanimous agreement among the researchers about the combined or hierarchical use of the two enzymes AscI and ApaI (please italicize). Indeed, this is an argument for the discussion. Generally speaking, the entire section is too long, detailed and, unavoidably, boring and dispersive. I would suggest to mark the clusters e.g. with Roman numbers, in the dendrogram and refer to them, instead of listing all pulsotypes.

The old but evergreen suggestion to no duplicate the same information in different forms (text, tables or figures) is to be ever taken into account. Pag. 9, lines 20-28. This statement about the Tenover criteria is a matter of Method, not of Results, and is contradictory withrespect to the previously cited clustering criteria.

The entire section was rewritten.

Discussion

-The Discussion is too long and in some parts repetitive.

The discussion was rewritten in a shorter form.

-The entire paragraph from page 9, line 44 to page 10, line 16 should be rewritten in a more consistent and consequential manner.

Modified accordingly -Pag. 10, line 36. The authors describe the characteristics of an active surveillance system, but wrongly. Form a conceptual point of view, an active surveillance system is a quite different issue than this one here described. So to speak, an active surveillance system is FoodNet, that is characterized by the active search for epidemiological data that can allow for a reliable estimate of the incidence of some foodborne diseases, including listeriosis. This is a serious misunderstanding that the Authors have to clarify.

We decided not to include this information.

-Pag. 11, lines 1-20. The content of this part of the Discussion has been previously included in the Results. This information was omitted from the Results -Pag.11, lines 22-47. It's very difficult and maybe poorly informative to complement the mandatory notification of each case with a questionnaire about food consumption habits. This last should be used during the epidemiological investigation driven by a suspicion about a possible outbreak arising from traditional and molecular epidemiological findings.

It was decided to omit this "information" as we consider that it is not relevant in the context of the aims of the present work.

-Page 11, lines 49 and following. Comparison with French isolates cannot be presented in the Discussion, but also in M&M and Results. Otherwise, the authors could discuss possible similarities between strains or pulsotypes from the two countries with reference to published data.

Modified accordingly:

Methods: "PFGE pulsotypes of indistinguishable Portuguese strains were compared with PFGE pulsotypes of the French PFGE database of the Centre National de Référence des Listeria using the BioNumerics software as previously described in this section."

Results: "Comparison with the PFGE pulsotypes database of French human strains, underlined that pulsotypes Me, Jb, Pb, HHb, FF, MM and LLb have been previously described in human clusters in France and are part of the main, pulsotypes from human strains observed in France. Pulsotypes MM and LLb are indistinguishable from pulsotypes associated with the main outbreak of listeriosis in France in 1992. The main pulsotypes observed in Portugal, U and KKa, have not been recorded for French human cases." -Pag. 12, lines 4 and following. As I have previously commented, the active surveillance is not a microbiological surveillance. Accordingly, the entire paragraph should be thoroughly revised. Modified accordingly: "The possible epidemiological links with human strains isolated in other countries, underlines the need for an active surveillance system of listeriosis in Portugal harmonized with other national systems. As the French National Surveillance system [START_REF] Goulet | Surveillance of human listeriosis in France, 2001-2003[END_REF][START_REF] Monnier | Listeria et listériose : des animaux d"élevage à nos assiettes[END_REF], this should be based on the obligatory notification of human cases of listeriosis and epidemiological data collection, on the basis of European regulation EC 178/2002 (obligatory notification of unsatisfactory food according to microbiological criteria defined by European regulation) and also on the dispatch of isolates to a National reference laboratory for typing."

Removed accordingly

Table 1. This table in the present form is not reader-friendly. The Table has to be reorganized in a much more synthetic manner. Maybe less information (e.g. specimen could be removed, age and sex grouped, etc.) and inclusion of molecular subtype clusters instead of pulsotypes could help to lighten the Table .   The table was reorganized. As it is still to long it might be possible to submit it as a "supplementary file"

Introduction

Listeria monocytogenes is recognized as a major, opportunistic, foodborne pathogen in humans. The condition which this species causes, listeriosis, occurs worldwide both sporadically and epidemically and has a case-fatality rate between 20 and 30%. L. monocytogenes has the ability to cross the intestinal, blood-brain, and fetoplacental barriers; and thus septicaemia, central nervous system (CNS) infections, miscarriages and stillbirths are risks to immunodeficient or pregnant individuals [START_REF] Wing | Listeria monocytogenes: clinical and experimental update[END_REF].

In Portugal, listeriosis is not a notifiable disease and has thus been under-estimated.

Nevertheless, Almeida and his colleagues in 2006 [START_REF] Almeida | Listeriosis in Portugal: an existing but under reported infection[END_REF], in a retrospective study, reported an estimated incidence of at least 1.4 cases per million inhabitants in 2003. The result of the implementation of an active surveillance program in the Netherlands led to a 43% increase in the reported incidence of listeriosis in the first year of operation [START_REF] Doorduyn | First results of the active surveillance of Listeria monocytogenes infections in the Netherlands reveal higher than expected incidence[END_REF] might give some indication as to the current degree of underestimation in Portugal. Any such programme would certainly omit reporting some sporadic cases and spontaneous miscarriages as these are often not investigated. Since 2005, several European countries reported an increase of listeriosis and several foodborne outbreaks have been reported [START_REF] Goulet | Increasing incidence of listeriosis in France and other European countries[END_REF]. Some examples are the outbreaks occurred in Switzerland, associated with Tome cheese [START_REF] Bille | Outbreak of human listeriosis associated with tomme cheese in northwest Switzerland[END_REF], in the United Kingdom associated with sandwich consumption [START_REF] Dawson | Listeria outbreak associated with sandwich consumption from a hospital retail shop, United Kingdom[END_REF], in the Czech Republic associated with soft cheese [START_REF] Vít | Outbreak of listeriosis in the Czech Republic, late 2006preliminary report[END_REF], and a recent multinational outbreak due to the consumption of "Quargel" cheese in Austria and Germany [START_REF] Fretz | Listeriosis outbreak caused by acid curd cheese "Quargel", Austria and Germany[END_REF].

The characterization of L. monocytogenes strains can be based on its molecular subtyping by PCR grouping or geno-serotyping [START_REF] Doumith | Differentiation of the major Listeria monocytogenes serovars by multiplex PCR[END_REF] and by macrorestriction pulsotype analysis of its DNA using the PulseNet protocol [START_REF] Graves | PulseNet standardized protocol for subtyping Listeria monocytogenes by macrorestriction and pulsed-field gel electrophoresis[END_REF]. The use of subtyping methods to differentiate strains (or subtypes) of L. monocytogenes has important epidemiological applications: rapid, precise, and efficient foodborne listeriosis surveillance can minimize outbreaks and track sources of L. monocytogenes contamination throughout the food system. Moreover, molecular subtyping in listeriosis surveillance would allow the detection of clusters of cases that could be erroneously considered as sporadic cases.

The association between a particular pulsotype and specific virulence traits is another possibility offered by molecular subtyping [START_REF] Franciosa | Characterization of Listeria monocytogenes strains involved in invasive and noninvasive listeriosis outbreaks by PCR-based fingerprinting techniques[END_REF].

The study presented here was initiated in 2003, with a view to support the establishment of an integrated, food-chain surveillance system in Portugal. Ninety-five clinical Portuguese isolates recovered from apparently sporadic cases of listeriosis were collected, identified, biotyped by cadmium and arsenic sensitivity, geno-serotyped, and typed by DNA macrorestriction pulsed field gel electrophoresis (PFGE). The aim was to obtain epidemiological data on cases of listeriosis in the country and to construct a molecular-type database of clinical strains of L. monocytogenes.

Materials and methods

Collection of L. monocytogenes strains and related data to listeriosis episodes

A total of 95 L. monocytogenes strains isolated between 1994 and 2007 were collected from major Portuguese hospitals. The case definition of listeriosis employed was that contained in Commission Decision 2002/253/CE [START_REF] Anonymous | Case definitions for reporting communicable disease to the Community network. Commission Decision No. 2119/98/EC of the European Parliament and of the Council[END_REF]. Thus on isolation of L. monocytogenes from a hospitalised patient with a clinical compatible illness, each strain was considered as a single case of listeriosis. A case was defined as maternal/neonatal (MN) in the following situations: infected pregnant woman, miscarriage, stillbirth or newborn less than one month. Only one strain was kept when the pathogen was isolated from both the pregnant woman and her newborn child. If a case does not apply to any of these, it is considered as non-maternal/neonatal (non-MN). Information regarding, gender and age of the patient, the tissue or fluid origin where the bacteria was isolated and the year of isolation was reported when available. These epidemiological characteristics are described in Table 1. Confirmed isolates of L. monocytogenes were stored in Tryptic Soy Broth with 30% (v/v) glycerol at -80 ºC in the culture collection of the Escola Superior de Biotecnologia.

Biotyping by arsenic and cadmium sensitivity

The characterization of their differential resistance to arsenic and cadmium were performed in Isosensitest agar plates (ISA, Oxoid, Hampshire, UK), containing 500 µg/ml sodium arsenite (Merck, Darmstad, Germany) or 75 µg/ml cadmium chloride (Merck) [START_REF] Vaz-Velho | Characterization of Listeria monocytogenes isolated from production lines of fresh and cold-smoked fish[END_REF][START_REF] Mclauchlin | Subtyping of Listeria monocytogenes on the basis of plasmid profiles and arsenic and cadmium susceptibility[END_REF].

Geno-serotyping or PCR grouping

Geno-serotyping was determined by PCR grouping with a multiplex PCR as described by Doumith et al. [START_REF] Doumith | Differentiation of the major Listeria monocytogenes serovars by multiplex PCR[END_REF], using primers targeting fragments of genes lmo0737, ORF2819, ORF 2110, lmo1118 and prs (MWG-Biotech, Switzerland). PCR was performed in Eppendorf thermocycler (Eppendorf, Hamburg, Germany) and PCR products were resolved on a 2% agarose gel containing 0.5 µg/ml of ethidium bromide (Eurobio, Courtaboeuf, France) and visualized and photographed under a UV transilluminator (Bio-Rad Gel Doc 2000 TM imaging system, Bio-Rad Laboratories, Milan, Italy).

Molecular characterisation by pulsed-field gel electrophoresis (PFGE)

The DNA macrorestriction was performed at the Centre National de Référence des Listeria Institut Pasteur (Paris, France) with the restriction enzymes AscI (New England BioLabs, Massachusetts, USA) and ApaI (MBI Fermentas, Burlington, Canada) as previously described by Graves and Swaminathan [START_REF] Graves | PulseNet standardized protocol for subtyping Listeria monocytogenes by macrorestriction and pulsed-field gel electrophoresis[END_REF].

The pulsotypes obtained were scanned, and the computerized data were analyzed using the BioNumerics software, version 5.1 (Applied Maths, Kortrijk, Belgium). Bands automatically assigned by the computer were checked visually and corrected manually when necessary. A position tolerance of 1.5 was selected for each PFGE. Cluster analysis of the individual or combined PFGE pulsotypes was done by the unweighted pair group method with average linkages (UPGMA), using the Dice coefficient to analyze the similarities of the banding pulsotypes. The discriminatory power was determined by calculating the discrimination index (D) based on Simpson's index of diversity as described by Hunter and Gaston [START_REF] Hunter | Numerical index of the discriminatory ability of typing systems: an application of Simpson's index of diversity[END_REF]. Two PFGE patterns were considered indistinguishable when their similarity was higher than 98% [START_REF] Tenover | Interpreting chromosomal DNA restriction pulsotypes produced by pulsed-field gel electrophoresis: criteria for bacterial strain typing[END_REF] and a capital letter was ascribed to AscI pulsotype; when strains were similar at more than 98% by AscI but not similar at more than 98% by ApaI, were denoted, in addition to the capital letters, by lower case letters. PFGE pulsotypes of indistinguishable Portuguese strains were compared with PFGE pulsotypes of the French PFGE database of the Centre National de Référence des Listeria using the BioNumerics software as previously described in this section.

Statistical analysis

The statistical package used was STATA v10.0 (StataCorp LP, College Station TX, USA).

The contingency table analysis was based on the chi-square distribution (Pearson"s chi square test).

Results

Data collected from human episodes

A total of 95 isolates from cases of listeriosis were collected from major Portuguese hospitals during the study period. From the information available on 81 cases (Table 1), 85.2% and 14.8% corresponded to non-MN infections and MN infections, respectively.

For the 69 confirmed non-MN cases, strains were isolated from blood (58.0%), from cerebrospinal fluid (34.8%) and from other specimens (7.2%). The clinical symptoms were not recorded for the majority of cases. The gender ratio (M/F) of confirmed non-MN cases was 2.3. The mean age of non-MN cases with documented age was 60 years old with 38 cases (55.9%) equal or up to 60 years. Geographical distribution of listeriosis cases was difficult to define from our collected data in the absence of data about the residence of patient.

Biotyping results by arsenic and cadmium sensitivity

Four groupings of sensitivity to heavy metals were differentiated among the 95 isolates (Table 1), the D value for this biotyping method being 0.667. The predominant groupsensitive to both arsenic (As) and cadmium (Cd) -contains 46 isolates (48.4%). Twenty four isolates were arsenic sensitive and cadmium resistant (25.3%), 18 were resistant to arsenic and sensitive to cadmium (18.9%) and 7 were resistant to both heavy metals (7.4%).

PCR grouping results

Three PCR groups were identified in the 95 L. monocytogenes isolates recovered from sporadic human listeriosis cases in Portugal. Most isolates were of PCR group IVb (including serotypes 4b or 4d or 4e) 71.6% (n=68): 17.9% (n=17) and 10.5% (n=10) of the isolates showed PCR group IIb (including serotypes 1/2b or 3b) and PCR group IIa (including serotype 1/2a or 3a), respectively. D obtained from these PCR grouping results was 0.449.

Combining results from PCR grouping and sensitivity to heavy metals, it was possible to segregate the 95 isolates into nine groups (D = 0.831). Two groups predominate: PCR group IVb, As and Cd sensitive (30.5%); PCR group IIb, As resistant and Cd sensitive (17.9%). Comparisons based on such combined patterns are reported in Table 1 and

PFGE results

PFGE

Combination of biotyping, PCR grouping and PFGE results

The highest D value, 0.994, and thus the greatest number of distinguishable types (72) was obtained when results of multiplex PCR, sensitivity to heavy metals and analysis of AscI and ApaI were combined.

Discussion

The 2007 Annual Community Summary Report by the European Food Safety Authority (EFSA) and the European Centre for Disease Prevention and Control (ECDC), established an overall incidence rate of listeriosis in Europe of 3 cases per million inhabitants with a range of 0 -11 cases per million inhabitants. The results presented here estimated an incidence rate of listeriosis in Portugal, based on information from voluntary reporting, of 2.3 cases per million inhabitants for the year 2007, which is comparable to the reported incidence in Austria, Estonia, Latvia, Slovakia and Slovenia of 2 cases per million inhabitants [START_REF] Anonymous | The Community Summary Report on trends and sources of zoonoses and zoonotic agents in the European Union in 2007[END_REF]. In Portugal"s only neighbouring country, Spain, the incidence for 2007 was similar to that described in this study and was also based on voluntary reporting of cases to the National Reference Laboratory. However, it has been demonstrated that the implementation of an active surveillance system for listeriosis in Navarra, a region of northern Spain, led to an incidence for this region similar to that described in countries with mandatory notification of listeriosis such as France, Denmark and the Netherlands [START_REF] Garrido | Surveillance of listeriosis in Navarre, Spain, 1995-2005 -epidemiological pulsotypes and characterisation of clinical and food isolates[END_REF]. An apparent increase in numbers of cases of listeriosis in recent years, observed in some other countries, e.g. Denmark, Finland, France, Germany, the Netherlands, Switzerland and United Kingdom [START_REF] Doorduyn | First results of the active surveillance of Listeria monocytogenes infections in the Netherlands reveal higher than expected incidence[END_REF][START_REF] Goulet | Increasing incidence of listeriosis in France and other European countries[END_REF], was also observed in Portugal. These results indicate that voluntary reporting under-estimates the occurrence of listeriosis in a country, and that the EC requirement for statutory reporting of listeriosis will probably lead to many more cases being uncovered. A statutory reporting and investigation system in Portugal, will inevitably take some time to establish, and it is recommended that in parallel, a surveillance system for the pathogen in typical foods should be established, with the capability for in-depth characterisation of isolates for comparisons of clinical and food strains.

The majority of patients with listeriosis in Portugal were people older than 60 years with bacteraemia, as recorded in some other countries including France and United Kingdom [START_REF] Gillespie | Changing pattern of human listeriosis, England and Wales, 2001-2004[END_REF][START_REF] Goulet | Surveillance of human listeriosis in France, 2001-2003[END_REF]. Most of these cases were caused by PCR group IVb strains, generally associated with epidemic clones [START_REF] Swaminathan | The epidemiology of human listeriosis[END_REF]. As in other countries [START_REF] Garrido | Surveillance of listeriosis in Navarre, Spain, 1995-2005 -epidemiological pulsotypes and characterisation of clinical and food isolates[END_REF][START_REF] Goulet | Surveillance of human listeriosis in France, 2001-2003[END_REF], serogroup 1/2a became more common than serogroup 1/2b in 2006 and 2007.

The results of our study confirm that PCR grouping alone has the lowest discriminatory power but, when combined with PFGE AscI and ApaI it becomes the most powerful of all [START_REF] Jacquet | Investigations related to the epidemic strain involved in the french listeriosis outbreak in 1992[END_REF]. Nevertheless, during outbreaks, the screening method of strains based on PCR grouping rather than classical serotyping is useful. Biotyping by As and Cd sensitivity gave additional information data but not enough to consider the use of this method in a routine system of microbiological surveillance. As observed in Belgium [START_REF] Anonymous | Centre National de Reference des Listeria. Rapport annuel souches de Listeria isolées en Belgique en[END_REF] an increase in strains resistant to Cd but sensitive to As was verified.

In our study, it was possible to link sporadic cases on six occasions related in time and geographical distributions; thus a common source of contamination could be suspected. This suspicion underlined the need to characterise food and environmental strains at the same time as human strains at a national level in order to trace sources of contamination and to detect and confirm related cases.

The finding that combined pulsotypes of Portuguese clinical isolates have already been described in human clusters, and even outbreaks, in France can be explained by both human travel and food commerce. It can be argued that there is, at least, a European distribution of clinical strains that necessitates European tracing such as a PulseNet initiative for the continent. Nevertheless, combined pulsotypes U and KKa have been detected in Portugal but not in France, which suggests that indigenous clones of L. monocytogenes may exist in the country which might, at some time, become epidemic clones.

The possible epidemiological links with human strains isolated in other countries, underlines the need for an active surveillance system of listeriosis in Portugal harmonized with other national systems. As the French National Surveillance system [START_REF] Goulet | Surveillance of human listeriosis in France, 2001-2003[END_REF][START_REF] Monnier | Listeria et listériose : des animaux d"élevage à nos assiettes[END_REF], this should be based on the obligatory notification of human cases of listeriosis and epidemiological data collection, on the basis of European regulation EC 178/2002 (obligatory notification of unsatisfactory food according to microbiological criteria defined by European regulation) and also on the dispatch of isolates to a National reference laboratory for typing.

Teresa Afonso (Hospital Central do Funchal do Serviço de Saúde da Região Autónoma da Madeira), Helena Peres, Teresa Pina e Maria José Silvestre (Hospital Curry Cabral, Lisboa), Maria Dolores Pinheiro (Hospital de São João, Porto), Maria Alberta Faustino e Maria Carmen Iglesias (Hospital de São Marcos, Braga), José Diogo, Ana Rodrigues e Isabel NAscImento (Hospital Garcia da Horta, Almada), Fernanda Bessa e Elmano Ramalheira (Hospital Infante D. Pedro-Aveiro, E.P.E.), João Lago (Hospital Militar de Belém, Lisboa), Maria Antónia Read (Hospital Pedro Hispano, Matosinhos), Lurdes Monteiro, Luís Marques Lito e J. Melo Cristino (Hospital Santa Maria, Lisboa), Maria Helena Ramos (Hospital Santo António, Porto), Maria Augusta Guimarães (Instituto Português de Oncologia, Porto).

Figure 1 .

 1 Figure 1. This Figure has to be removed. Indeed, it does not illustrate any finding of this work.

  typing revealed a total of 39 AscI macrorestriction and 50 ApaI macrorestriction types among clinical isolates, distinguished by one or more band differences ranging in molecular size from 50 to 500 kb (Fig1). Combined analyses of AscI and ApaI PFGE data yielded a total of 58 PFGE pulsotypes with D = 0.966 for AscI, D = 0.979 for ApaI and D = 0.986 combined AscI and ApaI.

  the corresponding dendrogram in Figure 1. Pulsotypes DD, EE, FF, G, HHb, Jb, KKa, La, LLa, LLb, Me, MM, Pb, S, T, U, V, and Ya contained two or more strains which remained indistinguishable from each other. Only the pulsotypes FF, LLb, MM, Pb, T, U, V and Ya, contained indistinguishable strains by Cd and As sensitivity. Pulsotypes DD, EE, FF, HHb, Jb, KKa, La, LLa, LLb, Me, MM, Pb, S and T were constituted of L. monocytogenes isolates from geno-serotype IVb, pulsotypes U, V and Ya of geno-serotype IIb, and pulsotype G of geno-serotype IIa. While strains of pulsotypes DD, FF, HHb, La, LLa, LLb, MM, Pb, S, T, V and Ya were recovered from different years and geographical distribution, pulsotypes EE, G, Jb, KKa, Me, and U were related in time or geographical distribution. Two pulsotypes (U and KKa) have six indistinguishable strains. Three pulsotype U strains were isolated in the Lisbon region, respectively in February 2004, August 2004 and October 2004, with the same Cd and As sensitivity. Two pulsotype KKa strains having the same Cd and As sensitivity were isolated in March and in April 2004. Pulsotype G contained two indistinguishable strains, but with distinct Cd and As sensitivity isolated in February and May 2006 in different towns. Concerning to pulsotype EE, two indistinguishable strains, but with distinct Cd and As sensitivity were isolated in different hospitals in Porto in 2007 six months apart, from a women and a newborn child. The pulsotype Jb contained three indistinguishable strains isolated in Lisbon in March 2006, September 2006 and June 2007. Pulsotype Me is constituted by four indistinguishable strains, three isolated in the Porto region over a period of one year. Comparison with the PFGE pulsotypes database of French human strains, underlined that pulsotypes Me, Jb, Pb, HHb, FF, MM and LLb have been previously described in human clusters in France and are part of the main, pulsotypes from human strains observed in France. Pulsotypes MM and LLb are indistinguishable from pulsotypes associated with the main outbreak of listeriosis in France in 1992. The main pulsotypes observed in Portugal, U and KKa, have not been recorded for French human cases.

Figure 1 .PFGE

 1 Figure 1. Dendrogram for Listeria monocytogenes pulsotypes of all 95 isolates obtained from clinical cases, Portugal, 1994-2007

  Figure

Table 1 .

 1 L. monocytogenes strains used in this study and collected epidemiological data concerning the cases with which they were associated.

	Isolate	Hospital localization	Year of isolation	Clinical form a	Patient Gender / Age	b	PCR group (Geno-serotype)	Susceptibility to As / Cd c	PFGE Combined type
									U	I

Acknowledgements

This work was supported by FCT project -PTDC/AGR-ALI/64662/2006 -Listeria monocytogenes in foods: contributing data for risk assessment. Gonçalo Almeida was recipient of a Fundação Calouste Gulbenkian short visit grant 96780. Grateful acknowledgements to Laboratoire des Listeria, Centre National de Référence des Listeria, WHO Collaborating Center for Foodborne Listeriosis, Institut Pasteur for accepting Gonçalo Almeida and typing by PFGE the strains of this work.

Members of the Research Team:

Ana Florinda (Centro Hospitalar de Coimbra), Graça Ribeiro e Luisa Boaventura (Hospitais da Universidade de Coimbra),


Amandine Bellenger
email: amandine.bellenger@eads.com

Sylvain Gatepaille
email: sylvain.gatepaille@eads.com

Uncertainty in Ontologies: Dempster-Shafer Theory for Data Fusion Applications

Keywords: ontologies, uncertainty, belief functions, data fusion

Nowadays ontologies present a growing interest in Data Fusion applications. As a matter of fact, the ontologies are seen as a semantic tool for describing and reasoning about sensor data, objects, relations and general domain theories. In addition, uncertainty is perhaps one of the most important characteristics of the data and information handled by Data Fusion. However, the fundamental nature of ontologies implies that ontologies describe only asserted and veracious facts of the world. Different probabilistic, fuzzy and evidential approaches already exist to fill this gap; this paper recaps the most popular tools. However none of the tools meets exactly our purposes. Therefore, we constructed a Dempster-Shafer ontology that can be imported into any specific domain ontology and that enables us to instantiate it in an uncertain manner. We also developed a Java application that enables reasoning about these uncertain ontological instances.

I. INTRODUCTION

An ontology contains the concepts used to describe and represent an area of knowledge. By clearly defining semantically a group of terms in the given domain and the relationships among them, without any ambiguity, an ontology encodes the knowledge of the domain in such a way that it can be understood by a computer.

For this to be possible, ontologies must be formalized in languages processable by computers. Without any doubt, the most popular is OWL: Web Ontology Language, which is the latest recommendation of W3C (World Wide Web Consortium), made in February 2004 for the first version 1.0 and more recently at the end of October 2009 for version 2.0. OWL 2 adds new functionalities, which some are said to be only "syntactic sugar" while others really offer new expressivity.

There has been since 2003 a growing interest of ontologybased technologies within data fusion, as shown by the increasing number of papers in international Conferences. For instance during the 6 th International Conference on Information Fusion, held in Australia in 2003, was organized a Special Session titled "Ontology Needs and Issues for Higher-Level Fusion." Data Fusion embodies the process of data combination to refine state estimates and predictions [START_REF] Hall | Handbook of Multisensor Data Fusion[END_REF]. These data are obtained from various and heterogeneous sensors such as radar, satellite, human messages, etc. The JDL model, elaborated by the Joint Directors of Laboratories Data Fusion Group, presents a pedagogically common understanding of Data Fusion, illustrated on the figure 1 below.

Figure 1. JDL Recommended Revised Data Fusion Model

(version from 1998)

In the field of National Defense, community focuses on problems involving the location, characterization, and identification of distinct and dynamic entities such as emitters, platforms, weapons, and military units (level 1). Beyond this task, one seeks higher-level inferences about the enemy situation (such as the relationship among entities, their relationships with the environment and higher level enemy organizations for example, which refers to level 2) and the possible threat they embody (level 3).

In that context, ontologies are useful in providing means for describing and reasoning about sensor data, objects, relations and general domain theories. In that way, they enable to explicitly encode a shared understanding of some domain, in order to disambiguate terms associated with that domain.

However, uncertainty is an important characteristic of our data and information handled by Data Fusion applications. At a low level of the JDL model, observations received from sensors are sullied with uncertainty, due to operational conditions of observations (concealment, jamming, dissemination, etc.). In this paper, we could note that the term "uncertainty" is intended to cover a variety of forms of incomplete knowledge, including incompleteness, vagueness, ambiguity, and others. Uncertainty can be due to measuring errors made by physical sensors (human or electronic). For example, a radar can observe the speed of a vehicle with an error of + or -3 Km/h. At level 1, it should be necessary to enable the representation of knowledge such as: "Possibility of existence of a regiment position (x,y,t)". There is here a doubt concerning the existence of the observed entity. At level 2, there could be uncertain relations between entities. For instance, "do two military aircrafts maintain a communication?". Finally, uncertainty is also ubiquitous in higher levels where the assessment of impact (including threat) is always associated to a certain degree of confidence.

As previously shown, uncertainty is inherent to data. However, uncertainty also naturally occurs in the fusion process itself. Issues related to uncertainty arise in case the set of information acquired from multiple sources about the same fact is inconsistent, or -more generally -in case that multiple information sources attribute different grades of belief to the same statement. If the user/application is not able to decide in favor of a single alternative (due to insufficient trust in the respective information sources), the aggregated statement resulting from the fusion of multiple statements is typically uncertain. The result needs to reflect and weight the different information inputs appropriately, which typically leads to uncertainty. This paper is organized as follows. In the second section it begins to establish the limitation of traditional ontology formalism in the field of uncertainty representation. Then, it discusses the various ways that have been chosen to represent uncertainty within ontologies, by making a state of art of the most known approaches and associated tools.

In section 3, we will briefly remind what make the Belief Theory a so appealing theory to represent uncertainty within our Data Fusion Applications. Consequently, we will present the ontology that we have built, called DS-Ontology, according to the Dempster-Shafer model, which helps to construct uncertain aspects into any specific domain ontologies. The section will then present the Java application we developed in order to reason formally on an ontology that imports the DS-Ontology, thanks to Jena [START_REF] Mcbride | A Semantic Web Toolkit[END_REF], a Java framework for building Semantic Web applications.

II. EXISTING APPROACHES FOR UNCERTAINTY REPRESENTATION WITHIN ONTOLOGIES

We will focus here naturally on approaches that directly deal with Semantic languages, and especially OWL. Moreover, we will present some open source tools that we have been able to find out and that permit in some way to represent uncertainty in ontology. We will organize this survey regarding their underlying theory. But first of all, let's remind why traditional ontologies cannot, on their own, answer this uncertainty issue.

A. Limit of traditional ontologies for uncertainty representation

One of the major limitations of traditional ontology formalisms is the lack of consistent support for uncertainty, reliability and imprecision. As a matter of fact, ontologies currently designed contain only concepts and relations that describe asserted facts about the world. This means that the ontology itself is not uncertain in nature, but rather presents an a priori model of the world, which has to be taken as true by its users. However, in many cases, it is preferable to store a piece of information even imprecise and uncertain rather than to interpret its contents in a restrictive manner, which will lead to store erroneous pieces of information.

There is currently no standard mechanism for interoperable description and exchange of uncertain information over ontologies and even less a standard to reason on this type of information.

However, many researchers are currently trying to enhance ontological capabilities concerning this field. As a matter of fact, the requirement for representation has led the World Wide Web Consortium (W3C) to set up the Uncertainty Reasoning for the World Wide Web Incubator Group in 20072 . It delivered its final report in March 2008, which exposed mainly the different reasoning challenges and the various use cases for the need of uncertainty representation in the Semantic Web.

B. Probabilistic Approaches

Probability domain is surely the most known mathematical theory dealing with uncertainty. In brief, it provides a mathematically sound representation language and formal calculus for rational degrees of belief.

Firstly, some existing tools are based on this theory and more specifically on the Bayesian networks. Bayesian networks (BN) are a powerful probabilistic graphical model to represent a set of random variables and their conditional independencies. Bayesian networks are directed acyclic graphs. The arcs point the direction from the cause to the consequence. BayesOWL [START_REF] Ding | Uncertainty Modelling in Semantic Web Ontologies[END_REF] is one proposal to model uncertainty in OWL ontologies through BN. It is a mechanism to express OWL ontologies as BN by adding a second ontology to this translation which declares the probabilistic relationships. The advantage is that neither OWL nor ontologies defined in OWL need to be modified. It is used to quantify the degree of the overlap or inclusion between two concepts. However, there are important limitations considering the translation of ontologies. As a matter of fact, it does not take into account neither the properties represented by OWL, the instances nor the specific datatypes.

Secondly, there are also the so-called probabilistic extensions to Description Logics (DL) that want to be seen as an alternative to more traditional Bayesian approaches. For instance, Pronto [START_REF] Klinov | Pronto: a Non-Monotonic Probabilistic Description Logic Reasoner[END_REF] is a probabilistic DL reasoner prototype. Pronto is able to represent and reason about uncertainty in both, generic background knowledge and individual facts (respectively probabilistic relationships between OWL classes and relationships between an OWL class and an individual). We could note that Pronto uses OWL version 1.1 axiom annotations (which is however not a W3C recommendation) to associate probability intervals with uncertain OWL axioms. The main advantages are clearly the ease of the representation and of the reasoner manipulation. However this tool presents really serious deficiencies, considering its scalability and speed of processing. Most notably, Pronto's performance does not scale past beyond around 15 generic conditional constraints in an OWL knowledge base.

Finally, there are also probabilistic approaches that rely on first-order logic such as PR-OWL [START_REF] Laskey | Probabilistic Ontologies for Knowledge Fusion[END_REF] in combination with UnBBayes-MEBN. PR-OWL is an upper ontology. In order to use it, one has to import the PR-OWL ontology into an ontology editor (e.g. Protégé). Then one can start constructing our domain-specific concepts using the PR-OWL definitions to represent uncertainty about their attributes and relationships according to the Multi-Entity Bayesian Network (MEBN) model. A graphical user interface (UnBBayes-MEBN) is also available to make it easier to instantiate the main ontological concepts (M-Frags, Resident, Input, Context Nodes, etc). UnBBayes-MEBN implements also a reasoner based on the PR-OWL/MEBN framework. Unfortunately, this GUI has a General Public License (GPL) which is a little too restrictive in order to integrate it into a commercial application. In addition, to our knowledge MEBN community is not wide enough to be considered as an emerging standard. Thus it represents a major difficulty to manipulate this tool.

C. Fuzzy Approaches

Fuzzy formalisms allow the representation and the gradual assessment of truth about vague information.

FuzzyDL [START_REF] Bobillo | fuzzyDL: An Expressive Fuzzy Description Logic Reasoner, Fuzzy Systems[END_REF] is one of the most succeeded tools that propose a fuzzy description language associated to a reasoning engine. Even if the syntax is based on fuzzy SHIF, we can translate a basic ontology into a fuzzyDL file, thanks to a given specific API. Then fuzzy statements can be added to this file, or we can directly make use of the fuzzyOntology. The latter is an OWL ontology that may be used to encode Fuzzy OWL statements and thanks to a parser, it can be translated into a fuzzyDL file. Finally, it supports two types of reasoning: Zadeh semantics and Lukasiewicz Logic. However, we could point out that the implementation is only intended to be run either on MacOSX or Linux.

D. Dempster-Shafer Approaches

Dempster-Shafer theory [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], also known as the theory of evidence or the theory of belief functions, was developed by Glenn Shafer in 1975 after the work made by Arthur P. Dempster. Beliefs in a hypothesis are calculated as the sum of the masses of all sets it encloses. It is often presented as a generalization of the probability theory. Briefly, it allows combining evidence from different sources and arriving at a degree of belief (represented by a belief function) that takes into account all the available evidence.

Regarding ontology, it has been yet most applied in areas such as inconsistency handling in OWL ontologies and ontology mapping ( [START_REF] Nagy | Uncertain Reasoning for Creating Ontology Mapping on the Semantic Web[END_REF] and [START_REF] Ben | OWL-CM: OWL Combining Matcher based on Belief Functions Theory[END_REF]). These areas start from the hypothesis that ontologies do not handle uncertainty, but produce uncertainty when grouping together a set of ontologies. However, one could notice that very recently a new approach [START_REF] Essaid | BeliefOWL: An Evidential Representation in OWL Ontology[END_REF] has been presented, which does not deal with ontology mapping or inconsistencies; it focuses rather on translating an OWL taxonomy into a directed evidential network based on the evidence theory. However, it deals only with classes and none open source tool is yet being available to test it.

III. MODELING AND REASONING ON DEMPSTER-SHAFER THEORY

We are now going to introduce the obvious advantages of the theory of belief functions that lead us to seek a tool, which implements this theory. However, following this brief state of art, there is currently and to our knowledge no available tool based on Dempster-Shafer theory that meets our purposes that is to say to represent and reason about the uncertainty contained in our data/information.

A. Advantages of Dempster-Shafer Theory

Inside the theory of uncertainty representation, we encountered an important difficulty when trying these tools in regards to the type of knowledge available in input of data fusion applications. As a matter of fact, the representation of information absence is badly taken into account by the theory of probability. Indeed, prior and conditional probabilities need to be specified into probabilistic methods. This requirement often lead in using a symmetry (minimax error) argument to assign prior probabilities to random variables (e.g. assigning 0.5 to binary values for which no information is available about which is more likely). However, any information contained in the missing priors and conditionals is not used in the Dempster-Shafer framework unless it can be obtained indirectly -and arguably is then available for calculation using Bayes equations.

One of the major advantages of Dempster-Shafer theory over probability theory is thus to allow one to specify a degree of ignorance in a situation instead of being forced to supply prior probabilities. This ability to explicitly model the degree of ignorance makes the theory very appealing. Moreover, probabilistic approaches reason only on singletons. On the contrary, Dempster-Shafer theory enables us not only to affect belief on elementary hypotheses but also on composite ones. This last point illustrates the fact that Dempster-Shafer theory manages also imprecision and inaccuracies.

In addition, there is in the theory of Probabilities, a strong relation between an event and its negation, since its sum equals to 1. The evidence theory implies no relations between the existence or not of an event. Thus it models only the belief associated to a class, without influencing the belief allots to others classes.

Lastly the evidence combination rule of the Dempster-Shafer theory provides an interesting operator to integrate multiple pieces of information from different sources. Thus it is very helpful when working on pieces of information that come from various sources, as in Data Fusion applications. Finally, decision on the optimal hypothesis choice can be made in a flexible and rational manner.

To that point of view, the evidence theory is much more flexible than the probability theory. It permits to manage as well uncertainties as the inaccuracies and the ignorance.

B. Ontological Representation

In order to represent the uncertainty contained in ontologies, it appears natural that it should be the instances that embody uncertainty. Indeed, in traditional ontology languages (as in object programming languages) the instances represent "real" world entities, which are a specific example of the structure defined by concepts or classes.

1) Use case

The use case is placed at the first level of the JDL and it supposes that we have already built an ontology of a military battlefield. We want to instantiate this ontology with different pieces of information that come from various sensors and that capture some data/information directly from the battlefield of interest. However, frequently these sensors convey contradictory pieces of information. Moreover, these sensors can be given a certain degree of confidence and thus lead to the assessment of the mass value associated to each observation. Even if in evidence theory, the determination of mass functions is a crucial step, it is not our purpose here and this matter will not be handled in this paper.

For example, sensor A and B observe the same moving entity which moves towards a specific direction. Sensor A grants the confidence of 0.4 that this entity is a military tank with characteristics i and the one of 0.6 that it embodies either a tank with characteristics i or with characteristics j. But sensor B has observed with a 0.5 confidence that it is a tank with characteristics i. It grants 0.2 of its confidence to the fact that it is a military truck and 0.3 to its total ignorance.

In terms of instances, also called individuals or objects, sensor A and B would lead to the creation of two instances of the same concept Military_Tank that have, for example, the object property hasCharacteristics linked to different instances (related to characteristics i and j) and to the instantiation of concept Military_Truck.

According to the Dempster-Shafer formalism, Ω which is the universal set, that is to say, the set of all states under consideration will be defined in this case by Ω = { tank_i, tank_j, truck }. Hereafter is given the assignment of the belief masses according to sensor A and B to their observations: m A ({tank_i}) = 0.4 ; m A ({tank_i, tank_j}) = 0.6 m B ({tank_i}) = 0.5 ; m B ({truck}) = 0.2 ; m B ({tank_i, tank_j, truck}) = 0.3 This use case is situated at the first level of the JDL model, but it could have also presented some situation where we handle uncertainty in higher level as presented in the introduction of this paper.

2) Model

We modeled a Dempster-Shafer ontology that can be merged with any ontology and that enables us to instantiate its concepts in an uncertain manner.

This ontology is what we call an upper ontology, since one can use it in every area of knowledge, in other words it is non domain specific. It is a formal representation of the theory of Dempster-Shafer, as it proposes a shared understanding of the main concepts: mass, belief, plausibility, source, etc. The following figure illustrates the global structure of this ontology called DS-Ontology, in regards of the different classes, hierarchical relations (has subclass) and object/datatype properties (dotted arrows). The Uncertain_concept is here to represent a concept that we want to instantiate in our domain ontology but it can refer to different classes, since sources convey different observations. This class (to be precise: its instance) gathers all the different individuals of our domain ontology it can embody thanks to the object property: is_either. One can note therefore that this property has for range the class: owl:Thing which is the root of all the classes, in order to accept all possible instances. For example, in the use case above, there would be only one instance of Uncertain_concept, linked to the three previously mentioned instances. The universal set whose definition is the set of all states under consideration is actually given by the list of instances linked to a specific instance of Uncertain_concept.

There is one DS_concept instance associated to each hypothesis, or composite hypotheses, thanks to the object property DS_relation. A DS_concept has datatype property: DS_source, which cardinality equals to 1. In other words, for each DS_concept, there is one DS_source associated. We proposed here to symbolize the source by a string (source "A", for instance). Then it also has the following properties: DS_mass, DS_belief and DS_plausibility, which have for value a double, which is implicitly ranging from 0 to 1. If we recall our initial use case for sensor A when dealing with the composite hypotheses {tank_i, tank_j}, the two instances of military tank will point to the same DS_concept object which has for DS_source: A and we assume for DS_mass: 0.6. A unique DS_concept will be linked with DS_relation to more or less instances according to the imprecision handled by the sensor.

Finally, we can finish filling in our domain ontology with instances that are not uncertain by the classical method, or when a certain instance is being involved in a relation that has for domain or range an uncertain concept, we bind it to the adequate instance of Uncertain_concept.

The following figure gives an outline of the instances that could be created regarding the initial use case. To recap briefly: when we want to reason about an uncertain concept, we instantiate all the possible classes that this concept can embody and we link them with a specific instance of Uncertain_concept thanks to the relation: is_either. Then, we associate them to a DS_concept (thanks to DS_relation) and we can here declare which is the source that has made this observation and what is the value of mass, the belief or credibility that is associated to it.

C. Reasoning on uncertain ontological aspects

Once having a unique general representation of Dempster-Shafer for any field, it has been quite easy to implement a Java application based on Jena framework that enables us to reason automatically about the uncertain objects contained in the ontology. Jena is an open source Java framework for building Semantic Web applications. It provides indeed a programmatic environment for RDF, RDFS and OWL, SPARQL and includes a rule-based inference engine. In our application, the Jena framework is a tool to retrieve the instances associated to each individual uncertain concept, and the Dempster-Shafer information collected. This information is then transmitted to a common basic Dempster-Shafer library [START_REF]Open source Java Dempster-Shafer library developed[END_REF] which then performs calculations in the Dempster-Shafer theory. In other words, our Java application first maps our ontology-based annotation (the set of related instances, for example those represented in Figure 3), written in OWL, into a Java representation of the Dempster-Shafer theory (according here to the Java library of [START_REF]Open source Java Dempster-Shafer library developed[END_REF]). Then this library enables us to manipulate the numerical values (mass, credibility, plausibility) which were previously contained in the annotation in order to perform classical calculations (conjunctive/disjunctive combination, conditioning, pignistic transformation, several uncertainty measures). As a matter of fact, our application calculates K, which represents the measure of the amount of conflict between mass sets. According to the value of K, we combine evidence from different sources, i.e. we combine the independent sets of mass assignments, thanks to Dempster's rule of combination. Finally, decision criteria can be applied to extract the chosen hypothesis, either based on the maximum of plausibility or belief function or either on pignistic probability criteria, etc. in regards to the type of problem handled.

As a consequence, the application creates a mapping between ontology representation and the Dempster-Shafer model which enables to reason about uncertainty in ontology.

D. Advantages, limits and future work

For the moment, we have a simple mechanism to instantiate our domain ontology in an uncertain manner by importing the Dempster-Shafer ontology.

The advantage of this method is that one can come with any domain ontology and instantiate it, without making any change in this ontology. This is mostly due to the fact that OWL is a structured language but flexible enough to overcome the strict definition of properties which restricts the value of the range or domain to some given classes. What we mean is that without this flexibility, we would have to modify slightly the original ontology during the last phase of instantiation of certain classes in relation to instance of uncertain concept. Indeed, it would be impossible to link a property to an instance of Uncertain_concept (in the role of range or domain) since this class does not appear in the property definition in the domain ontology. Therefore we would have to add that the relation can accept for domain (or for range) an instance of Uncertain_concept. However, even if this is accepted by the syntax, it lowers naturally a little the expressivity of the ontology.

Future work can carry about the representation of uncertainty within relations (between concepts or between a concept and data value) in ontology.

Moreover, in a near future, we are also interested in using some reasoning capabilities of OWL language instead of simply use the ontology as a mean to represent the observations (observed entity and mass value, belief and/or plausibility associated to it) carried out by independent sources. As a matter of fact, OWL enables us, for example, to link resources which are instances of equivalent concepts defined under different labels ("owl:equivalentClass") or to reference a single individual using different names ("owl:sameAs"). Sources can thus use different ways to refer to identical resources. Therefore it would be conceivable to take them into account while applying the Dempster's rule of combination when these specific OWL properties are met in the domain ontology. In the same way, we could also enlarge this reasoning to the taxonomy of the ontology, by including the notion of semantic distance between two concepts. Indeed, two entities observed by different sources that are quite similar in nature (i.e. "closed" in the taxonomy) should have their belief augmented in comparison to a single entity observed, which is far from the others. Further work is needed in that field but a rule language (e.g. Jena rules [START_REF] Mcbride | A Semantic Web Toolkit[END_REF], SWRL [START_REF] Horrocks | SWRL: A semantic web rule language combining OWL and RuleML[END_REF], RIF [START_REF] Kifer | Rule Interchange Format: The Framework[END_REF], etc.) could be used in order to perform those changes of mass values.

For other purposes, it could also be imagined that the application, which has an uncertain ontology for input, returns a non uncertain ontology, i.e. a traditional ontology, which would be the result of the Dempster's rule of combination, followed by a decision process on single hypothesis. However, for Data Fusion applications, it is preferable to keep this representation of uncertainty.

IV. CONCLUSION

To conclude, let's remind that Data Fusion is the art of managing many pieces of information that are imperfect in multiple ways and to provide at the end a clearer view of the situation, that is to say less uncertain. Therefore there is currently a serious deficiency in ontological capacities. Thus, we have seen that uncertainty extension to OWL has started to make great strides in the last few years. We have proposed in this paper a simple approach to address the problem of representing uncertainty, based on the evidential approach. We have presented a mechanism to instantiate our domain ontology thanks to the DS-Ontology. The advantage of this method is that one can come with any domain ontology and instantiate it in an uncertain manner, without making any change in the domain ontology.

Figure 2 .

 2 Figure 2. DS-Ontology structure To import this DS-Ontology.owl file within a specific domain ontology, we use the owl:imports statement, such as: <owl:imports rdf:resource="DS-Ontology.owl"/>.

Figure 3 .

 3 Figure 3. Instances example

further details on: http://www.w3.org/2005/Incubator/urw3/

ACKNOWLEDGMENT

We are grateful to Arnaud Saval and Khaled Khelif for their comments and hope that the revised paper has addressed their concerns.


Philippe Thomas
email: philippe.thomas@cran.uhp-nancy.fr

André Thomas
email: andre.thomas@cran.uhp-nancy.fr

Sana Belmokhtar
email: sana.belmokhtar@cran.uhp-nancy.fr

Petri net control of a kanban loop *

Keywords: Kanban, Petri net, gradient, just in time

Just in Time (JIT) is a management philosophy that favorates improvement through inventory reduction by producing only the right quantity at the right time. A kanban system is an important element of JIT philosophy. However, whereas kanban system is suitable when demand is stable, it should to be adjusted when demand is a significantly variable to be efficient. In addition, some works have proved that Petri nets are useful to model a kanban loop. Then, the objective of the present work is to exploit the analytical relation of Petri net models in order to improve the control of kanban system by using the real data provided by the system or by the product. This approach is based on the use of a continuous approximation of a discrete Petri net model in order to exploit a strategy of command based on gradient descent. In the present paper, two continuous approximations are proposed and compared.

Introduction

The Just in Time (JIT) philosophy has appeared during the seventies in Japan [START_REF] Di Mascolo | A Unified Modeling of Kanban Systems Using Petri Nets[END_REF], [START_REF] Mohanty | Expert Enhanced Coloured Fuzzy Petri Net Models of Traditional, Flexible and Reconfigurable Kanban System[END_REF], [START_REF] Sugimori | Toyota Production System Materialization of Just-intime and Respect-for-human System[END_REF]. In a JIT system, a good is produced with the right quantity at the right time [START_REF] Beranger | Les Nouvelles Règles de la Production[END_REF]. In order to drive a JIT system, a kanban system is needed. Kanban means card in Japanese. In a kanban system, cards are used systematically to control the production within stations and the movement of parts between stations. A kanban card is attached to each product (or to each batch). Then, consumption of one product (or batch) frees the kanban card which can be attached to a new product (or batch) to product. This release of kanban card leads to a new manufacturing order. The kanban system is a pull control system, which can be represented by using stage notion [START_REF] Di Mascolo | A Unified Modeling of Kanban Systems Using Petri Nets[END_REF]. Pull systems are most successful in production environments with stable demand and lead time [START_REF] Tardif | An Adaptive Approach to Controlling Kanban Systems[END_REF]. In this case, a kanban system uses a constant number of cards which can be allocated to a product (or batch) or free. In an instable environment (high variation of demand), such a system is inefficient in such context leading to modifying and adjusting its parameters to avoid starving or high stock level. Usually, two approaches can be used. First, the number of kanban cards present in the system may be adjusted. Second, the number of products associated to a kanban card may be modified. This is an adaptive kanban system [START_REF] Shahabudeen | Algorithm for the Design of Single-stage Adaptive Kanban System[END_REF], [START_REF] Tardif | An Adaptive Approach to Controlling Kanban Systems[END_REF].

Petri nets (PN) are useful for the discrete event systems (DES) and hybrid systems (HS) modelling [START_REF] Cassandras | Discret Event Systems: Modeling and Performance Analysis[END_REF], [START_REF] Lefebvre | Parameters estimation for timed and continuous Petri nets: application to the identification and monitoring of hybrid systems[END_REF], [START_REF] Zaytoon | Hybrid dynamical Systems[END_REF] because they combine, in a comprehensive way, intuitive graphical representations and powerful analytic expressions [START_REF] Brams | Réseaux de Petri[END_REF], [START_REF] Brauer | Petri Nets: Central Models and their Properties[END_REF], [START_REF] Murata | Petri Nets: Properties, Analysis and Application[END_REF]. A lot of results have been established for the control of the DES or HS. The modelling of kanban system is one of the applications of the PN theory. In fact, numerous models of kanban systems by using PN [START_REF] Jain | Performance Modelling of FMS with Flexible Process Plans -A Petri Net Approach[END_REF], timed Petri nets [START_REF] Bohez | A new Generic Timed Petri Net Model for Design and Performance Analysis of a Dual Kanban FMS[END_REF], [START_REF] Di Mascolo | A Unified Modeling of Kanban Systems Using Petri Nets[END_REF], [START_REF] Giua | Firing Rate Optimization of Cyclic Event Graphs by Token Allocations[END_REF], [START_REF] Panayiotou | Optimization of Kanban-based Manufacturing Systems[END_REF], [START_REF] Seeluangsawat | Integration of JIT Flexible Manufacturing, Assembly and Disassembly System using Petri Net Approach[END_REF], stochastic Petri nets [START_REF] Nakashima | Performance Evaluation of a Supplier Management System with Stochastic Variability[END_REF] or coloured Petri nets [START_REF] Desrochers | A Supply Chain Model Using Complex-Valued Token Petri Nets[END_REF], [START_REF] Mohanty | Expert Enhanced Coloured Fuzzy Petri Net Models of Traditional, Flexible and Reconfigurable Kanban System[END_REF], [START_REF] Moore | Stochastic Coloured Petri Net (SCPN) Models of Traditional and Flexible Kanban Systems[END_REF], [START_REF] Ullah | A Petri Net Model for Sequence Optimization and Performance Analysis of Flexible Assembly Systems[END_REF] have been proposed. When the dynamics of a physical system are numerous, the corresponding discrete PN (PN, TPN, CPN) model has too many marks which lead to a high complexity. Thus, David and Alla [START_REF] David | Petri Nets and Grafcet -Tools for Modelling Discrete Events Systems[END_REF] have proposed to use continuous Petri nets with variable speed (VCPN). Moreover, they have proposed some methods of transformation of TPN into VCPN. A lot of results have been established with VCPN for the control of system [START_REF] Amrah | Constrained State Feedback Control of a Class of Discrete Event Systems Modelled by Continuous Petri Nets[END_REF], [START_REF] Ghabri | Sur la Modélisation et la Commande des Systèmes Flexibles de Production[END_REF], [START_REF] Hanzalek | Continuous Petri Nets and Polytopes[END_REF], [START_REF] Lefebvre | Commande des flux dans les réseaux de Petri continus par propagation du gradient[END_REF], [START_REF] Silva | On Fluidification of Petri Nets: from Discrete to Hybrid and Continuous models[END_REF]. This approach appears as an interesting alternative to the discrete control of DES [START_REF] Lefebvre | Identification par phase des fréquences maximales de franchissement dans les réseaux de Pétri continus à vitesse variable[END_REF].

The main contribution of this work is to propose and compare two VCPN approximation models of a TPN model of a kanban system. The use of VCPN approximations allows using control methods of VCPN. A gradient based controller for continuous Petri nets [START_REF] Lefebvre | Commande des flux dans les réseaux de Petri continus par propagation du gradient[END_REF] is used in order to control the flows of products in the system. Now, the Petri nets theory is resumed by focusing on TPN and VCPN and the definition of notations is performed. In a third part, the TPN model of a kanban system used as reference is recalled and two VCPN approximations of this model are proposed. In the next part, we present the gradient based controller strategy used in the part five where the results are presented before to conclude.

Petri nets

A Petri net (PN) with n places and p transitions is defined as < P, T, Pre, Post, M 0 > where P={P i } i=1,…,n is a not empty finite set of places, T={T j } j=1,…,p is a not empty finite set of transitions, such that P ∩ T = ∅ [START_REF] Brams | Réseaux de Petri[END_REF], [START_REF] Murata | Petri Nets: Properties, Analysis and Application[END_REF]. IN is the set of integer numbers. Pre: P × T → IN is the pre-incidence application: Pre (P i , T j ) is the weight of the arc from place P i to transition T j and

W PR = ( w PR ij ) i=1,…,n, j=1,…,p ∈ IN n × p with w PR ij = Pre (P i , T j )
is the pre-incidence matrix. Post: P × T → IN is the post-incidence application: Post (P i , T j ) is the weight of the arc from transition T j to place P i and

W PO = ( w PO ij ) i=1,…,n, j=1,…,p ∈ IN n × p with w PO ij = Post (P i , T j ) is the post-incidence matrix. The PN incidence matrix W is defined as W = W PO -W PR ∈ IN n × p . Let us also define M = (m i ) i=1,…,n ∈ IN n
as the marking vector and M 0 ∈ IN n as the initial marking vector. °Tj (resp T j ° ) stands for the pre-set (resp. post-set) places of T j . A firing sequence is an ordered set of transitions that are successively fired from marking M to marking M'. Such a sequence is represented by its characteristic vector X = (x j ) j=1,…,p ∈ IN p where x j stands for the number of T j firings. The marking M' is related to the marking M and to the firing sequence X according to:

M' = M + W.X (1)
In autonomous PN without conflict, the enabling degree of each transition T j , related to the marking M, is given by: min

i j i j PR P T ij m x fix w ∈°      =           (2)
where fix(.) stands for the integer part of (.).

Timed Petri nets TPN

Two types of timed Petri nets occur, T-timed and P-timed Petri nets [START_REF] David | Petri Nets and Grafcet -Tools for Modelling Discrete Events Systems[END_REF]. Here, only the T-timed Petri nets (TPN) are considered. A TPN is defined as < PN, Tempo > such as PN is an ordinary Petri net as defined above and Tempo is an application from the set T of transitions into IR + . Tempo (T j ) = d j is the temporization associated to the transition T j .

Continuous Petri nets VCPN

Continuous PN are a particular class of timed PN, deduced from TPN [START_REF] Ramchandani | Analysis of Asynchronous Concurrent Systems by Timed Petri nets[END_REF] to provide a continuous approximation of the system behaviour [START_REF] David | Petri Nets and Grafcet -Tools for Modelling Discrete Events Systems[END_REF]. A continuous PN with n places and p transitions is defined as < PN, X max > where PN is a Petri net and X max = (x max j ) j=1,…,p ∈ IR + p is the vector of maximal firing frequencies with IR + the set of non-negative real numbers. The marking m i (t) of each place P i , i = 1,…,n, at time t has a non-negative real value and each transition firing is a continuous flow in continuous PN. In fact, the transition T j is fired with a frequency x j (t) less than the maximal frequency x max j . Let us define X(t) = (x j (t)) j=1,…,p ∈ IR + p as the firing frequencies vector at time t. The marking evolution is given by the differential system (3):

) t ( X . W dt dM(t) = (3)
Among the existing models of continuous PN, continuous PN with variable speeds (VCPN) are proved to give good approximations of TPN [START_REF] David | Petri Nets and Grafcet -Tools for Modelling Discrete Events Systems[END_REF]. Components of the marking vector are continuous functions of the time; components of the firing frequencies vector X(t) depend continuously on the marking of the places according to:

( ) max ( ) . ( ) ( ) min ( ) i j j j j j i P T x t x t where t m t µ µ ∈°= = (4)
A self loop is usually associated to each transition T j in order to limit the number of simultaneous firings.

Piecewise linear state space representation for VCPN

Due to the commutation function « min » and to the products between marking vector and maximal firing frequencies vector in (4), VCPN models are not linear but piecewise linear systems [START_REF] Amrah | Constrained State Feedback Control of a Class of Discrete Event Systems Modelled by Continuous Petri Nets[END_REF], [START_REF] Lefebvre | Source and sink transitions controllers for continuous Petri nets: a gradient -based approach[END_REF], [START_REF] Lefebvre | Commande des flux dans les réseaux de Petri continus par propagation du gradient[END_REF]. In order to bring VCPN models in the usual state space representation, let us introduce U(t) ∈ IR + d as the VCPN input vector at time t and Y(t) ∈ IR + q as the VCPN output vector at same instant. The input vector U(t) is defined as the maximal firing frequencies of some transitions. For this purpose, the set of transitions T is divided into 2 disjoint subsets T C , and T NC such that T = T C ∪ T NC . T C is the subset of the controllable transitions, and T NC is the uncontrollable transitions subset. As a consequence, let us define

X C (t) = ( x j (t) ) Tj∈TC ∈ IR +d and X NC (t) = (x j (t)) Tj ∈ TNC ∈ IR +p-d according to: 1 ( ) . ( ) ( ) C NC X t D X t X t -   =     (5)
with D ∈ IR p x p a suitable permutation matrix (i.e. D is the matrix of a bijective mapping from T to T that clusters the set of transitions into controllable and uncontrollable ones). The controllable inputs vector U(t) = X max C (t) ∈ IR +d corresponds to the maximal firing frequencies of the transitions to be controlled. The input vector is constrained 0 ≤ U(t) ≤ U max in order to limit the firing frequencies in a non negative bounded interval. The uncontrollable maximal firing frequencies X max NC are supposed to be constant according to the VCPN models. The output vector Y(t) = Q.M(t) ∈ IR +e is composed of a selection of subnets marking that are observable. For this purpose, let us define Q = (q ki ) k=1,…,e ,i=1,…,n ∈ IR e × n as a positive observation matrix (i.e. Q is the matrix of a constant projector, each row corresponds to a positive weighted sum of the PN places marking). The goal of the controller is to drive Y(t) according to some reference trajectories in the output space. Equation (3) can be rewritten as:

( ) . ( ) . ( ) ( ) . ( ) NC NC C C dM t W X t W X t Y t Q M t dt = + = (6)
with

W C = (w C ij ) i=1,…,n, j=1,…,d ∈ IR n × d and W NC = (w NC ij ) i=1,…,n, j=1,…,p-d ∈ IR n × (p-d) such that (W C | W NC ) = W.D.
Several phases occur in the VCPN behaviour. Each phase ϕ is active between two successive commutations of the "min" operators in (4) and corresponds to a particular configuration of these operators characterised by the p clustering functions f j :

{ } : 1,..., ( ) ( ( )) such as ( ) ( ) n j j j f j f n M t f M t m t t µ + → → = ℝ (7)
Each function f j specifies the place in the preset of T j which has the minimal marking. During each phase ϕ, a constant relationship between the components of vectors X C (t) and M(t) and also between X NC (t) and M(t) occurs. This relation can be expressed under scalar form by using the functions f j or under vectorial form by using the set of vectors A j (ϕ )∈ {0,1} 1 × n and B j (ϕ )∈ {0,1}

ϕ ϕ = = = = - (8)
Equation ( 6) can be rewritten under vectorial form:

max 1 1 ( ) ( ). . ( ) . . ( ) . ( ) ( ) . ( ), 1, 2,... j j j p d d j C j NC NC j j j dM t u t W A x W B M t Y t Q M t dt ϕ ϕ ϕ - = =   = + = =     ∑ ∑ (9)
where W Cj denotes the j th column of matrix W C and W NCj denotes the j th column of matrix W NC . Equations ( 9) is piecewise bilinear representation of the VCPN (2). Each phase is characterised by a set of matrices W Cj .A j (ϕ )∈ IN n × n associated to the controllable transitions and W NCj .B j (ϕ)∈ IN n × n associated to the uncontrollable ones.

Petri net models of kanban systems

As shown in the introduction, a lot of models of kanban systems based on Petri nets have been proposed. In the proposed work, a TPN model initially presented in [START_REF] Di Mascolo | A Unified Modeling of Kanban Systems Using Petri Nets[END_REF] has been particularly studied because of its simplicity and its modularity. It can be noticed that the proposed approach can be applied to any model based on TPN and even to those based on CPN since an equivalent TPN could always be built. The considered kanban system has the following characteristics: each stage consists only of a single facility comprising one or more identical machines; each stage has, at most, one preceding stage and one succeeding stage; the manufacturing system produces only one type of part; the size of all kanbans is the same and is taken to be equal to one; when a kanban is removed from a part consumed by the downstream stage, it is immediately available to be attached to a part of the upstream stage. Fig. 1. Links between different stages In a kanban system, the production system is decomposed in stages. Figure 1 presents the kanban system mechanism at the stage i and shows the flow (of parts and of kanban cards) between the stages i-1, i and i+1. This system is modeled by [START_REF] Di Mascolo | A Unified Modeling of Kanban Systems Using Petri Nets[END_REF] by using the TPN model shown figure 2. When the stage i is considered (figure 1), each kanban card can be in three different states: free and waiting to be attached to a new part of stage i-1, or attached to a part that is in manufacturing process, attached to a finished part that is in the output buffer. So, these three states are represented by three places denoted respectively F i , I i and O i . The number of tokens in place I i represents the number of parts in the manufacturing process. The number of tokens in place O i represents the number of parts in the output buffer when the number of tokens in F i represents the number of free kanban cards.

The number of tokens in the place N i represents the number of identical machines of stage i. The transition T i between the places I i and O i is a timed transition. Its delay d i corresponds to the processing time. The transition τ i represents the synchronization between stages i and i+1. This transition is an immediate transition. The TPN shown figure 2 corresponds to the case where the demand and the supply are supposed infinite. Di Mascolo et al. [START_REF] Di Mascolo | A Unified Modeling of Kanban Systems Using Petri Nets[END_REF] have proposed some variations of this initial model in order to take into account, not infinite supply, or lost demands as examples. This paper focuses only on this first model.

F 1 I 1 O 1 N 1 T 1 d 1 τ τ τ τ 0 F 2 I 2 O 2 N 2 T 2 d 2 τ τ τ τ 1 τ τ τ τ 2
Fig. 2. TPN model for a two-stage kanban system

The goal of this work is to drive the considered kanban system by using its PN model and a control algorithm of the VCPN. So, a VCPN approximation of the TPN model shown figure 2 must be constructed. The transformation of a TPN into a VCPN is always feasible, but some modification must be applied to the model [START_REF] David | Petri Nets and Grafcet -Tools for Modelling Discrete Events Systems[END_REF].

In order to do that, these different transformations must be applied: the discrete marking of places must be replaced by continuous marking; the delays associated to transitions of the TPN are used in order to determine the maximal speeds of firing of VCPN transitions. The maximal speeds of firing of the transitions are then obtained by using the relation:

max 1 i i x d = ( 10
)
To do that, the main difficulty is the immediate transitions τ 0 , τ 1 and τ 2 of the TPN (figure 2). In fact, these transitions have a null delay which leads to a maximal firing speed of transition infinite. To solve this problem, two approaches can be used. The first one is to consider these immediate transitions as timed transitions but with a short delay comparing with the other dynamics of the system. This approach leads to the VCPN model shown figure 3. The resulting model is called here the complete VCPN model. The transitions T 1 , T 3 and T 5 corresponds to the immediate transitions of the TPN (figure 2), and so, have a great maximal firing speed. The firing speeds T 2 and T 4 correspond to the processing speeds of the two stages. The marking of places N 2 and N 4 correspond to the number of machines constituting the two stages. The second approach is to consider that, because τ 0 , τ 1 and τ 2 are immediate transitions of the TPN, each token in place O i implies that transition τ i is immediately fired and the considered token is driven in the place I i+1 . So it is possible to aggregate these two places O i and I i+1 in order to preserve uniquely the timed transitions. This approach leads to the VCPN model shown figure 4 which is called reduced VCPN model. These two approaches will be compared in the part 5. It can be noticed that, in this reduced model, the processing of a part needs that some tokens are present in place F corresponding to free kanban cards. This fact is the main limitation of this model. However, because the main objective is to determine how many kanban cards must be introduced in the real system, the number of kanban cards must be oversized in order to allow the introduction of new cards. So, this limitation is not problematic.

Control design for VCPN

Flow control for VCPN was investigated by several authors [START_REF] Amrah | Constrained State Feedback Control of a Class of Discrete Event Systems Modelled by Continuous Petri Nets[END_REF], [START_REF] Ghabri | Sur la Modélisation et la Commande des Systèmes Flexibles de Production[END_REF], [START_REF] Hanzalek | Continuous Petri Nets and Polytopes[END_REF], [START_REF] Lefebvre | Identification par phase des fréquences maximales de franchissement dans les réseaux de Pétri continus à vitesse variable[END_REF], [START_REF] Lefebvre | Source and sink transitions controllers for continuous Petri nets: a gradient -based approach[END_REF], [START_REF] Lefebvre | Commande des flux dans les réseaux de Petri continus par propagation du gradient[END_REF], [START_REF] Silva | On Fluidification of Petri Nets: from Discrete to Hybrid and Continuous models[END_REF]. The control algorithm used here is those proposed by Lefebvre et al. [START_REF] Lefebvre | Source and sink transitions controllers for continuous Petri nets: a gradient -based approach[END_REF] which is inspired from the learning algorithm of the neural networks. This approach takes advantage of the gradient propagation through the PN nodes in order to minimise the square of instantaneous error between desired and measured outputs by modifying the maximal firing frequencies of controllable transitions. Gradient algorithms perform the minimisation of a scalar cost function that evaluates the distance between the desired output Y d (t) and the system output Y(t). Let us assume that measures of the desired output are obtained with a sampling period ∆t during the time horizon H. As a consequence, the proposed controllers will be worked out in discrete time. This algorithm is now summary.

Gradient based controller

For seek of simplicity, let us first consider the single output case. The instantaneous error is defined as

ε(k) = y d (k) -y(k)
, where y d (k) stands for the desired output at time t = k.∆t, and y(k) stands for the marking of the VCPN output y at time t = k.∆t obtained from the marking M(k-1) and the input vector U(k-1) according to a first order numerical method:

max 1 1 ( ) ( 1)
.(

. . . ( ) . . . ( )). ( 1) 0

j j j p d d j C j NC NC j j j y k y k t u k Q W A x Q W B M k k ϕ ϕ - = = = -+ ∆ - + - > ∑ ∑ (11)
Let us consider the scalar cost function v(k):

2 1 ( ) ( ) 2 v k k ε = ∈ ℝ (12)
Gradient-based methods result from the Taylor series expansion of the cost function v(k) in order to work out the optimal value of the input vector U(k). Second order terms are usually neglected in evaluation of hessian matrix, but an adaptive term λ.I is added in order to approximate the inverse of the hessian matrix when it is not regular or badly conditioned. Thus, the actualisation of the control input is given by: 1

( ) ( ( ). ( ) . ) . ( ). ( ), 0

T U k S k S k I S k k k δ λ ε - = - + ≥ (13) with ( ) ( ) ( 1) U k U k U k δ = - -. ( ) d
S k ∈ ℝ is the gradient of the output y with respect to the input vector U, calculated at time . t k t = ∆ . When λ is great, the algorithm works as a gradient method. On the contrary, when λ is small, the algorithm works as a hessian method which is faster but may be instable. Different methods can be used to tuned λ [START_REF] Lefebvre | Parameters estimation for timed and continuous Petri nets: application to the identification and monitoring of hybrid systems[END_REF]. Here, λ is tuned to 1 which corresponds to hessian comportment.

The previous controller can be generalised in the multi-outputs case, by considering the scalar cost function:

2 1 1 ( ) ( ) 2 e v k k α α ε = = ∈ ∑ ℝ (14)
that results in the following updating rule for the controller:

( ) ( ( ). ( ) . ) . ( ( ). ( )

e e T U k S k S k I S k k α α α α α α δ λ ε - = =     = - +         ∑ ∑ (15) where ( ) d S k
α ∈ ℝ is the gradient of the output y α considering the variations of the input vector U, calculated at time . t k t = ∆ . In order to converge quickly to the minimum of the cost function, the learning algorithms based on the steepest descent of the gradient may be iterated several times on each sample [START_REF] Lefebvre | Commande des flux dans les réseaux de Petri continus par propagation du gradient[END_REF]. In order to use this algorithm the value of the gradient ( ) S k α used in (15) must be determined.

Gradient of the output

Gradient algorithms are based on the evaluation of sensitivity functions. Such functions are defined in continuous time for VCPN and will be worked out in discrete time according to the sampling period ∆t in order to be implemented in numerical controllers. Considering ( ) S k αγ the gradient of the output y α with respect to input u γ (the maximal firing frequency max c

x γ ). The gradient ( ) S k αγ is determined by using a first order method and the classification functions j f given by ( 7):

max 1 1 ( ) . . ( ) . . ( ) . j j p n i i ij f i j j s k q w k w x s k t αγ α γ γ γ γ δ µ = = ≠     = + ∆       ∑ ∑ (16)
where i q α is the cell of the i th line and α th column of the matrix Q.

( )

s k αγ δ
represents the variation of the gradient

( ) ( ) ( 1) s k s k s k αγ αγ αγ δ = -
-between times k-1 and k:

( ) ( ) ( 1)
(0) 0

s k s k s k s αγ αγ αγ αγ δ = - -    =   (17)

Example

Now, the control of the two-stage kanban system modelled thanks a TPN described figure 2 is investigated. As seen in part 3, two continuous approximations of this TPN has been built thanks VCPN theory. These two models called complete VCPN model and reduced VCPN model are described by figures 3 and 4. The incidence matrixes of these two VCPN are given by: 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1

T T complete reduced W W -     - -         = = - - - -       - -       -   (18)
For the two VCPN models, Transition T 1 represents the arrival of parts in the system. The marking of the places N i limit the number of simultaneous firing of the transitions. The output transitions (T 5 for the complete model and T 3 for the reduced one) represent the consumption of finished parts. In order to simulate this demand, the maximal firing frequency of these transitions ( x for the reduced one) is chosen equal to 2. The transitions T 2 and T 4 for the complete model and T 1 and T 2 for the reduced model allow to control the system. The command U(t) corresponds to the maximal firing frequencies of these transitions and it is constraint between 0 and 5. The transitions T 1 and T 3 of the complete VCPN model which correspond to the immediate transitions in TPN have a great maximal firing speeds comparing to the other dynamics of the system. Their maximal firing speeds are fixed to 10. Now the two VCPN models are completely defined. In order to control them, the objectives must be defined. The main objective of a kanban system is to supply the demand. In order to do that, the output buffer of the second stage should never be empty. So, for our VCPN models, this objective results in a constraint on the marking of the place which represent this buffer (O 2 for the complete model and O 2 I 3 for the reduced one). So the measured output y of our system is the marking of the place O 2 for the complete model and O 2 I 3 for the reduced one. This measured output must converge to the desired value y d = 1.2. In a first time, the initial marking M 0 is given by: ( ) ( )

0 0
1,1,1,1,1,0, 2, 0,3, 0,0 1,1,1, 2,3, 0, 0

complete reduced T T M M = = (19)
This marking corresponds to a system where all the kanban cards are associated to finished parts waiting to be consumed by the downstream system. The marking of the places F 1 and F 2 which correspond to the free kanban cards are both empty. The figures 7 show the marking of places F 1 and F 2 which represents the number of free kanban cards in the two stages. These figures show a great difference of behavior between the two models. In the Complete model, only 0.2 cards are free in the two stages when 0.68 and 1.8 cards are free in the reduced model after stabilization. This fact implies that the complete model stocks parts in the input buffer of the two stages I 1 and I 2 which explain the speed of convergence of this model. However, the complete model is less parsimonious that the reduced one. Now, a second set of initial conditions described by a second vector of initial marking is used:

( ) ( ) 01 01 1,1,1,1,1, 0, 0, 0,0, 2,3 1,1,1, 0, 0, 2,3 complete reduced T T M M = = (20)
This marking correspond to a system where all the kanban cards are free. The figures 8 show the marking of places corresponding to the output buffer. This figure shows that the goal of 1.2 tokens in places O 2 (complete) and O 2 I 3 (reduced) is reached with the two VCPN models and even quicker than in the preceding case. Now, the initial marking is again the marking M 0 defined by [START_REF] Moore | Stochastic Coloured Petri Net (SCPN) Models of Traditional and Flexible Kanban Systems[END_REF]. However, the demand is doubled at time 10. Figures 9 show the marking of places corresponding to the output buffer during the time. The variation of demand (demand is doubled at time 10) leads to a small variation of the marking of places O 2 (complete model) and O 2 I 3 (reduced model). However, the behavior of both models is different. In fact, for the complete model, the impact of variation of demand is mainly absorbed by consuming the stock of stage 1 (marking of place O 1 ). This leads to another variation of the marking of place O 2 at time 13. For the reduced model, the variation of demand is mainly absorbed by increasing the maximal firing speeds of the two transitions T 1 and T 2 .

Epilogue

A new approach of control of kanban system has been proposed based on Petri nets. A gradient based controller of VCPN model has been used and two VCPN models of kanban system have been compared on different experiences. From these different experiences, the main characteristics of the two models can be highlighted and resumed in table 1. The main advantages of complete model are speed and stability when the main advantages of reduced model are parsimony and adaptability. This work shows that this approach can be used in order to adapt automatically the number of kanban cards in function of the demand which can be related to the adaptive kanban approach. The control of the Petri net model determines the needed number of kanban cards in function of the demand. So, it can be used to perform a fast simulation of the kanban system by considering an evolution of the demand to determine whether some kanban cards must be introduced or removed from the kanban system. The perspectives of this work are to use this approach in order to design a real kanban system. Moreover, the use of a continuous approximation of a TPN model introduces some mistakes. Thus evaluation of the error performed during this approximation phase must be done. Furthermore, this method must be compared with concurrent methods of kanban system dimensioning.

2 Fig. 3 .

 23 Fig. 3. Complete VCPN model for a two-stage kanban system

Fig. 4 .

 4 Fig. 4. Reduced VCPN model for a two-stage kanban system

3Fig. 5 .Fig. 6 .Fig. 7 .

 567 Fig. 5. Measured marking of places O 1 and O 1 I 2 (dashed line) and places O 2 and O 2 I 3

2Fig. 8 .3Fig. 9 .

 89 Fig. 8. Measured marking of places O 1 and O 1 I 2 (dashed line) and places O 2 and O 2 I 3 (marking M 01 )

  1 × n which are constant during each phase but which may varied from one phase to another:

	( ) x t u t A ( ). ( ). ( ), C j j j M t j	1,... d	x	NC j	max t x ( )	NCj	. ( ). ( ), j B M t j	1,...	p d

Table 1

 1 Characteristics of the two models.

		Speed	Stability	Parsimony Adaptability
	Complete	++	+	--	+
	Reduced	+	-	++	+