N Vandecandelaere

F Bosc

C Rey

C Drouet

Peroxide-doped apatites: Preparation and effect of synthesis parameters

Keywords:

This contribution focused on the preparation of peroxide-doped calcium phosphate apatitesin view of potential uses as bioactive bioceramics with antimicrobial functions, and on their main physico-chemical characteristics. Two synthesis routes were investigated. First, the hydrolysis of β-TCP in the presence of H 2 O 2 was followed. However, only elevated concentrations in H 2 O 2 in the medium or temperatures around 150 °C allowed us to reach the complete β-TCP-to-apatite hydrolysis process, and the obtained samples exhibited a high crystallinity state with no non-apatitic chemical environments. The second protocol tested consisted in the direct apatite precipitation in the presence of H 2 O 2 in the medium (at room temperature). This protocol led to single-phased nanocrystalline apatites, and our data indicate that part of the apatitic OH -ions were substituted by oxygenated species, and typically by peroxide ions (quantified). Physico-chemical modifications in the form of an improvement in crystallinity state, an increase in unit cell volume, and the presence of additional Raman bands were noticed and discussed.

Introduction

Calcium phosphates are major candidates for the design of bioceramic-based systems intended to bone regeneration (self-supported scaffolds, injectable bone cements, and implant coatings). In particular, calcium phosphate apatite compounds and predominantly nanocrystalline ones occupy a very peculiar position since they mimic the physicochemical characteristics of bone mineral [START_REF] Eichert | Nanocrystalline apatite-based biomaterials: synthesis, processing and characterization[END_REF].

In addition to bare apatitic systems, a great deal of studies have also been devoted to explore associations between apatite crystals and a variety of (bio)molecules or drugs, such as antibiotics, anticancer drugs, growth factors, and vitamins [START_REF] Gomez-Morales | Progress on the preparation of nanocrystalline apatites and surface characterization: overview of fundamental and applied aspects[END_REF], so as to convey additional properties to be exploited on a localized level at the site of implantation. Beside such hybrid organic/inorganic materials, it is however also possible to modify the biological and/or physico-chemical behavior of apatite systems by adequate ion substitutions. For example, the "doping" of calcium phosphate apatites by magnesium or strontium ions that has been reported (e.g. [START_REF] Drouet | Surface enrichment of biomimetic apatites with biologically-active ions Mg2+ and Sr2+: a preamble to the activation of bone repair materials[END_REF][START_REF] Christoffersen | Effects of strontium ions on growth and dissolution of hydroxyapatite and on bone mineral detection[END_REF], either throughout the lattice or more specifically on the surface of the nanocrystals) is aimed at favoring osteoblast cell activity while limiting osteoclast resorptive functions, which may then be used for locally treating osteoporotic sites. The incorporation of silicate ions in phosphate crystallographic sites has also been shown to improve bone regeneration processes [START_REF] Porter | Effect of sintered silicate-substituted hydroxyapatite on remodelling processes at the bone-implant interface[END_REF]. In another context, the substitution of calcium by lanthanide ions such as europium or terbium ions was also shown to convey luminescence properties to apatite particles that can then be exploited for other (not bone-related) applications such as cancer diagnosis [START_REF] Al-Kattan | Medical potentialities of biomimetic apatites through adsorption, ionic substitution, and mineral/organic associations: three illustrative examples[END_REF][START_REF] Al-Kattan | Preparation and physicochemical characteristics of luminescent apatite-based colloids[END_REF][START_REF] Al-Kattan | Biomimetic nanocrystalline apatites: emerging perspectives in cancer diagnosis and treatment[END_REF].

The substitution of hydroxide OH -ions (located in the so-called "apatitic channels" of the apatite lattice) by other anions has, in contrast, received globally less attention to this date, except for the particular case of A-type carbonation. The substitution of apatitic OH -ions by oxygenated species, and especially by peroxide anions (i.e. species containing at least a O\O covalent bond), could however be seen as a way to modify apatite features that may find new applications in medicine, possibly for bone site asepsis after surgery. Indeed such oxygenated species are characterized by oxidizing properties that are naturally used in vivo (formation of Reactive Oxygenated Intermediates, ROI [START_REF] Lushchak | Oxidative stress and mechanisms of protection against it in bacteria[END_REF][START_REF] Farr | Oxidative stress responses in Escherichia coli and Salmonella typhimurium[END_REF][START_REF] Storz | Bacterial defenses against oxidative stress[END_REF]) for fighting against infections. For instance, phagocytes locally produce superoxide (O 2

2-

) ions to fight against bacteria [START_REF] Rada | Oxidative innate immune defenses by Nox/Duox family NADPH oxidases[END_REF][START_REF] Shenep | Lack of antibacterial activity after intravenous hydrogen peroxide infusion in experimental Escherichia coli sepsis[END_REF]. The generation of ROI is also the mode of action of antibiotics such as fluoroquinolones [START_REF] Albesa | Oxidative stress involved in the antibacterial action of different antibiotics[END_REF]. This explains the use of peroxide-containing materials as antibacterial agents [START_REF] Shenep | Lack of antibacterial activity after intravenous hydrogen peroxide infusion in experimental Escherichia coli sepsis[END_REF][START_REF] Feuerstein | Synergic antibacterial effect between visible light and hydrogen peroxide on Streptococcus mutans[END_REF][START_REF] Muller | Modulation of the H 2 O 2 -induced SOS response in Escherichia coli PQ300 by amino-acids, metal chelators, antioxidants and scavengers of reactive oxygen species[END_REF][START_REF] Pedahzur | The interaction of silver ions and hydrogen peroxide in the activation of Escherichia colia preliminary evaluation on a new long-acting residual drinking water disinfectant[END_REF]. It should also be noted that natural pathways of elimination of such oxygenated species also exist in vivo, so as to regulate their overall activity. This regulation implies in particular specific enzymes such as superoxide dismutases and peroxydases (e.g. catalase), which ensure antioxidizing effects. Despite these statements, the development of oxygenated apatites as "reactive" implantable bioceramics has not received much development in medicine to date.

Although "oxygenated" apatites have not been overly investigated as compared to other substituted apatites, some past studies have however reported the possibility for apatitic channels to incorporate oxygenated species such as H 2 O 2 or O 2 [START_REF] Rey | Étude des Relations Entre Apatites et Composés Moléculaires Oxygénés[END_REF] or molecular ions including O 2

2-(the peroxide ion) and superoxide O 2 - [START_REF] Dugas | Electron-spin resonance characterization of superoxide ions in some oxygenated apatites[END_REF]. Furthermore, the incorporation of such species in the apatite lattice was found to lead to specific modifications as compared to hydroxyapatite [START_REF] Rey | Étude des Relations Entre Apatites et Composés Moléculaires Oxygénés[END_REF][START_REF] Trombe | Mise en Evidence d'une Peroxyapatite Phosphocalcique[END_REF][START_REF] Yu | Local structure of hydroxyperoxy apatite: a combined XRD, FT-IR, Raman, SEM, and solid-state NMR study[END_REF][START_REF] Zhao | Characterization of peroxide ions in hydroxyapatite lattice[END_REF], and in particular a decrease in the FTIR intensity of OH -bands and the appearance of additional Raman bands due to the presence of peroxide O 2 2-ions (in particular at 750 cm -1 due to the symmetrical vibration of the O 2 2-ion). Unit cell parameters were also found to be altered upon apatite "oxygenation", although varying results were reported probably due to different synthesis protocols resulting in different oxygenated species and apatite compositions [START_REF] Rey | Étude des Relations Entre Apatites et Composés Moléculaires Oxygénés[END_REF][START_REF] Trombe | Mise en Evidence d'une Peroxyapatite Phosphocalcique[END_REF].

Taking into account the above statements, the present contribution aims at determining with further details the physico-chemistry of oxygenated apatites which could find future applications for example in bone infection treatments. In this original contribution, the preparation of peroxide-doped apatites was examined, and the impact of synthesis conditions on their physico-chemical characteristicswhich we followed by several complementary techniques (XRD, FTIR, Raman, chemical analyses, and SEM) -was explored. Two different synthesis routes were considered in the presence of H 2 O 2 in the reaction medium: 1) the hydrolysis of beta tricalcium phosphate (β-TCP) into apatite (a type of protocol initiated in early studies [START_REF] Rey | Étude des Relations Entre Apatites et Composés Moléculaires Oxygénés[END_REF][START_REF] Simpson | Oxygen rich apatite[END_REF]), and 2) the direct apatite precipitation at room temperature from aqueous calcium and phosphate solutions.

Materials and methods

Preparation of peroxide-doped apatites

Two types of synthesis protocols were used in this work, either based on the hydrolysis of β-TCP (β-Ca 3 (PO 4 ) 2 ) or on direct precipitation. In both cases, hydrogen peroxide/water media were used.

In the first case, 500 mg of β-TCP (previously synthesized from calcining amorphous tricalcium phosphate at 900 °C for 24 h [START_REF] Rey | Tricalcium phosphate-based ceramics[END_REF]) was mixed with 30 mL of hydrogen peroxide H 2 O 2 (stock solution at 110 vol. oxygen, equivalent to 9.82 mol/L H 2 O 2 ) in deionized water in a closed container, and then heated to 100 °C for 24 h. After cooling, the compounds obtained for varying starting amounts of H 2 O 2 were filtered on Büchner funnel and freeze-dried prior to analysis. Table 1 reports the concentrations in hydrogen peroxide that were tested in this work.

In the second protocol, direct precipitations were carried out in a way similar to the previously reported preparation of nanocrystalline biomimetic apatites [START_REF] Vandecandelaere | Biomimetic apatite-based biomaterials: on the critical impact of synthesis and post-synthesis parameters[END_REF] but in the presence of increasing amounts of H 2 O 2 in the medium. A solution «A» containing 0.3 M of calcium nitrate (Ca(NO 3 ) 2 •4H 2 O) was prepared in a mixture of H 2 O 2 /H 2 O in variable proportions (see Table 2). A solution «B» of di-ammonium hydrogenphosphate (NH 4 ) 2 HPO 4 , 0.6 M, was prepared in parallel in the same H 2 O 2 /H 2 O medium. A volume of solution «A» was then poured into the doubled volume of solution «B», under stirring. The precipitation medium was then left to mature for 3 days at room temperature before filtration on Büchner funnel and freeze-drying.

Physico-chemical characterization

The nature and crystallographic structural features of the crystalline phases obtained in this work were investigated by X-ray diffraction (XRD) using a Seifert XRD 3000 TT diffractometer (Cu Kα1Kα2 radiation). The counting time was of 60 s for every step of 0.04°, typically in the 2θ range 20-70°. Unit cell parameters and volume were evaluated by XRD data treatment thanks to the JANA 2006 software, considering the systems as single-phased apatites (P6 3 /m space group).

Complementary analyses were run by Fourier transform infrared (FTIR) spectroscopy. Spectra were recorded on a Nicolet 5700 spectrometer in the range 400-4000 cm -1 (64 scans, resolution of 4 cm -1 ). Spectral deconvolutions were carried out as previously described [START_REF] Vandecandelaere | Biomimetic apatite-based biomaterials: on the critical impact of synthesis and post-synthesis parameters[END_REF], after subtraction of a linear baseline, in the 400-800 cm -1 wavenumber range corresponding to the ν 2 ν 4 (PO 4 ) and ν(OH) vibration modes of phosphate and hydroxide ions respectively, using the ORIGIN 8.1 software.

Raman spectra were recorded on a Horiba Jobin-Yvon LabRAM HR 800 spectrometer, typically in the range 100-4000 cm -1 using a λ = 532 nm laser. The acquisition was realized with an exposure time of 180 s and 6 accumulations for each point with an optical objective of ×100 and a diaphragm opening of 100 μm.

