Feng Niu

Qiyan Wang

Zhen Yan

Bright Kusema b Andrei Y Khodakov
email: andrei.khodakov@univ-lille.fr

Vitaly V Ordomsky
email: vitaly.ordomsky-ext@solvay.com

Highly Efficient and Selective N-alkylation of Amines with Alcohols Catalyzed by in-situ Rehydrated Titanium Hydroxide

Keywords: N-alkylation, Amines, Alcohols, Heterogeneous, Titanium hydroxide, Alkoxides

Catalytic N-alkylation of amines by alcohols to produce desired amines is an important catalytic reaction in industry. Various noble metal-based homogeneous and heterogeneous catalysts have been reported for this process. Development of cheap non-noble metal heterogeneous catalysts for N-alkylation reaction would be highly desirable. Hereby, we propose the N-alkylation of amines by alcohols over a cheap and efficient heterogeneous catalyst -titanium hydroxide. The catalyst provides the selectivity higher than 90% to secondary amines for functionalized aromatic, aliphatic alcohols and amines at high catalytic activity and stability. Mild Brönsted acidity formed by continuous rehydration of Lewis acidity excludes side reactions and deactivation by adsorbed species. The mechanism of the reaction involves dehydration of alcohols to ethers with subsequent C-O bond cleavage by amine with formation of secondary amine and recovery of alcohol.

Introduction

Complex amines are very important intermediates in chemical industry and life science. They are widely used in the production of agrochemicals, pharmaceuticals, organic dyes, detergents, fabric softeners, surfactants, corrosion inhibitors, lubricants, polymers and so on [START_REF] Lawrence | Amines: Synthesis, Properties and Applications[END_REF][START_REF] Wittcoff | Industrial Organic Chemicals[END_REF][START_REF] Arpe | Industrial Organic Chemistry[END_REF]. Due to the widespread use of these products, a number of synthesis routes have been developed based on classic nucleophilic substitution, like Buchwald-Hartwig [START_REF] Magano | Large-scale applications of transition metalcatalyzed couplings for the synthesis of pharmaceuticals[END_REF], Ullmann reactions [START_REF] Monnier | Ullmann-type coupling reactions: copper makes a difference[END_REF], and hydroamination [START_REF] Yadav | Recent progress in transition metal catalysed hydrofunctionalisation of less activated olefins[END_REF][START_REF] Pirnot | Copper hydride catalyzed hydroamination of alkenes and alkynes[END_REF][START_REF] Lequitte | Amination of butenes over protonic zeolites[END_REF].

Conventionally, N-alkyl amines are synthesized using alkylating agents, such as alkyl halides, which is environmentally unfriendly due to the toxic nature of halides and production of large amount of inorganic salts as waste. The selectivity to desired amines is generally low due to further over-alkylation [START_REF] Smith | Advanced Organic Chemistry[END_REF][START_REF] Buchwald | Industrial-scale palladium-catalyzed couplingof aryl halides and amines-a personal account[END_REF][START_REF] Navarro | Rapid room temperature Buchwald-Hartwig and Suzuki-Miyaura couplings of heteroaromatic compounds employing low catalyst loadings[END_REF].

In the last few decades, three main strategies have been applied for amination of alcohols: (i) "Borrowing Hydrogen" methodology using either noble metal based Ru- [START_REF] Marichev | Ruthenium-catalyzed amination of secondary alcohols using borrowing hydrogen methodology[END_REF], Pd- [START_REF] Dang | An efficient palladium-catalyzed N-alkylation of amines using primary and secondary alcohols[END_REF], Ir- [START_REF] Prades | IrCl 2 Cp*(NHC)] Complexes as highly versatile efficient catalysts for the cross-coupling of alcohols and amines[END_REF], Rh- [START_REF] Kondo | Ruthenium complex-catalyzed facile synthesis of 2-substituted benzo-azoles[END_REF], and Pt- [START_REF] Watanabe | The ruthenium catalyzed N-alkylation and N-heterocyclization of aniline using alcohols and aldehydes[END_REF] complexes, and more recently non-noble metal Mn- [START_REF] Sreedhar | AgOTf catalyzed direct amination of benzyl alcohols with sulfonamides[END_REF][START_REF] Landge | Manganese catalyzed N-alkylation of anilines with alcohols: ligand enabled selectivity[END_REF], Co- [START_REF] Zhang | Cobalt-catalyzed N-alkylation of amines with alcohols[END_REF][START_REF] Midya | A simple cobalt(II) chloride catalyzed N-alkylation of amines with alcohols[END_REF][START_REF] Midya | Direct access to N-alkylated amines and imines via acceptorless dehydrogenative coupling catalyzed by a cobalt(II)-NNN pincer complex[END_REF], Ni- [START_REF] Vellakkaran | An efficient and selective nickel-catalyzed direct N-alkylation of anilines with alcohols[END_REF][START_REF] Bains | Borrowing hydrogen-mediated N-alkylation reactions by a well-defined homogeneous nickel catalyst[END_REF][START_REF] Yang | Nickel -catalyzed N -alkylation of acylhydrazines and arylamines using alcohols and enantioselective examples[END_REF][START_REF] Subaramanian | General synthesis of N-alkylation of amines with secondary alcohols via hydrogen autotransfer[END_REF] and Fe- [START_REF] Zhao | Iron/amino acid catalyzed direct N-alkylation of amines with alcohols[END_REF] complexes. Also various of heterogeneous catalysts [START_REF] Yan | Benzylamines via iron-catalyzed direct amination of benzyl alcohols[END_REF][START_REF] He | Efficient and clean gold-catalyzed one-pot selective N-alkylation of amines with alcohols[END_REF][START_REF] Corma | A bifunctional Pd/MgO solid catalyst for the one-pot selective N-monoalkylation of amines with alcohols[END_REF][START_REF] Ishida | Support effects of metal oxides on gold-catalyzed one-pot N-alkylation of amine with alcohol[END_REF][START_REF] Ousmane | Highly selective direct amination of primary alcohols over a Pd/K-OMS-2 catalyst[END_REF][START_REF] Shimizu | -Alumina-supported silver cluster for N-benzylation of anilines with alcohols[END_REF][START_REF] Kim | Heterogeneously catalyzed selective N-alkylation of aromatic and heteroaromatic amines with alcohols by a supported ruthenium hydroxide[END_REF][START_REF] Wu | Alcohol amination catalyzed by copper powder as a self-supported catalyst[END_REF] have been used. (ii) Tsuji-Trost type reactions for allylic alcohols using Pd [START_REF] Akkarasamiyo | Tsuji-Trost reaction of non-derivatized allylic alcohols[END_REF] or Ni [START_REF] Bricout | Synthetic and kinetic aspects of nickel-catalysed amination of allylic alcohol derivatives[END_REF] complexes. (iii) Lewis-acid catalyzed reactions using a variety of salts and ligands [START_REF] Emer | Direct nucleophilic S N 1-type reactions of alcohols[END_REF][START_REF] Bähn | The Catalytic amination of alcohols[END_REF]. Among the best performing catalysts, different metal triflates and triflimides, including the parent triflic acid (HOTf) were found active for synthesis of secondary amines through N-alkylation of amines with alcohols based on S N 1 or S N 2 mechanisms [START_REF] Payard | Direct amination of alcohols catalyzed by aluminum triflate: an experimental and computational study[END_REF]. However, these processes have several disadvantages due to use of expensive non-recoverable catalysts, difficulties in catalyst-product separation and indispensable use of additives or co-catalysts such as inorganic or organic bases and stabilizing ligands [START_REF] Sun | Ni-Cu/γ-Al 2 O 3 catalyzed N-alkylation of amines with alcohols[END_REF]. Thus, development of easily recoverable and recyclable non-noble metal based heterogeneous catalysts for N-alkylation system is still a challenging topic.

Herein, we firstly report the selective N-alkylation of amines by alcohols in the absence of hydrogen, bases and organic ligands under ambient pressure of N 2 by an easily prepared transition metal-and solid acid-based heterogeneous catalyst such as titanium hydroxide. For comparison, a number of metal oxides and hydroxides have been tested in the N-alkylation process. Interestingly, titanium hydroxide exhibits the highest activity and selectivity towards the desired amine. In addition, the titanium hydroxide catalyst provides high catalyst stability and good substrate tolerance for amination of different alcohols and substituted amines under optimized conditions. To the best of our knowledge, this new efficient heterogeneous catalyst provides a green route for selective synthesis of amines.

In terms of catalytic mechanism, it is generally accepted that substitution of OH-groups with N nucleophiles proceeds via a S N 1 or S N 2 type mechanism, in the presence of hard Lewis or Brönsted acids [START_REF] Baeza | Recent advances in the direct nucleophilic substitution of allylic alcohols through S N 1-type reactions[END_REF]. In this work, we show that N-alkylation process of alcohols involves intermediate formation of ethers, which could be a kinetic relevant step of the whole reaction. The high yield of secondary amine can be attributed to the easier C-O bond cleavage in the ether by amines based on effect of mild Brönsted acidity formed by adsorbed water over Lewis acid sites.

Experimental Section

Catalyst preparation

Titanium hydroxide was prepared through the hydrolysis of titanium isopropoxide (99%, supplied by J&K) under neutral condition. 200 ml of distilled water was heated up to 60 o C and 10 mL titanium isopropoxide was added dropwise using a peristaltic pump (0.05 mL/min) under continuous stirring (500 rpm) for almost 10 h. Then the obtained white suspension was centrifuged and washed with ethanol and distilled water for several times followed by drying in vacuum at 80 o C overnight. The obtained sample was denoted as TiOH. The hydrolysis of isopropoxide in hot water is an easy and efficient method to produce amorphous titanium hydroxide with high purity (no NH 3 or Cl -) and surface area. This sample has been further calcined at 180 o C and 400 o C for 2 h to produce dehydrated samples denoted as TiOH-180 and TiOH-400, respectively.

The hydroxides of Al (Al-OH) and Zr (Zr-OH) have been prepared in the similar way using alkoxides of aluminium t-butoxide, aluminium isopropoxide, zirconium butoxide and zirconium ethoxide. For comparison, different metal oxides and commercial zeolite ZSM-5 were also used for this reaction as references. The hydrolyzed AlOH sample was calcined under 180 o C, which was denoted as AlOH-180.

Catalytic test

Typical procedure for N-alkylation of amines with alcohols was carried out in a 30 mL stainless steel autoclave geared with a pressure gauge and a safety rupture disk.

In a typical experiment, the reactor was charged with 4.62 mmol benzyl alcohol, 21.5 mmol aniline and 100 mg of catalyst. 2 g xylene, THF or water was used as a solvent.

Then, the reactor was purged with N 2 several times to remove the air. Finally, the reactor was placed on a hot plate equipped with a magnetic stirrer (500 rpm) at 50 o C-180 o C for 0.5-48 h. After the reaction, the reactor was cooled down to room temperature, and the mixture was filtrated and analyzed using an Agilent 7890 GC equipped with a HP-5 capillary column using biphenyl as the internal standard for calculation of alcohol conversion and product yields. After each amination test, the catalyst was washed with ethanol and separated by centrifugation several times and dried at 80 o C for 10 h for further test of the recyclability. The used catalyst after reaction was denoted as TiOH-80-AR. For the rehydration of the dehydrated catalysts TiOH-180, water was added into the reactor before catalytic test. For characterization, the catalyst was suspended in distilled water overnight followed by drying under vacuum at 80 o C before test. The corresponding rehydrated samples were denoted as TiOH-180-Re, TiOH-400-Re, TiO 2 -Re and AlOH-180-Re.

