Lucie Tsamba
email: lucie.tsamba@cstb.fr

Nicolas Cimetiere

Dominique Wolbert

Olivier Correc

Nicolas Cimetière

Pierre Le Cloirec

Body fluid analog chlorination: Application to the determination of disinfection byproduct formation kinetics in swimming pool water

Keywords:

come

Introduction

Because of its residual disinfection capacity, chlorine is used in most swimming pool water treatment processes to ensure a good microbiological water quality. However, the formation of irritating or potentially toxic chlorinated disinfection by-products (Cl-DBPs) by reaction of chlorine with organic matter has been highlighted by many studies in the last 40 years [START_REF] Beech | Estimated worst case trihalomethane body burden of a child using a swimming pool[END_REF][START_REF] Florentin | Health effects of disinfection byproducts in chlorinated swimming pools[END_REF][START_REF] Zwiener | Drowning in Disinfection Byproducts? Assessing Swimming Pool Water[END_REF]. Bathers and lifeguards are exposed to Cl-DBPs mainly through inhalation of volatile compounds or through dermal absorption [START_REF] Erdinger | Pathways of trihalomethane uptake in swimming pools[END_REF][START_REF] Lévesque | Evaluation of dermal and respiratory chloroform exposure in humans[END_REF]. The exposure assessment and prediction require a model for the formation and degradation kinetics of Cl-DBPs in swimming pool water.

One of the major difficulties lies in the complex composition of the pollution released by bathers in the pool. Both the nature and amount of these organic compounds depend on various parameters, such as water temperature or bathers hygiene [START_REF] Bessonneau | Determinants of chlorination byproducts in indoor swimming pools[END_REF][START_REF] Keuten | Definition and quantification of initial anthropogenic pollutant release in swimming pools[END_REF]. Few studies described the amount of Cl-DBPs generated by the particles or by the pharmaceutical and personal care products released by bathers in the pools [START_REF] Kim | Formation of disinfection by-products in chlorinated swimming pool water[END_REF]Manasfi et al., 2017a;[START_REF] Teo | Chemical contaminants in swimming pools: Occurrence, implications and control[END_REF]. Most studies addressing DBP precursors in swimming pool focused on the dissolved human pollution, which consists mainly of urine and sweat, so that its responsibility for the production of large amounts of Cl-DBPs has now been well established [START_REF] Bessonneau | Determinants of chlorination byproducts in indoor swimming pools[END_REF][START_REF] Hureiki | Chlorination studies of free and combined amino acids[END_REF][START_REF] Kim | Swimmers contribute to additional formation of N-nitrosamines in chlorinated pool water[END_REF].

A c c e p t e d m a n u s c r i p t

Moreover, many studies have focused on urine and sweat compositions and on the quantities released in swimming pools [START_REF] Putnam | Composition and concentrative properties of human urine[END_REF][START_REF] Who | Guidelines for safe recreational water[END_REF], leading to the formulation of Body Fluid Analogs (BFAs).

BFA solutions consist of the main components of human body fluids and they are mainly used to simulate the anthropogenic pollution in pilot-scale or bench-scale experiments. The most widely used composition has been suggested by [START_REF] Judd | The fate of chlorine and organic materials in swimming pools[END_REF]. This solution has the advantage to yield representative amounts of Cl-DBPs while involving only 7 components, namely urea, ammonia, creatinine, L-histidine, citric acid, uric acid and hippuric acid.

As the number of precursor molecules is limited to 7, a mechanistic approach can be considered, since it produces more reliable models. However, the chlorination kinetics and DBPs formation potentials of the BFA components have been unequally studied. Ammonia chlorination kinetics has been determined within the scope of the breakpoint chemistry [START_REF] Jafvert | Reaction scheme for the chlorination of ammoniacal water[END_REF]. Urea, which is known to be a urine component responsible for the formation of large amounts of trichloramine, has been widely studied since 1980, considering the health concerns raised by this DBP. Creatinine and L-histidine have been less studied but chlorination mechanisms have been proposed in the literature. The formation of chloroform and dichloroacetonitrile by L-histidine chlorination as well as the methylamine formation by creatinine chlorination have been explained [START_REF] Li | Comparison of THMs and HANs formation potential from the chlorination of free and combined histidine and glycine[END_REF][START_REF] Liu | Effects of preoxidation and adsorption on haloacetonitrile and trichloronitromethane formation during subsequent chlorination[END_REF][START_REF] Tachikawa | Occurrence and production of chloramines in the chlorination of creatinine in aqueous solution[END_REF]. Finally, only few have focused on citric, uric and hippuric acids. Citric acid has been reported to produce large amounts of chloroform, whereas uric acid chlorination seems to be responsible for the production of high cyanogen chloride quantities [START_REF] Larson | Chloroform and chlorophenol production by decarboxylation of natural acids during aqueous chlorination[END_REF][START_REF] Lian | Volatile Disinfection Byproducts Resulting from Chlorination of Uric Acid: Implications for Swimming Pools[END_REF]. The formation potentials of the BFA components have been addressed for specific DBPs by few studies. [START_REF] Kanan | Formation of disinfection by-products in indoor swimming pool water: The contribution from filling water natural organic matter and swimmer body fluids[END_REF] described the important molar yields of citric acid for chloroform, dichloroacetic acid and trichloroacetic acid. However, individual contributions taking concentrations of the BFA formulation into account have not been determined, and kinetical aspects have not been considered by Kanan and Karanfil.

A c c e p t e d m a n u s c r i p t

This article focuses on the formation of the main volatile DBPs in swimming pools (trihalomethanes and haloacetonitriles). Since bromination mechanisms of the BFA components remain largely unknown, this study focuses only on the formation of chlorinated-DBPs (chloroform and dichloroacetonitrile). Even if the brominated DBPs are more toxic and may be observed in fresh water or seawater pools (Manasfi et al., 2017b), their concentrations in most swimming pools are drastically lower than the Cl-DBPs concentrations.

Chloroform (TCM) and dichloroacetonitrile (DCAN) have been chosen as target molecules because of their different stabilities. Chloroform (TCM) is an ultimate, volatile and very stable Cl-DBP, which formation kinetics has been reported to be slow [START_REF] Arnold | Evaluation of Functional Groups Responsible for Chloroform Formation during Water Chlorination Using Compound Specific Isotope Analysis[END_REF][START_REF] Blatchley | Copper catalysis in chloroform formation during water chlorination[END_REF]. On the contrary, dichloroacetonitrile (DCAN) has been proven to degrade quickly through hydrolysis and through reaction with hypochlorite (Yu andReckhow, 2017, 2015).

This study identified the main precursors of TCM and DCAN within the BFA. The DBPs formation modeling was based on the specific chlorination study of the main precursors.

Literature data such as chlorination mechanisms were coupled with experimental data from this study in order to determine kinetic rate constants. The resulting models were validated by comparison with the data provided by BFA chlorination experiments. Modeling the DBPs formation kinetics is the first step allowing to predict DBPs occurrence in pool water and air.

Then the hydrodynamic parameters have to be taken into account to accurately predict concentration variations in water and air [START_REF] Judd | Disinfection by-product formation in swimming pool waters a simple mass balance[END_REF][START_REF] Peng | Occurrence and simulation of trihalomethanes in swimming pool water: A simple prediction method based on DOC and mass balance[END_REF][START_REF] Schmalz | Trichloramine in swimming pools -Formation and mass transfer[END_REF]. This method already predicted trichloramine occurrence in swimming pool water and air [START_REF] Gérardin | Modeling of variations in nitrogen trichloride concentration over time in swimming pool water[END_REF].

Materials and methods

Ultra pure water (UPW) produced by a ElgaPureLab System (resistivity 18.2 M.cm, TOC< 50 µg C/L) was used for the preparation of all solutions and dilutions.

BFA chlorination

A c c e p t e d m a n u s c r i p t

The BFA solution (Table 1) was freshly prepared according to Judd and Bullock composition the day before starting chlorination experiments. To overcome solubility difficulties, uric and hippuric acids were solubilized in approximately 20 mL of ultrapure water supplemented with 1 mL of a sodium hydroxide solution (5 mol/L). The pH of the final solution was adjusted to 7 with HCl.Sodium hypochlorite stock solutions (≈ 1 mol/L, Fisher Scientific) were regularly titrated iodometrically.

Chlorinated solutions were prepared in a 1 L volumetric flask by diluting the BFA mix or individual stock solutions in 50 mL of a 0.2 mol/L phosphate buffer (pH = 7.5 ± 0.1). Chlorine was added and the volume was adjusted to 1 L with ultrapure water. In the case of the BFA mix, the total organic carbon (TOC) concentration of the chlorinated solution reached 4 mg/L. The concentration of each BFA component in the final solution is indicated in Table 1. After chlorine addition, the solution was divided into a series of 60 mL amber glass bottles filled without headspace and placed in a 27°C ± 2°C thermostated bath. For contact times longer than 1000 hr, bottles were placed in a thermostated chamber at 27°C ± 1°C. All chlorination experiments are summarized in Appendix A. Since the kinetics and mechanism of ammonia chlorination was extensively reviewed [START_REF] Jafvert | Reaction scheme for the chlorination of ammoniacal water[END_REF][START_REF] Qiang | Determination of Monochloramine Formation Rate Constants with Stopped-Flow Spectrophotometry[END_REF][START_REF] Weil | Equilibrium Studies on N-Chloro Compounds. II. The Base Strength of N-Chloro Dialkylamines and of Monochloramine[END_REF], no chlorination experiment was carried on ammonia. The model published by Jafvert and Valentine [START_REF] Jafvert | Reaction scheme for the chlorination of ammoniacal water[END_REF] was directly implemented in the BFA chlorination model.

Analytical methods

For each sampling point a 60-mL bottle was opened and 10 mL were immediately transferred into a 20 mL-headspace vial, quenched with 60 µL of a sodium thiosulfate solution (0.2 mol/L) and acidified with 60 µL of phosphoric acid (85%, Merck).

Free chlorine was measured by the DPD colorimetric method using a Shimadzu UV-1280 spectrophotometer (APHA, 2005). The quantification limit was 0.1 mg/L as Cl2. If necessary, solutions were diluted with ultrapure water before analysis to reach a free chlorine concentration lower than 5 mg/L as Cl2.

TCM and DCAN were measured by headspace GC-MS (Clarus 500, Perkin-Helmer). Vials were heated in the headspace oven (Perkin-Elmer) at 60°C for 10 min before injection.

Separation was achieved with a FFAP capillary column (25 m × 0.15 mm i. for TCM and DCAN respectively. Relative standard deviations (RSD) were below 5% (n=3) for both analyses.

Kinetic modeling

Kinetic modeling was performed on COPASI software v4.16. Kinetic rates were fitted either with chlorination experiment results from this study or with experimental data from the literature, using evolutionary programming. Acid base equilibria were supposed to be instantaneously reached. All equilibrium constants and literature sources are indicated in Table 2. The model includes 55 reactions, 7 precursors and a total of 64 molecules.

HOCl = ClO -+ H + K= 2.90×10 -8 mol/L (25°C) [START_REF] Morris | The acid ionization constant of HOCl from 5 to 35°C[END_REF] (3) NH4 + = NH3 + H + K=5.75×10 -10 mol/L (25°C) Bates and Pinching, 1950 (4) C6H8O7 = C6H7O7 + H + K= 7.40×10 -4 mol/L [START_REF] Bates | Resolution of the dissociation constants of citric acid at 0 to 50°, and determination of certain related thermodynamic functions[END_REF] (5) C6H7O7 = C6H6O7 + H + K= 1.73×10 -5 mol/L (Bates and Pinching, 1949) (6) C6H6O7 = C6H5O7 + H + K= 3.98×10 -7 mol/L (Bates and Pinching, 1949) (7) HOCl -> Cl -+ X k= 4.42×10 -7 sec -1 BFA90 (8) HOCl + NH3 -> NH2Cl + H2O k=4.17×10 6 L/mol/sec(25°C) [START_REF] Jafvert | Reaction scheme for the chlorination of ammoniacal water[END_REF]) (A1)