Scanning Electron Microscopy (SEM) analyses were performed on a LEO 435 VP microscope operated at 10-15 kV.

The chemical composition of the samples obtained was drawn from the measurement of ionic contents. The determination of the calcium and orthophosphate (PO 4 3-and HPO 4 2-ions) contents were obtained, after dissolution of the samples in perchloric acid, by way of EDTA complexometry and spectrophotometry (using the phospho-vanadomolybdenic complex, with λ = 460 nm) [START_REF] Charlot | Chimie Analytique Quantitative[END_REF], respectively. Peroxide titration was performed by manganimetry titration using potassium permanganate KMnO 4 [START_REF] Charlot | Les méthodes de la chimie analytique: Analyse Qualitative et minérale[END_REF], exploiting the redox couple MnO 4 -(purple)/ Mn 2+ (colorless) and the reaction:

2MnO - 4 þ 5H 2 O 2 þ 6H þ →2Mn 2þ þ 5O 2 þ 8H 2 O: ð1Þ
For this titration, powder apatite samples were first dissolved in concentrated perchloric acid (HClO 4 ), and the obtained solution was then titrated by addition of a solution of KMnO 4 (0.005 M). The equivalence was then reached when the purple coloration of the permanganate ion persisted in the reacting medium.

Results and discussion

As mentioned above, two types of protocols were investigated in this work. The general goal was to obtain single-phased peroxide-doped apatites allowing varying amounts of peroxide doping. Also, the search for rather low crystallinity states and/or small constitutive crystals was an appealing secondary objective in view of obtaining potentially reactive apatite compounds [START_REF] Vandecandelaere | Biomimetic apatite-based biomaterials: on the critical impact of synthesis and post-synthesis parameters[END_REF] in view of future medical applications.

Synthesis by hydrolysis of β-TCP in H 2 O 2 /H 2 O media

In a first step, we investigated the possible hydrolysis of β-TCP into apatite by heating in aqueous medium (mixtures of H 2 O 2 and H 2 O in pre-selected proportions), at a temperature of 100 °C for 24 h. Fig. 1 reports the XRD patterns obtained for 0, 25% and 75% (in volume) of H 2 O 2 (stock solution at 110 vol. oxygen) in H 2 O. In this figure, the characteristic patterns of the initial β-TCP compound (corresponding to JCPDS card No. 09-169) as well as of a reference stoichiometric hydroxyapatite HA (JCPDS card No. 09-432) were also added for comparative purposes.

Results indicated (see Fig. 1) that the sample treated at 100 °C for 24 h in the absence of H 2 O 2 (sample H0%) was still composed of β-TCP, thus witnessing the absence of hydrolysis into apatite in these conditions. In contrast, increasing proportions of H 2 O 2 in the reacting medium were found to allow a progression of the TCP-to-apatite hydrolysis rate, as shown by the gradual decrease of the intensity of diffraction peaks related to β-TCP in favor of HA peaks. Among the conditions tested here however, only the sample H75% was found to be exclusively composed of an apatite phase, indicating that the complete hydrolysis of the β-TCP starting phase had then taken place. The introduction of hydrogen peroxide in the medium was thus found to favor this hydrolysis; this process being complete only for elevated proportions of H 2 O 2 in the medium. Besides, the XRD pattern of sample H75% (see Fig. 1) showed wellresolved diffraction peaks characteristic of a high degree of crystallinity for the apatite phase obtained by this hydrolysis route (contrarily to biomimetic nanocrystalline apatites [START_REF] Gomez-Morales | Progress on the preparation of nanocrystalline apatites and surface characterization: overview of fundamental and applied aspects[END_REF][START_REF] Vandecandelaere | Biomimetic apatite-based biomaterials: on the critical impact of synthesis and post-synthesis parameters[END_REF]). SEM analysis carried out on the samples mentioned above (see the typical example of sample H75% in Fig. 2) showed that they were composed of acicular crystals of dimensions ranging from 0.5 to 2 μm in width and of several tens of microns in length. These micron-sized crystal dimensions (rather than nanometer-sized for bone apatite or synthetic analogs) agree well with the high degree of crystallinity noticed for all the samples, but are elements that disfavor surface reactivity aspects [START_REF] Vandecandelaere | Biomimetic apatite-based biomaterials: on the critical impact of synthesis and post-synthesis parameters[END_REF].

FTIR analysis was also carried out on sample H75%. Vibration bands characteristic of phosphate chemical environments in an apatite phase were observed at 471 cm -1 (ν 2 (PO 4 )), 560/571/605 cm -1 (ν 4 (PO 4 )), 960 cm -1 (ν 1 (PO 4 )) and 1040/1089 cm -1 (ν 3 (PO 4 )). Spectral deconvolution of the ν 2 ν 4 (PO 4 ) region, in the 400-800 cm -1 range, was also processed as was explained previously in detail [START_REF] Vandecandelaere | Biomimetic apatite-based biomaterials: on the critical impact of synthesis and post-synthesis parameters[END_REF]. The absence of bands related to non-apatitic chemical environments for this sample was noted, which may probably be related to the mode of preparation (at 100 °C) which does not favor such hydrated environments [START_REF] Vandecandelaere | Biomimetic apatite-based biomaterials: on the critical impact of synthesis and post-synthesis parameters[END_REF]. The presence of a high proportion of hydrogen peroxide in the medium therefore did not have a detectable impact on the development of non-apatitic chemical environments on the constitutive apatite crystals. FTIR revealed, on the other hand, the presence of a non-negligible amount of apatitic HPO 4 2-ions (contribution at 550 cm -1 ). The detection of an isolated band at 887 cm -1 , assignable to P\OH bonds in HPO 4

2-ions [1] also confirmed the presence of such species. These hydrogenphosphate ions are commonly observed in hydrolysis processes of different calcium phosphates (DCPD, DCPA, α-TCP) involving a dissolution-reprecipitation mechanism and an acidification of the solution related to the formation of apatite.

FTIR spectral analysis around 632 cm -1 (OH libration mode) only pointed out a very slight shoulder making it difficult at this stage to give direct evidence of the presence of regular apatitic OH -ions. Taking into account the presence of peroxide ions in the medium, the low intensity of this libration mode is probably related to a high proportion of substitution of apatitic OH -ions by peroxide ions (present in the medium) during the apatite formation. Bands due to peroxide ions are not, unfortunately, visualizable by the FTIR technique (being not suitable to detect symmetrical diatomic species such as O 2 2-, O 2 -or O 2 ) for direct confirmation; however the inset of Fig. 3 shows the appearance of additional contributive absorptions (as compared to the typical case of hydroxyapatite [START_REF] Vandecandelaere | Biomimetic apatite-based biomaterials: on the critical impact of synthesis and post-synthesis parameters[END_REF]) at 3524 and 3555 cm -1 . The location of these bands suggests a possible attribution to hydrogen bonds involving some "residual" OH -ions in the lattice that could explain the slight libration shoulder at 632 cm -1 .

The above findings show that only elevated amounts of H 2 O 2 in the medium (typically 75% in volume of stock solution at 110 vol. oxygen) allowed us to obtain a complete hydrolysis of β-TCP at 100 °C for 24 h. Generally speaking, the hydrolysis of β-TCP has been shown to follow a complex mechanism with several successive steps [START_REF] Rey | Étude des Relations Entre Apatites et Composés Moléculaires Oxygénés[END_REF]: 1) the partial dissolution of the β-TCP phase, 2) the increase of Ca/P ratio in the reaction medium, 3) the formation of an apatite phase and 4) the evolution of this phase towards stoichiometry. However, these stages may be influenced by synthesis conditions such as temperature or duration of treatment. Additional experiments were then carried out (without H 2 O 2 ) for up to 6 days at 100 °C or up to 48 h at 150 °C in view of obtaining single-phased apatite phases from β-TCP crystals. Some of the corresponding XRD patterns are reported in Fig. 4. Our results indicated that after 1, 2, 3 or 6 days of reaction at 100 °C, all samples remained composed of β-TCP (see for example samples H0% and H0c% corresponding to 1 and 6 days of reaction respectively). Therefore, an increase of reaction time (at 100 °C) did not allow for the TCP-toapatite transformation. In contrast, the sample prepared by treatment of β-TCP at 150 °C for 48 h led to an XRD pattern corresponding to an apatite phase with no detectable traces of residual tricalcium phosphate (Fig. 4, pattern H0f). Therefore, in this work, an elevation of temperature was the only way to obtain the complete TCP-to-apatite transformation in the absence of high amounts of H 2 O 2 in the medium. Unfortunately, this XRD pattern is still indicative of a highly-crystallized state (with no non-apatitic ionic environment detectable by FTIR), which is thus bound to exhibit a low surface reactivity [START_REF] Vandecandelaere | Biomimetic apatite-based biomaterials: on the critical impact of synthesis and post-synthesis parameters[END_REF].

All our attempts to obtain, via this TCP hydrolysis process, low(er)crystallinity apatite phases and/or containing non-apatitic features (as for bone apatite or biomimetic counterparts [START_REF] Eichert | Nanocrystalline apatite-based biomaterials: synthesis, processing and characterization[END_REF][START_REF] Rey | Bone mineral: update on chemical composition and structure, 3rd Meeting on Bone[END_REF]) were unsuccessful. The investigation of this preparation route was thus discontinued and our attention turned to the exploration of a second type of protocol involving the direct precipitation, at room temperature, of (eventually peroxide-doped) apatite phases, which is described in the following section.

Synthesis by direct apatite precipitation in the presence of H 2 O 2

This second protocol aimed at exploring the preparation of peroxidedoped apatites by direct precipitation from calcium and phosphate sources. Fig. 5 reports the XRD patterns obtained for samples matured for 3 days in a H 2 O 2 /H 2 O medium corresponding to 0, 10%, 25% and 50% of H 2 O 2 stock solution (110 vol. oxygen) in water. As can be seen, all the patterns obtained showed very similar features corresponding to poorly-crystallized apatite phases. No secondary phase could be detected. An increase in the overall resolution of the patterns was evidenced upon increasing the oxygen peroxide proportion in the medium, which is particularly visible for peaks (202) and (312). The presence of H 2 O 2 in the precipitating medium thus tends to increase the crystallinity of the obtained apatite phase (for identical synthesis parameters); however the compounds obtained by this route remained poorly-crystallized.

XRD profile fitting analyses (JANA software) indicated that this crystallinity improvement was mainly linked to an increase of the mean crystallite width (determined from application to peak (310) of Hosemann and Vogel [START_REF] Vogel | Evaluation of paracrystalline distortions from line broadening[END_REF] or Scherrer formulas [START_REF] Scherrer | Estimation of size and internal structure of colloidal particles by means of Röntgen rays[END_REF]), which continuously increased from 2.6 to 7.4 nm for H 2 O 2 proportions in the medium from 0 to 50% (Table 3). In contrast, mean crystallite lengths remained essentially unchanged. The Hosemann and Vogel distortion parameter (giving a measure of the crystal disorder within the lattice) in the [002] direction, denoted g 002 , was found to gradually decrease with the proportion of H 2 O 2 in the medium: a drop of 15% was indeed observed for H 2 O 2 proportion increasing from 10 to 50%. Although the value of g 002 was systematically found to be greater for samples prepared in the presence of H 2 O 2 rather than without H 2 O 2 , its decrease upon peroxidation of the medium could also contribute to the improvement in crystallinity observed.