Characterization methods

The powder X-ray diffraction (XRD) patterns were obtained using an X-ray diffractometer (D5000, Siemens) using Cu Kα radiation (λ = 0.15418 nm). Scans were recorded in the 2θ range of 10-80 o using a step size of 0.02 o and a step time of 5 s.

The BET specific surface areas and pore size were measured from the N 2 adsorption-desorption isotherms at 77 K on an automated gas sorption analyzer Micromeritics ASAP 2010. Thermogravimetric analysis (TGA) was carried out in air flow at the temperature range of 20-900 o C with a heating rate of 5 o C•min -1 on a Mettler Toledo SMP/PF7458/MET/600W instrument.

The FTIR (Perkin-Elmer 1720) spectra of the titanium hydroxide catalysts were measured in the range from 4000 to 1200 cm -1 to trace the variation of surface hydroxyl group of the catalysts. To investigate the nature of acid sites in the catalyst, the pyridine adsorption FTIR technique was employed and spectra were recorded in the range of 1700-1400 cm -1 . The self-supported wafers of all the catalysts were prepared by a pellet press instrument and the samples were degassed at 100 °C for 30 minutes followed by saturation with pyridine as reported elsewhere [START_REF] Vimont | Analysing and understanding the active site by IR spectroscopy[END_REF]. To explain the mechanism of alcohol dehydration over titanium hydroxide, in-situ FTIR was performed through heating the pellet from 25 to 180 o C (step 25 o C) in benzyl alcohol vapors (20 Torr).

The NH 3 temperature programmed desorption (NH 3 -TPD) was carried out on a Micromeritics AutoChem 2920 with a thermal conductivity detector (TCD). In all the experiments, ~50 mg of sample was calcined at 100 o C for 1 h in helium gas flow (20 mL (STP)/min) and then cooled down to 40 °C followed by saturation with 10% ammonia-helium for 1 h. Then the sample was flushed with helium for 1 h to remove the surface physisorbed ammonia. Finally, the desorption profiles were recorded in the temperature range of 40 o C-800 o C with a heating rate of 5 °C min -1 .

Results and Discussion

Catalysis over oxides and hydroxides

The additive-free N-alkylation reaction of benzyl alcohol (1) with aniline (2) to give corresponding secondary amine N-phenylbenzylamine (3) has been used as a model reaction over different non-noble metal hydroxide, oxide and zeolite catalysts (Table 1). The product has been identified by GC-MS, 1 H-NMR and 13 C-NMR analysis (Figure S1, S2, S3, SI). The blank test without catalyst did not show formation of desired amine (entry 1). The titanium hydroxide obtained by hydrolysis of titanium isopropoxide showed the highest catalytic activity and gave the desired secondary amine N-phenylbenzylamine (3) with the 99.6% yield (entry 2) without formation of secondary imine. Only traces of dibenzyl ether have been detected as byproduct. The product yield was slightly lower for the reaction performed without solvent due to easier formation of tertiary amine through condensation reaction (entry 3). It is interesting to note that the reaction can be performed in aqueous phase (entry 5), however, organic solvents provide the highest yield of the product (entry 4). The reaction in air atmosphere provides a bit lower yield than that under N 2 mainly due to The apparent activation energy of the reaction corresponds to 66.4 kJ/mol (Figure 1a).

The time course of the secondary amine synthesis over titanium hydroxide (TiOH-80) at 180 o C was investigated (Figure 2). The reaction proceeded smoothly to afford the corresponding secondary amine with 99% yield in 15 h. Dibenzyl ether was observed at the initial stage and its yield slowly decreased with time, suggesting the dibenzyl ether could be an intermediate. The reaction seems to proceed in two consecutive steps: 1) transformation of benzyl alcohol to dibenzyl ether and 2) secondary amine formation from dibenzyl ether with aniline.

Characterization

To identify, whether the high performance of secondary amine synthesis comes from the suitable acidic sites formed from surface hydroxyl group of the catalyst, titanium hydroxide obtained by hydrolysis was calcined at different temperatures. The TGA analysis (Figure 3a) shows that titanium hydroxide exhibited weight loss in two main steps. The initial weight loss below 250 o C can be assigned to desorption of surface water. The weight loss between 250 o C and 450 o C could be due to the removal of surface hydroxyl groups through dehydroxylation process [START_REF] Marakatti | Superior performance of mesoporous tin oxide over nano and bulk forms in the activation of a carbonyl group: conversion of bio-renewable feedstock[END_REF]. No obvious weight loss was detected for TiOH-400 sample. This indicates that high crystalline TiO 2 phase was formed after calcination at 400 o C. The catalyst TiOH-80-AR after reaction showed similar weight loss compared to the fresh catalyst.

This indicates similar content of hydroxyl groups and rehydration of the catalyst during reaction. The state of the material during calcination at different temperatures has been studied by XRD. The parent sample and sample after calcination at 180 o C are amorphous, the presence of anatase was detected after calcination at 400 o C [START_REF] Mahshid | Synthesis of TiO 2 nanoparticles by hydrolysis and peptization of titanium isopropoxide solution[END_REF].

XRD showed that the catalyst was still amorphous after reaction (Figure 3b).

FTIR has provided further information about the concentration and acidity of surface hydroxyl groups in titanium hydroxide. As shown in Figure 4a, the titanium hydroxide without calcination exhibited a broad peak at 3600 cm -1 and a peak at 1626 cm -1 due to the stretching vibration of hydroxyl groups interacting with adsorbed water and bending vibration of hydroxyl groups of adsorbed water, respectively [START_REF] Yates | Infrared studies of the surface hydroxyl groups on titanium dioxide, and of the chemisorption of carbon monoxide and carbon dioxide[END_REF].

As the calcination temperature increased, the intensity of the peak at 1626 cm -1 decreased and finally disappeared at 400 o C with significant narrowing of the peak at 3600 cm -1 . It indicates desorption of water and significant decrease in the amount of hydroxyl groups during dehydration of hydroxide and its transformation to anatase phase.

To identify the acidic properties of the surface hydroxyl groups of the catalyst, FTIR spectra of pyridine adsorbed on titanium hydroxide calcined at different temperatures were recorded (Figure 4b). The interaction of pyridine with Lewis acid sites gives rise to the specific bending vibration bands of pyridine ring at 1448 cm -1 , 1575 cm -1 and 1605 cm -1 [START_REF] Vimont | Analysing and understanding the active site by IR spectroscopy[END_REF]. The peak located at 1540 cm -1 can be assigned to the interaction of pyridine with Brönsted acid sites. It can be observed that an increase in the calcination temperature of titanium hydroxide to 180 o C leads to decrease in the intensity of all the peaks related to Lewis acid sites and nearly disappearance of Brönsted acid sites [START_REF] Marakatti | Superior performance of mesoporous tin oxide over nano and bulk forms in the activation of a carbonyl group: conversion of bio-renewable feedstock[END_REF]. Further increase in the calcination temperature to 400 o C results in disappearance of all adsorbed pyridine species over the catalyst, which means nearly no acidic sites left on the catalyst. It is interesting to note that the process of dehydration is reversible and treatment of TiOH-180 in water leads to recovery of adsorbed pyridine species corresponding to Brönsted and Lewis acid sites (Figure 4b). However, rehydration process did not lead to acidity generation over the crystalline sample TiOH-400, which could be explained by high stability of anatase structure. Thus, defected labile nature of titanium hydroxide provides both Brönsted and Lewis acid sites, which disappear during dehydration procedure due to the process of healing of defected sites (Figure 5). Indeed, the formation of Brönsted and Lewis acid sites can be proposed as reaction of protonation of hydroxyl groups with subsequent dehydration. The easy rehydration process provide constant presence of both types of acid sites in the catalyst during reaction (Figure 5).

To further identify the amount and strength of the acid sites, temperature programmed desorption of ammonia (NH 3 -TPD) has been measured as shown in test with the dehydrated catalysts (Figure 7). The reaction rate (12.55 mmol/g•h) for amorphous titanium hydroxide (TiOH-180) was almost recovered to the initial state after addition of water. We could propose reversible process of dehydration and rehydration for titanium hydroxide during reaction, which provides permanent acidity for amination reaction [START_REF] Parfitt | The surface of titanium dioxide[END_REF][START_REF] Benkoula | Water adsorption on TiO 2 surfaces probed by soft X-ray spectroscopies: bulk materials vs. isolated nanoparticles[END_REF] (Figure 5).

To investigate the structure-performance correlation, BET analysis of all catalysts has been performed. There is no obvious relationship between reaction activity and surface area or pore structure of the catalysts (Table S2, The activity recovery for the rehydrated sample TiOH-180 was mainly attributed to the continuous regeneration of intermediate Brönsted and Lewis acidic sites, (Figure 5). The lower activity for ZSM-5 was partially because of quasi-irreversible adsorption of aniline on the zeolite strong acid sites under the reaction conditions. Consequently, we could assume that weak and strong acidities would not play a determining role in amination reaction. Titanium hydroxide with optimum intermediate acidity and able to be rehydrated shows an exceptional catalytic performance for the N-alkylation reactions.

Mechanism

Among various strategies for amines synthesis, amination of alcohols using a borrowing hydrogen methodology (or hydrogen auto-transfer process) has been regarded as a highly atom-efficiency choice [START_REF] Winans | The alkylation of amines as catalyzed by nickel[END_REF][START_REF] Dobereiner | Dehydrogenation as a substrate-activating strategy in homogeneous transition-metal catalysis[END_REF][START_REF] Marichev | Ruthenium-catalyzed amination of secondary alcohols using borrowing hydrogen methodology[END_REF]. In this approach (Figure 8 (a)) alcohol was first dehydrogenated to the corresponding aldehyde with assistance of noble metals like Ru, Pt, Pd, Ir [START_REF] Liang | Structure-sensitive and insensitive reactions in alcohol amination over nonsupported Ru nanoparticles[END_REF][START_REF] Rausch | New aspects for heterogeneous cobalt-catalyzed hydroamination of ethanol[END_REF][START_REF] Dume | Amination of 1-octanol[END_REF][START_REF] Balker | Catalytic amination of aliphatic alcohols in the gas and liquid phases: kinetics and reaction pathway[END_REF]. Then the aldehyde was nucleophilically attacked by an amine to form secondary imine with the eliminating of water as the only byproduct. Finally, imine was hydrogenated to the desired secondary amine.

During the whole process, additional hydrogen is usually added for inhibition of the catalyst deactivation and fast hydrogenation step to suppress secondary processes.

In our case, the non-metallic acidic heterogeneous catalyst such as titanium hydroxide without dehydrogenation/ hydrogenation functions was found to be very efficient for the direct N-alkylation of benzyl alcohol with aniline to give desired secondary amine. A possible reaction mechanism in this case can be based on S N 2 mechanism of direct nucleophilic attack of α-carbon atom by N of aniline [START_REF] Deng | Low-temperature reductive amination of carbonyl compounds over Ru deposited on Nb 2 O 5 •nH 2 O[END_REF][START_REF] Timsina | Palladium-catalyzed C-H amination of C(sp 2 ) and C(sp 3 )-H bonds: mechanism and scope for N-based molecule synthesis[END_REF].The effect of the ratio of aniline to benzyl alcohol from 0 to 10 on the reaction selectivity is displayed in Figure 9a. It is interesting and obvious to note the presence of dibenzyl ether, which might be produced by dehydration of benzyl alcohol. The intermolecular dehydration of benzyl alcohol catalyzed by acid sites of metal oxides like alumina has been observed earlier [START_REF] Jain | Catalytic dehydration of alcohols over alumina: mechanism of ether formation[END_REF][START_REF] Kostestkyy | Structure-activity relationships on metal-oxides: alcohol dehydration[END_REF][START_REF] Shi | Alcohol dehydration: mechanism of ether formation using an alumina catalyst[END_REF]. Surprisingly, in the presence of larger amounts of aniline (amine to alcohol ratio >1), the dehydration of benzyl alcohol is completely suppressed. There are two possible explanations of this effect: 1) acid sites of titanium hydroxide are responsible for dehydration of alcohol and amination of alcohol. The presence of excess of aniline suppresses the first reaction;