HOCl + NH2Cl -> NHCl2 + H2O k= 2.77×10 2 L/mol/sec (25°C) [START_REF] Jafvert | Reaction scheme for the chlorination of ammoniacal water[END_REF]

) (A2) HOCl + NHCl2 -> NCl3 + H2O k= 1.70×10 3 L/mol/sec (25°C) (Jafvert and Valentine, 1992) (A3) NH2Cl + H2O -> HOCl + NH3 k= 2.11×10 -5 sec -1 (25°C) (Jafvert and Valentine, 1992) (A4) NHCl2 + H2O -> NH2Cl + HOCl k=7.60×10 -7 sec -1 (25°C) (Jafvert and Valentine, 1992) (A5) 2 NH2Cl -> NHCl2 + NH3 k= 5.22×10 -3 L/mol
C5H7N3Cl -> C5H5N3 + H + + Cl - k= 7.04×10 -4 sec -1 H5, H10, H30S, H60, H90S (H4) C6H6N3O2Cl -> C5H5N3 + CO2 + Cl -k= 1.00×10 -8 sec -1 H5, H10, H30S, H60, H90S (H4bis) C5H5N3 -> DCAN k= 6.64×10 -4 sec -1 H5, H10, H30S, H60, H90S (H5)

C6H8N3O2Cl-> C5H7N3 + CO2 + Cl -k= 7.91×10 -8 sec -1 H30, H90 (H6) C5H7N3-> TCM + K k= 1.10×10 -2 sec -1 H30, H90 (H7) HOCl + C6H5O7 -> C5H4O5 + CO2 + H + + Cl -+ OH - k= 5.50×10 -3 L/mol/sec CA10, CA30, CA65, CA90S, CA90, CA_B_20 (CA1) 2 HOCl + C5H4O5 -> C5H4O5Cl2 + 2 OH - k>10 15 L 2 /mol 2 /sec CA10, CA30, CA65, CA90S, CA90, CA_B_20 (

Results and discussion

Chlorine consumption

Chlorine demand has been determined during a long-term experiment involving a contact time of 270 hr. Free chlorine rapidly decreased during the BFA chlorination experiment. The high initial chlorine doses were calibrated to ensure a residual chlorine concentration during longterm experiments. After 100 hr of reaction, 65 mg/L of free chlorine had been consumed. Then the free chlorine concentration decreased very slowly due to chlorine degradation. The BFA chlorine demand was estimated at 15 mg Cl2/mg C. This value is close to the 18 mg Cl2/mg C reported by [START_REF] Kanan | Formation of disinfection by-products in indoor swimming pool water: The contribution from filling water natural organic matter and swimmer body fluids[END_REF] for the same BFA at 26°C and pH = 7. The BFA chlorine demand is higher than the chlorine demand of humic substances which is estimated at 1.1 -2.3 mg Cl2/mg C [START_REF] Reckhow | Chlorination of humic materials : byproducts formation and chemical interpretations[END_REF]. Consequently, the filling water chlorine demand can be neglected compared to the chlorine consumption caused by the anthropogenic pollution in pools. The BFA components were individually chlorinated at chlorine doses of 30 mg/L of Cl2 and 90 mg/L of Cl2 with contact times of 170 hr and 270 hr respectively. Urea consumed 54 mg/L of Cl2 after 270 hr of chlorination at 90 mg/L, which amounts to 78% of the total BFA chlorine demand (Fig. 1a and Appendix A S2). The ammonia molar chlorine demand, 1.7 mol/mol, is in good agreement with the value of 1.5 mol/mol proposed by the breakpoint model.

A c c e p t e d m a n u s c r i p t

L-histidine chlorine demand was estimated at 10 mol/mol after 170 hr of reaction, which is slightly lower than the 12 mol/mol reported by [START_REF] Hureiki | Chlorination studies of free and combined amino acids[END_REF] and slightly higher than the 8 mol/mol measured by [START_REF] Li | Volatile disinfection byproduct formation resulting from chlorination of organic-nitrogen precursors in swimming pools[END_REF] and [START_REF] Li | Comparison of THMs and HANs formation potential from the chlorination of free and combined histidine and glycine[END_REF]. The 6 mol/mol reported here for creatinine chlorine demand are higher than the value of 2 mol/mol reported by [START_REF] Tachikawa | Occurrence and production of chloramines in the chlorination of creatinine in aqueous solution[END_REF] and Li and Blatchle (2007). It could be explained by different contact times (150 hr in this study). With a molar chlorine demand of 7 mol/mol, uric acid is one of the most chlorine consuming component but its contribution to the BFA total chlorine demand is limited due to its low concentration in the solution. Citric acid contribution is also low. [START_REF] Dickenson | Haloacetic acid and Trihalomethane Formation from the Chlorination and Bromination of Aliphatic β-A c c e p t e d m a n u s c r i p t Dicarbonyl Acid Model Compounds[END_REF] reported 0.5 mol/mol after 24 hr contact time. In this study, the value was estimated at 4 mol/mol after 160 hr reaction. Although this value is comparable to the molar values of other components, the contribution of citric acid to the BFA chlorine consumption (1%) is low because of the low concentration of citric acid in the BFA solution.

Little data is available concerning the chlorine demand of hippuric acid. After 150 hr reaction, hippuric acid had the lowest molar chlorine demand among the BFA components (1 mol/mol; 0.7% of the BFA chlorine demand).

Although urea has the highest chlorine demand in the BFA, note that its contribution to the chlorine consumption increases during the first 20 hr of reaction. Indeed, ammonia reacts more quickly than the other components including urea, which leads to a higher contribution (40%) to chlorine consumption at the beginning of the reaction.

L-histidine was found to consume very little chlorine during the first 3 hours of reaction at a chlorine to L-Histidine ratio of 10. Thus, its contribution to the overall BFA consumption at the beginning of the reaction may not be significant compared to urea's consumption. Lian et al. reported that uric acid reacts very quickly with chlorine. Its consumption rate is similar to the consumption rate of glycine. At a chlorine to uric acid molar ratio of 6.4, 85% of free chlorine were consumed after 60 min [START_REF] Lian | Volatile Disinfection Byproducts Resulting from Chlorination of Uric Acid: Implications for Swimming Pools[END_REF].

A c c e p t e d m a n u s c r i p t

The model also includes a reaction representing chlorine degradation in the medium (Reaction (8), Table 2). The associated kinetic rate, included in the model, was calibrated on a long term experiment at the initial chlorine dose of 90 mg/L and is in agreement with the rate proposed by [START_REF] Lister | Decomposition of sodium hypochlorite : the uncatalyzed reaction[END_REF] for sodium hypochlorite decomposition (k = 3.8×10 -7 sec -1 ).

Urea chlorination has been widely documented. The chlorination mechanism has been proposed by [START_REF] Samples | A study on the chlorination of urea[END_REF], then modified by [START_REF] Blatchley | Reaction Mechanism for Chlorination of Urea[END_REF], who suggested that the first step, which is rate-limiting, involves molecular chlorine rather than hypochlorous acid. [START_REF] Blatchley | Reaction Mechanism for Chlorination of Urea[END_REF] also measured a rate constant for this first step by monitoring the N-chlorourea concentration spectrophotometrically at λ = 245 nm and pH = 2.0. However, the mechanism proposed with this rate did not fit with the experimental data of this study (Fig. 2).

The residual chlorine concentration following 600 hr of reaction and estimated with this model reached 0.045 mg/L of Cl2, whereas long term experiments exhibited a residual concentration of 15 mg/L of Cl2 for the same duration. Hence, urea chlorination by hypochlorous acid was taken into account and a rate constant was fitted. As a result of this change, the reaction rate of Cl2 with urea was also reassessed. The reaction rate of urea chlorination by HOCl was estimated at 8.44×10 -2 L/mol/sec, whereas the reaction rate with Cl2 was calculated at 3.10×10 7 L/mol/sec. These values confirm that Cl2 reacts more quickly with urea than HOCl. Urea consumed 3.8 mol/mol at pH = 7.5, which is consistent with the literature data [START_REF] De Laat | Chlorination of organic compounds : chlorine demand and reactivity in relationship to the trihalomethane formation[END_REF]. However De Laat (2011) observed that this value is pH-dependent: at pH = 4.5 urea chlorine demand reaches 2.5 mol/mol urea. The model presented here could not fit for pHvalue out of the range 6.5 -8.

Chlorine demand for other components and examples of chlorine consumption fits are reported in Appendix A S2.

Chloroform formation

Chloroform formation from the BFA components

A c c e p t e d m a n u s c r i p t

All BFA components were individually chlorinated at 30 and 90 mg/L of Cl2 during 150 hr and 270 hr respectively. For some components, specific chlorination experiments at lower initial chlorine doses were performed (Appendix A S3).

Very different TCM molar yields were obtained from the chlorination experiments of BFA components. However, urea, creatinine, L-histidine and uric acid have similar contributions (3% -5%) due to their different concentrations in the BFA mix (Table 3). TCM amounts formed by citric acid were significantly higher than the concentrations produced by the other components. For example, urea and creatinine formed 10 µg/L of TCM (0.084 µmol/L) after 150 hr chlorination at 90 mg/L, which involves formation potentials of 4.2×10 -4 mol/mol and 7.2×10 -3 mol/mol for urea and creatinine respectively. After the same contact time citric acid chlorination produced 250 µg/L of TCM (2.1 µmol/L) (Appendix A S3). One mole of citric acid produced 120 times more chloroform than one mole of creatinine and 2000 times more chloroform than one mole of urea. The ability of citric acid to form higher quantities of TCM than other BFA components has been reported in numerous studies [START_REF] Blatchley | Copper catalysis in chloroform formation during water chlorination[END_REF][START_REF] Dickenson | Haloacetic acid and Trihalomethane Formation from the Chlorination and Bromination of Aliphatic β-A c c e p t e d m a n u s c r i p t Dicarbonyl Acid Model Compounds[END_REF], with yields varying between 50% and 80% [START_REF] Blatchley | Copper catalysis in chloroform formation during water chlorination[END_REF][START_REF] Larson | Chloroform and chlorophenol production by decarboxylation of natural acids during aqueous chlorination[END_REF]. Regarding the TCM formation potential determined in this study, it appears that citric acid is the main precursor for TCM in the BFA. Citric acid is responsible for 80% of the TCM formed during BFA chlorination. In fact, the total TCM quantity yielded by the BFA components excluding citric acid was in the same order of magnitude as the measurement uncertainty. Only hippuric acid yielded significant TCM quantities.

Citric acid chlorination modeling

Citric acid was chlorinated at 90 mg/L during 270 hr in UPW at 27°C. 2.5 µmol/L TCM were formed during this experiment, which implies a TCM formation potential of 0.9 ± 0.2 mol/mol for citric acid.

A chlorination mechanism has been proposed by [START_REF] Larson | Chloroform and chlorophenol production by decarboxylation of natural acids during aqueous chlorination[END_REF], in which the first step leads to the formation of 3-ketoglutaric acid by citric acid decarboxylation.

3-Ketoglutaric acid yields large amounts of TCM by undergoing the haloform reaction [START_REF] Deborde | Reactions of chlorine with inorganic and organic compounds during water treatment-Kinetics and mechanisms: A critical review[END_REF][START_REF] Dickenson | Haloacetic acid and Trihalomethane Formation from the Chlorination and Bromination of Aliphatic β-A c c e p t e d m a n u s c r i p t Dicarbonyl Acid Model Compounds[END_REF][START_REF] Fuson | The Haloform Reaction[END_REF]. The resulting chlorination mechanism proposed in this study is shown in Appendix A S4. [START_REF] Larson | Chloroform and chlorophenol production by decarboxylation of natural acids during aqueous chlorination[END_REF] proposed a rate-limiting decarboxylation step based on the finding that the optimum pH corresponds to the simultaneous presence of the citrate trianion and of the hypochlorous acid. Acid-base equilibria of citric acid were included in the model via Reactions (5), ( 6) and ( 7) (Table 2). Considering the much higher yield observed by [START_REF] Larson | Chloroform and chlorophenol production by decarboxylation of natural acids during aqueous chlorination[END_REF] at pH = 7, it was supposed that the citrate trianion was the only form reacting with hypochlorous acid. For the same reason it was supposed that hypochlorous acid was the only chlorine specie involved in the reaction. No kinetic rate was proposed in previous studies for the decarboxylation step. In this study the first kinetic rate was fitted with data obtained from experiments performed at different initial chlorine doses (Table 2 andAppendix A S3). The experimental data published by [START_REF] Blatchley | Copper catalysis in chloroform formation during water chlorination[END_REF], were also used to fit the rate with experiments performed at a different citric acid concentration. The reaction rate was established at 5.50×10 -3 L/mol/sec. Fig. 3 presents the main results of kinetic modeling. It can be observed that the model fits with experimental points for long-term experiments (350 hr) as well as for short term experiments (10 hr). However, the values predicted by the model are 15% to 20% lower than the experimental data from [START_REF] Blatchley | Copper catalysis in chloroform formation during water chlorination[END_REF].

A c c e p t e d m a n u s c r i p t

A very long-term experiment was performed on BFA and citric acid at 90 mg/L to evaluate chloroform formation for contact times longer than 1500 hr (Fig. 4). The mean concentration measured for chloroform was 1.3 µmol/L. Although the experimental values are dispersed, a clear decreasing trend can be observed for long contact times, which suggests a loss during the experiments. Moreover, gas bubbles and thus headspace formation were observed in the bottles during the experiments. This phenomenon could be explained by the gas formed as reactions by-products (N2, CO2), and it could lead to the loss of TCM. UPW could also degas and participate in the bubble formation. To take this into account in the model, a loss rate was fitted with the results of a dedicated experiment and it was validated with long term experiments performed on BFA and citric acid.

A c c e p t e d m a n u s c r i p t

The other BFA components contributions were also modeled, based on the experiments presented in Appendix A S3. The results presented in Fig. 5 show that the predicted overall chloroform concentration is slightly higher than the measured concentration. The minor contributions are, as said, in the same range as the experimental uncertainty. However, it is noticeable that the TCM formation rates of the BFA components are different. Urea, creatinine, L-histidine and uric acid contributions were mainly formed within the first 150 hr of reaction.

On the contrary, the contribution of hippuric acid was not visible during the first 50 hr of reaction.

Dichloroacetonitrile formation kinetics 2.3.1. DCAN formation from the BFA chlorination

A c c e p t e d m a n u s c r i p t

The BFA was chlorinated at different initial chlorine doses and the DCAN formation was monitored during the first 24 hr of reaction. DCAN is not stable in the aqueous media. Indeed, it is easily degraded by hydrolysis and by reaction with hypochlorite to form dichloroacetamide and N-chloro-2,2-dichloroacetamide respectively [START_REF] Glezer | Hydrolysis of haloacetonitriles : linear free enegy relationship, kinetics and products[END_REF][START_REF] Yu | Kinetic Analysis of Haloacetonitrile Stability in Drinking Waters[END_REF].

The DCAN produced by the BFA chlorination reached a maximum concentration of 0.9 µmol/L before starting to decrease (Appendix A S5, Fig. S30) Few articles address the relative DCAN formation potentials of BFA components. In this study, all BFA components were individually chlorinated at 90 mg/L and the DCAN was monitored during the first 10 hr of reaction. DCAN was detected only during L-histidine chlorination.

However, DCAN formation was different whether the L-histidine was isolated or in the BFA solution. The BFA chlorination yielded immediately high amounts of DCAN from the beginning of the chlorination. On the contrary, during isolated L-histidine chlorination experiments, the DCAN concentration started to increase quickly after 2 hr of reaction (Appendix A S5).

DCAN formation from L-histidine chlorination

L-histidine produced large amounts of DCAN by reaction with chlorine. The maximum concentration measured during L-histidine chlorination at 90 mg/L was 1 µmol/L, or 166.6 mmol/mol, which is very close to the maximum DCAN concentration observed during BFA chlorination (0.9 µmol/L). Note that for high initial chlorine doses (above 60 mg/L) the DCAN concentration increased very slowly during the first 2 hr and then sharply increased to reach a peak before decreasing due to DCAN degradation (Fig. 6).

L-histidine reactivity with chlorine has been studied previously within the scope of amino-acids chlorination. Amino-acids generally form high quantities of DCAN because of the amine group which facilitates the decarboxylation step leading to the formation of the nitrile group [START_REF] Shah | Halonitroalkanes, Halonitriles, Haloamides, and N-Nitrosamines: A Critical Review of Nitrogenous Disinfection Byproduct Formation Pathways[END_REF][START_REF] Trehy | Chlorination Byproducts of Amino Acids in Natural Waters[END_REF]. Note that combined amino-acids derived from the condensation of two or more amino-acids, were proven to produce lower amounts of DCAN A c c e p t e d m a n u s c r i p t than free amino-acids, while having a lower molar chlorine demand [START_REF] Hureiki | Chlorination studies of free and combined amino acids[END_REF][START_REF] Li | Comparison of THMs and HANs formation potential from the chlorination of free and combined histidine and glycine[END_REF]. In the case of combined amino-acids, the nitrogen is indeed engaged into an amide bound, making it less available for the decarboxylation reaction. In the case of L-histidine, [START_REF] Li | Volatile disinfection byproduct formation resulting from chlorination of organic-nitrogen precursors in swimming pools[END_REF] also pointed out the possible chlorination of the secondary amine located on the ring.

No kinetic rate has been proposed before for the formation of DCAN from L-histidine chlorination. However, Yu andReckhow (2017, 2015) reported complete degradation mechanism and degradation kinetics of DCAN, which was in good agreement with experimental results of this study. Hence, their rate constants were directly included in the model to take this degradation into account. [START_REF] Li | Comparison of THMs and HANs formation potential from the chlorination of free and combined histidine and glycine[END_REF] proposed a chlorination mechanism of L-histidine explaining the formation of both DCAN and TCM. This mechanism was considered for kinetic rate fitting (Appendix A S4). The kinetic rates of reactions (H1) to (H7) were obtained by fitting the mechanism with chlorination experiments of L-histidine at 5, 10, 30, 60 and 90 mg/L of Cl2 (Table 2 and Appendix A S5). Reactions (H1) to (H5) were fitted on experiments H5, H10, H60, H30S, H90S. These experiments were specifically designed for the monitoring of DCAN, which degradation implies short contact times. Reactions (H6) and (H7) were fitted on experiments H5, H10, H30 and H90, whose contact times were longer. All the fitted models included the degradation rates determined by Yu andReckhow (2017, 2015). Ammonia or one of its chlorination by-products may accelerate the DCAN formation during the L-histidine chlorination. The mechanism proposed previously [START_REF] Li | Comparison of THMs and HANs formation potential from the chlorination of free and combined histidine and glycine[END_REF][START_REF] Li | Volatile disinfection byproduct formation resulting from chlorination of organic-nitrogen precursors in swimming pools[END_REF][START_REF] Liu | Effects of preoxidation and adsorption on haloacetonitrile and trichloronitromethane formation during subsequent chlorination[END_REF] does not allow to explain the role of ammonia. This point should be further investigated to build a kinetic model explaining these differences of reactivity.

Conclusion

In this work, an original kinetic model has been established for the prediction of chlorine consumption, chloroform formation and dichloroacetonitrile formation. The BFA chlorine demand was estimated at 15 mg Cl2/mg TOC, which is considerably higher than the chlorine demand of natural organic matter. Urea was found to be responsible for 78% of the BFA chlorine demand. The first step of urea chlorination is confirmed to be rate-limiting, and the contributions of both HOCl (k= 8.44×10 -2 L/mol/sec) and Cl2 (k= 3.10×10 7 L/mol/sec) were considered in order to obtain a good fitting. It is noteworthy that the contribution of ammonia at the beginning of the reaction is significant because of its high reactivity. Chloroform is slowly formed (k=5.50×10 -3 L/mol/sec), mainly by citric acid chlorination, which contributes to almost 80% of the chloroform formation potential of the BFA. The model of chloroform formation was calibrated on several experiments including a wide range of contact times as well as data of the literature. Dichloroacetonitrile was formed by the chlorination of L-histidine which is the only precursor for this by-product. The kinetic model for L-histidine chlorination was fitted with the latest published chlorination mechanism and different reactivities were observed for L-histidine depending on its environment. The presence of ammonia seemed to catalyze the

  d. × 0.25 µm) pressurized at 35 psi. Temperature for the GC oven started at 40°C for 5 min then rose to 120°C at 10°C/min and held for 5 min. The source temperature was set to 250°C. Standard solutions (2000 µg/mL, Sigma-Aldrich) were used to prepare external standards. TCM and DCAN were identified using full-scan analysis and they were quantified in Single Ion Monitoring (SIM) mode using ions at m/z = 83 and 74 respectively. Quantification limits were 5 µg/L and 2 μg/L A c c e p t e d m a n u s c r i p t

  CA2)C5H4O5Cl2 + OH --> HCO3 -+ C4H2O3Cl2 k>10 15 L/mol/sec CA10, CA30, CA65, CA90S, given for rate constants taken from the literature. References of the experiments used for rates adjustment are precised for the rates determined in this study. If experimental data used for the adjustment come from another published paper, the experiment reference is indicated in bold. P = unidentified reaction products; I = unidentified intermediate.

  The model fits satisfactorily with the experiments, considering the sudden slope changes observed. The presence of two parallel ways of reaction leading to the formation of the nitrile group in the mechanism is in agreement with the kinetic modeling since the presence of these parallel ways improves significantly the fit for the experiments with high initial chlorine doses (60 and 90 mg/L) compared to a linear mechanism (Fig.6).To further investigate the DCAN formation mechanism and the reactivity of L-histidine in the BFA, chlorination experiments of BFA components mixtures at 90 mg/L were performed. The BFA components concentrations were the same as in the BFA. Fig.7shows the evolution of DCAN concentration for different mixtures.