The XRD profile analysis also pointed out a significant increase of the "a" unit cell parameter, from 9.432 to 9.470 Å, and a (moderate) decrease of the «c» parameter from 6.870 to 6.864 Å, when the initial amount of H 2 O 2 increased from 0 to 50% (Table 3). This variation in unit cell parameters thus led to an increase of unit cell volume for syntheses realized in the presence of H 2 O 2 (Table 3). The unit cell volume increased rapidly up to a concentration of H 2 O 2 in solution of 2.46 M (corresponding to 25% stock solution of H 2 O 2 ), and then stabilized at a value close to 533 Å 3 (Fig. 6). These findings strongly suggest the progressive incorporation of rather large chemical species in the apatitic core of the nanocrystalsmost probably oxygenated species due to the presence of H 2 O 2 -provoking a dilatation of the unit cell. Beyond an initial proportion of H 2 O 2 in the medium around 25% of stock solution, the observed stabilization of the unit cell volume suggests however the attainment of a maximal amount of oxygenated species incorporated in the apatite core of the nanocrystals.

SEM observations of samples prepared in the presence or in the absence of H 2 O 2 were then carried out (not shown); however no morphological differences were found.

In order to complete these analyses, a titration of incorporated peroxide groups was carried out by manganimetry assessments (see experimental section) for the samples 3d-10%H 2 O 2 , 3d-25%H 2 O 2 and 3d-50%H 2 O 2 , leading to a peroxide content of 0.014 ± 0.001, 0.013 ± 0.001 and 0.018 ± 0.001 mmol/100 mg of apatite, respectively. These findings thus confirmed the presence of peroxide groups in the composition of these apatite samples. Note that this titration method only quantifies peroxide groups such as O 2 2-ions and possibly H 2 O 2 molecules which could be associated, like water molecules, to these apatites. This titration method is not directly suited to quantify other (metastable) oxygenated species such as superoxide or ozonide ions. These radical ions are however unstable, their lifetime in solution is very short, and their decomposition may lead to peroxides that can then be titrated. FTIR analyses were then carried out on these samples (Fig. 7). The spectra were all found to be characteristic of nanocrystalline biomimetic apatites, without additional bands. The OH -bands at ca. 3570 and 631 cm -1 appeared less easily detectable for samples precipitated in the presence of hydrogen peroxide. This phenomenon could be related to the substitution of OH -ions by oxygenated species such as peroxide ions (previously quantified) in the apatite lattice. Spectral deconvolution of the ν 2 ν 4 (PO 4 ) region additionally unveiled a decrease of about 50% of the amount of non-apatitic HPO 4 2-ions (contribution at 530 cm -1 ) in the presence of peroxide ions in the medium. These findings suggest that the maturation state of the apatite phase tends to improve in the presence of peroxides, which is thus accompanied by a decrease in non-apatite environments. The «accelerating» crystal growth effect mentioned above, as witnessed from XRD analyses by a noticeable increase in crystallinity state in the presence of hydrogen peroxide, is in good agreement with this result.

Raman spectroscopy analyses were carried out at this stage (Fig. 8). In addition to bands regularly observed for nanocrystalline apatites, the presence of additional Raman bands was evidenced for samples prepared in the presence of H 2 O 2 , in the form of 3 main modifications:

m 1 in the range 750-850 cm Very few data are available in the literature on the Raman characteristics of peroxidized or oxygenated apatites. Rey [START_REF] Rey | Étude des Relations Entre Apatites et Composés Moléculaires Oxygénés[END_REF] indicated that several types of peroxide ions could be found in apatite channels, such as «simple» peroxide ion O 2 In the present study (Fig. 8), the presence of bands located at 450 cm -1 (relative to large molecular species) or at 1552 cm -1 (O 2 ) was not detected, suggesting that these chemical species are not present in detectable amounts in the prepared samples. In contrast, the m 1 bands observed between 750 and 850 cm -1 probably correspond to peroxide bands reported previously by Rey [START_REF] Rey | Étude des Relations Entre Apatites et Composés Moléculaires Oxygénés[END_REF] around 800 cm -1 and globally assigned to a "O\O stretching" and by Zhao et al. [START_REF] Zhao | Characterization of peroxide ions in hydroxyapatite lattice[END_REF] at 750 cm -1 assigned to the peroxide ion O 2 2-. Moreover, bands from the m 2 region in the range 1080-1140 cm -1 can probably be related to the band observed at 1150 cm -1 by Rey [START_REF] Rey | Étude des Relations Entre Apatites et Composés Moléculaires Oxygénés[END_REF] which was attributed to the vibration of the superoxide ion O 2 -. The yellowish color of samples obtained in the presence of H 2 O 2 (in comparison to the white color of samples prepared without H 2 O 2 ) is indeed an element in favor of the presence of at least traces of superoxide ion in our samples. The m 3 bands (between 2800 and 3100 cm -1 ), on the other hand, do not seem to be easily assignable to bands previously described in the literature to our knowledge and their exact attribution remains at this point uncertain. Although this vibration domain could correspond to C\H stretching, the presence of organic compounds associated to the powders remains quite unlikely as no such species were involved in the synthesis.

Although bands related to OH -ions in apatitic environment were not clearly visible by FTIR, the band at 3570 cm -1 is identifiable by Raman spectroscopy for all samples (doped and non-doped), thus revealing the presence of remaining OH -ions in the lattice for all samples.

In addition, it can be noted that two low-intensity Raman bands at 881 and 910 cm -1 -also detectable for non-doped sampleswere found to become more clearly visible for samples prepared in the presence of H 2 O 2 . A vibrational contribution in this range (e.g. 880 cm -1 ) was attributed to HPO 4 2-ions in apatites [START_REF] Penel | MicroRaman spectral study of the PO 4 and CO 3 vibrational modes in synthetic and biological apatites[END_REF]. This increase in intensity could probably be related to the improved crystallinity state of samples prepared in the presence of hydrogen peroxide, as was shown above by XRD analyses, thus allowing for better spectral resolution.

The above findings thus indicate that it is possible, by way of direct precipitation, to synthesize peroxide-loaded nanocrystalline apatites in the presence of hydrogen peroxide in the precipitating medium, without formation of detectable secondary phases (even for high H 2 O 2 contents, tested here up to 50% of stock solution at 110 vol. oxygen). The presence of H 2 O 2 in the precipitating medium led to various physico-chemical modifications: the crystallinity state of the apatite phase was found to improve for increasing H 2 O 2 proportions in the medium; a noticeable increase in unit cell volume was evidenced strongly supporting the idea of an incorporation of oxygenated species in the apatite lattice; peroxide ions were in particular evidenced and quantifiable by manganimetry, showing that this synthesis route was appropriate to prepare apatite samples with varying peroxide contents; the presence of at least traces of superoxide ion was also suspected; and the presence of additional Raman bands linked to such oxygenated species was pointed out. Based on these elements, associated to the nano-sized dimensions of the constitutive crystals and to the remaining presence of non-apatitic species, this synthetic route appears as very appropriate for the production of peroxidedoped reactive apatite materials.

Concluding remarks

In this contribution, two ways of preparation of peroxide-doped calcium phosphate apatites were investigated.

First, the hydrolysis of β-TCP in the presence of H 2 O 2 was followed. By this protocol, however, only elevated concentrations in H 2 O 2 in the medium allowed us to obtain single-phased apatite compounds (attesting for the complete TCP-to-apatite hydrolysis) at 100 °C, unless higher temperatures (tested here: 150 °C) were used. Moreover, the apatite samples obtained by this route always exhibited a high crystallinity state with no non-apatitic chemical environments (the presence of which has been related to the surface reactivity of apatitic compounds [START_REF] Eichert | Nanocrystalline apatite-based biomaterials: synthesis, processing and characterization[END_REF][START_REF] Gomez-Morales | Progress on the preparation of nanocrystalline apatites and surface characterization: overview of fundamental and applied aspects[END_REF][START_REF] Drouet | Surface enrichment of biomimetic apatites with biologically-active ions Mg2+ and Sr2+: a preamble to the activation of bone repair materials[END_REF][START_REF] Rey | Physico-chemical properties of nanocrystalline apatites: implications for biominerals and biomaterials[END_REF]).

The second protocol tested consisted in the direct apatite precipitation from an aqueous calcium and phosphate solutions and in the presence of H 2 O 2 in the medium (at room temperature). This route allowed us to obtain single-phased nanocrystalline apatites in a wide range of H 2 O 2 proportions in the precipitating medium. Moreover, our data indicate that part of the apatitic OH -ions were replaced in this case by oxygenated species, and typically by peroxide ions (quantified) and at least traces of superoxide ions. Several physico-chemical modifications such as an improvement in crystallinity state, an increase in unit cell volume, and the presence of additional bands in the Raman spectra were noticed and discussed.

Fig. 1 .Fig. 2 .

 12 Fig. 1. XRD patterns for samples obtained by hydrolysis of β-TCP at 100 °C for increasing H 2 O 2 proportions in the medium.

Fig. 3 .Fig. 4 .

 34 Fig. 3. FTIR spectrum for sample H75%.

Fig. 5 .

 5 Fig. 5. XRD patterns for samples (3 days maturation) obtained by direct precipitation in varying proportions of H 2 O 2 .

- 1 , 1 - 1 -

 111 constituted by 3 bands at 793, 827 and 845 cm -m 2 in the range 1080-1140 cm -1 , constituted by 4 bands at 1096, 1103, 1114 and 1124 cm -and m 3 in the range 2800-3100 cm -1 , constituted by 3 bands at 2858, 2883 and 2940 cm -1 .

3 )Fig. 6 .Fig. 7 .

 367 Fig. 6. Evolution of unit cell volume for samples prepared by direct precipitation versus initial concentration in H 2 O 2 in the medium.

Fig. 8 .

 8 Fig. 8. Raman spectra for samples (3 days maturation) obtained by direct precipitation in varying proportions of H 2 O 2 (the band at 960 cm -1 was truncated for greater visibility).

Table 1

 1 Initial proportions of H 2 O 2 tested for the β-TCP synthesis route.

	Sample reference Vol.% of H 2 O 2 stock solution	Initial molar concentration
		(at 110 vol. oxygen) in the medium	in H 2 O 2 in the medium (M)
	H0%	0%	0
	H5%	5%	0.49
	H10%	10%	0.98
	H25%	25%	2.46
	H50%	50%	4.91
	H75%	75%	7.37

Table 2

 2 Initial proportions of H 2 O 2 tested for the direct precipitation synthesis route.

	Sample reference Vol.% of H 2 O 2 stock solution	Molar concentration in
		(at 110 vol. oxygen) in the medium	H 2 O 2 in the medium (M)
	3d-10% H 2 O 2	10%	0.98
	3d-25% H 2 O 2	25%	2.46
	3d-50% H 2 O 2	50%	4.91

Table 3

 3 XRD profile fitting results (λCu) for nanocrystalline apatite synthesized at room temperature in various H 2 O 2 /H 2 O media (3 days of maturation in solution).

	Sample reference	Scherrer

Acknowledgments

This work was financially supported by the French "Agence Nationale de la Recherche" (ANR) by way of the PICF BioCapabili project.


Paul Brunet

Damien Pous

Decidability of Identity-free Relational Kleene Lattices

Families of binary relations are important interpretations of regular expressions, and the equivalence of two regular expressions with respect to their relational interpretations is decidable: the problem reduces to the equality of the denoted regular languages.

Putting together a few results from the literature, we first make explicit a generalisation of this reduction, for regular expressions extended with converse and intersection: instead of considering sets of words (i.e., formal languages), one has to consider sets of directed and labelled graphs.

We then focus on identity-free regular expressions with converse-a setting where the above graphs are acyclic-and we show that the corresponding equational theory is decidable. We achieve this by defining an automaton model, based on Petri Nets, to recognise these sets of acyclic graphs, and by providing an algorithm to compare such automata.