2) ether is the primary product of the reaction. The ammonolysis of the ether by aniline proceeds much faster than that of the relevant alcohol.

To provide experimental evidence for the second hypothesis, the catalytic reaction of dibenzyl ether with aniline over titanium hydroxide was investigated (Figure 9 (b)). No product was formed without catalyst. TiOH-80 clearly catalyzed the ammonolysis reaction of dibenzyl ether with high initial reaction rate (80 mmol/g•h), which was about 6 times higher than that of the whole N-alkylation reaction (12.8 mmol/g•h) (Figure 1b, Figure 6). It demonstrates that the ammonolysis of dibenzyl ether through C-O bond cleavage [START_REF] Cui | Palladium-catalyzed synthesis of alkylated amines from aryl ethers or phenols[END_REF][START_REF] Li | Nickel-catalyzed amination of aryl 2-pyridyl ethers via cleavage of the carbon-oxygen bond[END_REF][START_REF] Li | Rapid ether and alcohol C-O bond hydrogenolysis catalyzed by tandem high-valent metal triflate + supported Pd catalysts[END_REF][START_REF] Assary | Reaction pathways and energetics of etheric C-O bond cleavage catalyzed by lanthanide triflates[END_REF] to the desired secondary amine proceeds much faster than the relevant reaction of benzyl alcohol. This indicates that dehydration of alcohol could be the limiting step of the whole N-alkylation reaction (Figure 8b). Water was the only byproduct during the whole reaction process. The product yield for the ammonolysis reaction dramatically decreased from 86 % to nearly 0 as the pretreatment temperature increased from 180 to 400 o C (inset of Figure 9b). It indicates that the ammonolysis of dibenzyl ether requires acid sites as well, which is consistent with the previous report [START_REF] Fu | Reaction route and mechanism of the direct N-alkylation of sulfonamides on acidic mesoporous zeolite β-catalyst[END_REF]. However, the reaction is less sensitive to amount of acid sites in comparison with dehydration of alcohol to ether.

To investigate the alcohol dehydration process on the acid sites of titanium hydroxide, in-situ FTIR experiments were performed (Figure 10 Adsorption of benzyl alcohol leads to appearance of the bands at 1230, 1380, 1360, 1447, 1470 and 1494 cm -1 . The bands at 1447 and 1494 cm -1 can be assigned to the in-plane C-O-H bending modes [START_REF] Mukhopadhyay | High resolution synchrotron radiation Fourier transform infrared spectrum of the COH-bending mode in methanol-D 1 (CH2DOH)[END_REF]. The bands at 1230 and 1470 cm -1 are associated usually with methylene group [START_REF] Mukhopadhyay | High resolution synchrotron radiation Fourier transform infrared spectrum of the COH-bending mode in methanol-D 1 (CH2DOH)[END_REF]. The bands at 1360 and 1380 cm -1 can be assigned to aromatic skeletal vibrations [START_REF] Ajjan | Spectroelectrochemical investigation of redox states in a polypyrrole/lignin composite electrode material[END_REF].

As the temperature increased from room temperature to N-alkylation temperature, the additional bands appears at 1600 cm -1 and 1575 cm -1 (Figure 10, Figure S7, SI)

These bands can be assigned to bending vibrations of strongly adsorbed water over Lewis acid sites and C=C stretching vibrations in benzyl ether [START_REF] Smith | The C-O bond III: ethers by a knockout[END_REF]. Additionally the band at 3510 cm -1 of OH stretching vibration increases at higher temperature (Figure S7, SI). This indicates dehydration of alcohol with formation of water and ether.

The FTIR spectrum of the catalyst after reaction and intensive washing in xylene shows the peaks at 1380 and 1360 cm -1 similar to FTIR spectra after benzyl alcohol adsorption (Figure 11). In order to verify if these species could be intermediates during catalytic reaction, the catalyst after reaction has been treated at the reaction conditions in pure xylene. The liquid phase after reaction contained 0.33 mmol (3.3 mmol ether/g p ) of dibenzyl ether which was the only product of the reaction (Figure S8, SI). The amount of the product corresponds well to the amount of acidic active sites determined by TPD of NH 3 (Table S1, SI). FTIR analysis shows that surface species have disappeared after reaction (Figure 11). In order to identify the localization of these species, Py has been adsorbed over the catalyst before and after treatment in solvent (Figure 11). It is interesting to note that the peak attributed to adsorption of Py over Lewis acid sites decreased significantly after reaction but has been totally recovered after treatment in xylene. The possible explanation of this effect could be formation of surface alkoxide species by interaction of alcohol with Lewis acid sites (Figure 11). The presence of intermediate surface alkoxides have been observed earlier over alumina [START_REF] Heiba | Alumina-catalyzed cleavage of ethers and thermal decomposition of aluminum alkoxides[END_REF]. FTIR analysis of low wavenumber region (Figure 11) of the catalyst after reaction (TiOH-80-AR) shows intensive bands at 1126, 1070 and 1041 cm -1 , which has been earlier assigned to vibration modes of Ti-O-C species in alkoxides [START_REF] Velasco | Hydrolysis of Titanium Tetrabutoxide. Study by FT-IR Spectroscopy[END_REF].

The kinetic analysis of the reaction of benzyl alcohol dehydration to benzyl ether shows that it corresponds to the second order similar to the whole N-alkylation reaction (Figure S9, SI).

Based on the catalytic and characterization results discussed above, a possible reaction mechanism of ether formation on acidic titanium hydroxide as key intermediate for further ammonolysis to N-alkylation product was proposed in Figure 12. The alcohol reacts with Lewis acid sites over the TiOH catalyst with formation of surface alkoxides. Protonation of oxygen of alkoxide species by hydroxyl group with SN2 attack of α-carbon by oxygen of another alkoxide results in formation of ether and partial hydration of the catalyst. Subsequent dehydration leads to regeneration of the active sites. Thus, synergetic effect of mild Brönsted and Lewis acid sites over titanium hydroxide for activation of alcohol able to transform it to ether by dehydration is necessary. These properties make titanium hydroxide unique for this reaction.

Adsorption of pyridine over other catalysts confirms this assumption. Oxides containing mainly Lewis acid sites and zeolite with Brönsted acidity provide low activity in N-alkylation reaction (Table S3, SI). Presence of both Brönsted and Lewis acid sites can be observed also over other hydroxides like Al-OH, however, catalyst cannot be rehydrated in-situ during reaction loosing activity in time (Figure S6, SI).

Thus, amount, nature and regenerability of acid sites are the key factors affecting activity of the catalyst in N-alkylation reaction.

To investigate the stability and reusability of titanium hydroxide, the used catalyst was washed with ethanol and separated from the liquid phase by centrifugation for several cycles and dried at 80 o C for 10 h. As shown in Figure 13, the titanium hydroxide could be used for at least three catalytic cycles without obvious change in reaction rate and amine yield, indicating good stability and recyclability for titanium hydroxide.

Substrate scope

The scope of the present titanium hydroxide system with regard to alkylation of various amines and alcohols was also examined. Table 2 shows that the catalyst can be used for selective conversion with aniline of structurally diverse aromatic and biomass based alcohols to the secondary amines (entry 1-5). The o-methyl benzyl alcohol (entry 4) was less reactive, which could be due to the steric hindrance effect of the methyl group at the o-position [START_REF] Wu | Alcohol amination catalyzed by copper powder as a self-supported catalyst[END_REF]. Aniline derivatives bearing an electron-donating or electron-withdrawing group also reacted with benzyl alcohol to afford the corresponding secondary amines with the yields higher than 90 % (entry 6-9). Aliphatic amines (butylamine and dibutylamine) can be also used for the synthesis of secondary and tertiary amines by reaction with benzyl alcohol, respectively (entry 10 and 11). However, the yield of the product in this case is lower than in the case of aromatic amines (<50 %) with significant contribution of ethers in the products due to the lower reactivity of aliphatic amine. The reaction conditions have been modified: the time of the test, amount of the catalyst were increased, while the loading of reagents were decreased (entry 12 and 13). Higher yield of the products comparable to the aromatic amines (≈ 90%) was obtained.

Titanium hydroxide provides high selectivity at reasonable conversions for the reaction of octanol, tetrahydrofurfuryl alcohol and isopropanol with aniline (entry [START_REF] Prades | IrCl 2 Cp*(NHC)] Complexes as highly versatile efficient catalysts for the cross-coupling of alcohols and amines[END_REF][START_REF] Kondo | Ruthenium complex-catalyzed facile synthesis of 2-substituted benzo-azoles[END_REF][START_REF] Watanabe | The ruthenium catalyzed N-alkylation and N-heterocyclization of aniline using alcohols and aldehydes[END_REF]. There is still a significant contribution of ether but the yield of the target product can be easily improved by increase of the contact time as it has been demonstrated earlier (entry 12 and 13).

Titanium hydroxide also provides reasonable yield of secondary aliphatic amine through N-alkylation of aliphatic alcohols (primary and secondary) with aliphatic amines (entry [START_REF] Sreedhar | AgOTf catalyzed direct amination of benzyl alcohols with sulfonamides[END_REF][START_REF] Landge | Manganese catalyzed N-alkylation of anilines with alcohols: ligand enabled selectivity[END_REF][START_REF] Zhang | Cobalt-catalyzed N-alkylation of amines with alcohols[END_REF][START_REF] Midya | A simple cobalt(II) chloride catalyzed N-alkylation of amines with alcohols[END_REF]. The main difference in comparison with aromatic alcohols and amines is higher contribution of ether in the case of aliphatic amines and alcohols (Table 2). Note that variation of the product yields with time of aliphatic amine remains consistent with the hypothesis about the role of ether as an intermediate of alcohol ammonolysis. Indeed, N-alkylation of isopropanol with aniline demonstrate continuous increase of the yield of the product and a volcano curve for the di-isopropyl ether as a function of time (Figure S10, SI). Thus, unique structure of titanium hydroxide provides efficient amination of aromatic and aliphatic alcohols by aromatic and aliphatic amines toward secondary and tertiary amines.

Conclusions

In summary, we have demonstrate that a non-noble metal solid titanium hydroxide acts as a stable, reusable and efficient heterogeneous catalyst for N-alkylation of amines with alcohols to secondary amines without hydrogen, bases or organic ligands promotion. The conversion and selectivity of titanium hydroxide were much higher than other hydroxides, metal oxides and zeolite due to the availability of mild intermediate Brönsted and Lewis acidities formed by rehydration-dehydration processes. The high yield for direct secondary amine synthesis can be attributed to the acidic catalytic intermolecular dehydration of alcohol to form corresponding ether followed by easier ether ammonolysis.

Page 7 of 42 ACS

 42 Paragon Plus Environment ACS Catalysis the partial oxidation of benzyl alcohol to benzoic acid (entry 6). Hydroxides of Al and Zr prepared by hydrolysis of different types of alkoxides could afford the maximum yield of N-phenylbenzylamine of only 16.9% (entry 7-10). Additionally, different metal oxides were also tested for N-alkylation reaction. The yield was lower than 2% for TiO 2 , CeO 2 , ZrO 2 , MgO, SiO 2 and Al 2 O 3 (entry 11-16). The alkylation yield for commercial zeolite ZSM-5 was only 25% (entry 17). Titanium hydroxide (TiOH-80) was the most active catalyst. The reaction temperature dependence of the secondary amine yield in the N-alkylation of benzyl alcohol with aniline on this catalyst was further investigated (Figure S4, SI). Below 100 o C, there was nearly no activity in this reaction. The conversion gradually increases as the temperature increases from 100 to 180 o C reaching full conversion.

Figure 6 .Figure 7 .

 67 Figure 6. The highest amount of acid sites is observed over pristine titanium

  SI). Indeed, high surface area of hydroxides AlOH and ZrOH or oxides Al 2 O 3 and SiO 2 does not provide high activity of these catalysts in amination. Analysis of the structure-catalytic performance relationship shows good correlation between intermediate acidity measured by NH 3 desorption in the range 200-400 o C and reaction rate in amination over different catalysts (Figure S5, SI). It is obvious that the reaction rate increases with increase in the intermediate acidity. However, high content of intermediate acid sites over Al-OH does not lead to high activity in amination. The possible explanation of this effect could be low rehydration of Al-OH at the reaction conditions. Dehydration of Al-OH at 180 o C leads to significantly lower activity in comparison with the parent catalyst Al-OH (Figure S6, SI). Rehydration of AlOH-180 does not show significant increase of the activity in comparison with the rehydration of TiOH-180. This fact could be explained by less labile structure of Al hydroxide in terms of reversible hydration-dehydration process.

  , Figure S7, SI).