Table 1

 1 Body Fluid Analog (BFA) composition

			a n u s c r i p t
		m
	Compound Ammonium chloride Urea L-Histidine A c c e p t e d CAS Developed formula 7664-41-7 NH4Cl 57-13-6 71-00-1	Initial concentration in the chlorinated solution (individual and mix) (mmol/L) 2.88×10 -2 1.90×10 -1 6.01×10 -3	TOC (mg/L) 0 2.28 0.036	% of total TOC 0 56.7 0.9	TN (mg/L) 0.40 5.3 0.25	% of total TN 5.9 79 3.7
	Creatinine	60-27-5	1.23×10 -2	0.594	14.8	0.52	7.7

Table 2

 2 Reaction rates of the model.

	Reaction	Rate	or	equilibrium	Source*	Reaction
		constant				label
	H2O = H + + OH -	Ke=10 -14 mol/L			(1)
	Cl2 = HOCl + H + + Cl -	K= 3.94×10 -4 mol 2 /L 2
		(25°C)

[START_REF] Connick | The hydrolysis of chhlorine and its variation with temperature[END_REF]

Table 3

 3 Chloroform formation from the BFA components.

	BFA component	Concentration (mmol/L)	Yield	of	TCM	Contribution to the TCM
			formation (mmol/mol)	production	from	BFA
						chlorination (%)
	Ammonium chloride	2.88×10 -2	0			0
	Urea	1.90×10 -1	0.40			2.7
	Creatinine	1.23×10 -2	7.20			3.0
	L-Histidine	6.01×10 -3	24.0			5.1
	Citric acid	2.57×10 -3	881			77
	Uric acid	2.24×10 -3	63.4			4.9
	Hippuric acid	7.35×10 -3	28.5			7.2
	Initial Cl2 concentration 90 mg/L, pH 7.5, temperature 27°C.

Acknowledgments

The authors would like to acknowledge the Conseil Régional de Bretagne for financial support.

They also would like to express their sincere thanks to colleagues who improved the quality of this document.

formation of dichloroacetonitrile, but further information about L-histidine chlorination mechanism is required to fully explain the chlorination kinetics of this molecule.

Appendix A. Supplementary data

Supplementary data associated with this article can be found in the online version at xxxxxx.


Structure of action plans and the notion of temporal stops

Marie-Françoise Valax, Françoise


Alain Finkel
email: finkel@lsv.fr

Serge Haddad
email: haddad@lsv.fr

Igor Khmelnitsky
email: khmelnitsky@lsv.fr

Minimal Coverability Tree Construction Made Complete and Efficient

Keywords: Petri nets, Karp-Miller tree algorithm, Coverability, Minimal coverability set, Clover, Minimal coverability tree

Downward closures of Petri net reachability sets can be finitely represented by their set of maximal elements called the minimal coverability set or Clover. Many properties (coverability, boundedness, ...) can be decided using Clover, in a time proportional to the size of Clover. So it is crucial to design algorithms that compute it efficiently. We present a simple modification of the original but incomplete Minimal Coverability Tree algorithm (MCT), computing Clover, which makes it complete: it memorizes accelerations and fires them as ordinary transitions. Contrary to the other alternative algorithms for which no bound on the size of the required additional memory is known, we establish that the additional space of our algorithm is at most doubly exponential. Furthermore we have implemented a prototype MinCov which is already very competitive: on benchmarks it uses less space than all the other tools and its execution time is close to the one of the fastest tool.

Introduction

Coverability and coverability set in Petri nets. Petri nets are iconic as an infinite-state model used for verifying concurrent systems. Coverability, in Petri nets, is the most studied property for several reasons: (1) many properties like mutual exclusion, safety, control-state reachability reduce to coverability, [START_REF] Blondin | Approaching the coverability problem continuously[END_REF] the coverability problem is EXPSPACE-complete (while reachability is non elementary), and (3) there exist efficient prototypes and numerous case studies. To solve the coverability problem, there are backward and forward algorithms. But these algorithms do not address relevant problems like the repeated coverability problem, the LTL model-checking, the boundedness problem and regularity of the traces.