Introduction

Binary relations appear everywhere in mathematics and computer science, together with the operations of union (∪), intersection (∩), composition (○), converse (. ∨ ), reflexive-transitive closure (. ⋆ ), and the constants identity (Id) and empty relation (∅). As such, an algorithm for deciding the equivalence of expressions built with these operators with respect to their relational interpretations is a very desirable goal. However such an algorithm has yet to be found.

Regular expressions [START_REF] Conway | Regular algebra and finite machines[END_REF], where only the operators ∪, ○, . ⋆ , Id, and ∅ are allowed, are the most famous example of a decidable fragment [START_REF] Kleene | Representation of Events in Nerve Nets and Finite Automata[END_REF]. In this setting, it is now well-known that the equivalence of two expressions in all relational interpretations is equivalent to the equality of the regular languages denoted by these expressions. Several equational or semi-equational theories are known to be complete for this fragment [START_REF] Kozen | On Kleene Algebras and closed semirings[END_REF][START_REF] Kozen | A completeness theorem for Kleene Algebras and the algebra of regular events[END_REF][START_REF] Krob | A Complete System of B-Rational Identities[END_REF].

The converse operation can also be added to regular expressions, and the resulting theory remains decidable (see [START_REF] Bloom | Notes on equational theories of relations[END_REF][START_REF] Ésik | Equational properties of Kleene algebras of relations with conversion[END_REF] or [START_REF] Brunet | Kleene algebra with converse[END_REF]). In this case, decidability is obtained by 1) reducing the problem of equivalence of two expressions to the equality of some regular sets of words over an extended alphabet, and 2) defining automata constructions to recognise these sets.

Freyd and Scedrov sketched an algorithm for representable allegories [8, page 208], that is, expressions with composition, intersection, converse, and identity, but without union or reflexivetransitive closure. Similar constructions were given independently by Andréka and Bredikhin [START_REF] Andréka | The equational theory of union-free algebras of relations[END_REF], in a more comprehensive way. The key idea is the following: if we restrict ourselves to the above syntax (variables, composition, intersection, converse, identity), we get what is called ground terms. Such a term u can be represented as labelled directed graphs G(u) with two distinguished vertices called the input and the output. A variable a corresponds to a graph with one edge labelled by a linking the input to the output. The identity is represented by the graph with a single vertex and no edges, The composition of two graphs with disjoints sets of vertices can be performed by identifying the output of the first graph and the input of the second one. The operation corresponding to the intersection ) consists in merging the inputs of the two graphs, as well as their outputs. And finally, converse is obtained by swapping the inputs and the outputs. Some examples are given in Figure 1.

G(a): G G • a G G • G G G(b ∧ c ∨ ): G G • b @ @ • c h h G G G ((a ⋅ (b ∧ c)) ∧ d): • b " " c F F G G • a I I d S S • G G G ((a ⋅ b) ∧ (a ∧ c)): • b # # G G • a G G a H H • G G • c p p
) c H H G G • a F F d R R • G G • ❦ s s b ) ) G G • ❦ s s a F F a H H • G G ❙ • c e e ❱
These graphs can be endowed with a preorder relation G ◂ F , defined by the existence of a graph homomorphism from F to G (preserving inputs and outputs). For instance the graph corresponding to (a ⋅ (b ∧ c)) ∧ d is smaller than the graph of (a ⋅ b) ∧ (a ⋅ c), thanks to GE homomorphism depicted in Figure 2 using dotted arrows. The key result from Freyd and Scedrov [8, page 208], or Andréka and Bredikhin [2, Theorem 1], is that for any two ground terms u, v, u is contained in v under any relational interpretation if and only if G(u) ◂ G(v).

This is for ground terms; to handle the whole syntax, we need to add union and reflexive-transitive closure. It suffices for that to consider sets of graphs: to each expression e, one can associate a set of graphs G(e). Writing X ◂ for the downward closure of a set of graphs X by the relation ◂, we obtain the following generalisation of the above result: for any two expressions e and f , e is contained in f under any relational interpretation if and only if G(e) ⊆ G(f ) ◂ . (Theorem 6 in the sequel-this result is almost there in the work by Andréka et al. [START_REF] Andréka | The equational theory of Kleene lattices[END_REF], but this explicit formulation is new, to the best of our knowledge.)

This result encompasses the case of plain regular expressions, whose graphs are just words and for which the preorder ◂ reduces to isomorphism, but also the case of regular expressions with converse, whose graphs are words over a duplicated alphabet and for which the preorder ◂ can be reformulated in terms of the rewriting system proposed by Esik et al. [START_REF] Bloom | Notes on equational theories of relations[END_REF][START_REF] Ésik | Equational properties of Kleene algebras of relations with conversion[END_REF].

Our main contribution is then to exploit this characterisation to obtain decidability for identityfree regular expressions with intersection, whose equational theory has been studied by Andréka et al. [START_REF] Andréka | The equational theory of Kleene lattices[END_REF]. The reason why we need to exclude identity and converse is that in presence of intersection, they yield cyclic graphs, and we do not know how to handle such graphs. We hope to get rid of this assumption in future work.

The key concept which we introduce is a new kind of finite automaton, allowing us to recognise sets of graphs that are downward-closed w.r.t. the graph embedding relation ◂. To give some intuition about this automaton model, let us look at the example from Figure 2, and try to build sequentially a morphism

h from F = G((a ⋅ b) ∧ (a ⋅ c)) to G = G((a ⋅ (b ∧ c)) ∧ d).
• We start by placing a token α ○ on A. We know that for h to be a morphism, it has to preserve the input of the graph, so we map A to position 0 in G.

• There are two outgoing edges from A, both labelled by a. We split token α ○ into β ○ and γ ○, and move β ○ to position B and γ ○ to position C. We then map the positions of both tokens to position 1 in G, which is consistent with h being a morphism, thanks to the arc (0, a, 1).

• Now we try to move β

○. B has one outgoing edge, labelled by b. We may move β ○ to D, and using the arc (1, b, 2) in G we map D to position 2. • Then we can look at γ ○. We have to move it to position D, and thanks to the arc (1, c, 2) we can confirm the map of D to 2, and merge back β ○ and γ ○.

At the end, we have only one token, placed on the output of F , and during the procedure we have mapped all positions in F to positions in G, while preserving all labelled edges. This kind of procedure is reminiscent of Petri nets [START_REF] Murata | Petri nets: Properties, analysis and applications[END_REF][START_REF] Petri | Fundamentals of a theory of asynchronous information flow[END_REF][START_REF] Petri | Kommunikation mit Automaten[END_REF]: at each step we relate tokens to positions in G, and fire transitions according to the edges of G. This is the basic idea behind the notion of Petri automata which we introduce in Section 2. For instance the Petri automaton we will construct for the term (a ⋅ b) ∧ (a ⋅ c) is depicted in Figure 3, and the procedure sketched above can then be formally described as a reading of the graph G in this automaton.

Given an expression e, we show in Section 3 how to build a Petri automaton that recognises exactly the graphs in G(e) ◂ . We then show in Section 4 how to compare Petri automata. Several difficulties arise, that do not appear with classical word automata. Our solution nevertheless uses a standard coinductive approach, where we define an appropriate notion of simulation.

Expressions and languages

In this section we consider the full signature ⟨∧, ∨, ⋅, ⋅ ⋆ , ⋅ ∨ , 0, 1⟩ of Kleene lattices with conversion. We fix a set X of variables, and we denote by Reg ∨∧ X the set of expressions build from variables in X with these connectives. These expressions are meant to be interpreted in relational models: ⋅ corresponds to the composition of relations; ∨ to the union; ∧ to the intersection; R * to the reflexive transitive closure of a relation R; and R ∨ to the converse of R. The constants 0 and 1 are respectively interpreted as the empty relation and the identity relation. For any set S, we write P (S) ∶= {P P ⊆ S } for the set of subsets of S. Let A → B be the functions from A to B and A ⇢ B the partial maps from A to B. dom (f ) denotes the domain of a partial map f . If σ ∶ X → P (S × S) is an interpretation of the alphabet X into some space of relations, we write σ for the unique homomorphism extending σ from Reg ∧- X to P (S × S). We say that two expressions e and f are relationally equivalent, written Rel ⊧ e = f , if for any relational interpretation σ we have σ(e) = σ(f ). Similarly, we write Rel ⊧ e ⩽ f if σ(e) ⊆ σ(f ) holds for any σ.

The ground terms are defined by the following sub-syntax:

u, v, w ∈ W X ∶∶= x ∈ X w ⋅ w w ∧ w w ∨ 1 .
We let G range over 2-pointed labelled directed graphs, which we simply call graphs in the sequel.

Those are tuples ⟨V, E, ι, o⟩ with V a finite set of vertices, E ⊆ V × X × V a set of edges labelled with X, and ι, o ∈ V the two distinguished vertices, respectively called input and output.

To each ground term w, we associate such a graph G(w). The graph for 1 has only one vertex, both input and output. The graph of a has one edge labelled by a linking its input to its output. The composition of two graphs with disjoints sets of vertices can be performed by identifying the output of the first graph and the input of the second one. The intersection on graphs consists in merging their inputs and merging their outputs. The converse consists simply in exchanging the input and the output of a graph. See Figure 4 for a graphical description of this construction. Those graphs were introduced independently by Freyd and Scedrov [8, page 208], and Andréka and Bredikhin [START_REF] Andréka | The equational theory of union-free algebras of relations[END_REF]. Another useful notion is the notion of morphism between graphs:

G(1) ∶= G G • G G G(a) ∶= G G • a G G • G G G(w ∨ ) ∶= • o o G(w) G G • o o G(u ⋅ v) ∶= G G • G(u) G G • G(v) G G • G G G(u ∧ v) ∶= G G • G(u) @ @ G(v) T T • G G
Definition 1 (Graph morphism, preorder on ground terms)

A graph morphism from ⟨V 1 , E 1 , ι 1 , o 1 ⟩ to ⟨V 2 , E 2 , ι 2 , o 2 ⟩ is a map h ∶ V 1 → V 2 such that h(ι 1 ) = ι 2 , h(o 1 ) = o 2 , and (p, x, q) ∈ E 1 entails (h(p), x, h(q)) ∈ E 2 .
We denote by ◂ the relation on graphs defined by G ◂ G ′ if there exists a graph morphism from G ′ to G. This relation gives rise to a preorder on ground terms, written ⊲ and defined by u

⊲ v if G(u) ◂ G(v). *
Given a set S of graphs, we write S ◂ for its downward closure w.r.t. ◂:

S ◂ ∶= {G G ◂ G ′ , G ′ ∈ S }.
Similarly, we write S ⊲ for the downward closure of a set of ground terms w.r.t. ⊲.

As explained in the introduction, the above preorder on ground terms precisely characterises inclusion under arbitrary relational interpretations: [8, page 208]). For all ground terms u, v ∈ W X , we have