Figure 1 Figure 2 Figure 3 Figure 4 Figure 5 Figure 6 Figure 7 Figure 8

 12345678 Figure 1 The Arrhenius plot of secondary amine yield for N-alkylation from benzyl alcohol and aniline over titanium hydroxide TiOH-80 (a) and time dependence for N-alkylation with catalysts before and after dehydration (b)

Figure 9 Figure 11 Figure 12

 91112 Figure 9 (a) Products distribution under different amine/alcohol molar ratio. Condition: benzyl alcohol 4.62 mmol, aniline/benzyl alcohol molar ratio 0-9.28, xylene 2 g, catalyst 100 mg, 15 h, atmospheric N 2 . (b) Time dependence for amine formation directly from dibenzyl ether. Condition: dibenzyl ether 5 mmol, aniline 20 mmol, xylene 2 g, catalyst 100 mg, atmospheric N 2 (inset: reaction performed with different catalysts for 1 h).

Figure 13

 13 Figure 13 Reusability test of N-alkylation of benzyl alcohol with aniline using titanium hydroxide. Reaction conditions: alcohols (4.62 mmol), amines (21.5 mmol), xylene 2 g, catalyst 100 mg, reaction temperature 180 o C, 15 h, atmospheric N 2 .

Table 1 .

 1 Amine synthesis from benzyl alcohol and aniline over various non-noble metal oxides and hydroxides (benzyl alcohol (4.62 mmol), aniline (21.5 mmol), xylene 2 g, catalyst 0.1 g, reaction temperature 180 •C, 15 h, atmospheric N 2 )

						Page 26 of 42
			NH 2
		OH	180 o C, 15 h, cat xylene (2 g)	N H	H 2 O
	1		2		3
	Entry	Catalyst	Yield of 3 (%)	Entry	Catalyst	Yield of 3 (%)
		Hydroxides			Oxides
	1	-	0	11	TiO 2	1.4
	2	Ti-OH	99.6	12	MgO	<1
	3	a Ti-OH	92.4	13	SiO 2	<1
	4	b Ti-OH	99.2	14	Al 2 O 3	<1
	5	c Ti-OH	97	15	CeO 2	0
	6	d Ti-OH	89.8	16	ZrO 2	<1
	7	e Al-OH	16.9		Zeolites
	8	f Al-OH	10	17	ZSM-5	25
	9	g Zr-OH	8.1
	10	h Zr-OH	12

a No solvent used; b under solvent THF; c under water; d under air; e hydrolysis from aluminium t-butoxide; f hydrolysis from aluminium isopropoxide; g hydrolysis from zirconium butoxide; h hydrolysis from zirconium ethoxide.

Table 2

 2 Scope of alcohols and amines for amine synthesis a

					ACS Catalysis				Page 40 of 42
			R 1 OH	R 2 NH 2	TiOH-80 180 o C, N 2	R 1	H N R 2	H 2 O
	Entry	Alcohols		Amines		Products	Conv. %	Selc.%	Ethers (%)
	1		OH		NH 2		H N		99.4	100	0
	2	Cl	OH		NH 2	Cl	H N		99	100	0
	3	O	OH		NH 2	O	H N		97	98	0
	b 4		OH		NH 2		H N		90	91	2
	5	O	OH		NH 2	O	H N		100	98	0
	b 6		OH		NH 2		N H		99	95	0
	7		OH	Cl	NH 2		H N	Cl	99	97	0
	8		OH	O	NH 2		H N	O	100	99	0
	9		OH		NH 2		H N		100	99	0
					ACS Paragon Plus Environment

Acknowledgements

The authors thank Solvay and University of Lille for financial support of this work.

Chevreul Institute (FR 2638), Ministère de l'Enseignement Supérieur, de la Recherche et de l'Innovation, Hauts-de-France Region and FEDER are acknowledged for supporting and funding partially this work.

ACS Paragon Plus Environment

ACS Catalysis

Data availability

All data are available from the authors upon reasonable request.

Supporting Information

GC-MS, 1 H NMR, 13 C NMR, FTIR, reaction activity, catalytic reaction rate, kinetic analysis, ether formation, acidity of the catalysts and BET analysis. This information is available free of charge on the ACS Publications website.

For Table of Contents Only


Alexandru Iosif

DUALITY IN MASS-ACTION NETWORKS

We introduce a duality theory for mass-action networks and we show that preclusters and maximal invariant polyhedral supports are dual objects.

Introduction

A chemical reaction is a transformation between two sets of chemical species; a set of chemical reactions is called chemical reaction network. Often chemical reaction networks are regarded as dynamical systems in which the concentrations of the chemical species are described by partial differential equations depending on position and time. When the chemical system is spatially homogeneous one can use ordinary differential equations instead. This rough approximation is often made in Biochemistry where the rate at which a concentration

x i changes is ẋi = j φ ij (x 1 , . . . , x n ).
Here j runs over all chemical reactions involving x i and φ ij is the rate at which x i is consumed or produced by the j th reaction. A special case of this dynamics can be derived from the Law of Mass-Action: "The rate at which a unit of a chemical species is consumed or produced by a chemical reaction is proportional to the product of the concentrations of the reactants." This law was first introduced by Guldberg and Waage in a series of papers during the second part of XIX century. Interestingly enough, this principle has been successfully applied to biochemical reaction networks (see, for example, [START_REF] Voit | 150 years of the mass action law[END_REF]).

Combinatorial view of mass-action networks

Mathematically, a mass-action network is a finite directed graph whose vertices are labelled by monomials and whose edges are labelled by rate constants: If we use the notation x = (x 1 , . . . , x n ) T and k = (k 1 , . . . , k r ) T , any massaction network can be uniquely expressed as a quadruple (Y e , Y p , k, x). The dynamics of a mass-action network is given by

n i=1 x (Ye) i1 i n i=1 x (Yp) i1 i k 1 , . . . ,
(1) ẋ = (Y p -Y e )diag(k)x Ye ,
where x Ye is a column vector of length r such that (x Ye ) j = n i=1 x

(Ye) ij i . Realistic models tend to be large; hence often one does not intend to solve them, but rather study their asymptotic behaviour, like their steady states. Steady states are defined as the non-negative solutions of

(2) (Y p -Y e )diag(k)x Ye = 0.
Note that, when one replaces the dynamical system (1) with the static system (2), information about the conserved quantities is lost. Therefore one has to regard the solutions of system (2) with respect to such conserved quantities. In biochemical reaction networks one usually restricts conservation laws to linear ones, that is, those which are of the form z 1 x 1 + . . . z n x n = c, where z is an element of the conservation space left-ker(Y p -Y e ) and c is the value of the conserved quantity. As

x are nonnegative, it only makes sense to consider those solutions to the conservation equations contained in R n ≥0 . The set of such solutions gives rise to a polyhedron called invariant polyhedron. As the values of the conserved quantities change, the shape of the invariant polyhedron also changes. However it is known that there is only a finite number of combinatorial changes of such polyhedra [START_REF] Jesús | Graphs of transportation polytopes[END_REF]. The relevance of these polyhedra lays in the fact that they are related to siphons, which are combinatorial objects that indicate which concentrations are allowed to vanish at steady states. It is usual that one decorates the vertices of the abstract shapes of such polyhedra by the product of the variables whose supports coincide with these vertices (see [START_REF] Shiu | Siphons in chemical reaction networks[END_REF] for a method to compute all combinatorial types of invariant polyhedra and their decorations). We call such representation a decorated abstract invariant polyhedron. Siphons have also proved to be useful in finding partial solutions for the Global Atractor Conjecture [START_REF] Gheorghe Craciun | Toric dynamical systems[END_REF].

Note that when the trajectories of (1) are bounded (i.e., when the system is conserved ), it is enough to restrict z to the conservation cone ker(Y p -Y e ) T ∩ R n ≥0 , and invariant polyhedra become polytopes. A strategy towards solving (2) is by first linearizing the vector diag(k)x Ye , and then by imposing binomial relations between its coordinates. For the linearization step, note that x is non-negative, so information about the stoichiometric cone ker(Y p -Y e ) ∩ R r ≥0 is enough. For the second step, the authors of [START_REF] Conradi | Multistationarity in mass action networks with applications to ERK activation[END_REF] introduced a key concept, namely clusters. Clusters and special unions of them, preclusters1 , were used in author's thesis to show that mass-action networks with the isolation property have toric steady states.

A set of species Σ = {x i | i ∈ I ⊆ [n]} is called a maximal invariant polyhedral supports if all combinatorial types of decorated invariant abstract polyhedra are invariant under the map x i → x j for all x i , x j ∈ Σ. In order to compute the maximal invariant polyhedral supports, one needs to compute the chamber decomposition in the space of linear conserved quantities, and decorate each ray with the corresponding variables. The set of all variables decorating an individual ray is a maximal invariant polyhedral support. A maximal symmetric chamber support is a maximal set of concentration indices such that, when the supports are changed within these sets, the vertices of the invariant polyhedra do not change supports.

The dual of a mass-action network

There is a clear duality between the stoichiometric and the conservation space. This duality can be interpreted as a duality between chemical species and rate constants. Consequently, we define the dual of a chemical reaction network to be

x Ye x Yp k * = k Y T e k Y T p x .
For conservative systems the duality between the conservation and the stoichiometric space can be interpreted in terms of a duality between the corresponding nonnegative cones. As there is a one to one correspondence between the extreme rays of the stoichiometric cone and the minimal cycles of the mass-action network, one can conclude that conserved quantities are dual to minimal cycles. Consequently we get the following result:

Theorem. For conservative mass-action networks that do not have two species with exactly the same rates the set of preclusters is dual to the set of maximal invariant polyhedral supports.

The condition ẋi = ẋj is necessary because we need to make sure that no further clustering on the left kernel is done.

We conclude with the following question:

Question. Is there a duality relation between clusters and siphons?

  December 11, 2020.