However these problems are EXPSPACE-complete [START_REF] Demri | On selective unboundedness of VASS[END_REF][START_REF] Blockelet | Model checking coverability graphs of vector addition systems[END_REF] and are also decidable using the Karp-Miller tree algorithm (KMT) [START_REF] Karp | Parallel program schemata[END_REF] that computes a finite tree labeled by a set of ω-markings C ⊆ N P ω (where N ω is the set of naturals enlarged with an upper bound ω and P is the set of places) such that the reachability set and the finite set C have the same downward closure in N P . Thus a marking m is coverable if there exists some m ≥ m with m ∈ C. Hence, C can be seen as one among all the possible finite representations of the infinite downward closure of the reachability set. This set C allows, for instance, to solve multiple instances of coverability in linear time linear w.r.t. the size of C avoiding to call many times a costly algorithm. Informally the KMT algorithm builds a reachability tree but, in order to ensure termination, substitutes ω to some finite components of a marking of a vertex when some marking of an ancestor is smaller.

Unfortunately C may contain comparable markings while only the maximal elements are important. The set of maximal elements of C can be defined independently of the KMT algorithm and was called the minimal coverability set (MCS) in [START_REF] Finkel | The minimal coverability graph for Petri nets[END_REF] and abbreviated as the Clover in the more general framework of Well Structured Transition Systems (WSTS) [START_REF] Finkel | Forward analysis for WSTS, part II: Complete WSTS[END_REF]. The minimal coverability tree algorithm. So in [START_REF] Finkel | Reduction and covering of infinite reachability trees[END_REF][START_REF] Finkel | The minimal coverability graph for Petri nets[END_REF] the author computes the minimal coverability set by modifying the KMT algorithm in such a way that at each step of the algorithm, the set of ω-markings labelling vertices is an antichain. But this aggressive strategy, implemented by the so-called Minimal Coverability Tree algorithm (MCT), contains a subtle bug and it may compute a strict under-approximation of Clover as shown in [START_REF] Finkel | A counter-example to the minimal coverability tree algorithm[END_REF][START_REF] Geeraerts | On the efficient computation of the minimal coverability set of Petri nets[END_REF]. Alternative minimal coverability set algorithms. Since the discovery of this bug, three algorithms (with variants) [START_REF] Geeraerts | On the efficient computation of the minimal coverability set of Petri nets[END_REF][START_REF] Reynier | Minimal coverability set for Petri nets: Karp and Miller algorithm with pruning[END_REF][START_REF] Piipponen | Constructing minimal coverability sets[END_REF] have been designed for computing the minimal coverability set without building the full Karp-Miller tree. In [START_REF] Geeraerts | On the efficient computation of the minimal coverability set of Petri nets[END_REF] the authors proposed a minimal coverability set algorithm (called CovProc) that is not based on the Karp-Miller tree algorithm but uses a similar but restricted introduction of ω's. In [START_REF] Reynier | Minimal coverability set for Petri nets: Karp and Miller algorithm with pruning[END_REF], Reynier and Servais proposed a modification of the MCT, called the Monotone-Pruning algorithm (called MP), that keeps but "deactivates" vertices labeled with smaller ω-markings while MCT would have deleted them. Recently in [START_REF] Reynier | On the computation of the minimal coverability set of petri nets[END_REF], the authors simplified their original proof of correctness. In [START_REF] Valmari | Old and new algorithms for minimal coverability sets[END_REF], Valmari and Hansen proposed another algorithm (denoted below as VH) for constructing the minimal coverability set without deleting vertices. Their algorithm builds a graph and not a tree as usual. In [START_REF] Piipponen | Constructing minimal coverability sets[END_REF], Piipponen and Valmari improved this algorithm by designing appropriate data structures and heuristics for exploration strategy that may significantly decrease the size of the graph. Our contributions.

1. We introduce the concept of abstraction as an ω-transition that mimics the effect of an infinite family of firing sequences of markings w.r.t. coverability. As a consequence adding abstractions to the net does not modify its coverability set. Moreover, the classical Karp-Miller acceleration can be formalized as an abstraction whose incidence on places is either ω or null. The set of accelerations of a net is upward closed and well-ordered. Hence there exists a finite subset of minimal accelerations and we show that the size of all minimal acceleration is bounded by a double exponential. 2. Despite the current opinion that "The flaw is intricate and we do not see an easy way to get rid of it....Thus, from our point of view, fixing the bug of the MCT algorithm seems to be a difficult task" [START_REF] Geeraerts | On the efficient computation of the minimal coverability set of Petri nets[END_REF], we have found a simple modification of MCT which makes it correct. It mainly consists in memorizing discovered accelerations and using them as ordinary transitions. 3. Contrary to all existing minimal coverability set algorithms that use an unknown additional memory that could be non primitive recursive, we show, by applying a recent result of Leroux [START_REF] Leroux | Distance Between Mutually Reachable Petri Net Configurations[END_REF], that the additional memory required for accelerations, is at most doubly exponential. 4. We have developed a prototype in order to also empirically evaluate the efficiency of our algorithm and the benchmarks (either from the literature or random ones) have confirmed that our algorithm requires significantly less memory than the other algorithms and is close to the fastest tool w.r.t. the execution time. Organization. Section 2 introduces abstractions and accelerations and studies their properties. Section 3 presents our algorithm and establishes its correctness. Section 4 describes our tool and discusses the results of the benchmarks. We conclude and give some perspectives to this work in Section 5. The appendix contains the missing proofs and an illustration of the behavior of the algorithm.

Covering abstractions

Petri nets: reachability and covering

Here we define Petri nets differently from the usual way but in an equivalent manner. i.e. based on the backward incidence matrix Pre and the incidence matrix C. The forward incidence matrix is implicitly defined by C + Pre. Such a choice is motivated by the introduction of abstractions in section 2.2. Definition 1. A Petri net (PN) is a tuple N = P, T, Pre, C where:

-P is a finite set of places; -T is a finite set of transitions, with P ∩ T = ∅; -Pre ∈ N P ×T is the backward incidence matrix; -C ∈ Z P ×T is the incidence matrix which fulfills: for all p ∈ P and t ∈ T , C(p, t) + Pre(p, t) ≥ 0.

A marked Petri net (N , m 0 ) is a Petri net N equipped with an initial marking m 0 ∈ N P .

The column vector of matrix Pre (resp. C) indexed by t ∈ T is denoted

Pre(t) (resp. C(t)). A transition t ∈ T is fireable from a marking m ∈ N P if m ≥ Pre(t). When t is fireable from m, its firing leads to marking m def = m + C(t), denoted by m t -→ m .
One extends fireability and firing to a sequence σ ∈ T * by recurrence on its length. The empty sequence ε is always fireable and let the marking unchanged. Let σ = tσ be a sequence with t ∈ T and σ ∈ T * . Then σ is fireable from m if m t -→ m and σ is fireable from m . The firing of σ from m leads to the marking m reached by σ from m . One also denotes this firing by m σ -→ m .

Definition 2. Let (N , m 0 ) be a marked net. The reachability set Reach(N , m 0 ) is defined by:

Reach(N , m 0 ) = {m | ∃σ ∈ T * m 0 σ -→ m}
In order to introduce the coverability set of a Petri net, let us recall some definitions and results related to ordered sets. Let (X, ≤) be an ordered set. The downward (resp. upward) closure of a subset E ⊆ X is denoted by ↓ E (resp. ↑ E) and defined by:

↓ E = {x ∈ X | ∃y ∈ E y ≥ x} (resp. ↑ E = {x ∈ X | ∃y ∈ E y ≤ x}) A subset E ⊆ X is downward (resp. upward) closed if E =↓ E (resp. E =↑ E).
An antichain E is a set which fulfills: ∀x = y ∈ E ¬(x ≤ y ∨ y ≤ x). X is said FAC (for Finite AntiChains) if all its antichains are finite. A non empty set E ⊆ X is directed if for all x, y ∈ E there exists z ∈ E such that x ≤ z and y ≤ z. An ideal is a set which is downward closed and directed. There exists an equivalent characterization of FAC sets which provides a finite description of any downward closed set: a set is FAC if and only if every downward closed set admits a finite decomposition in ideals (a proof of this well-known result can be found in [START_REF] Blondin | Well behaved transition systems[END_REF]).

X is well founded if all its (strictly) decreasing sequences are finite. X is well ordered if it is FAC and well founded. There are many equivalent characterizations of well order. For instance, a set X is well ordered if and only if for all sequence (x n ) n∈N in X, there exists a non decreasing infinite subsequence. This characterization allows to design algorithms that computes trees whose finiteness is ensured by well order. Let us recall that (N, ≤) and (N P , ≤) are well ordered sets.

We are now ready to introduce the cover (also called the coverability set) of a net and to state some of its properties. Definition 3. Let (N , m 0 ) be a marked Petri net. Cover(N , m 0 ), its coverability set, is defined by:

Cover(N , m 0 ) =↓ Reach(N , m 0 )
Since the coverability set is downward closed and N P is FAC, it admits a finite decomposition in ideals. The ideals of N P can be defined in an elegant way as follows. One first extends the sets of naturals and integers: N ω = N ∪ {ω} et Z ω = Z ∪ {ω}. Then one extends the order relation and the addition to Z ω : for all n ∈ Z, ω > n and for all n ∈ Z ω , n + ω = ω + n = ω. N P ω is also a well ordered set and its members are called ω-markings. There is a one-to-one mapping between ideals of N P and ω-markings. Let m ∈ N P ω . Define m by: m = {m ∈ N P | m ≤ m} m is an ideal of N P (and all ideal can be defined in such a way). Let Ω be a set of ω-markings, Ω denotes the set m∈Ω m . Due to the above properties, there exists a unique finite set with minimal size Clover(N , m 0 ) ⊆ N p ω such that: Cover(N , m 0 ) = Clover(N , m 0 ) A more general result can be found in [START_REF] Blondin | Well behaved transition systems[END_REF] for well structured transition systems.

Example 1. The marked net of Figure 1

Abstraction and acceleration

In order to introduce abstractions and accelerations, we generalize the transitions to allow the capability to mark a place with ω tokens.

Definition 4. Let P be a set of places. An ω-transition a is defined by:

-Pre(a) ∈ N P ω its backward incidence; -C(a) ∈ Z P ω its incidence with Pre(a) + C(a) ≥ 0. In order to define abstractions, we first define the incidences of a sequence σ of ω-transitions by recurrence on its length. As previously, we denote Pre(p, σ) One checks by recurrence that σ is firable from m if and only if m ≥ Pre(σ) and in this case, m σ -→ m + C(σ). An abstraction of a net is an ω-transition which concisely expresses the behaviour of the net w.r.t. covering (see Proposition 1). One will observe that a transition t of a net is by construction (with σ n = t for all n) an abstraction. Definition 5. Let N = P, T, Pre, C be a Petri net and a be an ω-transition. a is an abstraction if for all n ≥ 0, there exists σ n ∈ T * such that for all p ∈ P with Pre(p, a) ∈ N:

1. Pre(p, σ n ) ≤ Pre(p, a); 2. If C(p, a) ∈ Z then C(p, σ n ) ≥ C(p, a); 3. If C(p, a) = ω then C(p, σ n ) ≥ n.
The following proposition justifies the interest of abstractions. Let us check that σ n is fireable from m . Let p ∈ P ,

-If m(p) < ω then m (p) = m(p) ≥ Pre(p, a) ≥ Pre(p, σ n ); -Else m (p) = ≥ Pre(p, σ n ). Let us show that m + C(σ n ) ≥ m * . Let p ∈ P , -If m(p) < ω and C(p, a) < ω then m (p) + C(p, σ n ) ≥ m(p) + C(p, a) = m (p) ≥ m * (p); -If m(p) < ω and C(p, a) = ω then m (p) + C(p, σ n ) ≥ C(p, σ n ) ≥ n ≥ m * (p) ; -If m(p) = ω then m (p) + C(p, σ n ) ≥ n -C(p, σ n ) + C(p, σ n ) = n ≥ m * (p).
An easy way to build new abstractions consists in concatenating them. We now introduce the underlying concept of the Karp and Miller construction. Definition 6. Let N = P, T, Pre, C be a Petri net. One says that a is an acceleration if a is an abstraction such that C(a) ∈ {0, ω} P .

The following proposition provides a way to get an acceleration from an arbitrary abstraction. Let us study more deeply the set of accelerations. First we equip the set of ω-transitions with a"natural" order w.r.t. covering. Definition 7. Let P be a set of places and two ω-transitions a and a .