Theorem 2 ( [2, Theorem 1], or
Rel ⊧ u ⩽ v ⇔ u ⊲ v .
To extend this result to the expressions we consider in this paper, we introduce the following generalisation of the language of a regular expression. Sets of words become sets of ground terms.

Definition 3 (Term language of an expression)

The term language denoted by an expression e ∈ Reg ∨∧ X , written e , is the set of ground terms defined inductively as follows:

x ∶= {x} e ⋅ f ∶= {w ⋅ w ′ w ∈ e and w ′ ∈ f } e ∨ f ∶= e ∪ f e ∧ f ∶= {w ∧ w ′ w ∈ e and w ′ ∈ f } e ⋆ ∶= ⋃ n∈◆ {w 1 ⋅ ⋯ ⋅ w n ∀i, w i ∈ e } e ∨ ∶= {w ∨ w ∈ e } 1 ∶= {1} 0 ∶= ∅ . *
We need a slight refinement of a lemma established by Andréka, Mikulás, and Németi [START_REF] Andréka | The equational theory of Kleene lattices[END_REF]:

Lemma 4.
For all expression e ∈ Reg ∨∧ X X, and all relational interpretation σ ∶ X → P (S × S), we have

σ(e) = ⋃ w∈ e σ(w) = ⋃ w∈ e ⊲ σ(w) .
Proof. The first equality is exactly [1, Lemma 2.1]; for the second one, we use the fact that σ(w) ⊆ σ(u) whenever w ⊲ u, thanks to Theorem 2 (i.e., [2, Theorem 1]).

The above definitions make it possible to characterise inclusion under all relational interpretation in terms of downward-closed term languages. To obtain decidability, we need to go one step further, by considering graph languages.

Definition 5 (Graph language of an expression)

The graph language of an expression e, denoted by G(e) is the set of graphs associated to the ground terms in e : G(e) ∶= {G(w) w ∈ e }. *

We finally obtain the following characterisation, which allows us to reduce validity in Rel to an equality of graph languages. Theorem 6. The following properties are equivalent, for all expressions e, f ∈ Reg ∨∧ X :

(i) Rel ⊧ e = f , (ii) e ⊲ = f ⊲ , (iii) G(e) ◂ = G(f ) ◂ .
Proof. We give a detailed proof in Appendix A.The implication (ii) ⇒ (i) follows easily from Lemma 4, and (iii) ⇒ (ii) is a matter of unfolding definitions. For (i) ⇒ (iii), we mainly use [2, Lemma 3].

The above statement can also be reformulated in terms of inclusions, to match the result announced in the introduction:

Rel ⊧ e ⩽ v if and only if e ⊆ f ⊲ if and only if G(e) ⊆ G(f ) ◂ .
Also notice that while by definition G(e) only contains graphs emanating from ground terms, this is not the case for its closure G(e) ◂ . For instance, G((a ⋅ b) ∧ (c ⋅ d)) ◂ contains the following graph, which is not the graph of any ground term.

• b

)

) e G G • a F F c H H • G G • d e e
The above result holds for the whole syntax of regular expressions with converse and intersection. However, in the remainder of the paper, we have to focus on expressions without converse and identity. This is because in combination with intersection, these two operations introduce cycles in the graphs associated to ground terms. Consider for instance the graphs for a ∧ 1 and a ∧ b ∨ :

G(a ∧ 1) = G G • a Ó Ó G G ; G(a ∧ b ∨ ) = G G • a @ @ • b h h G G .
Since reflexive-transitive closure (⋅ ⋆ ) implicitly contains an occurrence of the identity, we also have to replace this operator with transitive closure (⋅ + ). We thus work we expressions from Reg ∧- X , defined with the following syntax: e, f ∈ Reg ∧- X ∶∶= x ∈ X e ∧ f e ∨ f e ⋅ f e + 0. Accordingly, ground terms are restricted to the following syntax:

u, v, w ∈ W - X ∶∶= x ∈ X w ⋅ w w ∧ w.

Petri Automata

Before getting to our definition of automata, we recall the standard notion of Petri net.

Definition 7 (Petri Net)

A Petri Net is a structure N = ⟨P, T, F, W, M 0 ⟩ where:

• P and T are finite disjoints sets, respectively of places and transitions;

• F ⊆ (P × T ) ∪ (T × P ) is a set of arcs, called the flow relation;

• W ∶ (P × T ) ∪ (T × P ) → ◆ is a weight function, such that W (f ) = 0 if f ∈ F ; • M 0 ∶ P → ◆ is the initial marking.
Given a marking M in a net N , a transition τ ∈ T is enabled if for any place p such that (p, τ ) is in the flow relation F , we have W (p, τ ) ⩽ M (p). In that case, τ can fire, and it results in a new marking

M ′ such that M ′ (p) = M (p) -W (p, τ ) + W (τ, p).
A marking is called accessible if it can be obtained by successively firing transitions starting from M 0 . *

To present examples in a simple way, we use the standard graphical representation of Petri nets: they are represented as graphs, with round nodes for places and rectangular nodes for transitions. The flow relation is simply represented by arrows; the places appearing in the initial marking have an additional incoming arrow.

A Petri net is said to be one-bounded if in any accessible marking M , no place is marked with more than one token. Such markings can be seen as finite sets of places; we call them configurations in the sequel, and we let ξ, Ξ range over them. Bounded nets form an interesting class of nets, because many problems which are undecidable in the general case become decidable in this setting: whereas general Petri nets have an infinite set of accessible markings, they are finitely many in a bounded net.

Our notion of Petri Automata is defined below. The main difference with regular Petri nets is the labelling with letters from the alphabet X of all arcs coming out of transitions. Note that this slightly differs from the usual notion of labelled Petri net, where the labels are put on transitions.

Definition 8 (Petri Automaton)

A Petri automaton is a structure ⟨N, L, F ⟩ where:

• N = ⟨P, T, F, W, M 0 ⟩ is a one-bounded Petri net such that:
the weight W (f ) of all arcs f that appear in F is equal to 1; -all transitions τ ∈ T , have at least one incoming arc and one outgoing arc, meaning that there are places p, q ∈ P such that (p, τ ) ∈ F and (τ, q) ∈ F ;

there is an initial place ι such that M 0 contains only one token, placed in ι.

• L ∶ (T × P ) ∩ F → X is a labelling function;

• F ⊆ P (P ) is a set of final configurations. *

A transition τ in a Petri automaton can be alternatively described by a pair [τ ] = (s, t) where:

• s = {p (p, τ ) ∈ F } is the input of τ , often denoted by • τ , and

• t = {(x, q) (τ, q) ∈ F and x = L(τ, q) } is the output of τ .
Notice that this differs from the usual notion of output of a transition in a Petri net: in the usual setting τ • is just the set of places reachable from the τ . Here we add to each place the label of the arc reaching it.

For commodity reasons, we will thus define Petri automata using quadruples A = ⟨P, T , ι, F ⟩ with ι the initial place and

T = {(s, t) ∃τ ∈ T ∶ [τ ] = (s, t) }.
Graphical representations of such automata are given in Figures 3 and5. Now we explain how to use Petri automata to define languages of graphs. We first describe what is a run of an automaton, and then how to use runs to read graphs.

Let A = ⟨P, T , ι, F ⟩ be a Petri automaton. We write ξ τ → A ξ ′ when the configuration ξ ′ can be obtained by firing some transition τ in the configuration ξ. A set of transitions T ⊆ T is called compatible if their inputs are pairwise disjoint. If furthermore all transitions in T are enabled in a configuration ξ, one can observe that the configuration ξ ′ reached after firing them successively does not depend on the order in which they are fired. In that case we write ξ (Note that a run ξ is uniquely determined by ξ 0 and the sequence (τ k ): all subsequent configurations can be computed deterministically.)

T → A ξ ′ .
C 2 a G G D C 4 a G G D A 0 b G G a # # B 1 c d d b 0 0 3 c d d b 0 0 5 d G G F E E E E 6 G G G G G G
Example 10 (An accepting run in the automaton from Figure 5) Consider the run ξ = ⟨(ξ 0 , ξ 1 , ξ 2 , ξ 3 , ξ 4 , ξ 5 , ξ 6 ) , (τ 0 , τ 1 , τ 2 , τ 3 , τ 4 , τ 5 )⟩, with

ξ 0 ={A} , ξ 1 ={B, G} , ξ 2 = ξ 4 ={C, E, G} , ξ 3 = ξ 5 ={D, E, G} , ξ 6 ={F } . τ 0 =({A} , {(b, B), (a, G)}) , τ 1 =({B} , {(c, C), (b, E)}) , τ 2 = τ 4 =({C} , {(a, D)}) , τ 3 =({D, E} , {(c, C), (b, E)}) , τ 5 =({D, E} , {(d, F )}) .
We can easily check, using the firing rules of a Petri net that:

{A} τ0 G G {B, G} τ1 G G {C, E, G} τ2 G G {D, E, G} τ3 G G {C, E, G} τ4 G G {D, E, G} τ5 G G {F, G} .
As {A} is the initial configuration and {F, G} ∈ F , this run is accepting. It can be represented graphically as in Figure 6. ∎

As in finite-state automata, we now need to specify how to read a graph in an automaton. This is done by linking the intermediate configurations of a run to vertices in the graph, and by imposing conditions to match transitions with the edges of the graph.

Definition 11 (Reading along a run, parallel reading, language of a run) A reading of G = ⟨V, E, ι, o⟩ along a run ξ = ⟨(ξ k ) 0⩽k⩽n , (s k , t k ) 0⩽k<n ⟩ is a sequence (ρ k ) 0⩽k⩽n such that for all k, ρ k is a map from ξ k to V w , ρ 0 (ξ 0 ) = {ι}, ρ n (ξ n ) = {o}, and ∀k < n, the following holds:

2 a
) )

4 a ) ) 1 c G G b T T 3 c G G b T T 5 d ) ) G G 0 b G G a Q Q 6 G G
Figure 7: Trace of the run depicted in Figure 6 • all tokens in the input of the transition are mapped to the same vertex in the graph:

∀p, q ∈ s k , ρ k (p) = ρ k (q);
• the images of tokens in ξ k that are not in the input of the transition are unchanged:

∀p ∈ ξ k ∖ s k , ρ k (p) = ρ k+1 (p),
• each pair in the output of the transition can be mapped to an edge of the graph with the same label:

∀p ∈ s k , ∀(x, q) ∈ t k , (ρ k (p), x, ρ k+1 (q)) ∈ E.
Similarly, we define a parallel reading ρ along some parallel run Ξ = ⟨(Ξ k ) 0⩽k⩽n , (T k ) 0⩽k<n ⟩ by requiring that: ρ 0 (Ξ 0 ) = {ι}, ρ n (Ξ n ) = {o}, and ∀k < n the following holds:

• ∀p ∈ Ξ k ∖ ⋃ (s,t)∈T k s, ρ k+1 (p) = ρ k (p); • ∀(s, t) ∈ T k , ∀p, q ∈ s, ρ k (p) = ρ k (q); • ∀(s, t) ∈ T k , ∀p ∈ s, ∀(x, q) ∈ t, (ρ k (p), x, ρ k+1 (q)) ∈ E.
The language of a run ξ, denoted by L (ξ) is the set of graphs that can be read along ξ. *

The language of a Petri automaton is finally obtained by considering all accepting runs.

Definition 12 (Language recognised by a Petri automaton)

The language recognised by A , written L (A ), is the following set of graphs:

L (A ) ∶= ⋃ ξ accepting in A L (ξ) . *
The language of a run ξ can be characterised using a single graph which we call the trace of ξ: graphs are accepted by ξ exactly when they are smaller than the trace of ξ, according to ◂ (Lemma 14 below). For instance the trace of the run presented in Figure 6 is shown in Figure 7.