Clusters and preclusters are defined in Chapter 4 of Author's Thesis: https://www.opendata.uni-halle.de/handle/1981185920/14078

Acknowledgment

The main body of this research was done in parallel with author's thesis. This project was funded by the Deutsche Forschungsgemeinschaft, 284057449, and by the DFG-RTG "MathCore", 314838170.


Stefan Haar
email: stefan.haar@inria.fr

Serge Haddad
email: haddad@lsv.fr

Stefan Schwoon
email: schwoon@lsv.fr

Lina Ye
email: lina.ye@lri.fr

Active Prediction for Discrete Event Systems

Keywords: 2012 ACM Subject Classification Theory of Computation -Formal Languages and Automata; Mathematics of Computing -Discrete Mathematics Automata Theory, Partially observed systems, Diagnosability, Predictability

published or not. The documents may come

L'archive ouverte

Introduction

Monitoring faulty systems. In monitoring faulty systems, two central tasks consist in detecting a fault that has occurred, resp. will occur, i.e. the tasks of diagnosis and prediction, respectively, based on observations. However, such tasks may be defeasible due to ambiguity (i.e. observations associated with both correct and faulty runs). In this case, one may introduce a controller to restrict the behaviour in order to enforce diagnosis (resp. prediction) to be processed. Such a controller is called an active diagnoser (resp. active predictor ). Here we focus on the existence of an active predictor, a problem called active predictability. Diagnosis. In partially observed discrete-event systems, diagnosis was defined and studied in the seminal paper by Sampath et al [START_REF] Sampath | Diagnosability of discrete-event systems[END_REF] (see also [START_REF] Cassandras | Introduction to Discrete Event Systems -Second Edition[END_REF][START_REF] Cassez | Fault diagnosis with static and dynamic observers[END_REF]). That work builds a deterministic version of the original model, a so-called diagnoser, that tries to detect the occurrence of faults. A system is called diagnosable if the diagnoser can detect every fault occurrence, possibly after some delay. As an illustration, consider the system in Figure 1, which we shall use as a running example, sometimes with different values for Σ 1 and Σ 2 , where Σ 1 and Σ 2 are subsets of events in the system. Precisely, Σ 1 , Σ 2 ⊆ {a, b, c, d}, all of which are observable, while f represents a fault that is not directly observable. If, e.g., a is contained in both Σ 1 and Σ 2 , then the system is not diagnosable because any observation ada n may belong to a faulty run or a correct one.

The diagnosability problem is in PTIME [START_REF] Yoo | Polynomial-time verification of diagnosability of partially observed discrete-event systems[END_REF], via an approach called twin-plant construction. When the system is not diagnosable, it may have to be redesigned, e.g. by adding further sensors to enhance observability, or by forbidding some actions. Sampath et al [START_REF] Sampath | Active diagnosis of discrete-event systems[END_REF] followed the last approach, called active diagnosis: one strives to synthesise a controller, based on partial observations, that forces the behaviour of the system to stay within a diagnosable subset of its behaviours. For instance, if the system in Figure 1 has Σ 1 = Σ 2 = {b} and the controller has the right to block a, then the system is actively diagnosable.

The algorithm for the active-diagnosability problem in [START_REF] Sampath | Active diagnosis of discrete-event systems[END_REF] operates in doubly exponential time. In [START_REF] Haar | Optimal constructions for active diagnosis[END_REF], we revisited the problem using automata and game theory and established that in fact the active-diagnosability problem is EXPTIMEcomplete. Later on, we generalised the framework, e.g. allowing the controller to be aware of deadlocks [START_REF] Böhm | Active diagnosis with observable quiescence[END_REF]. We also studied active diagnosis for probabilistic systems [START_REF] Bertrand | Active diagnosis for probabilistic systems[END_REF].

In loosely related works. Chanthery and Pencolé [START_REF] Chanthery | Monitoring and active diagnosis for discrete-event systems[END_REF] proposed a planningbased approach that allows the verdict of the diagnoser to be ambiguous; the works in [START_REF] Cassez | Fault diagnosis with static and dynamic observers[END_REF][START_REF] Dallal | On most permissive observers in dynamic sensor activation problems[END_REF][START_REF] Yin | A general approach for optimizing dynamic sensor activation for discrete event systems[END_REF] studied the problem of dynamic sensor activation to ensure some observation properties. In work more closely related to ours [START_REF] Yin | A uniform approach for synthesizing property-enforcing supervisors for partially-observed discrete-event systems[END_REF], Yin and Lafortune proposed a uniform approach for synthesizing property-enforcing supervisor by mapping the considered property to a suitably-defined information state, which is applicable to a class of properties that can be expressed in terms of such information states, including safety, diagnosability, opacity and so on. Note that predictability cannot be formulated as an information state in that framework since it depends also on future behaviours of the system; its enforcement thus requires new methods. Fig. 1: Running example, with unobservable events indicated by dashed lines.

Prediction. Several works have studied the (passive) predictability problem, i.e. where no control is involved. For instance, if Σ 1 = {b} and Σ 2 = {c} in Figure 1, then upon first seeing c, an observer can predict that a fault will necessarily occur. In [START_REF] Genc | Predictability of event occurrences in partially-observed discrete-event systems[END_REF], Genc and Lafortune introduced a diagnoser construction to derive a necessary and sufficient condition for predictability in systems modeled by regular languages. Ye, Dague, and Nouioua [START_REF] Ye | Predictability Analysis of Distributed Discrete Event Systems[END_REF] proposed a polynomial time algorithm for predictability analysis in a centralized way and then extend it to a distributed framework. Brandan Briones and Madalinski [START_REF] Briones | Bounded predictability for faulty discrete event systems[END_REF] introduced and studied two variants of predictability by defining an additional requirement about either a lower bound or an upper bound on the number of events between the fault prediction and the fault occurrence. Then Yin and Li [START_REF] Yin | Decentralized fault prognosis of discrete event systems with guaranteed performance bound[END_REF] investigated the bounded predictability in the decentralized framework, and proposed a polynomial-time algorithm for its verification. Madalinski and Khomenko [START_REF] Madalinski | Predictability verification with parallel LTL-X model checking based on Petri net unfoldings[END_REF] reduce the predictability problem for a Petri net to LTL-X model checking. All these previous works focus on passive predictability.

Our contributions. First we refine the paradigm of prediction by allowing an observer to quantify its observations. Unlike [START_REF] Briones | Bounded predictability for faulty discrete event systems[END_REF] but similar to [START_REF] Yin | Decentralized fault prognosis of discrete event systems with guaranteed performance bound[END_REF], our predictors can at the same time provide both lower and upper bounds on the number of observations before a fault may (resp. must) occur. For instance, upon seeing c in the previous example, an observer can not only predict that a fault will eventually happen but that it will necessarily happen between the first and the second observable event after c. In practice, if a fault prediction is issued, the reaction procedure of the system should be triggered. As such interventions may require a certain amount of time to take effect, having both lower and upper bounds are relevant performance criteria for capture such timing issues.

We then turn to the case of active prediction, where a controller tries to restrict the system's behaviour so that faults can be reliably predicted. For instance, if Σ 1 = {a, b} and Σ 2 = {a, c} in Figure 1, then faults are unpredictable, but if a controller has the right to block a, it becomes actively predictable (with the aforementioned bounds). We formalize the idea of active predictability and then propose a class of controller, called active predictor. We then show that active predictability is equivalent to the existence of an active predictor.

Next, we focus on the decision and synthesis problems, i.e. to decide whether the system is actively predictable, and if so, how to build an active predictor. In active diagnosability [START_REF] Haar | Optimal constructions for active diagnosis[END_REF], the solution exploited the fact that whether a sequence of observations is ambiguous (i.e. corresponds to both faulty and correct runs) is independent of the control that was applied in the past. In prediction, by contrast, the eventuality of a fault occurence in the future depends on the control that is going to be applied. Thus solving the active-predictability problems requires new techniques.

We establish that the decision problem is EXPTIME-complete by reducing it to a turn-based game with a Büchi objective of exponential size. A memoryless winning strategy of this game provides the main ingredient to build an active predictor. Furthermore we show that instead of solving this Büchi game (which takes quadratic time), one can equivalently in linear time (1) solve a reachability game, (2) build a safety game that depends on the winning states of the reachability game, and (3) solve it and combine the winning strategies to get a winning strategy for the Büchi game when it exists (see [START_REF] Haar | Active Prediction for Discrete Event Systems[END_REF] for all details).

Finally we study the relation between the lower prediction bound k and the number of states n of the system. We establish that if k ≥ 2 n then a system is k-actively predictable if and only if it is actively safe. This bound is tight since we exhibit a family of systems of size O(n) such that the system is 2 n -actively predictable but not actively safe.

Organization. In Section 2, we introduce prediction in both the uncontrollable and controllable framework and establish a class of controller called active predictor. The existence of such a controller is equivalent to active predictability. The construction of an active predictor (if it exists) is carried out in Section 3, providing simultaneously the solutions to the decision and synthesis problems. Section 4 complements these results by a tight analysis of complexity bounds. We conclude and give some perspectives to this work in Section 5. The missing proofs are developed in [START_REF] Haar | Active Prediction for Discrete Event Systems[END_REF].

The Active Prediction Problem

As usual, for an alphabet Σ, we use Σ * and Σ ω , to denote the finite and infinite words over Σ, and Σ ∞ := Σ * ∪ Σ ω . The length of a word σ ∈ Σ * is denoted |σ|, and represents the prefix notation.

Labeled transition systems

When dealing with discrete event systems (DES), systems are often modeled using labeled transition systems (LTS). Definition 1. A labeled transition system is a tuple A = Q, q 0 , Σ, T where:

-Q is a set of states with q 0 ∈ Q the initial state; -Σ is a finite set of events; -T ⊆ Q × Σ × Q is a set of transitions.
We note q a -→ A q for (q, a, q ) ∈ T ; this transition is said to be enabled in q. A run over the infinite word σ = a 1 a 2 . . . ∈ Σ ω is a sequence of states (q i ) i≥0 with q i ai+1 ---→ A q i+1 for all i ≥ 0, and we write q 0 σ = ⇒ A if such a run exists. A finite run over σ ∈ Σ * is defined analogously, and we write q σ = ⇒ A q if it ends at state q . A state q is reachable if there exists a run q 0 σ = ⇒ A q for some σ. The index A in those relations will be omitted if unambiguous.

In order to formalize problems related to prediction, we partition Σ into two disjoint sets Σ o and Σ uo , the sets of observable and of unobservable events, respectively. Moreover, we distinguish a special fault event f ∈ Σ uo . We say σ is correct if σ ∈ (Σ \ {f }) * (we will denote Σ \ {f } with the short form Σ \f in the following), and that σ is faulty otherwise. For Σ ⊆ Σ, define its projection P Σ (σ) inductively by: P Σ (ε) = ε; P Σ (σa) = P Σ (σ)a when a ∈ Σ , and P Σ (σa) = P Σ (σ) otherwise. For the sake of simplicity, write P for P Σo , |σ| o for |P(σ)|, |σ| Σ for |P Σ (σ)|, and for a ∈ Σ, write |σ| a for |σ| {a} . When σ is an infinite word, its projection is the limit of the projections of its finite prefixes. This projection can be either finite or infinite. As usual the projection is extended to languages.

Definition 2 (Languages of an LTS). Let A = Q, q 0 , Σ, T be an LTS. The finite and the infinite (correct) languages of A are defined by:

-L * (A) = { σ ∈ Σ * | ∃q q 0 σ = ⇒ q } and L ω (A) = { σ ∈ Σ ω | q 0 σ = ⇒ }; -L * c (A) = { σ ∈ (Σ \f ) * | ∃q q 0 σ = ⇒ q } and L ω c (A) = { σ ∈ (Σ \f ) ω | q 0 σ = ⇒ } A is safe if L * (A) = L * c (A) (i.
e. no fault ever occurs).

The union of finite and infinite languages of

A is denoted L ∞ (A) = L * (A) ∪ L ω (A).
The inverse observable projection with respect to A and w ∈ Σ * o is defined as P -1 A (w) = {σ ∈ L * (A) | P(σ) = w}, which can be simply denoted by P -1 (w) if there is no ambiguity. An LTS A is deterministic if for every pair q ∈ Q, a ∈ Σ there is at most one q such that q a -→ q . For a deterministic LTS we write T (q, a) = q if q a -→ q . As is the case for classical diagnosis problems, we make two assumptions on A:

-Liveness: ∀q ∈ Q, ∃a, q , q a -→ q . -Convergence: L ω (A) ∩ Σ * Σ ω uo = ∅.
Liveness implies that from any reachable state of an LTS, there exists at least one transition enabled in that state. Convergence guarantees that there is no infinite sequence of unobservable events. When A is convergent, then for all σ ∈ L ω (A), one has P(σ) ∈ Σ ω o . Example 3. Figure 1 shows a live and convergent LTS with

Σ o = {a, b, c, d}, Σ uo = {f }, Σ 1 ⊆ Σ o , Σ 2 ⊆ Σ o and Σ 1 ∪ Σ 2 = ∅.
Transitions labelled by unobservable events are dashed. We also factorize transitions with same source and target states. Depending on Σ 1 and Σ 2 , this LTS may have different levels of predictability (see Example 7 for further explanation).

Predictability

Intuitively, a system is predictable with respect to a fault f if in every faulty run, an observer can be certain that f is going to occur before it actually happens. Before formally defining predictability, we first present some useful notations. Given σ ∈ L ∞ (A) and n ≤ |σ| o , pre n (σ) denotes the minimal (w.r.t.

) prefix of σ such that |pre n (σ)| o = n. As an abbreviation, pre(σ) := pre |σ|o (σ) removes unobservable events from the end of σ. For example, in the LTS of Figure 1, we have (as f is unobservable) pre 0 (bdf ) = ε, pre 1 (bdf ) = b and pre(bdf ) = pre 2 (bdf ) = bd. We naturally extend pre to sets of words.

An observed sequence w forbids prediction of a fault when a correct, infinite future behavior is still possible. We introduce different kinds of observed sequences.

-surely correct in A if pre(P -1 A (w)) ∩ Σ * f Σ * = ∅; -surely faulty in A if P -1 A (w) ∩ L * c (A) = ∅; -ambiguous in A if it is neither surely correct nor surely faulty in A; -m-correct in A if ww is surely correct in A for all w ∈ Σ m o ; -m-faulty in A if ww is surely faulty in A for all w ∈ Σ m o ; -ω-faulty in A if there exists m ∈ N such that w is m-faulty.
We now define the notion of k-l-predictability, which means that the occurrence of a fault can be predicted with certainty, based on what has been observed so far, at least k observations before it does occur, and such that the fault definitely occurs before the l-th additional observation. In the sequel, N + denotes N \ {0} and N ω (resp. N + ω ) denotes N (resp. N + ) enlarged with ω which is an absorbing item for addition.

Definition 5. (Predictability) Let

A be an LTS, w ∈ Σ * o , k ∈ N, and l ∈ N + ω . -w is k-l-faulty in A if w is k-correct and (k + l)-faulty in A. -A is k-l-predictable if for all σf ∈ L * (A), P(σ) has a k-l-faulty prefix. Remark 6. If w is k-l-faulty in A, then w is also k -l -faulty in A for all k ≤ k and k + l ≥ k + l.
As an abbreviation, we will call A k-predictable if it is k-ω-predictable, and simply predictable if it is 0-predictable. Thus, Remark 6 implies that predictability is weaker than any other notion of k-l-predictability.

Example 7. Consider the LTS of Figure 1:

-it is not predictable if Σ 1 ∩ Σ 2 = ∅; -it is 1-1-predictable and not 2-predictable if Σ 1 ∩ Σ 2 = ∅, and both of them are not empty; -it is 2-1-predictable if Σ 1 = ∅ and Σ 2 = ∅.
Proposition 8 establishes bounds for predictability in finite LTS: Proposition 8. kkpredic Let A be a k-predictable LTS with n states, where n is finite.

(i) A is k-n-predictable. (ii) If A is not safe, then k < n.

Active predictability

We suppose that Σ o is partitioned into subsets Σ c ⊆ Σ o of controllable and Σ uco = Σ o \Σ c of uncontrollable actions. Intuitively, a controller may forbid a subset of the controllable actions based on the observations made so far, thereby restricting the behaviour of A.

Definition 9 (Controlled LTS). Let A be an LTS. A controller for A is a mapping cont : P(L * (A)) → 2 Σ such that for all w, Σ uco ∪ Σ uo ⊆ cont(w). The controlled LTS A cont = Q cont , q 0cont , Σ, T cont is defined as the smallest LTS satisfying:

-q 0cont = ε, q 0 ∈ Q cont ; -if w, q ∈ Q cont , a ∈ cont(w)
, and q a -→ A q , then wP(a), q ∈ Q cont and w, q a -→ Acont wP(a), q .

The goal of our controllers is to make the system predictable by preserving liveness and to perform prediction at the same time. Before formally defining prediction verdicts in Definition 11, we discuss their intuitive meanings: means that the controller is currently unable to predict a fault, while k, l means that the run is correct so far but a fault can be predicted to happen between the next k and k + l observations. When l = ω, a fault is predicted but without an upper bound. ?, m means that a fault may or may not have happened yet but one will surely occur within m further observations, and ⊥ means that a fault has definitely already occurred.

Example 10. Consider again the LTS from Figure 1 and assume that Σ 1 = {a} and Σ 2 = {b}. At the beginning, no fault can be predicted, so a controller would be expected to emit the prediction . After observing b, the controller could predict that a fault will happen between the first and second next observation to come, i.e. 1, 1 . After seeing d, this would change to 0, 1 , and finally to ⊥.

Definition 11 (predictions). Let

P := { } ∪ (N × N + ω ) ∪ ({?} × N + ω )
∪ {⊥} be the set of possible predictions. We define the following measures κ, µ :

P → N ω ∪ {-1, ω + 1}: -κ( ) = ω + 1, κ( k, l ) = k, and κ(p) = -1 otherwise; -µ( ) = ω + 1, µ( k, l ) = k + l, µ( ?, m ) = m, and µ(⊥) = 0.
We also define two particular types of subsets of P: For k ∈ N and l ∈ N + , let

P k,l := { , ⊥} ∪ { k , l | k ≤ k, l ≤ l } ∪ { ?, m | m < l } and P k,ω := { , ⊥, ?, ω } ∪ { k , ω | k ≤ k }.
The values κ(p) and µ(p) define the 'window' (lower and upper bound on future observations) within which a fault is to occur according to prediction p. Here, -1 indicates that the fault may or must have occurred in the past, and in the case of , ω + 1 is chosen for technical convenience. A predictor using values from P k,l makes firm commitments on both the lower and upper bounds within which a fault is going to occur, while a predictor with values from P k,ω only commits to a lower bound.

Definition 12 (compatible predictions). Let p, p ∈ P and k ∈ N, l ∈ N + ω . We say that p, p are k-l-compatible if the following conditions are all satisfied:

-if p = , then κ(p ) ≥ k else κ(p ) ≥ κ(p) -1; -µ(p ) ≤ µ(p), and if 0 < µ(p) < ω, then µ(p ) < µ(p); -if p = , then µ(p ) ≤ k + l. Moreover, p is called k-l-initial if , p are k-l-compatible.
The conditions in Definition 12 describe the relations that should reasonably hold between a prediction p made for some observation w and the prediction p made when one has observed one additional event in a k-l-predictable controlled LTS. Intuitively these are:

1. When a fault is first predicted, it should be at least k observations in advance, and the gap between this lower bound and the upper bound should be at most l. This is why p = should imply κ(p ) ≥ k. In particular, one cannot switch from to k , l for any k < k, nor directly to ?, m or ⊥. Moreover, the third condition ensures that when switching from to k , l , we have

k + l ≤ k + l, which with k ≥ k implies l ≤ l. 2.
Having predicted a fault within a certain 'window', the subsequent predictions can only become more precise. Thus, one can maintain or shrink that window, but not enlarge, shift, or forget about it. Figure 2 illustrates this idea. E.g., when a predictor announces a fault between the 3rd and 7th following observation, expressed by p = 3, 4 , then one step later it must give p = 2, 4 or a more precise verdict such as 3, 2 . As another example, if the controller has arrived at a verdict of ?, 6 , meaning "a fault has occurred, or will occur within six further observations", then the information gained from an additional observation may lead it to conclude that the fault has now definitely occurred (⊥), will occur later (e.g., 1, 3 ), or to maintain the prediction (e.g., ?, 5 ). Note that ?, 6 could only be reached by passing through 0, m , for some m > 6, earlier in the observation. These relations are ensured by allowing κ to decrease by at most one and requiring µ to strictly decrease (if an upper bound was given).

A k-l-initial prediction is one that is admissible for the empty observation.

Definition 13 (active predictor). Let A be an LTS, P ⊆ P, and h = cont, pred , where cont is a controller and pred is a mapping from P(L * (A cont )) to P . We call h a k-l-active predictor over P , for k ∈ N and l ∈ N + ω , if and only if:

(i) A cont is live; (ii) pred (ε) is k-l-initial;
(iii) for w ∈ P(L * (A cont )), the prediction satisfies the following: (iv) for a ∈ Σ o , w, wa ∈ P(L * (A cont )), pred (w), pred (wa) are k-l-compatible.

-if pred (w) = , then w is (k + 1)-correct in A cont ; -if pred (w) = k , l , then w is k -l -faulty in A cont ; -if pred (w) = ?,
Intuitively, condition ((i)) requires that the control cannot introduce deadlocks, and conditions ((ii)),((iii)) ensure that the predictions have the intended semantics. Condition ((iv)) ensures compatibility between two subsequent predictions along an observation. If there exists a k-l-active predictor for A, we call A k-l-activepredictable, or just actively predictable. Moreover, A is called actively safe if there exists an active predictor for A over { }, which entails that A cont is safe. In this example, h is a 1-1-active predictor.

Proposition 15 and Proposition 16 will exhibit a tight correspondence between the existence of a k-l-predictor for A and the existence of a controller that makes A k-l-predictable. Additionally, Proposition 16 shows that the set of predictions used in a predictor can be limited to a finite set, either committing the prediction to a lower and upper bound for the occurrence of a fault, or just a lower bound.

Proposition 15. firstpart If h = cont, pred is a k-l-active predictor for an LTS A, then A cont is k-l-predictable.
Proposition 16. secondpart Let A be an LTS. If there exists a controller cont such that A cont is live and k-l-predictable, then there exist k-l-active predictors h = cont, pred for A over both P k,l and P k,ω .

Finally, we introduce the notion of pilot as an automata-based representation of k-l-active predictors. In Section 3 we will show how to find a finite-state pilot when A is actively predictable and finite-state.

Definition 17 (pilot). Let A be an LTS, then