a ≤ a if and only if Pre(a) ≤ Pre(a ) ∧ C(a) ≥ C(a )
In other words, a ≤ a if given any ω-marking m, if a is fireable from m then a is also fireable and its firing leads to a marking greater or equal that the one reached by the firing of a . Proposition 4. Let N be a Petri net. Then the set of abstractions of N is upward closed. Similarly, the set of accelerations is upward closed in the set of ω-transitions whose incidence belongs to {0, ω} P . Proposition 5. The set of accelerations of a Petri net is well ordered.

Proof. The set of accelerations is a subset of N P × {0, ω} P (where P is the set of places) with the order obtained by iterating cartesian products of sets (N, ≤) and ({0, ω}, ≥). These sets are well ordered and the cartesian product preserves this property. So we are done.

Since the set of accelerations is well ordered and it is upward closed, it is equal to the upward closure of the finite set of minimal accelerations. Let us study the size of a minimal acceleration. Given some Petri net, one denotes d = |P | and e = max p,t (max(Pre(p, t), Pre(p, t) + C(p, t)).

We are going to use the following result of Jérôme Leroux (published on HAL in June 2019) which provides a bound for the lengths of shortest sequences between two markings m 1 and m 2 mutually reachable.

Theorem 1. (Theorem 2, [11]) Let N be a Petri net, m 1 , m 2 be markings, σ 1 , σ 2 be sequences of transitions such that m 1 σ1 -→ m 2 σ2 -→ m 1 . Then there exist σ 1 , σ 2 such that m 1 σ 1 -→ m 2 σ 2 -→ m 1 fulfilling: |σ 1 σ 2 | ≤ ||m 1 -m 2 || ∞ (3de) (d+1) 2d+4
One deduces an upper bound on the size of minimal accelerations. Proof. Let a ≤ a, be a minimal acceleration. For all p such that Pre(p, a) = ω, P re(p, a ) ≤ e(3de) (d+1) 2d+4 . So a ≤ trunc(a). Since the set of accelerations is upward closed, one gets that trunc(a) is an acceleration.

Let v ∈ N P ω . One denotes ||v|| ∞ = max(v(p) | v(p) ∈ N).
σ 1 -→ m 2 and |σ 1 | ≤ (3de) (d+1) 2d+4 since ||m 1 -m 2 || ∞ = 1. By deleting the transitions of T 1 occurring in σ 1 , one gets a sequence σ 1 ∈ T * such that m 1 σ 1 -→ m 2 ≥ m 2 with |σ 1 | ≤ (3de) (d+1)

A coverability tree algorithm

Specification and illustration

As discussed in the introduction, to compute the clover of a Petri net, most algorithms build coverability trees (or graphs), which are variants of the Karp and Miller tree with the aim of reducing the peak memory during the execution. The seminal algorithm [START_REF] Finkel | The minimal coverability graph for Petri nets[END_REF] is characterized by a main difference with the KMT construction: when finding that the marking associated with the current vertex strictly covers the marking of another vertex, it deletes the subtree issued from this vertex, and when the current vertex belonged to the removed subtree it substitutes it to the root of the deleted subtree. This operation drastically reduces the peak memory but as shown in [START_REF] Finkel | A counter-example to the minimal coverability tree algorithm[END_REF] entails incompleteness of the algorithm.

Like the previous algorithms that ensure completeness with deletions, our algorithm also needs additional memory. However unlike the other algorithms, it memorizes accelerations instead of ω-markings. This approach has two advantages. First, we are able to exhibit a theoretical upper bound on the additional memory which is doubly exponential, while the other algorithms do not have such a bound. Furthermore, accelerations are reused in the construction and thus may even shorten the execution time and peak space w.r.t. the algorithm in [START_REF] Finkel | The minimal coverability graph for Petri nets[END_REF].

Before we delve into a high level description of this algorithm, let us present some of the variables, functions, and definitions used by the algorithm. Algorithm 1, denoted from now on as MinCov takes as an input a marked net (N , m 0 ) and constructs a directed labeled tree CT = (V, E, λ, δ), and a set Acc of ωtransitions (which by Lemma 2 are accelerations). Each v ∈ V is labeled by an ω-marking, λ(v) ∈ N P ω . Since CT is a directed tree, every vertex v ∈ V , has a predecessor (except the root r) denoted by prd(v) and a set of descendants denoted by Des(v). By convention, prd(r) = r. Each edge e ∈ E is labeled by a firing sequence δ(e) ∈ T o •Acc * , consisting of an ordinary transition followed by a sequence of accelerations (which by Lemma 1 fulfills λ(prd(v))

δ(prd(v),v) -------→ λ(v)).
In addition, again by Lemma 1, m 0 δ(r,r) ---→ λ(r). Let γ = e 1 e 2 . . . e k ∈ E * be a path in the tree, we denote by δ(γ) := δ(e 1 )δ(e 2 ) . . . δ(e k ) ∈ (T ∪ Acc) * . The subset Front ⊂ V is the set of vertices 'to be processed'.

MinCov may call function Delete(v) that removes from V a leaf v of CT and function Prune(v) that removes from V all descendants of v ∈ V except v itself as illustrated in the following figure:

u v v v Delete(u) Prune(v)
First MinCov does some initializations, and sets the tree CT to be a single vertex r with marking λ(r) = m 0 and Front = {r}. Afterwards the main loop builds the tree, where each iteration consists in processing some vertex in Front as follows.

MinCov picks a vertex u ∈ Front (line 3). From λ(u), MinCov fires a sequence σ ∈ Acc * reaching some m u that maximizes the number of ω produced, i.e. |{p ∈ P | λ(u)(p) = ω ∧ m u (p) = ω}|. Thus in σ, no acceleration occurs twice and its length is bounded by |P |. Then MinCov updates λ(u) with m u (line 5) and the label of the edge incoming to u by concatenating σ. Afterwards it performs one of the following actions according to the marking λ(u):

-Cleaning (line 7): If there exists u ∈ V \ Front with λ(u ) ≥ λ(u). The vertex u is redundant and MinCov calls Delete(u) -Accelerating (lines 8-16): If there exists u , an ancestor of u with λ(u ) < λ(u) then an acceleration can be computed. The acceleration a is deduced from the firing sequence labeling the path from u to u. MinCov inserts a into Acc, calls Prune(u ) and pushes back u in Front. -Exploring (lines 18 -25): Otherwise MinCov calls Prune(u ) followed by Delete(u ) for all u ∈ V with λ(u ) < λ(u) since they are redundant. Afterwards, it removes u from Front and for all fireable transition t ∈ T from λ(u), it creates a new child for u in CT and inserts it into Front.

For a detailed example of a run of the algorithm see Example 2 in the appendix.

Correctness Proof

We now establish the correctness of Algorithm 1 by proving the following properties (where for all W ⊆ V , λ(W ) denotes v∈W λ(v)):

its termination; the incomparability of ω-markings associated with vertices in V : λ(V ) is an antichain; its consistency: λ(V ) ⊆ Cover(N , m 0 ); its completeness: Cover(N , m 0 ) ⊆ λ(V ) .

We get termination by using the well order of N P ω and Koenig Lemma.

Proposition 8. MinCov terminates.

Proof. Consider the following variation of the algorithm.

Instead of deleting the current vertex when its marking is smaller or equal than the marking of a vertex, one marks it as 'cut' and extract it from Front.

Instead of cutting a subtree when the marking of the current vertex v is greater than the marking of a vertex which is not an ancestor of v, one marks them as 'cut' and extract from Front those who are inside.

Instead of cutting a subtree when the marking of the current vertex v is greater than the marking of a vertex which is an ancestor of v, say v * , one marks those on the path from v * to v (except v) as 'accelerated', one marks the other vertices Algorithm 1: Computing the minimal coverability set

MinCov(N , m0) Input: A marked Petri net (N , m0) Data: V set of vertices; E ⊆ V × V ; Front ⊆ V ; λ : V → N p ω ; δ : E → ToAcc * ; CT = (V, E, λ, δ) a labeled tree; Acc a set of ω-transitions; Output: A labeled tree CT = (V, E, λ, δ) 1 V ← {r}; E ← ∅; Front ← {r}; λ(r) ← m0; Acc ← ∅; δ(r, r) ← ε 2 while F ront = ∅ do 3 Select u ∈ Front 4
Let σ ∈ Acc * a maximal fireable sequence of accelerations from λ(u) // Maximal w.r.t. the number of ω's produced

5 λ(u) ← λ(u) + C(σ) 6 δ((prd(u), u)) ← δ((prd(u), u)) • σ 7 if ∃u ∈ V \ Front s.t. λ(u ) ≥ λ(u) then Delete(u) // λ(u) is covered 8 else if ∃u ∈ Anc(V ) s.t. λ(u) > λ(u ) then
// An acceleration was found between u and one of u's ancestors

if λ(u ) < λ(u) then Prune(u ); Delete(u ) end Front ← Front \ {u} foreach t ∈ T ∧ λ(u) ≥ Pre(t) do // Add the children of u u ← NewNode(); V ← V ∪ {u }; Front ← Front ∪ {u }); E ← E ∪ {(u, u )} λ(u ) ← λ(u) + C(t); δ((u, u )) ← t end end end return CT
of the subtree as 'cut' and inserts v again in Front with the marking of v * . All the markings of the subtree in Front are extracted from it.

All the vertices marked as 'cut' or 'accelerated' are ignored for comparisons and discovering accelerations. This alternative algorithm behaves as the original one except that the size of the tree never decreases and so if the algorithm does not terminate the tree is infinite. Since this tree is finitely branching, due to Koenig Lemma it contains an infinite path. On this infinite path, no vertex can be marked as 'cut' since it would belong to a finite subtree. Observe that the marking labelling the vertex following an accelerated subpath has at least one more ω than the marking of the first vertex of this subpath. So there is an infinite subpath with unmarked vertices in V . But N P ω is well-ordered, so there should be two vertices v and v , where v is a descendant of v with λ(v ) ≥ λ(v), which contradicts the behaviour of the algorithm.

Since we are going to use recurrence on the number of iterations of the main loop of Algorithm 1, we introduce the following notations:

CT n = (V n , E n , λ n , δ n ),
Front n , and Acc n are the the values of variables CT, Front, and Acc at line 2 when n iterations have been executed.

Proposition 9. For all n ∈ N, λ(V n \ Front n ) is an antichain. Thus on termi- nation, λ(V ) is an antichain. Proof. Let us introduce V := V \ Front and V n := V n \ Front n .
We are going to prove by induction on the number n of iterations of the while-loop that V n is an antichain. MinCov initializes variables V and Front at line 1. So V 0 = {r} and Front 0 = {r}, therefore V 0 = V 0 \ Front 0 = ∅ is an antichain. Assume that V n = V n \ Front n is an antichain. Modifying V n can be done by adding or removing vertices from V n and removing vertices from Front n while keeping them in V n . The actions that MinCov may perform in order to modify the sets V and Front are: Delete (lines 7 and 19), Prune (lines 16 and 19), adding vertices to V (line 23), adding vertices to Front (lines 16 and 23), and removing vertices from Front (line 21).

• Both Delete and Prune do not add new vertices to V . Thus the antichain feature is preserved.

• MinCov may add vertices to V only at line 23 where it simultaneously adds them to Front and therefore does not add new vertices to V . Thus the antichain feature is preserved.

• Adding vertices to Front may only remove vertices from V n . Thus the antichain feature is preserved.

• MinCov can only add a vertex to V when it removes it from Front while keeping it in V . This is done only at line 21. There the only vertex MinCov may remove (line 21) is the working vertex u. However if (in the iteration) MinCov reaches line 21 then it did not reach line 7 hence, (1) all markings of λ(V n ) ⊆ λ(V n ) are either smaller or incomparable to λ n+1 (u). Moreover, MinCov has also reached line 18-20, where (2) it performs Delete on all vertices u ∈ V n ⊆ V n with λ n (u ) < λ n+1 (u). Let us denote by V n ⊆ V n the set V at the end of line 20. Due to (1) and ( 2), marking λ n+1 (u) is incomparable to any marking in λ n+1 (V n ). Since V n ⊆ V n , λ n+1 (V n ) is an antichain. Combining this fact with the incomparability between λ n+1 (u) and any marking in λ n+1 (V n ), we conclude that the set λ n+1 (V n+1 ) = λ n+1 (V n ) ∪ {λ n+1 (u)} is an antichain.

In order to establish consistency, we prove that the labelling of vertices and edges is compatible with the firing rule and that Acc is a set of accelerations.

Lemma 1. For all n ∈ N, for all u ∈ V n \ {r}, λ n (prd(u))

δ(prd(u),u) -------→ λ n (u) and m 0 δ(r,r) ---→ λ n (r).
Proof. Let us prove by induction on the number n of iterations of the main loop that for all v ∈ V n , the assertions of the lemma hold. Initially, V 0 = {r} and λ 0 (r) = m 0 . Since m 0 ε -→ m 0 = λ 0 (r) the base case is established. Assume that the assertions hold for CT n . Observe that MinCov may change the labeling function λ and/or add new vertices in exactly two places: at lines 4-6 and at lines 22-25. Therefore in order to prove the assertion, we show that after each group of lines it still holds.

• After lines 4-6: MinCov computes (1) a maximal fireable sequence σ ∈ Acc * n from λ n (u) (line 4), and updates u's marking to m u = λ n (u) + C(σ) (line 5).

Since the assertions hold for CT

n , (2) if u = r, λ n (prd(u)) δ(prd(u),u) -------→ λ n (u) else m 0 δ(r,r) ---→ λ n (r). By concatenation, we get λ n (prd(u)) δ(prd(u),u)σ --------→ m u if u = r
and otherwise m 0 δ(r,r)σ ----→ m u which establishes that the assertions hold after line 6.

• After lines 22-25: The vertices for which λ is updated at these lines are the children of u that are added to the tree. For every fireable transition t ∈ T from λ(u), MinCov creates a child v t for u (lines 22-23). The marking of any child v t is set to m n+1 (v) := m n+1 (u) + C(t) (line 24). Therefore since λ n+1 (u) t -→ λ n+1 (v t ), the assertions hold. Lemma 2. At any execution point of MinCov, Acc is a set of accelerations.

Proof. At most one acceleration is added per iteration. Let us prove by induction on the number n of iterations of the main loop that Acc n is a set of accelerations. Since Acc 0 = ∅, the base case is straightforward. Assume that Acc n is a set of accelerations and consider Acc n+1 . In an iteration, MinCov may add an ω-transition a to Acc. Due to the inductive hypothesis, δ(γ) is a sequence of abstractions where γ is defined at line Lemma 5. Let CT , Front and Acc be the values of corresponding variables at some execution point of MinCov, u ∈ Front and u ∈ V such that the following items hold:

1. All m ∈ Cover(N , m 0 ) are quasi-covered; 2. λ(V \ Front) is an antichain; 3. For all v ∈ V \ {r}, λ(prd(v)) δ(prd(v),v) -------→ λ(v); 4. λ(u ) < λ(u) and u is not a descendant of u .
Then after performing Prune(u ); Delete(u ),

1. All m ∈ Cover(N , m 0 ) are quasi-covered; 2. λ(V \ Front) is an antichain; 3. For all v ∈ V \ {r}, λ(prd(v)) δ(prd(v),v) -------→ λ(v).
Lemma 6. Let CT , Front and Acc be the values of corresponding variables at some execution point of MinCov. and u ∈ Front such that the following items hold:

1. All m ∈ Cover(N , m 0 ) are quasi-covered; 2. λ(V \ Front) ∪ {λ(u)} is an antichain; 3. For all a ∈ Acc fireable from λ(u), λ(u) = λ(u) + C(a).
Then after removing u from Front and for all t ∈ T fireable from λ(u), adding a child v t to u in Front with marking of v t defined by λ u (v t ) = λ(u) + C(t), all m ∈ Cover(N , m 0 ) are quasi-covered.

Proposition 11. At the beginning of every iteration, all m ∈ Cover(N , m 0 ) are quasi-covered.

Proof. Let us prove by induction on the number of iterations that all m ∈ Cover(N , m 0 ) are quasi-covered. Let us consider the base case. MinCov initializes V and Front to {r} and λ(r) to m 0 . By definition, for all m ∈ Cov(N , m 0 ) there exists established as in the previous case. Assertion 3 holds due to Lemma 1, and the fact that no edge has been added since the beginning of iteration. Thus using this lemma the induction is proved in this case. Lines 18-25. We first show that the hypotheses of Lemma 6 hold before line 21.

σ = t 1 t 2 • • • t k ∈ T * such that m 0 σ -→ m ≥ m. Since V \ Front = ∅,
Let us denote the values of CT and Front after line 20 by CT n and Front n .

Observe that for all iteration of Line 19 in the inner loop, the hypotheses of Lemma 5 are satisfied. Therefore, in order to apply Lemma 6 it remains only to check assertions 2 and 3 of this lemma. Assertion 2 holds since (1) λ(V \ Front) is an antichain, (2) due to Line 7 there is no w ∈ V \ Front such that λ(w) ≥ λ(u), and (3) by iteration of Line 19 all w ∈ V \ Front such that λ(w) < λ(u) have been deleted. Assertion 3 holds due to Line 5 (all useful enabled accelerations have been fired) and Line 8 (no acceleration has been added).

Lines 21-25 correspond to the operations related to Lemma 6. Thus using this lemma, the induction is proved in this case.

The completeness of MinCov is an immediate consequence of the previous proposition.

Corollary 1. When MinCov terminates, Cover(N , m 0 ) ⊆ λ(V ) .

Proof. By Proposition 11 all m ∈ Cover(N , m 0 ) are quasi-covered. Since on termination, Front is empty for all m ∈ Cover(N , m 0 ), there exists v ∈ V such that m ≤ λ(v).

Tool and benchmarks

In order to empirically evaluate our algorithm, we have implemented a prototype tool which computes the clover and solves the coverability problem. This tool is developed in the programming language Python, using the Numpy library. It can be found on GitHub3 . All benchmarks were performed on a computer equipped by Intel i5-8250U CPU with 4 cores, 16GB of memory and Ubuntu Linux 18.03.

Minimal coverability set. We compare MinCov with the tool MP [START_REF] Reynier | Minimal coverability set for Petri nets: Karp and Miller algorithm with pruning[END_REF], the tool VH [START_REF] Valmari | Old and new algorithms for minimal coverability sets[END_REF], and the tool CovProc [START_REF] Geeraerts | On the efficient computation of the minimal coverability set of Petri nets[END_REF]. We have also implemented the (incomplete) minimal coverability tree algorithm denoted by AF in order to measure the additional memory needed for the (complete) tools. Both MP and VH tools were sent to us by the courtesy of the authors. The tool MP has an implementation in Python and another in C ++ . For comparison we selected the Python one to avoid biases due to programming language.

We ran two kinds of benchmarks: (1) 123 standard benchmarks from the literature in Table 1, (which were taken from [START_REF] Blondin | Approaching the coverability problem continuously[END_REF]), (2) 100 randomly generated Petri nets also in Table 1, since the benchmarks from the literature do not present all the features that lead to infinite state systems. These random Petri nets have the following properties: (1) 50 < |P |, |T | < 100, (2) the number of places connected of each transition is bounded by 10, and (3) they are not structurally bounded. The execution time of the tools was limited to 900 seconds.

Table 1 contains a summary of all the instances of the benchmarks. The first column shows the number of instances on which the tool timed out. The time column consists of the total time on instances that did not time out plus 900 seconds for any instance that led to a time out. The #Nodes column consists of the peak number of nodes in instances that did not time out on any of the tools (except CovProc which does not provide this number). For MinCov we take the peak number of nodes plus accelerations. In the benchmarks from the literature we observed that the instances that timed out from MinCov are included in those of AF and MP. However there were instances the timed out on VH but did not time out on MinCov and vice versa. MinCov is the second fastest tool, and compared to VH it is 1.2 times slower. A possible explanation would be that VH is implemented in C ++ . As could be expected, w.r.t. memory requirements MinCov has the least number of nodes. In the benchmarks from the literature MinCov has approximately 10 times less nodes then MP and 1.6 times less then VH. In the random benchmarks these ratio are significantly higher.

Coverability. We compare MinCov to the tool qCover [START_REF] Blondin | Approaching the coverability problem continuously[END_REF] on the set of benchmarks from the literature in Table 2. In [START_REF] Blondin | Approaching the coverability problem continuously[END_REF], qCover is compared to the most competitive tools for coverability and achieves a score of 142 solved instances while the second best tool achieves a score of 122. We split the results into safe instances (coverable) and unsafe ones (not coverable). In both categories we counted the number of instances on which the tools failed (columns T/O) and the total time (columns Time) as in Table 1.

We observed that the tools are complementary, i.e. qCover is faster at proving that an instance is safe and MinCov is faster at proving that an instance is unsafe. Therefore, by splitting the processing time between them we get better results.

The third row of Table 2 represents a parallel execution of the tools, where the time for each instance is computed as follows:

Time(MinCov qCover) = 2 min (Time(MinCov), Time(qCover)) .

Combining both tools is 2.5 times faster than qCover and 3.5 times faster than MinCov. This confirms the above statement. We could still get better results by dynamically deciding which ratio of CPU to share between the tools depending on some predicted status of the instance.

Conclusion

We have proposed a simple and efficient modification of the incomplete minimal coverability tree algorithm for building the clover of a net. Our algorithm is based on the introduction of the concepts of covering abstractions and accelerations. Compared to the alternative algorithms previously designed, we have theoretically bounded the size of the additional space. Furthermore we have implemented a prototype which is already very competitive. From a theoretical point of view, we plan to study how abstractions and accelerations, could be defined in the more general context of well structured transition systems. From an experimental point of view, we will follow three directions in order to increase the performance of our tool. First as in [START_REF] Piipponen | Constructing minimal coverability sets[END_REF], we have to select appropriate data structures to minimize the number of comparisons between ω-markings. Then we want to precompute a set of accelerations using linear programming as the correctness of the algorithm is preserved and the efficiency could be significantly improved. Last we want to take advantage of parallelism in a more general way than simultaneously running several tools. The proof is identical for accelerations.

) + C(p, σ ,b ) ≥ C(p, σ ,b ) ≥ ≥ Pre(p, σ n ). Last C(p, σ ,b ) + C(p, σ n ) ≥ + C(p, σ n ) ≥ n -C(p, σ n ) + C(p, σ n ) ≥ n.