This trace is constructed by creating a vertex k for each transition τ k = (s k , t k ) of the run, plus a final vertex n. We add an edge (k, x, l) whenever there is some place q such that (x, q) ∈ t k , and τ l is the first transition after τ k in the run with q among its inputs, or l = n if there is no such transition in the run. Formally: Definition 13 (Trace of a run) Let ξ = ⟨(ξ k ) 0⩽k⩽n , (s k , t k ) 0⩽k<n ⟩ be run. For an index k ⩽ n and a place q, let ν(k, q) be either the smallest index l such that k ⩽ l and q ∈ s l , or n if there is no such index. The trace of ξ is the graph Tr (ξ) ∶= ⟨{0, . . . , n} , E ξ , 0, n⟩ with E ξ ∶= {(k, x, ν(k + 1, q)) (x, q) ∈ t k }. We write Tr (A ) for the set of traces associated to the accepting runs of A . * Lemma 14. For any accepting run ξ, we have G ∈ L (ξ) if and only if G ◂ Tr (ξ).

Proof. Suppose there exists a graph morphism h from Tr (ξ) to G. Then we can build a reading by defining ρ k (p) = h(ν(k, p)) for 0 ⩽ k ⩽ n and p ∈ ξ k . On the other hand, if we have a reading (ρ k ) 0⩽k⩽n of G, we can build a morphism h by letting h(k) = ρ k (p) for any p ∈ s k . As (ρ k ) k is a reading, h is well defined. The details of this proof can be found in Appendix B.

As a corollary, we obtain the following characterisation of the language of a Petri automaton.

Corollary 15. L (A ) = Tr (A ) ◂ .
The left-hand side language is defined through readings along accepting runs, which a local and incremental notion and which allows us to define simulations in Section 4. In contrast, the right-hand side language is defined globally, which eases the following construction of an automaton recognising the language of an expression.

From expressions to automata

We now show how to associate to any expression e ∈ Reg ∧- X an automaton A (e) that recognises the language G(e) ◂ . In fact the produced automaton has an even stronger connection with e: the graphs in G(e) are exactly the traces of accepting runs in A (e).

Definition 16

To each expression e ∈ Reg ∧- X , we associate a Petri automaton A (e) defined inductively as follows:

• A (x) ∶= ⟨{0, 1} , {({0} , {(x, 1)})} , 0, {{1}}⟩ • A (0) ∶= ⟨{0} , ∅, 0, ∅⟩ • A (e 1 ∨ e 2 ) ∶= ⟨P 1 ∪ P 2 , T , ι 1 , F 1 ∪ F 2 ⟩ with T ∶= T 1 ∪ T 2 ∪ {({ι 1 } , t) ({ι 2 } , t) ∈ T 2 }. • A (e 1 ⋅ e 2 ) ∶= ⟨P 1 ∪ P 2 , T , ι 1 , F 2 ⟩ with T ∶= T 1 ∪ T 2 ∪ {(f, t) f ∈ F 1 and ({ι 2 } , t) ∈ T 2 }. • A (e + 1 ) ∶= ⟨P 1 , T , ι 1 , F 1 ⟩ with T ∶= T 1 ∪ {(f, t) f ∈ F 1 and ({ι 1 } , t) ∈ T 1 }. • A (e 1 ∧ e 2 ) ∶= ⟨P 1 ∪ P 2 , T , ι 1 , F ⟩ with F ∶= {f 1 ∪ f 2 f 1 ∈ F 1 , f 2 ∈ F 2 } and T ∶= {(s, t) i ∈ {1, 2} , (s, t) ∈ T i , ι i ∉ s } ∪ {({ι 1 } , t 1 ∪ t 2 ) ({ι 1 } , t 1 ) ∈ T 1 , ({ι 2 } , t 2 ) ∈ T 2 }
(In the inductive cases, we assume that A (e i ) = ⟨P i , T i , ι i , F i ⟩ for i ∈ {1, 2}, with P 1 ∩ P 2 = ∅.) *

We prove by induction on e that A (e) is indeed a Petri automaton; for the one-boundedness assumption, we add to the induction hypothesis the fact that for any configuration ξ accessible in A (e), if there is a final configuration f ∈ F such that f ⊆ ξ, then f = ξ. Another invariant is that the initial place never appears in a final configuration, nor in the outputs of any transition. Note that the place ι 2 becomes unreachable by construction in the cases for union, composition and intersection, so that it could safely be removed, together with the associated transitions.

Theorem 17 (Correctness). For all expression

e ∈ Reg ∧- X , L (A (e)) = G (e) ◂ .
Proof. As explained above, we prove a stronger result, namely Tr (A (e)) = G(e) (up to graph isomorphisms-see Appendix C). This allows us to conclude thanks to Corollary 15.

Remark 18. If e is an expression without intersection, it can be shown that the transitions in A (e) are all of the form ({p} , {(x, q)}), with only one input and one output. In consequence, the accessible configurations are singletons, and the resulting Petri automaton has the structure of a Nondeterministic Finite-state Automaton (NFA). Actually, in that case, the construction we described above is just a variation on Thompson's construction [START_REF] Thompson | Regular expression search algorithm[END_REF], with inlined epsilon transition elimination.

Combined with Theorem 6 from Section 1, the above theorem allows us to reduce the problem of deciding whether Rel ⊧ e = f to the problem of checking whether L (A (e 1 )) = L (A (e 2 )). By symmetry, it then suffices to decide inclusion of Petri automata languages.

Comparing automata

We want to compare automata by testing if any graph accepted by A 1 is also accepted by A 2 . Let us go back to standard non-deterministic finite-state automata (NFA), to find intuitions. In that setting an automaton over some alphabet Σ is defined by A = ⟨Q, ι, F, ∆⟩ where Q is a finite set of states, ι is an initial state, F is a set of finite states F and ∆ is a set of transitions of the form (p, a, q) where p and q are states and a is a letter. Consider two automata

A 1 = ⟨Q 1 , ι 1 , F 1 , ∆ 1 ⟩ and A 2 = ⟨Q 2 , ι 2 , F 2 , ∆ 2 ⟩. L(A 1 ) ⊆ L(A 2
) means that for any word w = a 1 ⋯a n accepted by A 1 , w is also accepted by A 2 . Thus if there is an execution in A 1 recognising w then there is an execution in A 2 recognising w. One can then put them together side by side like so:

ι 1 a1 → A1 p 1 a2 → A1 ⋯ an → A1 p n ∈ F 1 ι 2 a1 → A2 q 1 a2 → A2 ⋯ an → A2 q n ∈ F 2
Thus trying to prove that L(A 1 ) ⊆ L(A 2 ) amounts to finding a method to build from any run in A 1 a corresponding run in A 2 . This can be done by computing a simulation between the automaton A 1 and the determinised automaton of A 2 . A simulation between these automata is then a relation

≼ ⊆ Q 1 × P (Q 2 ) such that • ι 1 ≼ {ι 2 }, and if p ≼ P and p ∈ F 1 , then P ∩ F 2 ≠ ∅; • if p ≼ P and (p, a, p ′ ) ∈ ∆ 1 then p ′ ≼ P ′ , where P ′ ∶= {p ′ (p, a, p ′ ) ∈ ∆ 2 , p ∈ P }. p a G G p ′ P ≼ a G G P ′ ≼
If such a relation can be found, then for any accepting execution in A 1 , we can use the relation to extract a corresponding execution in A 2 . It is also possible to prove that if the language of A 1 is indeed included in the language of A 2 , then such a relation exists. This gives us an algorithm to decide the inclusion of languages, because the set of states of both automata being finite, there is only a finite number of candidates for ≼.

We follow a similar approach for Petri automata, but we need to make several important adjustments. Consider two automata A 1 = ⟨P 1 , T 1 , ι 1 , F 1 ⟩ and A 2 = ⟨P 2 , T 2 , ι 2 , F 2 ⟩, we try to show that for any graph G accepted by A 1 , G is recognised by A 2 . By Lemma 14, this amounts to proving that for any accepting run ξ in A 1 , Tr (ξ) is recognised by some accepting run ξ ′ in A 2 . Leaving nondeterminism apart, the first idea that comes to mind is to find a relation between the configurations in A 1 and the configurations in A 2 , that satisfy some conditions on the initial and final configurations, and such that if

ξ k ≼ ξ ′ k and ξ k τ → A1 ξ k+1 , then there is a configuration ξ ′ k+1 in A 2 such that ξ k+1 ≼ ξ ′ k+1 , ξ ′ k τ ′ → A2 ξ ′
k+1 , and these transition steps are compatible in some sense. However, such a definition will not give us the result we are looking for. Consider the two runs on the left-hand side:

B B A 1 a V V b 8 8 C 2 c G G D X 2 ′ c G G Z W 1 ′ a V V b 8 8 Y Y {A} 1 G G {B, C} 2 G G {B, D} {W } ≼ 1' G G {X, Y } ≼ 2' G G {Y, Z} ≼
The trace of the first run corresponds to the ground term a ∧ (b ⋅ c), and the trace of the second one corresponds to (a ⋅ c) ∧ b. These two terms are incomparable, but the relation ≼ depicted on the right-hand side satisfies the previously stated conditions.

The problem here is that in Petri automata, runs are token firing games. To adequately compare two runs, we need to closely track the tokens. For this reason, we will relate a configuration ξ k in A 1 not only to a configuration ξ ′ k in A 2 , but to a map η k from ξ ′ k to ξ k . This will enable us to associate to each token situated on some place in P 2 to another token placed on A 1 .

We want to find a reading of Tr (ξ) in A 2 , i.e. a run in A 2 together with a sequence of maps associating places in A 2 to positions in Tr (ξ). Consider the picture below. Since we already have a reading of Tr (ξ) along ξ (by defining ρ k (p) = ν(k, p), as in the proof of Lemma 14), it suffices to find maps from the places in A 2 to the places in A 1 (the maps η k ): the reading of Tr (ξ) in A 2 will be obtained by composing the η k with the ρ k .

Tr (ξ)