C = B C , cont C , pred C is called pilot for A over P ⊆ P if B C = Q c , q c 0 , Σ o , T c is a deterministic LTS with labellings cont C , pred C : Q c → 2 Σ × P . Let h C = cont,
pred associated with C be defined by cont(w) = cont C (q) and pred (w) = pred C (q) for all w ∈ P(L * (A)), where q is the unique state such that q c 0 w = ⇒ q. Then C is a k-l-active predictor for A if h C is one.

Controller construction

We solve the decision and synthesis problems simultaneously. We try to construct a pilot-based k-l-active predictor over some P ⊆ P for an LTS A. The construction succeeds if and only if A is k-l-actively predictable. According to Definition 13, the main challenges in building an active predictor are to ensure that (i) the controlled system remains live, (ii) the fault can be predicted at least k observations before its occurrences, and (iii) the prediction information is provided.

Our solution consists in building a turn-based game (see [START_REF] Grädel | Automata, Logics, and Infinite Games: A Guide to Current Research[END_REF] for turn-based games) by taking into account the control that has already been performed.

Definition 18 (turn-based game).

A game G with two players called Control and Environment is a tuple V C , V E , E, v 0 , WIN , where:

-V C , V E are the vertices owned by Control and Environment, respectively, and

V G = V C V E denoting all vertices, with v 0 ∈ V C being an initial vertex; -E ⊆ V G × V G is a set of directed edges such that for all v ∈ V G , there exists (v, v ) ∈ E; -WIN ⊆ V ω
G is a set of winning sequences.

Given a sequence ρ = v 0 v 1 ...v n , we denote ρ[i] = v i . A play is a sequence of V ω G such that ρ[0] = v 0 and ρ[i], ρ[i + 1] ∈ E for all i ≥ 0; we call ρ k := ρ[0] • • • ρ[k],
for some k ≥ 0, a partial play if ρ[k] ∈ V C , and define last(ρ k ) := ρ[k]. We write Play * (G) for the set of partial plays of G. A play ρ is called winning

(for Control) if ρ ∈ WIN . A Büchi game V C , V E , E, v 0 , V F defines a game V C , V E , E, v 0 , WIN such that WIN = { ρ ∈ V ω G | ρ[i] ∈ V F for infinitely many i }. A reachability game V C , V E , E, v 0 , V F defines a game V C , V E , E, v 0 , WIN such that WIN = V * G V F V ω G . A safety game V C , V E , E, v 0 , V F defines a game V C , V E , E, v 0 , WIN such that WIN = V ω F . Definition 19 (strategy). Let G = V C , V E , E, v 0 , WIN be a game. A strategy (for Control) is a function θ : Play * (G) → V G such that (last(ξ), θ(ξ)) ∈ E for all ξ ∈ Play * (G). A play ρ adheres to θ if ρ[i] ∈ V C implies ρ[i + 1] = θ(ρ i )
for all i ≥ 0. A strategy is called winning if every play ρ that adheres to θ is winning. A positional (also called memoryless) strategy is a function θ :

V C → V G such that (v, θ (v)
) ∈ E for all v ∈ V C ; we call θ winning if the strategy θ with θ(ξ) = θ (last(ξ)) is winning.

To verify k-l-active predictability of a given system, the controller that we propose needs to memorize two subsets of states with the corresponding prediction information Q c , Q f , p . The subset Q c (resp. Q f ) represents the possible states reached by a correct (resp. faulty) run after the last observable action, and Q c ∪ Q f = ∅. The prediction information p ∈ P is (non-deterministically) decided based on the current observations. We denote

Reach( Q c , Q f , p ) := Q c ∪ Q f and Q := 2 Q \ {∅}.
The set of possible tuples memorized by the controller is defined as S P = S c P ∪ S a P ∪ S f P , where:

-S c P = Q × {∅} × { p ∈ P | κ(p) ≥ 0 } -S a P = Q × Q × P ∩ ({?} × N + ω ) -S f P = {∅} × Q × {⊥}
In the following, we will simply write S for S P when P is clear from context.

The controller needs to update the state subsets after an observable action, for which we first define some sets of possible next states from a given state q after a ∈ Σ o .

-NO A (q, a) = { q | q σ = ⇒ A q , σ ∈ Σ * uo a } -NOC A (q, a) = { q | q σ = ⇒ A q , σ ∈ (Σ uo \ {f }) * a } -NOF A (q, a) = { q | q σ = ⇒ A q , σ ∈ Σ * uo f Σ * uo a }
One can omit the subscript A when there is no ambiguity. The extension to a set of states is defined in a natural way, e.g. NO(Q , a) = q∈Q NO(q, a). We now define how the controller updates its tuple once an observable action occurs.

In the following, represents a state in which the controller has lost, and we denote S := S ∪ { }.

Definition 20 (knowledge update).

Let A be an LTS, P ⊆ P, and k ≥ 0.

Then the knowledge transition relation

∆ k A ⊆ S × Σ o × S is defined as follows. Let s = Q c , Q f , p ∈ S and a ∈ Σ o . Then s, a, s ∈ ∆ k
A if and only if:

1. either s = NOC (Q c , a), NOF (Q c , a) ∪ NO(Q f , a
), p ∈ S and p, p are k-l-compatible; 2. or s = when there is no s ∈ S such that s, a, s ∈ ∆ k A .

Notice that, given s and a, the choice of s is largely deterministic except for p , which must be k-l-compatible with p. When s has no prediction consistent with the updated correct resp. faulty state subsets, cf Definition 13((iii)), then the only possible update is to .

Example 21. Consider the LTS in Figure 1 and assume that Σ 1 = {a, c}, Σ 2 = {a, b} and Σ c = {a, b, c}. 1. Let s = {q 0 }, ∅, . If the observable action a is chosen, then we have s, a, s ∈ ∆ k A , where s = {q 1 , q 4 }, ∅, . Notice that , are k-lcompatible.

2. Let s = {q 2 , q 5 }, ∅, after observing a and d. If a is chosen from here, we can only have s, a, ∈ ∆ k A . The reason is that after a, the system can end up in either q 3 (with a fault) or in q 5 (without fault), the next prediction should thus be an ambiguous one, i.e., ?, m . However, , ?, m are not k-l-compatible. It follows that there does not exist s ∈ S such that s, a, s ∈ ∆ k A . Hence we have s, a, ∈ ∆ k A by Definition 20.

The objective of Control is to obtain a winning play by suitably restricting the possible actions, and any winning strategy corresponds to a controller with which the controlled system is predictable. The game begins with Control to choose a prediction for ε. Then the game proceeds in rounds: 1) Control restricts the set of possible actions to some Σ ; 2) Environment chooses a ∈ Σ to determine the next state. 3) Control updates its knowledge.

The choices of Control are subject to some restrictions. Indeed, each state s = Q c , Q f , p represents Control's knowledge about the current potential states of A as well as the corresponding prediction information. To ensure that the controlled system remains live, the set of possible actions Σ must not cause deadlocks in any state reachable by unobservable actions from Q c ∪ Q f . Also, Control cannot prevent the uncontrollable actions. So we define the admissible sets and the game as follows, where we use

Σ PO (q) = {a ∈ Σ o | q σ = ⇒ q , σ ∈ Σ *
uo a } to denote the possible next observable actions from the state q, which can be extended to a set of states in a natural way.

Definition 22 (admissible action set)

. Let A = Q, q 0 , Σ, T be an LTS and Q ⊆ Q be a subset of states. We call Σ ⊆ Σ o an admissible set for Q if it fulfills the following conditions:

-Σ uco ⊆ Σ as any action in Σ uco is observable but not controllable.

for all q ∈ Q , q ∈ Q, and σ ∈ Σ * uo , q σ = ⇒ q implies Σ PO (q) ∩ Σ = ∅.

The set of admissible sets for Q are denoted as adm(Q ), which is not empty when Q = ∅ as A is a live and convergent LTS.

Example 23. Consider the same LTS as in Example 21.

Let Q = {q 0 }. Then adm(Q ) = {Σ | Σ ⊆ Σ o , {d} Σ }.
In other words, adm(Q ) contains all subsets of Σ o = {a, b, c, d} that include d, except the singleton {d}, which is not an admissible set as it blocks the system. More precisely, the set of possible next observable actions from q 0 is Σ PO (q 0 ) = {a, b, c}, whose intersection with {d} is empty. Thus {d} cannot be an admissible set for Q .

The vertices of our controller-synthesis game consist of an initial vertex ι, the states of S , a set V 1 := S × 2 Σo where Control has chosen a set of permitted actions, and a set V 2 := S × Σ o where Environment has chosen an observable action. The winning condition assures that once a fault has been predicted, it will eventually happen.

Definition 24 (controller-synthesis game). Let A be an LTS and P ⊆ P. We denote G k,l A,P the Büchi game

V C , V E , E, ι, V F , where V C = {ι} ∪ S ∪ V 2 , V E = V 1 , V F = Q × {∅} × { } ∪ {∅} × Q × {⊥} ⊆ S, and E = E ι ∪ E 1 ∪ E 2 ∪ E 3 ∪ { , },
where

-E ι = ι, {q 0 }, ∅, p | p is k-l-initial ⊆ {ι} × S; -E 1 = s, s, Σ | s ∈ S, Σ ∈ adm(Reach(s)) ⊆ S × V 1 ; -E 2 = s, Σ , s, a | s ∈ S, a ∈ Σ PO (Reach(s)) ∩ Σ ⊆ V 1 × V 2 ; -E 3 = s, a , s | s, a, s ∈ ∆ k A ⊆ V 2 × S .
Note that the set V 2 records the sequence of observable actions that occur during a play.

s 0 = {q 0 }, ∅, , s 1 = {q 1 , q 4 }, ∅, , s 2 = {q 1 }, ∅, p 2 , s 3 = {q 4 }, ∅, p 3 , and
s 4 = {q 2 , q 5 }, ∅, .
Example 25. Figure 3 depicts a part of a game for some k, l and the LTS of Figure 1, for which we assume again Σ 1 = {a, c}, Σ 2 = {a, b} and Σ c = {a, b, c}. From ι, Controller can choose any k-l-initial prediction; we consider the case where is chosen, so s 0 = {q 0 }, ∅, . Then from Example 23, we have adm(Reach(s 0 )) = adm({q 0 }) = {Σ | Σ ⊆ Σ o , {d} Σ }. Environment cannot choose the action d even when d is in the admissible set since d / ∈ Σ PO (Reach(s 0 )). After Environment chooses an available action (say a, leading to s 0 , a ), Control updates its knowledge and chooses a new prediction, say , leading to s 1 , with q 1 , q 4 as the possible new states. From here, d is the only choice for Environment. Suppose that Control then again chooses as its new prediction in s 4 , thus s 4 = {q 2 , q 5 }, ∅, . If a is now chosen, from the second case of Example 21, we know that the game enters . To avoid losing, Control needs to switch to a different prediction early enough. Now we establish the strong connection between winning strategies and active predictors.

Proposition 26. frompredtogame Given h = cont, pred a k-l-active predictor over P for an LTS A, there exists a corresponding winning strategy θ h in the game G k,l A,P .

The existence of a winning strategy implies the existence of a positional one due to well-known results of game theory (see e.g. [START_REF] Grädel | Automata, Logics, and Infinite Games: A Guide to Current Research[END_REF] for all results here related to turn-based games). For the reverse direction, we next define a pilot from a positional winning strategy in G k,l A,P before proving that this pilot is a k-l-active predictor.

Definition 27. Let θ be a positional winning strategy in G k,l A,P . We define a pilot C θ := B θ , cont θ , pred θ over P as follows:

-B θ = Q θ , q θ 0 , Σ o , T θ , where 1. Q θ = {q ∈ S | q = last(ξ θ ) and ξ θ ∈ Play * (G k,l A,P ) adhering to θ} 2. q θ 0 = θ(ι) 3. T θ (s, a) = θ( s, a ) -cont θ (s) = Σ ∪ Σ uo for any s ∈ Q θ , where θ(s) = s, Σ ; -pred θ (s) = p, for any s = Q c , Q f , p ∈ Q θ
Proposition 28. fromgametopred Let θ be a positional winning strategy in G k,l A,P . Then C θ is a k-l-active predictor over P for A.

Combining the results of Propositions 26 and 28, we obtain that the activepredictability problem for an LTS A with n states reduces to solving a Büchi game with 2 O(n) vertices. Since Büchi games can be solved in polynomial time, we obtain the following result:

Theorem 29. The active-predictability problem for finite-state LTS belongs to EXPTIME.

We conclude the section with a supplementary result showing that due to the special structure of G k,l A,P it can actually be solved in linear time (w.r.t. the size of the game), and not in quadratic time as performed for general Büchi games.

Proposition 30. linear If A is a finite-state LTS and P ⊆ P, then G k,l A,P can be solved in O(|E|).

Bound analysis

We first prove that it is EXPTIME-hard to decide whether a given LTS A is actively k-l-predictable, independently of k and . The proof (developed in [START_REF] Haar | Active Prediction for Discrete Event Systems[END_REF]) is similar to the proof in [START_REF] Haar | Optimal constructions for active diagnosis[END_REF] that active diagnosability is EXPTIME-hard and relies on a reduction from safety games with imperfect information [START_REF] Berwanger | On the power of imperfect information[END_REF].

Theorem 31. hardness The active-predictability decision problem is EXPTIMEhard.

Together with Theorem 29, we obtain the following corollary.

Corollary 32. The active-predictability decision problem is EXPTIME-complete.

We study the relation between active predictability and active safety. Theorem 33 relates the maximal advance warning for fault predictions to the number of states in A.

Theorem 33. predtosafe Let A be an LTS with n states. If A is 2 n -activepredictable, then it is actively safe.

Proof. If A is 2 n -ω-active-predictable then by definition there exists a 2 n -ω-active predictor h = cont, pred over P := P k,ω for A, and by Proposition 26 there exists a winning strategy θ in G k,ω A,P . In turn, this winning strategy provides a pilot C θ = B, cont , pred according to Proposition 28; let B = Q, q 0 , Σ o , T . We shall construct a new pilot C for A over { }, proving that A is actively safe.

Remember that Q is the set of Controller-owned vertices in G k,ω A,P that can be reached by plays adhering to θ and that these vertices are a subset of S P . For q, q ∈ Q, let us write q ≺ q if q is reachable from q in B. Since θ is positional and winning, ≺ must be an acylic relation between those states of Q that are not members of V F , i.e. their associated prediction is neither nor ⊥ (cf Definition 24). We now call q ∈ Q a cutoff if q is of the form Q c , Q f , p and there exists a state q = Q c , Q f , p with p = p and q ≺ q. Let co(q), the corresponding state of q, denote the state that is ≺-minimal among all the choices for q ; due to the structure of the states outside V F , co(q) is unique and not a cutoff itself. Moreover, a state of Q is called useless if it is either a cutoff or all its (immediate) predecessors in B are useless, and useful otherwise.

Remember that S P is a union of S c P , S a P , and S f P , where S c P contains the states of the form Q c , ∅, p , with κ(p) ≥ 0. Thus, states in S c P are only reached through correct runs in A cont . Let S := { Q c , ∅, p | κ(p) = 0 }. It follows from the construction of G k,ω A,P (cf Definition 20 and Definition 24) that any path from q 0 to a state from S is of length at least 2 n , so by pigeonhole principle, any path leading to S contains a cutoff. Since S a P ∪ S f P can only be reached by going through S , those states are useless.

We can now construct the desired pilot C by "folding" cutoffs back onto their corresponding states. We remark in this context that Reach(q) = Reach(co(q)), and therefore the admissible control choices for both states are the same; proving that the resulting controlled system is live depends only on this property. Since the controlled system never admits a fault, the prediction can be in all cases. More formally, C := Q , q 0 , Σ o , T , cont , pred , where Q is the useful subset of Q, and for all q ∈ Q , a ∈ Σ o :

-T (q, a) = T (q, a) if T (q, a) ∈ Q and T (q, a) = co(T (q, a)) otherwise; pred (q) = .

Theorem 33 implies that if a system is not actively safe, then there is an exponential upper bound on the advance warning that an active predictor can issue. This bound is asymptotically precise, as the following family of examples shows.

Theorem 34. counter There exists a family of systems (A n ) n≥1 with O(n) states such that A n is not actively safe but 2 n -active-predictable. Proof. Figure 4 shows a family of LTS with O(n) states but an alphabet of size O(n) and O(n 2 ) transitions. We first provide a proof for this family as it is easier to understand. After this, we provide a more complex example with a constant-size alphabet and O(n) states and transitions.

p s n-1 s 1 s 0 q q p p n -1 Σ n-1 1 Σ 1 0 Σ 0 Γ n-1 Γ 1 n -1 1 0 u f n Γ n n f n . . . . . .

Variable-size alphabet

Consider the LTS shown in Figure 4. The observable actions are {0, . . . , n}, all of which are controllable. There are only two unobservable actions, u and the fault f . We abbreviate by Σ i := {i + 1, . . . , n} the actions larger than i for 0 ≤ i < n, and by Γ i := {0, . . . , i -1} the actions smaller than i for 0 < i ≤ n. The initial state is p. Evidently A n is actively safe if a controller can avoid both p and q; as we shall see, this is impossible. However, the system is actively predictable if the controller can at least avoid q. We shall see that this is indeed possible while entering p only after 2 n steps, by simulating a binary counter.

We can assume (w.l.o.g.) that the controller permits a single action from Σ o in each step and hence the controlled system will admit a single infinite observation sequence ρ. Having allowed a prefix σ of ρ, let R(σ) be the set of states that this sequence can lead to. If the controller wants to keep the system from making a fault, it must ensure that R(σ) remains within the set R := {p, s 0 , . . . , s n-1 }. When R(σ) ⊆ R, let us associate a measure defined as I(σ) := si∈R(σ) 2 i . We observe the following:

-R(ε) = {p}, hence I(ε) = 0.

-If s i ∈ R(σ), then the controller must not allow action i in the next step, otherwise the system may go to q, rendering it unpredictable. -As long as I(σ) < 2 n -1, the controller must permit an action i such that I(σi) > I(σ). To see this, let s i / ∈ R(σ), then R(σi) = (R(σ) ∪ {s i }) \ {s 0 , . . . , s i-1 }. We shall assume that i is chosen minimally, so I(σi) = I(σ)+1.

-Therefore, after 2 n -1 steps, the controlled system will have performed a sequence σ with I(σ) = 2 n -1. The only possible course of action for the controller is to permit n from now on, i.e. ρ = σn ω . We then have R(σn) = {p, p }, R(σnn) = {p , p }, and R(σnnn) = {p }.

Going backwards, we can now associate predictions with each prefix of ρ: pred (σn k ) = ⊥ for k ≥ 3, pred (σnn) = ?, 1 , pred (σn) = 0, 2 , and pred (σ) = 2 n -|σ|, 2 for every prefix σ of σ. Thus, A n is 2 n -2-active predictable. Notice that the system could be made 2 n -1-active predictable if states s 0 , . . . , s n-1 transitioned with n to p instead, which we avoided simply to keep the drawing of the automaton planar.

Constant-size alphabet

To see that the proof with a variable-size alphabet can be adapted to an alphabet of constant size, consider the LTS A n in Figure 5. A n has O(n) states and three observable and controllable actions 0, 1, a and two unobservable actions u and f . Initially, the LTS performs an a going to either p or r. The LTS then simulates A n of Figure 4, using a unary encoding, in the following sense: Let code(i) = 1 i 0 n-i a, for i = 0, . . . , n. The reader can verify, case-by-case, that for any two states u, v ∈ {p, p , s 0 , . . . , s n-1 , q} and i ∈ {0, . . . , n}, we have

u i - → v in A n iff u code(i)
----→ v in A n . Moreover, the controller must account for the possibility that the system has gone to state r. Then, to keep the controlled system live, the only possible sequences that the controller can enforce are code(i) for i = 0, . . . , n, and we have r code(i) ----→ r for i < n. After the initial a, the controller must therefore admit code(σn), for σ as in A n . On this basis, a closer look shows that A n is k-l-active predictable for k = 1 + (n + 1) • 2 n and l = n + 2.

Note that Theorem 34 does not contradict Proposition 8, which establishes linear prediction bounds w.r.t. the number of states of A. However, Proposition 8 talks about passive predictability, whereas Theorem 34 is about active predictability.

Conclusion and perspectives

We have extended the prediction paradigm by introducing parameters related to the number of observations before fault may or must occur. Within this framework, we have established that active predictability is EXPTIME-complete through a procedure for synthetising active predictors that builds a Büchi game. Solving this game is proved linear in the number of edges in the game. We have shown that if the observation threshold for eventual prediction is chosen large enough (namely ≥ 2 n with n the number of states in the system), then active predictability is equivalent to active safety. Furthermore we have exhibited a family of systems proving that this bound is tight.

Out of several possible extensions for the present results, three stand out as natural continuations. First, we want to introduce a measure that quantifies the faultiness of the system, and then aim to find an active predictor that minimizes this criterium, or at least ensures a value below some threshold. Second, we plan to study the notion of prediagnosis introduced in [START_REF] Bertrand | Foundation of Diagnosis and Predictability in Probabilistic Systems[END_REF] that combines predictability and diagnosability for controllable systems. Finally, we also want to study active predictability for probabilistic systems, as we had previously done for diagnosis in [START_REF] Bertrand | Active diagnosis for probabilistic systems[END_REF].

Definition 4 .

 4 (observation properties) Let A be an LTS, w ∈ Σ * o , and m ∈ N. Then w is:

3 ⊥Fig. 2 :

 32 Fig.2: Examples of compatible predictions p, p after n resp. n + 1 observations, where p is illustrated above the timeline, and p is one of the predictions below. Solid intervals indicate periods in which a fault is predicted.

Example 14 .

 14 In the LTS A of Figure 1, assume that Σ 1 = {a, c}, Σ 2 = {a, b}, Σ c = {a, b, c}. Let h = cont, pred be defined by: cont(ε) = {b, c, d, f }, and cont(w) = Σ otherwise; pred (ε) = pred (w) = , where w ∈ cΣ * o ∩ P(L * (A)), pred (b) = 1, 1 , pred (bd) = 0, 1 , and pred (bda + ) = ⊥.

Fig. 3 :

 3 Fig. 3: Part of the game for the LTS in Figure 1 (Example 25):s 0 = {q 0 }, ∅, , s 1 = {q 1 , q 4 }, ∅, , s 2 = {q 1 }, ∅, p 2 , s 3 = {q 4 }, ∅, p 3 , and s 4 = {q 2 , q 5 }, ∅, .

Fig. 4 :

 4 Fig. 4: A 2 n -active predictable LTS with O(n) states, where Σ o = Σ c = {0, ..., n}, Σ i = {i + 1, ..., n}, and Γ i = {0, ..., i -1}.

Fig. 5 :

 5 Fig. 5: Variant of Figure 4 with constant-size alphabet, with Σ o = Σ c = {0, 1, a}.

This research was done while Lina Ye was on leave at MEXICO team of INRIA.