A run of the algorithm

Example 2. Lets us describe some iterations of MinCov(N , m init ), where N is the Petri net in Figure 1 and m init = p init . For each iteration of the main loop below we present a figure showing CT before and after the iteration. In the figures, we color in red the currently processed vertex and in blue the other vertices in Front.

Iteration 2: MinCov picks v 4 from Front to process it. Since Acc = ∅, there is no possible acceleration firing (Lines 4-5). Next, MinCov discovers an ancestor v 1 of v 4 with a smaller marking. Therefore it performs an acceleration phase (Lines 8-16). MinCov builds a new acceleration a 1 (according to labels of the edges between v 4 and v 1 ), with Pre(a 1 ) = p l and C(a 1 ) = ω •p ba and inserts it in Acc. Afterwards it performs Prune(v 1 ), and pushes back v 1 to Front.

r v 1 v 3 v 2 v 4 v 5 t2 t3 t1 t5 t4
Before:

Acc = ∅; λ(v 1 ) = p l + p m λ(v 4 ) = p l + p m + p ba r v 1 v 3 v 2 t2 t3 t1
After:

Acc = {a 1 }; λ(v 1 ) = p l + p m Iteration 7: MinCov picks v 3 from Front to process it. Since a 2 is fireable from λ(v 3 ), λ(v 3 ) becomes λ(v 3 ) + C(a 2 ) = p l + p bk + ωp ba + ωp c (Lines 4-5).
Since there is no marking greater than λ(v 3 ) in λ(V \ Front) and no ancestor with a smaller marking, MinCov goes to the exploration phase (Lines 18-25). Looking at all vertices, MinCov deletes (the subtree rooted in) v 5 since λ(v 5 ) < λ(v 3 ). Afterwards, it creates two children of v 3 (v 6 and v 7 ) since t 5 and t 6 are fireable from λ(v 3 ) .

r v 1 v 3 v 2 v 5 t2 a 1 t3 t 1 a 1 t4 Before: Acc = {a 1 , a 2 }; λ(v 3 ) = p l + p bk + ωp ba λ(v 5 ) = p l + ωp ba + p c Pre(a 2 ) = p bk + ωp ba ; C(a 2 ) = ωp c r v 1 v 3 v 2 v 6 v 7 t2 a 1 t3 t 1 a 1 t5 t6
After:

Acc = {a 1 , a 2 }; λ(v 3 ) = λ(v 7 ) = λ(v 6 ) = p l + p bk + ωp ba + ωp c
Iteration 11: MinCov picks v 8 from Front to process it. Neither a 1 , nor a 2 are fireable from λ(v 8 ), so it is unchanged (Lines 4-5). Then since λ(v 8 ) ≤ λ(v 3 ), MinCov performs the cleaning phase by calling Delete(v 8 ). This is the last iteration of MinCov since Front = ∅. Then all m ∈ Cover(N , m 0 ) are quasi-covered after performing Delete(u).