ξ 0 τ0 G G ξ 1 τ1 G G ⋯ τn-1 G G ξ n τn G G ξ n+1 ξ ′ 0 η0 y y τ ′ 0 G G ξ ′ 1 τ ′ 1 G G η1 y y ⋯ τ ′ n-1 G G ξ ′ n ηn y y τ ′ n G G ξ ′ n+1 ηn+1 y y ρ0 U U ρ1 `ρn ρn+1 e e
We need to impose some constraints on the maps (η k ) to ensure that (ρ k ○ η k ) 0⩽k⩽n is indeed a correct reading in A 2 . First, we need to ascertain that the a transition τ ′ k in A 2 may be fired from the reading state ρ k ○ η k to reach the reading state ρ k+1 ○ η k+1 . Furthermore, as for NFAs, we want transitions τ k and τ ′ k to be related: specifically, we require τ ′ k to be included (via the morphisms η k and η k+1 ) in the transition τ k . This is meaningful because transition τ k contains a lot of information about the vertex k of Tr (ξ) and about ρ: the labels of the outgoing edges from k are the labels on the output of τ k , and the only places that will ever be mapped to k in the reading ρ are exactly the places in the input of τ k .

B A 0 a U U b 9 9 C Y ✐ s s X ✐ s s 0 ′ a U U a 9
9 Z ❳ This already shows an important difference between the simulations for NFAs and Petri automata. For NFAs, we relate a transition p a → p ′ to a transition q a → q ′ with the same label a. Here the transitions ξ k τ k → A1 ξ k+1 may have different labels. Consider the step represented on the right, corresponding to a square in the above diagram. The output of 0 has a label b that doesn't appear in 0' , and 0' has two outputs labelled by a. Nevertheless this satisfies the conditions informally stated above, indeed, a ∧ b ⩽ a ∧ a holds. However this definition is not yet satisfactory. Consider the two runs below:

C A 0 a G G B 1 b U U c 9 9 D Y 1 ′ b G G T T X 0 ′ a U U a 9 9 Z Z 2 ′ c G G U
Their traces correspond respectively to the ground terms a ⋅ (b ∧ c) and

(a ⋅ b) ∧ (a ⋅ c). The problem is that a ⋅ (b ∧ c) ⩽ (a ⋅ b) ∧ (a ⋅ c
), but with the previous definition, we cannot relate these runs: they do not have the same length. The solution here consists in grouping the transitions 1' and 2' together, and consider these two steps as a single step in a parallel run. This last modification gives us a notion of simulation we can really work with.

Definition 19 (Simulation) A relation ≼ ⊆ P (P 1 ) × P (P 2 ⇢ P 1 ) between the configurations of A 1 and the partial maps from the places of A 2 to the places of A 1 is called is simulation between A 1 and A 2 if:

• {ι 1 } ≼ {[ι 2 ↦ ι 1 ]}; • if ξ ≼ E and ξ (s,t) → A1 ξ ′ , then ξ ′ ≼ E ′
where E ′ is the set of all η ′ such that there is some η ∈ E and a compatible set of transitions T ⊆ T 2 such that:

-dom (η) T → A2 dom (η ′ ); -∀(s ′ , t ′ ) ∈ T, η(s ′ ) ⊆ s and ∀(x, q) ∈ t ′ , (x, η ′ (q)) ∈ t; -∀p ∈ dom (η) , (∀(s ′ , t ′ ) ∈ T, p ∉ s ′ ) ⇒ η(p) = η ′ (p).
• if ξ ≼ E and ξ ∈ F 1 , then there must be some η ∈ E such that dom (η) ∈ F 2 . *

We will now prove that the language of A 1 is contained in the language of A 2 if and only if there exists such a simulation. We first introduce the following notion of embedding.

Definition 20 (Embedding) Let ξ = ⟨(ξ k ) 0⩽k⩽n , (τ k ) 0⩽i<n ⟩ be a run in A 1 , and Ξ = ⟨(Ξ k ) 0⩽k⩽n , (T i ) 0⩽i<n ⟩ a parallel run in A 2 .
An embedding of Ξ into ξ is a sequence (η i ) 0⩽i⩽n of maps such that for any i < n, we have:

• η i is a map from Ξ i to ξ i ;

• the image of T i by η i is included in τ i , meaning that for any (s, t) ∈ T i , for any p ∈ s and (x, q) ∈ t, η i (p) is contained in the input of τ i and (x, η i+1 (q)) is in the output of τ i ;

• the image of the tokens in Ξ i that do not appear in the input of T i are preserved (η i (p) = η i+1 (p)) and their image is not in the input of τ i . 6. Notice that is it necessary to have a parallel run instead of a simple one: to find something that matches transition 1 , we need to fire two transitions in parallel.

ξ i τi G G ξ i+1
There is a close relationship between simulations and embeddings:

Lemma 21. Let A 1 and A 2 be two Petri automata, the following are equivalent:

1. there exists a simulation ≼ between A 1 and A 2 ;

2. for any accepting run ξ in A 1 , there is an accepting parallel run Ξ in A 2 that can be embedded into ξ.

Proof. If we have a simulation ≼, let ξ = ⟨(ξ k ) 0⩽k⩽n , (τ k ) 0⩽k<n ⟩ be an accepting run in A 1 . By the definition of simulation, we can find a sequence of sets of maps (E k ) 0⩽k⩽n such that E 0 = {[ι 2 ↦ ι 1 ]} and ∀k, ξ k ≼ E k . Furthermore, we can extract from this a sequence of maps (η k ) 0⩽k⩽n and a sequence of parallel transitions (T k ) 0⩽k<n such that (η k ) is an embedding of ⟨(dom (η k )) 0⩽k⩽n , (T k ) 0⩽k<n ⟩ (which is accepting) into ξ. This follows directly from the definitions of embedding and simulation.

On the other hand, if we have property 2., then we can define a relation ≼ by saying that ξ ≼ E if there is an accepting run ξ ′ = ⟨(ξ ′ k ) 0⩽k⩽n , (τ k ) 0⩽k<n ⟩ in A 1 such that there is an index

k 0 : ξ = ξ ′ k0 ; C 2 a G G D C 4 a G G D A 0 b G G a % % B 1 c b 5 5
3 c b 5 5
5 d G G F E E E E G G G G G G β ❣ t t c G G δ ❢ u u a G G ζ ❢ u u b G G η ❙ η ❙ α ❣ u u b Y Y b 5 5 d G G κ ❲ γ ( b G G ǫ ❲ ǫ ❲ c G G θ ❞ v v a G G ι ❞ v v
Figure 8: Embedding of a parallel run into the run from Figure 6.

and the following holds: η ∈ E if there is an accepting parallel run Ξ = ⟨(Ξ k ) 0⩽k⩽n , (T k ) 0⩽k<n ⟩ and (η ′ k ) 0⩽k⩽n an embedding of Ξ into ξ such that η = η ′ k0 . It is then immediate to check that ≼ is indeed a simulation.

If η is an embedding of Ξ into ξ, we can easily check that (ρ i ○ η i ) 0⩽i⩽n is a parallel reading of Tr (ξ) along Ξ in A 2 , as illustrated by this diagram:

Tr (ξ) ξ 0 τ0 G G ξ 1 τ1 G G ⋯ τn-1 G G ξ n τn G G ξ n+1 Ξ 0 η0 y y T0 G G Ξ 1 T1 G G η1 y y ⋯ Tn-1 G G Ξ n ηn y y Tn G G Ξ n+1 ηn+1 y y ρ0 U U ρ1 `ρn ρn+1 f f
Thus, it is clear that once we have such a run Ξ with the sequence of maps η, we have that Tr (ξ) is indeed in the language of A 2 . The more difficult question is the completeness of this approach: if Tr (ξ) is recognised by A 2 , is it always the case that we can find a run Ξ that may be embedded into ξ? The answer is affirmative, thanks to Lemma 23 below. If (ρ j ) 0⩽j⩽n is a reading of G along ξ = ⟨(ξ k ) 0⩽k⩽n , (s k , t k ) 0⩽k<n ⟩, we write active(j) for the only position in ρ j (s j )1 .

Definition 22 (Consistent ordering)

⩿ is a consistent ordering on G = ⟨V, E, ι, o⟩ if ⟨V, ⩿⟩ is a linear order and (p, x, q) ∈ E entails p ⩿ q. * Lemma 23. Let G ∈ L (A 2 ) and ⩿ be any consistent ordering on G. Then there exists a run ξ and a reading (ρ j ) 0⩽j⩽n of G along ξ such that ∀k, active(k) ⩿ active(k + 1).

Proof. The proof of this result is achieved by taking any run ξ accepting G, and then exchanging transitions in ξ according to ⩿, while preserving the existence of a reading. The details of this proof being a bit technical, we moved them to Appendix D. This enables us to build an embedding from any reading of Tr (ξ) in A 2 .

Lemma 24. Let ξ a accepting run of A 1 . Then Tr (ξ) is in L (A 2 ) if and only if there is a accepting parallel run in A 2 that can be embedded into ξ.

Proof. The detailed proof of this result can be found in Appendix E.

For the if direction, we build a parallel reading from the embedding, as explained above. For the other direction, we consider a reading of Tr (ξ) in A 2 along some run ξ ′ . Notice that the natural ordering on ◆ is consistent for Tr (ξ); we may thus change the order of the transitions in ξ ′ (using Lemma 23) and group them adequately to obtain a parallel reading Ξ that embeds in ξ.

So we know that the existence of embeddings is equivalent to the inclusion of languages, and we previously established that it is also equivalent to the existence of a simulation relation. Hence, the following characterisation holds: Theorem 25. Let A 1 and A 2 be two Petri automata. L (A 1 ) ⊆ L (A 2 ) if and only if there exists a simulation relation ≼ between A 1 and A 2 .

Proof. By Lemmas 14, 21 and 24.

As Petri automata are finite, there are finitely many relations in P (P (P 1 ) × P (P 2 ⇢ P 1 )). The existence of a simulation thus is decidable, allowing us to prove the main result: Theorem 26. Given two expressions e, f ∈ Reg ∧- X , testing whether Rel ⊧ e = f is decidable.

Proof. By Theorems 6, 17 and 25, and reasoning by double inclusion.

Conclusions and directions for future work

By introducing Petri automata, we proved the decidability of the equivalence of identity-free regular expressions with intersection, with respect to their relational interpretations. Actually, this also holds for their language interpretations, because Andréka et al. showed in [START_REF] Andréka | The equational theory of Kleene lattices[END_REF] that the classes of identityfree relational Kleene lattices and identity-free language Kleene lattices coincide. They differ however when we include the identity constant, or the converse operation. The construction and algorithm presented here were implemented in OCaml as an exercise. The resulting program is available online as an interactive applet [START_REF] Brunet | Web appendix to this abstract[END_REF].

By adding ǫ-transitions to Petri automata, we could partly cope with the identity, in the sense that we can build automata to recognise the graph languages of expressions over the signature ⟨∨, ∧, ⋅, ⋅ ⋆ , 1, 0⟩. However, we did not find a way of comparing ǫ-Petri automata: the notion of simulation we described here is not equivalent to the inclusion of languages for these automata.

Similarly, we could define a variant of Petri automata for recognising the graph languages associated to expressions with converse: it suffice to consider a duplicated alphabet. However, we did not find a proper way of extending our notion of simulation to capture language inclusion of such automata.

A. Omitted proof: Theorem 6

We want to establish that for any regular expressions with intersection and converse e and f , the following are equivalent:

(i) Rel ⊧ e = f , (ii) e ⊲ = f ⊲ , (iii) G(e) ◂ = G(f ) ◂ .
We will in fact prove an equivalent result, being that these are equivalent:

(a) Rel ⊧ e ⩽ f , (b) e ⊆ f ⊲ , (c) G(e) ⊆ G(f ) ◂ . (c)⇒(b) Suppose G(e) ⊆ G(f ) ◂ , let u ∈ e be a ground term. Necessarily there is some graph G ∈ G(f ) such that G(u) ◂ G. By definition of G(f ), there is some term v ∈ f such that G = G(v).
This means that u ⊲ v, thus proving that u ∈ f ⊲ . (a)⇒(c) In order to prove this last implication, we need the following lemma, which is due to Andréka and Bredikhin.

Lemma 27 ( [2, Lemma 3]). Let S be a base set, i, j ∈ S, v ∈ W X , G(v) = ⟨V v , E v , ι v , o v ⟩ and σ ∶ X → P (S × S). The following are equivalent:

1. (i, j) ∈ σ(v);

2. ∃h ∶ V v → S such that h(ι v ) = i; h(o v ) = j and (p, a, q) ∈ E v ⇒ (h(p), h(q)) ∈ σ(a).

Let e, f ∈ Reg ∨∧ X two expressions such that Rel ⊧ e ⩽ f , and u ∈ e such that G(u) = ⟨V u , E u , ι u , o u ⟩; we can build an interpretation σ ∶ X → P (V u × V u ) by specifying: σ(a) ∶= {(p, q) (p, a, q) ∈ E u } .

It is quite simple to check that σ(u) = {(ι u , o u )}. As Rel ⊧ e ⩽ f and Lemma 4, we know that

σ(u) ⊆ σ(f ) = ⋃ v∈ f σ(v).
Thus there is some v ∈ f such that (ι u , o u ) ∈ σ(v). By Lemma 27 we get that there is a map h ∶ V v → V u such that h(ι v ) = ι u ; h(o v ) = o u and (p, a, q) ∈ E v ⇒ (h(p), h(q)) ∈ σ(a). Using the definition of σ, we rewrite this last condition as (p, a, q) ∈ E v ⇒ (h(p), a, h(q)) ∈ E u . Thus h is a graph morphism from G(v) to G(u), proving that G(u) ◂ G(v), hence G(u) ∈ G(f ) ◂ .