r v 1 v 3 v 2 v 8 t2 a 1 t3 t 1 a 1 a 2 Before: Acc = {a 1 , a 2 }; λ(v 3 ) = p l + p bk + ωp ba + ωp c λ(v 8 ) = p b + p c r v 1 v 3 v 2 t2 a 1 t3 t 1 a 1 a 2 After: Acc = {a 1 , a 2 };

Proof.

Let u be a leaf of CT . Assume the assertions of the lemma are satisfied. Denote by CT = (V , E , λ , δ ) and Front , the value of variables CT and Front after performing Delete(u) on CT . Let m * ∈ Cov(N , m 0 ). Thus m * is quasi-covered. By definition, V = V \ {u} and Front = Front \ {u}. Moreover, for all v ∈ V we have λ (v ) = λ(v ). We split the proof in two cases:

• There exists w ∈ V \ Front with λ(w) ≥ m * -If w = u then w ∈ V \ Front . Since λ (w) = λ(w), m * is still quasi-covered. -If w = u then there exists v such that λ (v) = λ(v) ≥ λ(u). Therefore, if v / ∈ Front then m * is still quasi-covered. Otherwise since λ(V \ Front) is an antichain, for all v / ∈ Front λ(v ) ≥ λ(u) implying λ(v ) ≥ λ(v). Therefore, the sequence λ(v) ε -→ λ(v) ≥ m * , is an exploring sequence.
• There is an exploring sequence m σ -→ m ≥ m * with some w such that m = λ(w).

Let σ = σ 0 t 1 σ 1 • • • t k σ k , where t i ∈ T and σ i ∈ Acc * . -Assume w = u. Since (1) for all 0 ≤ i ≤ k, there does not exist v ∈ V \ Front such that λ(w) + C(σ 0 t 1 σ 1 . . . t i σ i ) ≤ λ(v ), (2) V \ Front ⊆ V \ Front, and (3) λ
(w) = λ(w), m σ -→ m is still an exploring sequence. -Assume w = u. Since λ(v) ≥ λ(u) = λ(u) + C(σ 0 ) then v ∈ Front: otherwise it would contradict the definition of an exploring sequence. Since λ[u](v) = λ(v) ≥ λ(u)
, σ is also fireable from λ[u](v). Since V \Front ⊆ V \Front, there does not exist v ∈ V \Front such that λ[u](v)+C(σ 0 t 1 σ 1 . . . t i σ i ) ≤ λ[u](v ) for some i. Therefore λ (v) σ -→ λ (v) + C(σ) ≥ m * is an exploring sequence.

Lemma 4. Let CT , Front and Acc be the values of corresponding variables at some execution point of MinCov. and u ∈ V such that the following items hold:

1. All m ∈ Cover(N , m 0 ) are quasi-covered; 2. λ(V \ Front) is an antichain;

3. For all v ∈ V \ {r}, λ(prd(v))

δ(prd(v),v)

-------→ λ(v).

Then all m ∈ Cover(N , m 0 ) are quasi-covered after performing Prune(u) and then adding u to Front. • There is an exploring sequence m σ -→ m ≥ m * with some w such that m = λ(w). Let σ = σ 0 t 1 σ 1 • • • t k σ k , where t i ∈ T and σ i ∈ Acc * .

-Assume that w is not a descendant of u. Thus w ∈ Front . Since V \ Front ⊆ V \ Front, and for all v , λ (v ) = λ(v ), m σ -→ m ≥ m * is still an exploring sequence.

-Assume that w is a descendant of u by a path in CT u = w 0 δ(w0,w1)

------→ w 1 • • • w k-1 δ(w k-1 ,w k )
-------→ w k = w. Since λ(V \Front) is an antichain any λ(w i ) with i < k is incomparable with any λ(w ) in λ(V \ Front). -Assume that w is not a descendant of u . Since w is not a descendant of u , w is still in V \ Front. Since λ(w) ≥ m * , m * is quasi-covered.

acceleration produces some ω, one would obtain λ(u) + C(σ 0 ) = λ(u). Since only u has been added to V \ Front, m σ -→ m ≥ m * is still an exploring sequence.

-Otherwise pick the greatest index i ≤ k such that λ(w)+C(σ 0 t 1 σ 1 • • • t i σ i ) ≤ λ(u). If i = k, then λ (u) = λ(u) ≥ λ(w) + C(σ 0 t 1 σ 1 • • • t k σ k ) = m ≥ m implying that m is quasi-covered. If i < k then denote by σ = t i+1 σ i+1 • • • t k σ k , this suffix of σ. σ is fireable from λ(u), hence t i+1 is fireable from λ(u). So u has a child v ti+1 in V with λ (v ti+1 ) = λ(u) + C(t i+1 ). Let σ =

σ i+1 t i+2 • • • t k σ k .
Then σ is fireable from λ (v ti+1 ) and λ (v ti+1 ) σ --→ m ≥ m ≥ m. Since only u has been added to V \Front, for all i < j ≤ k there does not exist v ∈ V \ Front such that λ u (v ti+1 ) + C(σ i+1 t i+2 • • • t j σ j ) ≤ λ u (v ).

Therefore since v ti+1 ∈ Front u , λ (v ti+1 ) σ --→ m is an exploring sequence.

For

  sake of homogeneity, one denotes Pre(a)(p) (resp. C(a)(p)) by Pre(p, a) (resp. C(p, a)). An ω-transition a is fireable from an ω-marking m ∈ N P ω if m ≥ Pre(a). When a is fireable from m, its firing leads to the ω-marking m def = m + C(a), denoted as previously m a -→ m . One observes that if Pre(p, a) = ω then for all values of C(p, a), m (a) = ω. So without loss of generality, one assumes that for all ω-transition a, Pre(p, a) = ω implies C(p, a) = ω.

  )(p) and C(p, σ) def = C(σ)(p). The base case corresponds to the definition of an ω-transition. Let σ = tσ , with t an ω-transition and σ a sequence of ω-transitions, then: -C(σ) = C(t) + C(σ ); for all p ∈ P • if C(p, t) = ω then Pre(p, σ) = Pre(p, t); • else Pre(p, σ) = max(Pre(p, t), Pre(p, σ ) -C(p, t)).

Proposition 1 .

 1 Let (N , m 0 ) be a marked Petri net, a be an abstraction and m be an ω-marking such that: m ⊆ Cover(N , m 0 ) and m a -→ m . Then m ⊆ Cover(N , m 0 ). Proof. Pick some m * ∈ m . Denote n = max(m * (p) | m (p) = ω) and = max(Pre(p, σ n ), n -C(p, σ n ) | m(p) = ω). Let us define m ∈ m by: -If m(p) < ω then m (p) = m(p); -Else m (p) = .

Proposition 2 .

 2 Let N = P, T, Pre, C be a Petri net and σ be a sequence of abstractions. Then the ω-transition a defined by Pre(a) = Pre(σ) and C(a) = C(σ) is an abstraction.

Proposition 3 .

 3 Let N = P, T, Pre, C be a Petri net and a be an abstraction. Define a an ω-transition as follows. For all p ∈ P : -If C(p, a) < 0 then Pre(p, a ) = C(p, a ) = ω; -If C(p, a) = 0 then Pre(p, a ) = Pre(p, a) and C(p, a ) = 0; -If C(p, a) > 0 then Pre(p, a ) = Pre(p, a) and C(p, a ) = ω.Then a is an acceleration.

Proposition 6 . 1 σ1-→ m 2 . 2 σ2-→ m 1 .

 61221 Let N be a Petri net and a be a minimal acceleration. Then ||Pre(a)|| ∞ ≤ e(3de) (d+1) 2d+4 . Proof. Let us consider the net N = P , T , Pre , C obtained from N by deleting the set of places {p | Pre(p, a) = ω} and adding the set of transitions T 1 = {t p | p ∈ P } with Pre(t p ) = p et C(t p ) = -p. Observe that d ≤ d and e = e. One denotes P 1 = {p | Pre(p, a) < ω = C(p, a)}. One introduces m 1 the marking obtained by restricting Pre(a) to P and m 2 = m 1 + p∈P1 p. Let {σ n } n∈N be a family of sequences associated with a. Let n * = ||Pre(a)|| ∞ +1.Then σ n * is fireable in N from m 1 and its firing leads to a marking that covers m 2 . By concatenating some occurrences of transitions of T 1 , one gets a firing sequence in N m Using the same process, one gets a firing sequence m Let us apply Theorem 1. There exists a sequence σ 1 with m 1

  2d+4 . The ω-transition a , defined by Pre(p, a ) = Pre(p, σ 1 ) for all p ∈ P , Pre(p, a ) = ω for all p ∈ P \ P and C(a ) = C(a), is an acceleration whose associated family is {σ 1 n } n∈N . By definition of m 1 , a ≤ a. Since a is minimal, a = a. Observing that |σ 1 | ≤ (3de) (d+1) 2d+4 , one gets ||Pre(a)|| ∞ = ||Pre(a )|| ∞ ≤ e(3de) (d+1) 2d+4 . Thus given any acceleration, one can easily obtain a smaller acceleration whose (representation) size is exponential. Proposition 7. Let N be a Petri net and a be an acceleration. Then the ω-transition trunc(a) defined by: -C(trunc(a)) = C(a); for all p such that Pre(p, a) = ω, Pre(p, trunc(a)) = min(Pre(p, a), e(3de) (d+1) 2d+4 ) ; for all p such that Pre(p, a) = ω, Pre(p, trunc(a)) = ω. is an acceleration.

9

  Let γ ∈ E * the path from u to u in CT a ← NewAcceleration() foreach p ∈ P do if C(p, δ(γ)) < 0 then Pre(p, a) ← ω; C(p, a) ← ω if C(p, δ(γ)) = 0 then Pre(p, a) ← Pre(p, δ(γ)); C(p, a) ← 0 if C(p, δ(γ)) > 0 then Pre(p, a) ← Pre(p, δ(γ)); C(p, a) ← ω end a ← trunc(a); Acc ← Acc ∪ {a}; Prune(u ); Front = Front ∪ {u } ; else for u ∈ V do // Remove vertices labeled by markings covered by λ(u)

9 .

 9 Consider b, the ω-transition defined by Pre(b) = Pre(δ(γ)) and C(b) = C(δ(γ)). Due to Proposition 2, b is an abstraction. Due to Proposition 3, the loop of lines 11-15 transforms b into an acceleration a. Due to Proposition 7, after truncation at line 16, a is still an acceleration. Proposition 10. λ(V ) ⊆ Cover(N , m 0 ).

Line 7 .

 7 this firing sequence is an exploring sequence. Assume that all m ∈ Cover(N , m 0 ) are quasi-covered at the beginning of some iteration. Let us examine what may happen during the iteration. In lines 4-6, MinCov computes the maximal fireable sequence σ ∈ Acc * n from λ n (u) (line 4) and sets u's marking to m u := λ n (u) + C(σ) (line 5). Afterwards, there are three possible cases: (1) either m u is covered by some marking associated with a vertex out of Front, (2) either an acceleration is found, (3) or MinCov computes the successors of u and removes u from Front. MinCov calls Delete(u). So CT n+1 is obtained by deleting u. Moreover, λ(u ) ≥ m u . Let us check the hypotheses of Lemma 3. Assertion 1 follows from induction since (1) the only change in the data is the increasing of λ(u) by firing some accelerations and (2) u belongs to Front so cannot cover intermediate markings of exploring sequences. Assertion 2 follows from Proposition 9 since V \ Front is unchanged. Assertion 3 follows immediately from lines 4-6. Assertion 4 follows with v = u . Thus using this lemma the induction is proved in this case. Lines 8-16. Let us check the hypotheses of Lemma 4. Assertions 1 and 2 are

Proposition 2 .

 2 Let N = P, T, Pre, C be a Petri net and σ be a sequence of abstractions. Then the ω-transition a defined by Pre(a) = Pre(σ) and C(a) = C(σ) is an abstraction. Proof. We establish the result par recurrence on the length of σ. The basis case is immediate. Let σ = bσ and (by recurrence hypothesis) let {σ n } n∈N be a family of sequences of transitions associated with σ . Let {σ n,b } n∈N be a family of sequences of transitions associated with b. Fix n ∈ N and define n = max(n, max(n -C(p, b) | C(p, b) < ω = C(p, σ ))). Define also = max(Pre(p, σ n ), n -C(p, σ n ) | Pre(p, b) < ω = C(p, b)). Let us check that σ ,b σ n fulfills the conditions of Definition 5. Let p ∈ P , Pre(p, a) < ω if and only if (1) Pre(p, b) < ω and C(p, b) = ω or (2) Pre(p, b) < ω and C(p, b) < ω and Pre(p, σ ) < ω. Case Pre(p, b) < ω and C(p, b) = ω. Consequently, Pre(p, a) = Pre(p, b) and C(p, a) = ω. So we get Pre(σ ,b ) ≤ Pre(p, b) = Pre(p, a). Moreover Pre(p, σ ,b

Proposition 3 .

 3 Case Pre(p, b) < ω and C(p, b) < ω and Pre(p, σ ) < ω. Hence Pre(p, a) = max(Pre(p, b), Pre(p, σ ) -C(p, b)). Observe that: Pre(p, σ ,b σ n ) = max(Pre(p, σ ,b ), Pre(p, σ n ) -C(p, σ ,b )) ≤ max(Pre(p, b), Pre(p, σ ) -C(p, b))=Pre(p, a)There are now two subcases to be considered.• C(p, σ ) < ω. Consequently, C(p, a) = C(p, b) + C(p, σ ). Observe now that C(p, σ ,b σ n ) = C(p, σ ,b ) + C(p, σ n ) ≥ C(p, b) + C(p, σ ) = C(p, a). • C(p, σ ) = ω. Consequently, C(p, a) = ω. Observe now that C(p, σ ,b σ n ) = C(p, σ ,b ) + C(p, σ n ) ≥ C(p, b) + n -C(p, b) = n.So a is an abstraction. Let N = P, T, Pre, C be a Petri net and a be an abstraction. Define a an ω-transition as follows. For all p ∈ P :-If C(p,a) < 0 then Pre(p, a ) = C(p, a ) = ω; -If C(p, a) = 0 then Pre(p, a ) = Pre(p, a) and C(p, a ) = 0; -If C(p, a) > 0 then Pre(p, a ) = Pre(p, a) and C(p, a ) = ω. Then a is an acceleration. Proof. Let us consider {σ n } n∈N a family associated with abstraction a. We are going to show that the family {σ n n } n∈N fulfills the conditions of Definition 5 w.r.t. a . For all n: -Let p ∈ P be such that Pre(p, a ) < ω. This implies that C(p, a) ≥ 0 and that Pre(p, a ) = Pre(p, a). Since C(p, σ n ) ≥ C(p, a) ≥ 0, Pre(p, σ n n ) = Pre(p, σ n ) ≤ Pre(p, a) = Pre(p, a ); -Let p ∈ P be such that C(p, a ) = 0. Then 0 = C(p, a) ≤ C(σ n ). Consequently, 0 ≤ nC(σ n ) = C(σ n n ); -Let p ∈ P be such that Pre(p, a ) < ω and C(p, a ) = ω. This implies that C(p, a) > 0. So 1 ≤ C(p, a) ≤ C(σ n ). Consequently, n ≤ nC(σ n ) = C(σ n n ). Proposition 4. Let N be a Petri net. Then the set of abstractions of N is upward closed. Similarly, the set of accelerations is upward closed in the set of ω-transitions whose incidence belongs to {0, ω} P . Proof. Let a be an abstraction and a ≥ a be an ω-transition. Let {σ n } n∈N be a family of sequences associated with a. Let n 0 = max(C(p, a ) | C(p, a ) ∈ N) with by convention max(∅) = 0. We will show that the family {σ max(n,n0) } n∈N can be associated with a . Let p be such that Pre(p, a ) ∈ N. This implies Pre(p, a) ∈ N. On the other hand: -Pre(p, σ max(n,n0) ) ≤ Pre(p, a) ≤ Pre(p, a ); -If C(p, a ) ∈ Z and C(p, a) ∈ Z then C(p, σ max(n,n0) ) ≥ C(p, a) ≥ C(p, a ); -If C(p, a ) ∈ Z and C(p, a) = ω then C(p, σ max(n,n0) ) ≥ n 0 ≥ C(p, a ); -If C(p, a ) = ω then C(p, a) = ω and C(p, σ max(n,n0) ) ≥ n.

6. 3 3 Lemma 3 .

 333 Proofs of Section Let CT , Front and Acc be the values of corresponding variables at some execution point of MinCov and u ∈ V be a leaf in CT such that the following items hold:1. All m ∈ Cover(N , m 0 ) are quasi-covered; 2. λ(V \ Front) is an antichain; 3. For all a ∈ Acc fireable from λ(u), λ(u) = λ(u) + C(a); 4. There exists v ∈ V \ {u} such that λ(v) ≥ λ(u).

Proof.

  Let u ∈ V . Denote by CT = (V , E , λ , δ ), and Front the value CT after performing Prune(u) on CT and adding u to Front. Assume that the assertions of the Lemma hold. If u ∈ Front then CT = CT and we are done. So let us assume that u / ∈ Front. Due to the definition of Prune,V \ Front = V \ (Front ∪ Des(u)). Moreover, for all v ∈ V , λ (v) = λ(v). Let m * ∈ Cov(N , m 0 ). Thus m * is quasi-covered. We split the proof in two cases: • There exists w ∈ V \ Front with λ(w) ≥ m * .-Assume that w is not a descendant of u. Since w is not a descendant of u, w ∈V \ Front . Since λ (w) = λ(w) ≥ m * , m * is quasi-covered. -Assume that w is a descendant of u, by a path in CT u = w 0 δ(w0,w1) ------→ w 1 • • • w k-1 δ(w k-1 ,w k ) -------→ w k = w. Since λ(V \ Front) is an antichain any λ(w i ) is incomparable with any λ(w ) in λ(V \ Front). Since V \ Front ⊆ V \ Front, the sequence λ(u) = λ(w 0 ) δ(w0,w1) ------→ λ(w 1 ) • • • λ(w k-1 ) δ(w k-1 ,w k )-------→ λ(w k ) = λ(w) ≥ m * is an exploring sequence.

  Consider the sequence λ(u) = λ(w 0 ) δ(w0,w1)------→ λ(w 1 ) • • • λ(w k-1 ) δ(w k-1 ,w k ) -------→ λ(w k ) σ -→ m ≥ m * . Since V \ Front ⊆ V \ Front,and for all v , λ (v ) = λ(v ), this sequence is an exploring sequence. Lemma 5. Let CT , Front and Acc be the values of corresponding variables at some execution point of MinCov, u ∈ Front and u ∈ V such that the following items hold:1. All m ∈ Cover(N , m 0 ) are quasi-covered; 2. λ(V \ Front) is an antichain; 3. For all v ∈ V \ {r}, λ(prd(v)) δ(prd(v),v)-------→ λ(v); 4. λ(u ) < λ(u) and u is not a descendant of u .Then after performing Prune(u ); Delete(u ),1. All m ∈ Cover(N , m 0 ) are quasi-covered; 2. λ(V \ Front) is an antichain; 3. For all v ∈ V \ {r}, λ(prd(v)) δ(prd(v),v) -------→ λ(v).Proof. The second and third assertions of the conclusion are still satisfied since we do no add vertices and edges. So let us establish that all m ∈ Cover(N , m 0 ) are still quasi-covered. Let m * ∈ Cov(N , m 0 ). • There exists w ∈ V \ Front with λ(w) ≥ m * .

  is unbounded. Its Clover is the following set: {p i , p bk + p m , p l + p m + ωp ba , p l + p bk + ωp ba + ωp c } For instance, the marking p l +p bk +αp ba +βp c is reached thus covered by sequence t 1 t α+β

	5	t β 6 .
		t 1	p l	t 5
				p ba
		t 2	p bk
		p i		t 6
		t 3		t 4
				p c
			p m
		Fig. 1. An unbounded Petri net

Table 1 .

 1 Benchmarks for clover123 benchmarks from the literature 100 random benchmarks

		T/O	Time	#Nodes		T/O	Time	#Nodes
	MinCov	16	18127	48218	MinCov	14	13989	61164
	VH	15	14873	75225	VH	15	13692	208134
	MP	24	23904	478681	MP	21	21726	755129
	CovProc	49	47081	N/A	CovProc	80	74767	N/A
	AF	19	19223	45660	AF	16	15888	63275

Table 2 .

 2 Benchmarks for the coverability problem (60 safe and 115 unsafe)

		Time Unsafe T/O Unsafe Time safe T/O safe	T/O Time
	MinCov	1754	1	51323	53	54 53077
	qCover	26467	26	11865	11	37 38332
	MinCov qCover	1841	2	13493	11	13 15334

https://github.com/IgorKhm/MinCov

Proof. Let v ∈ V . Consider the path u 0 , . . . , u k of CT from the root r = u 0 to u k = v. Let σ ∈ (T ∪ Acc) * denote δ(prd(u 0 ), u 0 ) • • • δ(prd(u k ), u k ). Due to Lemma 1, m 0 σ -→ λ(v). Due to Lemma 2, σ is a sequence of abstractions. Due to Proposition 2, the ω-transition a defined by Pre(a) = Pre(σ) and C(a) = C(σ) is an abstraction. Due to Proposition 1, λ(v) ⊆ Cover(N , m 0 ).

The following definitions are related to an arbitrary execution point of MinCov and are introduced to establish its completeness.

Definition 9. Let m be a marking. Then m is quasi-covered if:

either there exists v ∈ V \ Front with λ(v) ≥ m; or there exists an exploring sequence m σ -→ m ≥ m.

In order to prove completeness of the algorithm, we want to prove that at the beginning of every iteration, any m ∈ Cover(N , m 0 ) is quasi-covered. To establish this assertion, we introduce several lemmas showing that this assertion is preserved by some actions of the algorithm with some prerequisites. More precisely, Lemma 3 corresponds to the deletion of the current vertex, Lemma 4 to the discovery of an acceleration, Lemma 5 to the deletion of a subtree whose marking of the root is smaller than the marking of the current vertex and Lemma 6 to the creation of the children of the current vertex. Lemma 3. Let CT , Front and Acc be the values of corresponding variables at some execution point of MinCov and u ∈ V be a leaf in CT such that the following items hold:

Then all m ∈ Cover(N , m 0 ) are quasi-covered after performing Delete(u). Lemma 4. Let CT , Front and Acc be the values of corresponding variables at some execution point of MinCov. and u ∈ V such that the following items hold:

Then all m ∈ Cover(N , m 0 ) are quasi-covered after performing Prune(u) and then adding u to Front.

-Assume that w is a descendant of u , by a path in CT u = w 0 δ(w0,w1)

-------→ w k = w. Since λ(V \ Front) is an antichain any λ(w i ) is incomparable with any λ(w ) in λ(V \ Front). Since V \ Front does not include new items, the sequence λ(u) -------------→ m is an exploring sequence with m ≥ m * .

• There is an exploring sequence m σ -→ m ≥ m * with some w such that m = λ(w). --------------→ m ≥ m * . Since V \ Front does not include new items, this sequence is an exploring sequence. Lemma 6. Let CT , Front and Acc be the values of corresponding variables at some execution point of MinCov. and u ∈ Front such that the following items hold:

1. All m ∈ Cover(N , m 0 ) are quasi-covered; 2. λ(V \ Front) ∪ {λ(u)} is an antichain; 3. For all a ∈ Acc fireable from λ(u), λ(u) = λ(u) + C(a).

Then after removing u from Front and for all t ∈ T fireable from λ(u), adding a child v t to u in Front with marking of v t defined by λ u (v t ) = λ(u) + C(t), all m ∈ Cover(N , m 0 ) are quasi-covered.

Proof.

Let u ∈ Front, denote by CT = (V , E , λ , δ ) and Front the value of variables CT and Front after removing u from Front and for all transition t ∈ T fireable from λ(u), adding a child v t to u in Front with marking of v t defined by λ (v t ) = λ(u) + C(t). In words, this corresponds to lines 21-25 of MinCov. Assume the assertions of the lemma hold. Let m * ∈ Cov(N , m 0 ). Due to the assertions of the lemma, m * is quasi-covered. By definition, V \ Front = (V \ Front) ∪ {u}. We split the proof in two cases: • There exists w ∈ V \ Front with λ(w) ≥ m * . Since only u has been added to V \ Front and λ(u) is incomparable to any λ(w), m is still quasi-covered.

• There is an exploring sequence m σ -→ m ≥ m * with some w such that m = λ(w). Let σ = σ 0 t 1 σ 1 • • • t k σ k , where t i ∈ T and σ i ∈ Acc * .

-Either there does not exist i ≤ k such that λ(w) + C(σ 0 t 1 σ 1 • • • t i σ i ) ≤ λ(u).

Observe that this implies w = u. Otherwise since from λ(u) no fireable