C. Omitted proof: Lemma 17

We have to prove that Tr (A (e)) ≡ G (e), where ≡ denotes equality of sets of graphs, up to graph isomorphisms. We proceed by induction on e ∈ Reg ∧- X ; we recall the inductive definition of A (e) (Definition 16), giving the arguments for the correctness for each inductive case.

• A (x) ∶= ⟨{0, 1} , {({0} , {(x, 1)})} , 0, {{1}}⟩

G G 0 x G G 1
Proof. The only accepting run here is

ξ = ({0} ({0},{(x,1)}) → {1}),
and Tr (ξ) = → 0

x → 1 → is the graph of the only ground term in x .

• A (0) ∶= ⟨{0} , ∅, 0, ∅⟩ Proof. As there are no final configuration, no execution is accepting in this automaton. Hence Tr (A (0)) = ∅ = G(0).

• A (e 1 ∨ e 2 ) ∶= ⟨P 1 ∪ P 2 , T , ι 1 ,

F 1 ∪ F 2 ⟩ with T = T 1 ∪ T 2 ∪ {({ι 1 } , t) ({ι 2 } , t) ∈ T 2 }.
Proof. If ξ = ⟨(ξ k ) 0⩽k⩽n , (τ k ) 0⩽k<n ⟩ is an accepting run in A (e 1 ∨ e 2 ), then ξ 0 = {ι 1 } and either ∀k, τ k ∈ T 1 and ξ is accepting in A 1 , or τ 0 = ({ι 1 } , t) and ⟨({ι 2 } , ξ 1 , ⋯, ξ n ), (({ι 2 } , t), τ 1 , ⋯, τ n-1 )⟩ is an accepting run in A Proof. If ξ = ⟨(ξ k ) 0⩽k⩽n , (τ k ) 0⩽k<n ⟩ is an accepting run in A (e 1 ⋅ e 2 ), then ξ 0 = {ι 1 }. There must also be some m such that:

ξ 1 = ⟨(ξ k ) 0⩽k⩽m , (τ k ) 0⩽k<m ⟩ is accepting in A (e 1 ), in particular ξ m ∈ F 1 ;

τ m = (ξ m , t), with ({ι 2 } , t) ∈ T 2 ;

ξ 2 = ⟨({ι 2 } , ξ m+1 , ⋯, ξ n ), (({ι 2 } , t), τ m+1 , ⋯, τ n-1 )⟩ is an accepting run in A (e 2 ).

Furthermore, it can be shown that Tr (ξ) ≡ Tr ξ 1 ⋅ Tr ξ 2 . The isomorphism is:

π ∶ Tr (ξ) → Tr ξ 1 ⋅ Tr ξ 2 k ↦ k ∈ V ξ 1 if k < m k ↦ k -m ∈ V ξ 2 if k ⩾ m
Thus we can deduce that:

G(e 1 ⋅ e 2 ) = G(e 1 ) ⋅ G(e 2 ) ≡ Tr (A (e 1 )) ⋅ Tr (A (e 2 )) ≡ Tr (A (e 1 ⋅ e 2 ))

• A (e + 1 ) ∶= ⟨P 1 , T , ι 1 , F 1 ⟩ with T = T 1 ∪ {(f, t) f ∈ F 1 and ({ι 1 } , t) ∈ T 1 }.

Proof. The proof is extremely similar to the case of e 1 ⋅ e 2 , simply with multiple accepting runs separated by transitions in (f, t) with f final and ({ι 1 } , t) ∈ T 1 . Note that the construction does not add any transitions ending in ι 1 .

Figure 1 :

 1 Figure 1: Graphs associated to some ground terms

Figure 2 :

 2 Figure 2: A graph homomorphism.

Figure 3 :

 3 Figure 3: The automaton corresponding to the term (a ⋅ b) ∧ (a ⋅ c).

Figure 4 :

 4 Figure 4: Graphs corresponding to ground terms.

Figure 5 :

 5 Figure 5: A Petri automaton. The initial state is A, and the final configurations are {I} and {F, G}.

Figure 6 : 5 Definition 9 (

 659 Figure 6: An accepting run in the automaton from Figure 5

Figure 8

 8 Figure 8 illustrates the embedding of some parallel run, with trace((b ⋅ c ⋅ a ⋅ b) ∧ (b ⋅ b ⋅ c ⋅ a)) ⋅ d, intothe run presented in Figure6. Notice that is it necessary to have a parallel run instead of a simple one: to find something that matches transition 1 , we need to fire two transitions in parallel.There is a close relationship between simulations and embeddings:

  (b)⇒(a) Let e, f ∈ Reg ∨∧ X two expressions such that e ⊆ f ⊲ , and σ ∶ X → P (S × S) some relational interpretation.

2 .

 2 Hence Tr (A (e 1 ∨ e 2 )) = Tr (A (e 1 )) ∪ Tr (A (e 2 )), thus proving that: G(e 1 ∨ e 2 ) = G(e 1 ) ∪ G(e 2 ) ≡ Tr (A (e 1 )) ∪ Tr (A (e 2 )) ≡ Tr (A (e 1 ∨ e 2 ))• A (e ⋅ f ) ∶= ⟨P 1 ∪ P 2 , T , ι 1 , F 2 ⟩ with T = T 1 ∪ T 2 ∪ {(f, t) f ∈ F 1 and ({ι 2 } , t) ∈ T 2 }.

Recall that if (ρ j ) 0⩽j⩽n is a reading along ξ then ∀p, q ∈ s j , ρ j (p) = ρ j (q).

B. Omitted proof: Lemma 14

Suppose there exists a graph morphism h from Tr (ξ) = ⟨{0, . . . , n} , E ξ , 0, n⟩ to G = ⟨V, E, ι, o⟩. We build a reading (ρ k ) k of G along ξ by letting ρ k (p) ∶= h(ν(k, p)) for 0 ⩽ k ⩽ n and p ∈ ξ k .

• for the initialisation and conclusion of the reading:

(h is a morphism)

• for all p ∈ s k and (x, q) ∈ t k , we know that

If on the other hand we have a reading (ρ k ) 0⩽k⩽n of G, we define h ∶ {0, . . . , n} → V by h(k) ∶= ρ k (p) for any p ∈ s k . As (ρ k ) k is a reading, h is well defined. Let us check that h is a morphism from Tr (ξ) to G:

• if (k, x, l) ∈ E ξ is an edge of Tr (ξ), then there is some p ∈ s k and q such that (x, q) ∈ t k and l = ν(k + 1, q). By definition of ν we know that ∀k + 1 ⩽ j < l, q ∉ s j . Thus, because (ρ k ) k is a reading, ρ k+1 (q) = ρ l (q) and (ρ k (p), x, ρ k+1 (q)) ∈ E. Hence (h(k), x, h(l)) ∈ E.

For i ∈ {1, 2}, define π i (ξ) ∶= ξ ∖ P 2-i , and δ i (τ ) ∶= {τ } if τ ∈ T i , and ∅ otherwise.

We check that

))⟩ is an accepting parallel run in A (e i ), and that Tr (ξ) ≡ Tr ξ 1 ∧ Tr ξ 2 , which allows us to conclude.

(Although we did not properly introduce the trace of a parallel run, this does not hold any difficulty. As stated when we introduced the notion of parallel transition, such a transition may be unfolded by sequentially firing the underlying transitions, in any order. Accordingly, all of the unfoldings of a parallel run share the same trace (up to graph isomorphisms). We may thus take for the trace of a parallel run any of those traces.)

D. Omitted proof: Lemma 23

In the following, let A = ⟨P, T , ι, F ⟩ be a Petri automaton, and ξ = ⟨(ξ k ) 0⩽k⩽n , (τ k ) 0⩽k<n ⟩ a run of A with ∀k, τ k = (s k , t k ).

Definition 28 (Exchangeable transitions) Two transitions τ k and τ k+1 are exchangeable in ξ if for all p ∈ ξ k , if p is in s k+1 then there is no x ∈ X such that (x, p) ∈ t k . * Lemma 29. Suppose τ k and τ k+1 are exchangeable for some 0 ⩽ k < n -1. We write

), where:

→ A ξ k+2 is trivial to check, with the definition of exchangeable.

Let (ρ j ) 0⩽j⩽n be a reading of G along ξ. If ρ ′ j 0⩽j⩽n is defined by:

Recall that if (ρ j ) 0⩽j⩽n is a reading of G along ξ we write active(j) for the only position in ρ j (s j ).

Lemma 30. Let ⩿ be any consistent ordering (Definition 22) on G. If (ρ j ) 0⩽j⩽n is a reading of G along ξ, and if active(k + 1) ⩿ active(k) for some k, then τ k and τ k+1 are exchangeable.

Proof. Let G = ⟨V, E, ι, o⟩. As (ρ i ) 0⩽j⩽n is a reading, for any (x, p) ∈ t k , (active(k), x, ρ k+1 (p)) ∈ E, thus active(k) ⋖ ρ k+1 (p). We know that active(k + 1) ⩿ active(k), meaning by transitivity that active(k + 1) ⋖ ρ k+1 (p). Hence active(k + 1) ≠ ρ k+1 (p) and because (ρ i ) 0⩽j⩽n is a reading we can infer that p ∉ s k+1 , thus proving that τ k and τ k+1 are exchangeable.

Proof of Lemma 23. Because G is in L (A ), we can find a reading ρ ′ along some run ξ. If that reading is not in the correct order, then by Lemma 30 we can exchange two transitions and Lemma 29 ensures that we can find a corresponding reading. We repeat this process until we get a reading in the correct order.

E. Omitted proof: Lemma 24

Let ξ = ⟨(ξ k ) 0⩽k⩽n , (τ k ) 0⩽k<n ⟩ be a run, with τ k = (s k , t k ) for all k. Define ρ 1 k (p) ∶= ν(k, p) for all index k place p ∈ ξ k . We have that ρ 1 k 0⩽k⩽n is a reading of Tr (ξ) along ξ.

• Assume an embedding (η k ) 0⩽k⩽n of an accepting parallel run Ξ into ξ. We define a parallel reading (ρ 2 k ) of Tr (ξ) in A 2 by letting ρ 2 k (p) ∶= ρ 1 k (η k (p)).

• On the other hand, notice that the natural ordering on ◆ is consistent for Tr (ξ), and that

By Lemma 23 we gather that Tr (ξ) is in L (A 2 ) if and only if there exists a reading (ρ 2 j ) 0⩽j⩽n ′ of Tr (ξ) along some run ξ ′ = ⟨ ξ ′ j 0⩽j⩽n ′ , (τ ′ j ) 0⩽j<n ′ ⟩ such that ∀j, active(j) ⩽ active(j + 1) (with active(j) the only position in ρ 2 j (s j )). Now, suppose we have such a reading; we can build an embedding (η k ) 0⩽k⩽n as follows. For k < n, define T k ∶= (s ′ j , t ′ j ) active(j) = k . We describe the construction incrementally:

-For all p ∈ dom (η k ) ∖ ⋃ (s,t)∈T k s we simply set η k (p) = η k-1 (p).

-Otherwise, ∀(s ′ j , t ′ j ) ∈ T k , let q ∈ s ′ j . Then, for all (x, p) in t ′ j , because ρ 2 is a reading and by construction of Tr (ξ) we also know that there is some p ′ ∈ ξ k+1 such that (x, p ′ ) ∈ t k , and ρ 1 k+1 (p ′ ) = ρ 2 j+1 (p). That p ′ is a good choice for p, hence we define η k (p) = p ′ . It is then administrative to check that (η k ) 0⩽k⩽n is indeed an embedding.