S Schwan

M Menzel

M Fritzsche

A Heilmann

U Spohn

Micromechanical measurements on P-protein aggregates (forisomes) from Vicia faba plants

Keywords: P-protein aggregates, chemo-mechanical activity, influence of metal ions and pH, force measurement

Forisomes are chemomechanically active P-protein aggregates found in the phloem of legumes. They can convert chemical energy into mechanical work when induced by divalent metal ions or changes in pH, which control the folding state of individual forisome proteins. We investigated the changing geometric parameters of individual forisomes and the strength and dynamics of the forces generated during this process. Three different divalent ions were tested (Ca 2+ , Sr 2+ and Ba 2+ ) and were shown to induce similar changes to the normalized length and diameter. In the concentration range from 0.1 to 4 M, K + and Cl -ions had no influence on the contraction behaviour of the forisomes induced by 10 mM Ca 2+ . In the absence of dissolved oxygen, these changes were independent of the radius of the metal ion, water uptake and the strength of binding between the selected metal ions and those protein molecules responsible for forisome conformational transformation. In the absence of any load, bound Ca 2+ , Sr 2+ and Ba 2+ ions showed apparent and averaged dissociation constants of 14, 62 and 1070 µM, respectively. Various forisomes generated bending on a quartz glass fibre with a diameter of 9 µm. The fibre bending was measured microscopically also by correlation between the digital patterns of a predefined window of observation before and after bending. Similar bending forces of approximately 90 nN were measured for a single forisome sequentially exposed to 10 mM Ca 2+ , Sr 2+ and Ba 2+ . In the absence of dissolved oxygen, the same conditions resulted in averaged bending forces of (93 ± 40) nN, (58 ± 20) nN, and (91 ± 20) nN after contacting different forisomes with 10 mM Ca 2+ , 10 mM Sr 2+ , and 10 mM Ba 2+ respectively, demonstrating that the force generated was independent on ion concentrations above a certain threshold value.

Introduction

Protein-based motors [START_REF] Howard | Mechanics of motor proteins and Cytoskeleton[END_REF][START_REF] Vale | Millennial musings on molecular motors[END_REF] convert energy from chemical reactions directly into mechanical work. This is achieved through protein folding and unfolding, which is controlled by chemical reactions such as the protonation/deprotonation of amino and carboxylate groups, the formation of metal-protein complexes, and the phosphorylation/dephosphorylation of hydroxyl groups on serine and tyrosine residues. Some protein-based motors are dependent on nucleoside triphosphates [START_REF] Howard | Mechanics of motor proteins and Cytoskeleton[END_REF], while others such as spasmonems [3 -6] and forisomes [7 -9] are propelled directly by Ca 2+ . Spasmonems are isotropically-contracting aggregates of the protein spasmin, found in the stalks of Vorticella sp. Forisomes are aggregates of P-proteins, found in the phloem of legumes (e.g. Vicia faba) [START_REF] Knoblauch | Reversible calcium-regulated stopcocks in legume sieve tubes[END_REF][START_REF] Ehlers | Ultrastructural features of well-preserved and injured sieve elements: minute clamps keep the phloem transport conduits free for mass flow[END_REF]. In [START_REF] Knoblauch | Reversible calcium-regulated stopcocks in legume sieve tubes[END_REF][START_REF] Ehlers | Ultrastructural features of well-preserved and injured sieve elements: minute clamps keep the phloem transport conduits free for mass flow[END_REF] it was demonstrated that these protein aggregates rapidly disperse and occlude the pores of sieve plates between phloem cells after injury or by an osmotic shock induced under in vivo conditions. In the presence of free Ca 2+ , Sr 2+ or Ba 2+ , longitudinally extended forisomes contract to a squatter, more swollen form [START_REF] Knoblauch | ATP-independent contractile proteins from plants[END_REF][START_REF] Schwan | In vitro investigation of the contraction behaviour of chemomechanical Pprotein aggregates (forisomes)[END_REF]. A thermodynamic cycle process [START_REF] Schwan | In vitro investigation of the contraction behaviour of chemomechanical Pprotein aggregates (forisomes)[END_REF] can be completed by the extraction of these ions with ethylene diaminetetraacetic acid (EDTA), during which the forisomes revert to the longitudinally extended state.

During such contractions, forisomes generate forces of approximately 100 nN [START_REF] Knoblauch | ATP-independent contractile proteins from plants[END_REF][START_REF] Schwan | Micromechanical measurements on chemomechanical protein aggregates[END_REF][START_REF] Fritzsche | [END_REF] in comparison to spasmonems which generate 40-60 nN [START_REF] Moriyama | High-speed video cinematographic demonstration of stalk and zooid contraction of Vorticella convallaria[END_REF]. The threshold concentration of Ca 2+ is between one and two orders of magnitude higher for forisomes [START_REF] Schwan | In vitro investigation of the contraction behaviour of chemomechanical Pprotein aggregates (forisomes)[END_REF] than for spasmonems [START_REF] Asai | Improved preparation and cooperative calcium contraction of glycerinated vorticella[END_REF]. However, taking into consideration earlier investigations [12 -14], there are at least two sources of energy for these contraction processes: the binding of Ca 2+ ions to the functional groups of a large number of protein molecules and the con-

A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT

formational change of those protein molecules. Since only very small (<0.5%) volume changes occur during protein folding at normal pressure (even within tightly packed protein aggregates) [START_REF] Harpaz | Volume changes on protein folding[END_REF][START_REF] Abbruzzetti | Fast events in protein folding: Structural volume changes accompanying the early events in the N→I transition of apomyoglobin induced by ultrafast pH jump[END_REF], and since forisomes increase in volume by up to 184% during contraction [START_REF] Schwan | In vitro investigation of the contraction behaviour of chemomechanical Pprotein aggregates (forisomes)[END_REF], the absorption of water needs to be considered as a potential source of energy. Energy could derive from tightly bound water molecules around hydrophobic side chains and polar groups as well as the relatively weak binding that occurs in hydrogels. Since forisomes swell significantly during contraction, volumetric work should also be considered. The predominant energy source and the behaviour of water molecules in the vicinity of the protein molecules of the forisomes remain to be determined.

Here we describe a comparative investigation of the influence of selected metal ions on the changing geometric parameters of contracting forisomes, the threshold values of the cooperatively conformational changes as well as the strength and dynamics of forces underlying forisome conformational changes induced by metal ions and pH shifts. The first time, the generated forces were measured as a function of the concentration of Ca 2+ -, Sr 2+ -and Ba 2+ ions and in dependence on the pH value. Another aim of this work was to determine the apparent dissociation constants of Ca 2+ , Sr 2+ , and Ba 2+ ions bound in the forisomes unloaded and loaded with a bending force.

Materials and methods

Isolation and purification of forisomes

Forisomes were isolated from Vicia faba plants as described elsewhere [START_REF] Knoblauch | ATP-independent contractile proteins from plants[END_REF][START_REF] Knoblauch | Erratum: ATP-independent contractile proteins from plants[END_REF][START_REF] Schwan | In vitro investigation of the contraction behaviour of chemomechanical Pprotein aggregates (forisomes)[END_REF]. The plants were grown in pots of sterilized soil in a glasshouse for 6 weeks and then thor-

A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT
oughly irrigated. The first free internodes were excised and placed in the Ca 2+ -free Mbuffer containing 10 mM EDTA, 0.1 M KCl and 10 mM Tris (pH 7.3). The rind was peeled off the stalk in two strips, and the separated, pre-dried phloem tissue was powdered under liquid nitrogen and suspended in the same Ca 2+ -free solution. The suspension was filtered through a 55-µm nylon mesh and the filter cake was rinsed several times with small amounts of the Ca 2+ -free solution.

Measuring cell

The apparatus for measuring the force generated by individual forisomes (measuring cell) was set up as shown in Figure 1. The cell consisted of a measuring chamber (MC)

with the inflow (I) for the reagent and conditioning solutions, the outflows (O1 and O2), a transfer channel (TC) and the storage chamber (SC). The flow and exchange of conditioning and rinsing solutions were adjusted by three computer-controlled piston pumps (Metrohm Dosimat 665, Herisau, Schwitzerland). Two or three pumps were combined to mix stock solutions, adjust the concentrations of bivalent metal ions and EDTA, and modulate the pH value.

The measuring cell was mounted on a thermostatic microscope table (Axiovert 25 C, Zeiss, Jena, Germany) adjusted to 298.3 ± 0.5 K. The microscope was automated as described by Francke [18]. serving as the stator. The second micromanipulator (Mm2) held a bending glass fibre

A C C E P T E D M A N U S C R I P T

ACCEPTED MANUSCRIPT

(BF) 1.5-3 mm in length and with a diameter of 9 µm. With the exception of the pumps, the entire measuring cell was mounted on an actively dampened optical bench.

A video camera (JVC TK-C1481BEG, JVC, Japan) was installed on the microscope and connected to a PC by a frame grabber card (HaSoTec GmbH, Rostock, Germany). A home-made software package [18,19] was developed for automatic control of the microscope, the piston pumps and the image processing. The video images and films were evaluated by correlation analysis of digital grey patterns with a shifting reference window [START_REF] Gelles | Tracking kinesis-driven A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT movements with nanometre-scale precision[END_REF]21] using ARAMIS Software (GOM mbH, Braunschweig, Germany) or the image processing program Analysis 3.1 (SIS Soft Imaging System GmbH, Münster, Germany).

For scanning electron microscopy (SEM), forisomes were purified from crude preparations by centrifugation in a Nycodenz ® density gradient, freeze dried as described previously [START_REF] Knoblauch | ATP-independent contractile proteins from plants[END_REF] and resuspended in Ca 2+ -free medium. Some batches were incubated in 10

ACCEPTED MANUSCRIPT

holders and sputtered with platinum (up-graded sputter-coater B30, VEB Hochvakuumtechnik, Dresden, Germany). They were inspected using a cold field emission SEM (S4500, Hitachi, Tokyo, Japan) at accelerating voltages of 1 to 10 kV.

Measurement of the force generated by forisomes and analysis of geometric parameters

Single forisomes were captured on a thin glass pipette tip in the storage chamber and drawn through the small transfer channel (TC, Figure 1) 5 mm in length and 1 mm wide into the measuring chamber under slight reverse flow of M -buffer (Figure 1). To measure geometric parameters, single in situ purified forisomes were fixed at the tip of the micropipette by self-adhesion on the glass surface. The forisomes were aligned by the flow of the conditioning solution before the flow was stopped and image processing commenced. The diameter (D F ) and length (L F ) of each forisome were determined by image processing (Figure 2). Approximate volumes (V) were calculated according to equation [START_REF] Howard | Mechanics of motor proteins and Cytoskeleton[END_REF], given the assumption that forisomes from Vicia faba normally have a rotationally symmetrical ellipsoid shape.

V = 1/6 πD F 2 L F , (1)
To measure the force generated by forisome contraction, the free end of the forisome was fixed to the tip of a bending glass fibre (Advanced Glassfiber Yarns LLC, Aiken, the video microscope as demonstrated earlier [START_REF] Schwan | Micromechanical measurements on chemomechanical protein aggregates[END_REF] and correlation between the digital patterns of a predefined window of observation, before and after bending of the glass fibre (Figure 3).

The displacement of the fibre tip was calculated from the shifting vectors determined from the initial window and the shifted window with maximum correlation.

A thin glass fibre can be bent by a contracting forisome fixed on its ends between the tip of a stator and the glass fibre tip as shown earlier by Knoblauch et al. [START_REF] Knoblauch | ATP-independent contractile proteins from plants[END_REF] and by our own investigations [START_REF] Schwan | In vitro investigation of the contraction behaviour of chemomechanical Pprotein aggregates (forisomes)[END_REF][START_REF] Schwan | Micromechanical measurements on chemomechanical protein aggregates[END_REF]. Mechanical work is performed according to equation ( 2)

given a linear displacement (∆x) of the fibre tip. The force can then be calculated according to equation ( 3) where E is the Young module, d is the diameter of the glass fibre, and L b its length.

A C C E P T E D M A N U S C R I P T

ACCEPTED MANUSCRIPT

W mech = ½ F • ∆x (2) 3πEd 4 F =  • ∆x (3) 64 L b 3 2.

Analysis of metal ion concentration and pH variation

The concentrations of the free divalent metal ions Ca 2+ , Sr 2+ and Ba 2+ were adjusted by titration with EDTA or vice versa in a stirred vessel. Both the metal ion and the EDTA solutions were prepared in the buffer M containing 200 mM Tris, 0.1 M KCl and 10 mM of equilibrated D-glucose, adjusted to pH 7.3. The stock solutions of metal ions were mixed with a stock solution of EDTA in a magnetically stirred vessel to a final volume of 20 mL before force measurements were carried out.

The metal ion stock solutions were prepared by dissolving precisely weighed amounts of Ca(NO 3 ) 2 , Sr(NO 3 ) 2 and Ba(NO 3 ) 2 in deionized and bi-distilled water. The exact metal ion concentrations were adjusted by diluting with the M -buffer. The free metal ion concentrations were calculated using known conditional equilibrium constants. The dissolved

A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT

oxygen was eliminated in a two-step enzymatic reaction comprising 2 -3 U/ml glucose oxidase and 10 -15 U/ml catalase (both from SIGMA, Taufkirchen, Germany) in the Mbuffer solutions. The elimination of dissolved oxygen was based on reactions (4) and [START_REF] Asai | Improved preparation and cooperative calcium contraction of glycerinated vorticella[END_REF] and was fast enough to suppress back-diffusion of oxygen from the atmosphere.

β-D-glucose + O 2 → D-gluconate + H + + H 2 O 2 (4) 2H 2 O 2 → O 2 + 2H 2 O (5)
The oxygen concentration was monitored in the inlet and outlet solutions of the measuring chamber using a Clark-type pO 2 sensor (Oxi3000, WTW GmbH, Weilheim, Germany). The oxygen concentration was lower than 3 µM and could be maintained below this value at the immersed forisome. The backdiffusion of oxygen from the surrounding air to the forisome under investigation is clearly overcompensated by the high rates of the enzyme-catalyzed reactions (4) and ( 5) for at least 12 h under continuous flow.

To implement pH induced conformational changes in forisomes the M-buffer is replaced either by 200 mM sodium acetate/acetic acid/ 0,1 M KCl buffer adjusted to pH

A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT

Approximately the same amount of water is taken up and the forisome assumes the same ordered structure (Figure 5) suggesting the water is bound tightly to the forisome proteins regardless of the divalent ion present in solution.

Therefore, in the absence of dissolved oxygen, any changes in geometric parameters and the uptake of water seems to be independent of the ion radius and the strength of binding between the metal ions and the protein molecules responsible for forisome conformational transformation. An increase in KCl concentration from 0.5 mM to 4.0 M had no significant influence on the geometric shape of the longitudinally expanded forisomes supporting the conclusion that neither osmotic effects nor the increase of ionic strength alone can induce contraction (results not shown).

For the first time the conformational transition of forisomes was investigated with respect to cooperativity n and strength of chemical binding of Ca 2+ , Sr 2+ and Ba 2+ ions, expressed as apparent dissociation constants K m. Almost the same amount of water is taken up and the forisome assumes the same ordered structure (Figure 5) suggesting the water is bound tightly to the forisome proteins regardless of the divalent ion present in solution. Figure 6 shows the averaged titration curves for forisomes exposed to Ca 2+ , Sr 2+ and Ba 2+ , at first time performed for Sr 2+ and Ba 2+ ions to get a more detailed comparison. Using Hill plots based on equation ( 6), we calculated the apparent binding constants and apparent number of divalent ion-binding sites in the contracting protein molecules. The results are summarized in Table 1, where L F * is defined by equation [START_REF] Knoblauch | Forisomes, a novel type of Ca 2+dependent contractile motor[END_REF], where L F , min and L F , max represent forisome length in the completely contracted and expanded states, respectively.

lg((1-L F * )/L F * ) = n • lg[Ca 2+ ] -nlgK m A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT ( 6 )
L L * = (L F -L F,min )/(L F,max -L F,min ) ( 7 )
The binding strength, expressed by the apparent dissociation constants K m , between the divalent metal ions and the forisome proteins appears to decrease with increasing radius of the metal ions, resulting in larger dissociation constants. Therefore, the inflection points and threshold values of the ion concentrations during forisome contraction are much higher for Sr 2+ and Ba 2+ compared to Ca 2+ . The binding of Sr 2+ and Ba 2+ also showed a higher degree of cooperativity, as shown by their higher averaged n-values 5.0 and 6.0, respectively, in comparison to the approximate and averaged value n = 2 measured for Ca 2+ -ions. Since we studied different forisomes, the different degrees of contraction (Figure 6) did not contradict the independence of contraction on the chosen metal ion as had been assumed before.

Force generation during switching by selected bivalent metal ions

The forisomes were fixed between the tips of a stiff glass pipette and a flexible glass fibre. It should be noted that the forisomes become spontaneously fixed to the glass through chemisorption between unmodified glass and at least the outer protein shell of the forisome, allowing it to withstand forces of at least 300 nN without detachment.

In the contracted, swollen state the binding force between the forisome and the glass surface is considerably higher than in the longitudinally stretched state where they can be detached relatively easy from the glass surface. However, after only one con-

A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT

traction and stretching cycle, the forisomes remain strongly chemisorbed on the glass tips. Figure 7 shows the time-dependence of the lengths of the stretched and contracted forms of three different forisomes. These forisomes contracted in the presence of 50 µM Ca 2+ , 150 µM Sr 2+ and 2 mM Ba 2+ , respectively, and remained in this loaded state for the next 30 minutes. The ratio of the lengths R = L Fc /L Fc,o of the contracted forisomes decreased over the entire 30 min by only 0.09-0.92% in the stretched state. L Fc,o is the final length of the contracted forisomes immediately measured after the end of its contraction. L Fc is the length of the corresponding forisome measured thereafter in dependence on time. The averaged loads were 93 nN for Ca 2+ , 37 nN for Sr 2+ , and 81.5 nN for Ba 2+ for eight different forisomes. Therefore, the forisomes were able to keep their shape stable in the contracted state. The relatively high stability of forisome length in the contracted state under load reveals the surprisingly high mechanical stability of the forisome protein scaffold.

Our preliminary results [START_REF] Schwan | Micromechanical measurements on chemomechanical protein aggregates[END_REF] are extended here into a detailed investigation of the physicochemical behaviour of the forisomes under load in comparison to the measuring results obtained in the absence of load. For the first time the force generation by Ca 2+ -, Sr 2+ -and Ba 2+ -ions were investigated during step wisely performed titration experiments in the absence of dissolved oxygen taking into consideration the different binding strengths of these ions and the cooperativity of its binding. The conformational transition of forisomes was observed as a function of defined metal ions concentrations comparing the behaviour under load and in the absence of load.

However, the load should have a significant influence on the geometric parameters of the forisomes in their final states. We therefore titrated several forisomes with Ca 2+ ,

A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT

Sr 2+ and Ba 2+ , initially in the absence and then in the presence of the bending load. The forces generated during this experiment cause the amplitudes of the lengths to decrease by 15% (Ca 2+ ), 11% (Sr 2+ ) and 9% (Ba 2+ ), for the complete conversion of the fully extended forisome to the fully contracted state. The final and averaged bending forces of 93 nN for Ca 2+ , 58 nN for Sr 2+ and 91 nN for Ba 2+ were in the same order of magnitude and demonstrating the apparent independence of the selected metal ion. Earlier published measurements [START_REF] Schwan | Micromechanical measurements on chemomechanical protein aggregates[END_REF] support this conclusion. In that experiment the same forisome was successively contracted with 10 mM Ca 2+ , 10 mM Sr 2+ and 10 mM Ba 2+ , each replacement being preceded by a 10-min rinse with 10 mM EDTA in M-buffer. The same stationary force of approximately 90 nN was determined for all three metal ions.

Table 2 summarizes the parameters n and K m calculated from the Hill model as well as the normalized changes f V of the forisome volume each time for five different forisomes investigated for one kind of metal ion. f V is defined according to equation [START_REF] Knoblauch | ATP-independent contractile proteins from plants[END_REF], where V contracted is the measured volume of the contracted forisome and V expanded is the initial volume of the longitudinally expanded forisome.

A C C E P T E D M A N U S C R I P T

ACCEPTED MANUSCRIPT

V contracted -V expanded f V =  (8) V contracted
Under the load caused by fibre bending the mean apparent dissociation constant K m increased in comparison to those determined without load. With respect to K m , the outer force shifts the equilibrium to a slightly enhanced dissociation according to equation [START_REF] Knoblauch | Erratum: ATP-independent contractile proteins from plants[END_REF], where B G is the free reaction energy of binding. Under load, the normalized change of forisome volume decreased. The change of the cooperativety n is not significant. However, with increasing dissociation constants, the minimum of metal ion concentrations must also be increased to initiate the change of forisome conformation from the longitudinally expanded to the contracted and swollen state.

According to equation ( 9), an outer stretching force F will shift the equilibrium in the direction of forisome proteins with a lower content of metal ions, and Ca 2+ , Sr 2+ or Ba 2+ will be released. This process is combined with the release of water according to the well known and broadly investigated behaviour of the forisomes during longitudinal expansion. Further investigations at different temperatures, and of the Ca 2+ , Sr 2+ and Ba 2+ release as a function of load, will be necessary to separate and quantify these effects.

B G + ½ F x = RTlnK m (9)
The relative independence of geometric parameters D F and L F , and the generated

A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT
forces on the type of metal ion hints that the folding of proteins is the source of the generated mechanical force. It is widely known that protein folding always involves the binding and release of water molecules. It can be assumed that a significant proportion of the absorbed water is bound to hydrophobic amino acids [START_REF] Urry | Molecular machines: How motion and other functions of living organisms can result from reversible chemical changes[END_REF]. The strong forces generated (43 -120 nN) and the relatively high energy densities estimated by comparing the bending work to the initial forisome volumes (230-800 Jm -3 ) support this hypothesis.

Force development induced by pH shifts

For the first time, the force generation was measured during the earlier demonstrated [START_REF] Knoblauch | ATP-independent contractile proteins from plants[END_REF][START_REF] Schwan | In vitro investigation of the contraction behaviour of chemomechanical Pprotein aggregates (forisomes)[END_REF] conformational transition of forisomes initiated by pH changes. To achieve a better understanding of the conformational transition of the forisomes and their mechanism the force generation induced by pH changes both in the acid and in the alkaline range was compared to that induced by twofold charged metal ions.

Because the alternative divalent metal ions generate approximately the same force in a single forisome and very similar forces in different forisomes, we investigated the geometric contraction behaviour of additional forisomes and the forces generated in two pH ranges: 4.5-7.3 and 7.3-11. In the absence of any load, the mean normalized volume increased by a factor f V of 1.9 ± 0.6 for changing from pH 7.3 to 4.5 and increased by a factor of 3.9 ± 1.1 for changing from pH 7.3 to 11.0 as shown earlier [START_REF] Schwan | In vitro investigation of the contraction behaviour of chemomechanical Pprotein aggregates (forisomes)[END_REF]. These averaged values were determined by measuring 13 different forisomes and show very different swelling behaviours in the alkaline and acid ranges. Figure 9 shows how the force generated by the forisomes changes as the pH is reduced Since the metal ion and the pH induced conformational changes also show similar changes in relative volume and water uptake, the molecular mechanisms are likely to work in analogous ways. We propose that the swelling of a protein aggregate with a very high tensile stability, initiated by an unfolding event, is the common principle.

The ions Ca 2+ , Sr 2+ , and Ba 2+ as well as protons and hydroxide ions at pH < 4.9 and pH > 10.8, respectively, initiate the folding of at least a part of the protein molecules in the forisomes. It is assumed that according to Knoblauch and Peters [START_REF] Knoblauch | Forisomes, a novel type of Ca 2+dependent contractile motor[END_REF] repelling electrical charges localized in protein molecules are compensated inducing their conformational change. Based on the very similar bending forces independently of the kind of induction by metal ions and pH changes it can further be assumed that the amplified uptake and especially the binding of water is the thermodynamic driving force of contraction and swelling of the forisome essentially determining the changes

A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT

of both the geometrical parameters and the force generation of the forisome. The high mechanical stability of the forisome shape under load combined with a significant degree of swelling support the assumption of tightly binding of water. We propose that the swelling of the protein aggregate -forisome -with a very high tensile stability, initiated by an unfolding event, is the common principle of the conformational change of the forisome.

Conclusions

Since at least the metal ion-induced conformational change in forisomes is fully reversible in the absence of dissolved oxygen, we conclude that the binding and release of selected divalent metal ions, or simply a pH shift, can induce a highly cooperative folding process in the forisome followed by the uptake and strong binding of

  ) with a diameter of 9.0 µm and a Young module of 87 kNmm-2 [23]. The stiffness of the bending fibre was adjusted by its length L b . The fibre diameter was measured by raster electron microscopy and the length by light microscopy. The Young module of 87 kN/mm² [23] was verified by both micro tensile and micro bending tests. Both the bending fibre and the forisome were completely immersed in the measuring solution to exclude any forces at the liquid/air phase interface. The angle between the long axes of the forisome and bending fibre was fixed at 88-92 o by aligning the forisome in the flowing solution, which was orthogonal to the initial position of the bending fibre. The flow was stopped after alignment was achieved. Thereafter, the forces generated by the contracting forisome were measured using images of the bending fibre captured under

3 . 1

 31 4.5 or by A C C E P T E D M A N U S C R I P T Influence of different metal ions on the geometric parameters of forisomes Forisomes change from a longitudinally expanded form to a contracted and swollen form in the presence of divalent metal ions Ca 2+ , Sr 2+ , and Ba 2+ [12-14]. To gain a deeper insight into the molecular mechanisms involved in this process, we investigated the binding strength of metal ions with different radii in the absence of dissolved oxygen. The enzymatic elimination of dissolved oxygen was rapid and reliable, excluding the potential impact of oxidative deactivation. By sequentially contacting forisomes with concentrations of Ca 2+ , Sr 2+ , and Ba 2+ changing from zero to 10 mM in M-buffer interrupted by rinsing with 10 mM EDTA in the same buffer, the same forisomes showed in these experiments almost the same changes of both their normalized diameter D F /D F,o and normalized length L F /L F,o as demonstrated in Figure 4. L F , o and D F,o are the initial length and the initial diameter of the forisome, respectively. L F and D F are the time-dependent measuring values. Pairs of experiments were carried out each on the same forisome and repeated four to five times to compare the changes of its length induced by Ca 2+ and Sr 2+ , Ca 2+ and Ba 2+ , and Sr 2+ and Ba 2+ . The differences between the changes of the L F /L F,o values were smaller than 5 % if measured at the same forisome.. Both experiments were carried out three times (results not shown). The exact time-dependent concentrations changing continuously from approximately zero to 10 mM of metal ions could be calculated from the hydrodynamic mixing model in the measuring cell taking into consideration the fast reaction between EDTA and the metal ions. The investigated divalent ions had very similar effects on the normalized length and diameter of the corresponding forisomes.

Figure 8

 8 Figure 8 compares the corresponding changes in normalized forisome lengths ac-

from 7 .

 7 3 to 4.5, and as it is increased from 7.3 to 11.0. Both experiments on two dif-A C C E P T E D M A N U S C R I P T ACCEPTED MANUSCRIPT ferent forisomes produced similar final forces of approximately 120 nN. However, very different volume-specific forces of 1.21 µN/nL and 0.52 µN/nL were measured during the changes from pH 7.3 to 4.5 and from pH 7.3 to 11.0, respectively. The different response kinetics could be explained by the very different volumes of 188 fL and 900 fL estimated for the longitudinally expanded forisomes. The normalized volumes changed by factors of 1.29 and 1.75 during the changes from pH 7.3 to 4.5 and from pH 7.3 to 11.0, respectively. It follows that in both experiments, the swelling was significantly lower than in the load free state. As we found for forisome contraction induced by divalent metal ions, loading reduces the amount of absorbed water. These pH changes generate similar mechanical forces in comparison to the conformational transition induced by the bivalent metal ions.

  Figures and legends:

Figure 1

 1 Figure 1 Design of the measuring cell. MC, measuring chamber; SC, storage chamber;

Figure 2 Figure 3

 23 Figure 2 Geometric parameters for the longitudinally expanded and contracted forms V.

Figure 4 .

 4 Figure 4. Time dependencies of normalized forisome length L F /L F,o (a) and diameter

Figure 5 A

 5 Figure 5 A forisome imaged by FE-REM, 6 kV.

Figure 6

 6 Figure 6 Comparison of titration courses of different forisomes immersed in M-buffer containing   Ba 2+ ,   Sr 2+ ,   Ca 2+ with concentrations adjusted precisely

Figure 7

 7 Figure 7 Dependence of averaged (n = 4, measurements of four different forisomes for

Figure 8

 8 Figure 8 Forisome contraction induced by step wisely adjusted concentrations of (a) Ca 2+ at bending loads ( ) of F = 78 nN, of (b) Sr 2+ at F = 43 nN, and of (c) Ba 2+ at F

Figure 9

 9 Figure 9 Time courses of force generation on two different forisomes, measured

Table 1

 1 Titration of unloaded forisomes with Ca 2+ , Sr 2+ , and Ba 2+ , measuring conditions as described in legend to Figure5; ν = number of repeated measurements performed at different forisomes.

	Divalent metal ion	Inflection point	Apparent dissociation	Cooperativity n
		[µM]	constant K D
			[µM]
	Ca 2+ ( ν = 2 )	25 ± 3	14 ± 2	2.0
	Sr 2+ ( ν = 4 )	75 ± 7	62 ± 7	5.0
	Ba 2+ ( ν = 6 )	1100 ± 11	1070 ±10	6.0

Table 2

 2 Force titrations of forisomes with Ca 2+ , Sr 2+ , and Ba 2+ , Measuring conditions as described in legend to Figure9; ν number of repeated experiments performed at different forisomes in the absence of dissolved oxygen.

				normalized change	Average	Cooperativity	Apparent dissociation
				of forisome volume	final force	n		constant K m /µM
						[nN]
				Under	Without		Under	Without	Under	Without
				load	load		load	load	load	load
	Ca	2+ (ν=2) 4,9	5,8	93 ± 40	3.8	3.5	20.2	14,8
	Sr	2+ (ν=4)	2,5	3,2	58 ± 20	4.2	4.1	57.1	56,5
	Ba 2+ (ν=6) 5,6	6,8	91 ± 20	3.3	2.8	857	622

Acknowledgements

The authors would like to thank A. Cismak for the SEM images of the forisomes and M. Knoblauch, W. Peters, D. Prüfer and G. Noll for helpful discussions. The work was supported by a Fraunhofer Gesellschaft internal research program.

A C C E P T E D

M A N U S C R I P T


Member, IEEE Franck Cassez

A Note on Fault Diagnosis Algorithms

In this paper we review algorithms for checking diagnosability of discrete-event systems and timed automata. We point out that the diagnosability problems in both cases reduce to the emptiness problem for (timed) B üchi automata. Moreover, it is known that, checking whether a discrete-event system is diagnosable, can also be reduced to checking bounded diagnosability. We establish a similar result for timed automata. We also provide a synthesis of the complexity results for the different fault diagnosis problems.

I. INTRODUCTION

Discrete-event systems [START_REF] Ramadge | Supervisory control of a class of discrete event processes[END_REF], [START_REF]The control of discrete event systems[END_REF] (DES) can be modelled by finite automata over an alphabet of observable events Σ. To address decision problems under partial observation of DES, it is sufficient to add a special event τ which represents all the unobservable actions.

The Fault diagnosis problem is a typical example of a problem under partial observation. We assume that the behavior of the DES is known and a model of it is available as a finite automaton over an alphabet Σ ∪ {τ, f }, where Σ is the set of observable events, τ represents the unobservable events, and f is a special unobservable event that corresponds to the faults: this is the original framework introduced by M. Sampath and al. [START_REF] Sampath | Diagnosability of discrete event systems[END_REF] and the reader is referred to this paper for a clear and exhaustive introduction to the subject 1 . The aim of fault diagnosis is to detect faulty sequences of the DES by observing only the events in Σ. A faulty sequence is a sequence of the DES containing an occurrence of event f . We assume that an observer which has to detect faults, knows the specification/model of the DES, and it is able to observe sequences of observable events. Based on this knowledge, it has to announce whether an observation (a word in Σ * ) was produced by a faulty sequence (in (Σ∪{τ, f }) * ) or not. A diagnoser (for a DES) is an observer which observes the sequences of observable events and is able to detect whether a fault event occurred, although it is not observable. If a diagnoser can detect a fault at most ∆ steps 2 after it occurred, the DES is said to be ∆-diagnosable. It is diagnosable if it is ∆-diagnosable for some ∆ ∈ N. Checking whether a DES is ∆-diagnosable for a given ∆ is Franck Cassez is with National ICT Australia & CNRS, Locked Bag 6016, The University of New South Wales, Sydney NSW 1466, Australia.

franck.cassez@cnrs.irccyn.fr,Franck.Cassez@nicta.com.au Author supported by a Marie Curie International Outgoing Fellowship within the 7th European Community Framework Programme. 1 The "companion paper" [START_REF]Failure diagnosis using discrete-event models[END_REF] focuses on a less stringent notion of diagnosability called I-diagnosability. 2 Steps are measured by the number of events, observable or not, which occur in the DES. called the bounded diagnosability problem; checking whether a DES is diagnosable is the diagnosability problem.

Checking diagnosability for a given DES and a fixed set of observable events can be done in polynomial time using the algorithms of [START_REF] Jiang | A polynomial algorithm for testing diagnosability of discrete event systems[END_REF], [START_REF] Yoo | Polynomial-time verification of diagnosability of partially-observed discrete-event systems[END_REF]. Nevertheless the size of the diagnoser can be exponential as it involves a determinization step. The extension of this DES framework to timed automata [START_REF] Alur | A theory of timed automata[END_REF] (TA) has been proposed by S. Tripakis [START_REF] Tripakis | Fault diagnosis for timed automata[END_REF], and he proved that the problem of checking diagnosability of a timed automaton is PSPACE-complete. In the timed case, the diagnoser may be a Turing machine. In a subsequent work by P. Bouyer and al. [START_REF] Bouyer | Fault diagnosis using timed automata[END_REF], the problem of checking whether a timed automaton is diagnosable by a diagnoser which is a deterministic timed automaton was studied (we will not refer to this work in this paper.)

The algorithms proposed in the DES framework [START_REF] Jiang | A polynomial algorithm for testing diagnosability of discrete event systems[END_REF], [START_REF] Yoo | Polynomial-time verification of diagnosability of partially-observed discrete-event systems[END_REF] and in the timed automata framework [START_REF] Tripakis | Fault diagnosis for timed automata[END_REF] rely on different assumptions and use different techniques: for example [START_REF] Jiang | A polynomial algorithm for testing diagnosability of discrete event systems[END_REF], [START_REF] Yoo | Polynomial-time verification of diagnosability of partially-observed discrete-event systems[END_REF] assumes that the DES is live and contains no unobservable loops; the algorithm to check the diagnosability problem then consists in checking whether a cycle exists in a suitable product automaton; the algorithm of [START_REF] Tripakis | Fault diagnosis for timed automata[END_REF] for timed automata consists in checking whether a infinite word can be accepted by a (product) Büchi automaton: the main reason for the use of a Büchi acceptance condition in this case is to ensure time divergence. Our Contribution. In this paper, we try to put into perspective the results of [START_REF] Jiang | A polynomial algorithm for testing diagnosability of discrete event systems[END_REF], [START_REF] Yoo | Polynomial-time verification of diagnosability of partially-observed discrete-event systems[END_REF], [START_REF] Tripakis | Fault diagnosis for timed automata[END_REF], [START_REF] Cassez | Fault diagnosis with static or dynamic diagnosers[END_REF] by giving a uniform presentation of the algorithms for fault diagnosis both in the DES and timed automata settings. We also establish a (not difficult but still) missing result for timed automata: diagnosability can be reduced to bounded diagnosability. Another contribution of this paper is to examine in details the complexity of the problems and this is summarized in Table I.

The results in this paper that are not new and have already been published are followed by the reference(s) in the core of the text of after the Theorem keyword.

One such result is Theorem 3 which already appeared in [START_REF] Cassez | Fault diagnosis with static or dynamic diagnosers[END_REF]. It generalizes the previous results of [START_REF] Jiang | A polynomial algorithm for testing diagnosability of discrete event systems[END_REF], [START_REF] Yoo | Polynomial-time verification of diagnosability of partially-observed discrete-event systems[END_REF] and shows that fault diagnosis reduces to Büchi emptiness for DES. This has some interesting consequences regarding the algorithmic aspects of the problem as well as the tools that can be used to verify diagnosability. These considerations (Section IV) might be of interest for the DES community. Organisation of the Paper. Section II recalls the definitions of timed automata. Section III introduces the fault diagnosis problems we are interested in. Sections IV and V describes the algorithms to solve the diagnosability problems respect-ively for DES and TA. Section VI summarizes the results.

II. PRELIMINARIES

Σ denotes a finite alphabet and Σ τ = Σ∪{τ } where τ ∈ Σ is the unobservable action. B = {TRUE, FALSE} is the set of boolean values, N the set of natural numbers, Z the set of integers and Q the set of rational numbers. R is the set of real numbers and R ≥0 is the non-negative real numbers.

A. Clock Constraints

Let X be a finite set of variables called clocks. A clock valuation is a mapping v : X → R ≥0 . We let R X ≥0 be the set of clock valuations over X. We let 0 X be the zero valuation where all the clocks in X are set to 0 (we use 0 when X is clear from the context). Given δ ∈ R, v + δ denotes the valuation defined by (v + δ)(x) = v(x) + δ. We let C(X) be the set of convex constraints on X, i.e., the set of conjunctions of constraints of the form x ⊲⊳ c with c ∈ Z and ⊲⊳∈ {≤, <, =, >, ≥}. Given a constraint g ∈ C(X) and a valuation v, we write v |= g if g is satisfied by v. Given R ⊆ X and a valuation v, v[R] is the valuation defined by

v[R](x) = v(x) if x ∈ R and v[R](x) = 0 otherwise.

B. Timed Words

The set of finite (resp. infinite) words over Σ is Σ * (resp. Σ ω ) and we let Σ ∞ = Σ * ∪ Σ ω . A language L is any subset of Σ ∞ . A finite (resp. infinite) timed word over Σ is a word in (R ≥0 .Σ) * .R ≥0 (resp. (R ≥0 .Σ) ω ). We let Dur(w) be the duration of a timed word w which is defined to be the sum of the durations (in R ≥0 ) which appear in w; if this sum is infinite, the duration is ∞. Note that the duration of an infinite word can be finite, and such words which contain an infinite number of letters, are called Zeno words. We let Unt(w) be the untimed version of w obtained by erasing all the durations in w, e.g., Unt(0. TW * (Σ) is the set of finite timed words over Σ, TW ω (Σ), the set of infinite timed words and TW ∞ (Σ) = TW * (Σ) ∪ TW ω (Σ). A timed language is any subset of TW ∞ (Σ).

Let π /Σ ′ be the projection of timed words of TW ∞ (Σ) over timed words of TW ∞ (Σ ′ ). When projecting a timed word w on a sub-alphabet Σ ′ ⊆ Σ, the durations elapsed between two events are set accordingly: for instance π /{a,c} (0.4 a 1.0 b 2.7 c) = 0.4 a 3.7 c (projection erases some letters but keep the time elapsed between two letters). Given a timed language L, we let

Unt(L) = {Unt(w) | w ∈ L}. Given Σ ′ ⊆ Σ, π /Σ ′ (L) = {π /Σ ′ (w) | w ∈ L}.

C. Timed Automata

Timed automata (TA) are finite automata extended with real-valued clocks to specify timing constraints between occurrences of events. For a detailed presentation of the fundamental results for timed automata, the reader is referred to the seminal paper of R. Alur and D. Dill [START_REF] Alur | A theory of timed automata[END_REF].

Definition 1 (Timed Automaton): A Timed Automaton A is a tuple (L, l 0 , X, Σ τ , E, Inv, F, R) where: L is a finite set of locations; l 0 is the initial location; X is a finite set of clocks; Σ is a finite set of actions; E ⊆ L × C(X) × Σ τ × 2 X × L is a finite set of transitions; for (ℓ, g, a, r, ℓ ′ ) ∈ E, g is the guard, a the action, and r the reset set; Inv ∈ C(X) L associates with each location an invariant; as usual we require the invariants to be conjunctions of constraints of the form x c with ∈ {<, ≤}. F ⊆ L and R ⊆ L are respectively the final and repeated sets of locations. An example of TA is given in Fig. 1

. A state of A is a pair (ℓ, v) ∈ L × R X ≥0 . A run ̺ of A from (ℓ 0 , v 0
) is a (finite or infinite) sequence of alternating delay and discrete moves:

̺ = (ℓ 0 , v 0 ) δ0 -→ (ℓ 0 , v 0 + δ 0 ) a0 -→ (ℓ 1 , v 1 ) • • • • • • an-1 ---→ (ℓ n , v n ) δn -→ (ℓ n , v n + δ n ) • • • s.t.
for every i ≥ 0:

• v i + δ |= Inv(ℓ i ) for 0 ≤ δ ≤ δ i ; • there is some transition (ℓ i , g i , a i , r i , ℓ i+1 ) ∈ E s.t. : (i) v i + δ i |= g i and (ii) v i+1 = (v i + δ i )[r i ].
The set of finite (resp. infinite) runs from a state s is denoted Runs * (s, A) (resp. Runs ω (s, A)) and we define Runs * (A) = Runs * ((l 0 , 0), A) and Runs ω (A) = Runs ω ((l 0 , 0), A). As before Runs(A) = Runs * (A) ∪ Runs ω (A). If ̺ is finite and ends in s n , we let last(̺) = s n . Because of the denseness of the time domain, the unfolding of A as a graph is infinite (uncountable number of states and delay edges). The trace, tr(̺), of a run ̺ is the timed word

π /Σ (δ 0 a 0 δ 1 a 1 • • • a n δ n • • • ). We let Dur(̺) = Dur(tr(̺)). For V ⊆ Runs(A), we let Tr(V ) = {tr(̺) | ̺ ∈ V }, which
is the set of traces of the runs in V .

A finite (resp. infinite) timed word w is accepted by A if it is the trace of a run of A that ends in an F -location (resp. a run that reaches infinitely often an R-location). L * (A) (resp. L ω (A)) is the set of traces of finite (resp. infinite) timed words accepted by A, and L(A) = L * (A) ∪ L ω (A) is the set of timed words accepted by A. In the sequel we often omit the sets R and F in TA and this implicitly means F = L and R = ∅.

A finite automaton (FA) is a particular TA with X = ∅. Consequently guards and invariants are vacuously true and time elapsing transitions do not exist. We write A = (L, l 0 , Σ τ , E, F, R) for a FA. A run is thus a sequence of the form:

̺ = ℓ 0 a0 -→ ℓ 1 • • • • • • an-1 ---→ ℓ n • • •
where for each i ≥ 0, (ℓ i , a i , ℓ i+1 ) ∈ E. Definitions of traces and languages are straightforward. In this case, the duration of a run ̺ is the number of steps (including τ -steps) of ̺: if ̺ is finite and ends in ℓ n , Dur(̺) = n and otherwise Dur(̺) = ∞.

D. Region Graph of a TA

The region graph RG(A) of a TA A is a finite quotient of the infinite graph of A which is time-abstract bisimilar to A [START_REF] Alur | A theory of timed automata[END_REF]. It is a FA on the alphabet E ′ = E ∪ {τ }. The states of RG(A) are pairs (ℓ, r) where ℓ ∈ L is a location of A and r is a region of R X ≥0 . More generally, the edges of the graph are tuples (s, t, s ′ ) where s, s ′ are states of RG(A) and t ∈ E ′ . Genuine unobservable moves of A labelled τ are labelled by tuples of the form (s, (g, τ, r), s ′ ) in RG(A). An edge (g, λ, R) in the region graph corresponds to a discrete transition of A with guard g, action λ and reset set R. A τ move in RG(A) stands for a delay move to the time-successor region. The initial state of RG(A) is (l 0 , 0). A final (resp. repeated) state of RG(A) is a state (ℓ, r) with ℓ ∈ F (resp. ℓ ∈ R). A fundamental property of the region graph [START_REF] Alur | A theory of timed automata[END_REF] is:

Theorem 1 ( [START_REF] Alur | A theory of timed automata[END_REF]): L(RG(A)) = Unt(L(A)). In other words:

1) if w is accepted by RG(A), then there is a timed word

v with Unt(v) = w s.t. v is accepted by A. 2) if v is accepted by A, then Unt(w) is accepted RG(A).
The (maximum) size of the region graph is exponential in the number of clocks and in the maximum constant of the automaton A (see [START_REF] Alur | A theory of timed automata[END_REF]):

|RG(A)| = |L| • |X|! • 2 |X| • K |X|
where K is the largest constant used in A.

E. Product of TA Definition 2 (Product of TA):

Let A i = (L i , l i 0 , X i , Σ i τ , E i , Inv i ), i ∈ {1, 2}, be TA s.t. X 1 ∩ X 2 = ∅. The product of A 1 and A 2 is the TA A 1 × A 2 = (L, l 0 , X,Σ τ , E, Inv) given by: L = L 1 × L 2 ; l 0 = (l 1 0 , l 2 0 ); Σ = Σ 1 ∪ Σ 2 ; X = X 1 ∪ X 2 ; and E ⊆ L × C(X) × Σ τ × 2 X × L and ((ℓ 1 , ℓ 2 ), g 1,2 , σ, r, (ℓ ′ 1 , ℓ ′ 2 )) ∈ E if: • either σ ∈ (Σ 1 ∩ Σ 2 ) \ {τ }, and (i) (ℓ k , g k , σ, r k , ℓ ′ k ) ∈ E k for k = 1 and k = 2; (ii) g 1,2 = g 1 ∧ g 2 and (iii) r = r 1 ∪ r 2 ; • or for k = 1 or k = 2, σ ∈ (Σ k \ Σ 3-k ) ∪ {τ }, and (i) (ℓ k , g k , σ, r k , ℓ ′ k ) ∈ E k ; (ii) g 1,2 = g k and (iii) r = r k ; and finally Inv(ℓ 1 , ℓ 2 ) = Inv(ℓ 1 ) ∧ Inv(ℓ 2 ).
The definition of product also applies to finite automata.

III. FAULT DIAGNOSIS PROBLEMS

The material in this section is based on [START_REF] Yoo | Polynomial-time verification of diagnosability of partially-observed discrete-event systems[END_REF], [START_REF] Tripakis | Fault diagnosis for timed automata[END_REF], [START_REF] Cassez | Fault diagnosis with static or dynamic diagnosers[END_REF]. To model timed systems with faults, we use timed automata on the alphabet Σ τ,f = Σ τ ∪ {f } where f is the faulty (unobservable) event. We only consider one type of fault here, but the results we give are valid for many types of faults {f 1 , f 2 , • • • , f n }: indeed solving the many types diagnosability problem amounts to solving n one type diagnosability problems [START_REF] Yoo | Polynomial-time verification of diagnosability of partially-observed discrete-event systems[END_REF]. Other unobservable events are abstracted as a τ action (one τ suffices as these events are all unobservable).

The system we want to supervise is given as a TA A = (L, l 0 ,X, Σ τ,f , E, Inv). Fig. 1 gives an example of such a system (α ∈ N is a parameter). Invariants in the automaton A(α) are written within square brackets as in which are the traces 3 of ∆-faulty and non-faulty runs of A.

[x ≤ 3]. Let ∆ ∈ N. A run of A ̺ = (ℓ 0 , v 0 ) δ0 -→ (ℓ 0 , v 0 + δ 0 ) a0 -→ (ℓ 1 , v 1 ) • • • • • • an-1 ---→ (ℓ n , v n ) δn -→ (ℓ n , v n + δ) • • • is ∆-faulty if: (1) there is an index i s.t. a i = f and (2) the duration of the run ̺ ′ = (ℓ i , v i ) δi -→ • • • δn -→ (ℓ n , v n + δ n ) • • • is larger than ∆. We let Faulty ≥∆ (A) be the set l0 l1 [x ≤ 6] l2 [x ≤ 6] l4 [x ≤ 3]
The purpose of fault diagnosis is to detect a fault as soon as possible. Faults are unobservable and only the events in Σ can be observed as well as the time elapsed between these events. Whenever the system generates a timed word w, the observer can only see π /Σ (w). If an observer can detect faults in this way it is called a diagnoser. A diagnoser must detect a fault within a given delay ∆ ∈ N.

Definition 3 (∆-Diagnoser): Let A be a TA over the alphabet Σ τ,f and ∆ ∈ N. A ∆-diagnoser for A is a mapping D : TW * (Σ) → {0, 1} such that:

• for each ̺ ∈ NonFaulty(A), D(tr(̺)) = 0, • for each ̺ ∈ Faulty ≥∆ (A), D(tr(̺)) = 1. A is ∆-diagnosable if there exists a ∆-diagnoser for A. A is diagnosable if there is some ∆ ∈ N s.t. A est ∆-diagnosable.
Remark 1: Nothing is required for the ∆ ′ -faulty words with ∆ ′ < ∆. Thus a diagnoser could change its mind and answers 1 for a ∆ ′ -faulty word, and 0 for a ∆ ′′ -faulty word with ∆ ′ < ∆ ′′ < ∆.

Example 1: The TA A(3) in Fig. 1 taken from [8] is 3-diagnosable. For the timed words of the form t.a.δ.b.t ′ with δ ≤ 3, no fault has occurred, whereas when δ > 3 a fault must have occurred. A diagnoser can then be easily constructed. As we have to wait for a "b" action to detect a fault, D cannot detect a fault in 2 time units. If α = 2, in A(2) there are two runs:

ρ 1 (δ) = (l 0 , 0) a -→ (l 1 , 0) 2.5 --→ (l 1 , 2.5) f -→ (l 2 , 2.5) 0.2 --→ (l 2 , 2.7) b -→ (l 3 , 2.7) δ -→ (l 2 , 2.7 + δ) ρ 2 (δ) = (l 0 , 0) a -→ (l 1 , 0) 2.5 --→ (l 1 , 2.5) τ -→ (l 4 , 2.5) 0.2 --→ (l 4 , 2.7) b -→ (l 5 , 2.7) δ -→ (l 5 , 2.7 + δ)
3 Notice that tr(̺) erases τ and f . that satisfy tr(ρ 1 (δ)) = tr(ρ 2 (δ)), and this for every δ ≥ 0. For each ∆ ∈ N, there are two runs ρ 1 (∆) and ρ 2 (∆) which produce the same observations and thus no diagnoser can exist. A( 2) is not diagnosable. The classical fault diagnosis problems are the following: Problem 1 (Bounded or ∆-Diagnosability):

INPUTS: A TA A = (L, ℓ 0 , X, Σ τ,f , E, Inv) and ∆ ∈ N. PROBLEM: Is A ∆-diagnosable?
Problem 2 (Diagnosability):

INPUTS: A TA A = (L, ℓ 0 , X, Σ τ,f , E, Inv). PROBLEM: Is A diagnosable?
Problem 3 (Maximum delay):

INPUTS: A TA A = (L, ℓ 0 , X, Σ τ,f , E, Inv). PROBLEM: If A is diagnosable, what is the minimum ∆ s.t. A is ∆-diagnosable ?
We do not address here the problem of synthesizing a diagnoser and the reader is referred to [START_REF] Yoo | Polynomial-time verification of diagnosability of partially-observed discrete-event systems[END_REF], [START_REF] Jiang | A polynomial algorithm for testing diagnosability of discrete event systems[END_REF], [START_REF] Tripakis | Fault diagnosis for timed automata[END_REF], [START_REF] Bouyer | Fault diagnosis using timed automata[END_REF] for a detailed presentation.

A necessary and sufficient condition for diagnosability was already established in [START_REF] Sampath | Diagnosability of discrete event systems[END_REF], but was stated on a candidate diagnoser. We give here a simple language based condition, valid in both the discrete and timed cases. According to Definition 3, A is diagnosable, iff, there is some ∆ ∈ N s.t. A is ∆-diagnosable. Thus:

A is not diagnosable⇐⇒∀∆ ∈ N, A is not ∆-diagnosable.
Moreover a trace based definition of ∆-diagnosability can be stated as:

A is ∆-diagnosable iff Faulty tr ≥∆ (A) ∩ NonFaulty tr (A) = ∅. (1)
This gives a necessary and sufficient condition for nondiagnosability and thus diagnosability:

A is not diagnosable⇐⇒          ∀∆ ∈ N, ∃ρ ∈ NonFaulty(A) ∃ρ ′ ∈ Faulty ≥∆ (A) s.t. tr(ρ) = tr(ρ ′ ), (2)
or in other words, there is no pair of runs (ρ 1 , ρ 2 ) with ρ 1 ∈ Faulty ≥∆ (A), ρ 2 ∈ NonFaulty(A) the traces of which are equal.

IV. ALGORITHMS FOR DISCRETE EVENT SYSTEMS

In this section we briefly review the main results about diagnosability of discrete-event systems. We consider here that the DES is given by a FA A = (Q, q 0 , Σ τ,f , →).

Moreover we assume that the automaton A is such that every faulty run of length n can be extended to a run of length n + 1; this assumption simplifies the proofs (of some lemmas in [START_REF] Cassez | Fault diagnosis with static or dynamic diagnosers[END_REF]) and if A does not satisfy it, it is easy to add τ loops to deadlock states of A to ensure it holds. It does not modify the observation made by the external observer and thus does not modify the diagnosability status of A.

A. Problem 1

To check Problem 1 we have to decide whether there is a (∆ + 1)-faulty run ρ 1 and a non-faulty run ρ 2 that give the same observations when projected on Σ. An easy way to do this is to build a finite automaton B which accepts exactly those runs, and check whether L(B) is empty or not.

Let A 1 = (Q × {-1, 0, • • • , ∆ + 1}, (q 0 , -1), Σ τ , → 1 ) be the automaton with → 1 defined by:

• (q, n) λ --→ 1 (q ′ , n) if q λ --→ q ′ and n = -1 and λ ∈ Σ ∪ {τ }; • (q, n) λ --→ 1 (q ′ , min(n + 1, ∆ + 1)) if q λ --→ q ′ and n ≥ 0 and λ ∈ Σ ∪ {τ }; • (q, n) τ --→ 1 (q ′ , min(n + 1, ∆ + 1) if q f --→ q ′ . Let A 2 = (Q, q 0 , Σ τ , → 2 ) with: q λ --→ 2 q ′ if q λ --→ q ′ and λ ∈ Σ ∪ {τ }. Define B = A 1 × A 2 with the final states F B of B given by: F B = {((ℓ, ∆ + 1), ℓ ′ ) | (ℓ, ℓ ′ ) ∈ Q × Q}. We let R B = ∅. It is straightforward to see that: Theorem 2: A is ∆-diagnosable iff L * (B) = ∅.
As language emptiness for B amounts to reachability checking, it can be done in linear time in the size of B. Still strictly speaking, the automaton B has size (∆ + 1) • |A| 2 which is exponential in the size of the inputs of the problem A and ∆ because ∆ is given in binary. Thus Problem 1 can be solved in EXPTIME. As storing ∆ requires only polynomial space Problem 1 is in PSPACE. Actually checking Problem 1 can be done in PTIME (see the end of this section).

B. Problem 2

To check whether A is diagnosable, we build a synchronized product A 1 × A 2 , s.t. A 1 behaves exactly as A but records in its state whether a fault has occurred, and A 2 behaves like A without the faulty runs as before. It is then as if ∆ = 0 in the previous construction. We let → 1,2 be the transition relation of A 1 × A 2 . A faulty run of A 1 × A 2 is a run for which A 1 reaches a faulty state of the form (q, 1). To decide whether A is diagnosable we build an extended version of A 1 ×A 2 which is a Büchi automaton B as follows: B has a boolean variable z which records whether A 1 participated in the last transition fired by A 1 × A 2 . Assume we have a predicate 4 A 1 Move(t) which is true when A 1 participates in a transition t of the product A 1 ×A 2 . A state of B is a pair (s, z) where s is a state of A 1 ×A 2 . B is given by the tuple ((Q×{0, 1}×Q)×{0, 1}, ((q 0 , 0), q 0 , 0), Σ τ , -→ B , ∅, R B ) with:

• (s, z) σ --→ B (s ′ , z ′ ) if (i) there exists a transition t : s σ --→ 1,2 s ′ in A 1 × A 2 , and (ii) z ′ = 1 if A 1 Move(t) and z ′ = 0 otherwise; • R B = {(((q, 1), q ′ ), 1) | ((q, 1), q ′ ) ∈ A 1 × A 2 }.
B accepts the language L(B) = L ω (B) ⊆ Σ ω . Moreover this language satisfies a nice property:

Theorem 3 ([10]): A is diagnosable iff L ω (B) = ∅.
This theorem has for consequence that the diagnosability problem can be checked in quadratic time: the automaton B has size 4 • |A| 2 i.e., O(|A| 2 ) and checking emptiness for Büchi automaton can be done in linear time. Thus diagnosability can be checked in PTIME. Polynomial algorithms for checking diagnosability (Problem 2) were already reported in [START_REF] Jiang | A polynomial algorithm for testing diagnosability of discrete event systems[END_REF], [START_REF] Yoo | Polynomial-time verification of diagnosability of partially-observed discrete-event systems[END_REF]. In these two papers, the plant cannot have unobservable loops i.e., loops that consist of τ actions. Our algorithm does not have this limitation (we even may have to add τ loops to ensure that each faulty run can be extended). Note also that in [START_REF] Jiang | A polynomial algorithm for testing diagnosability of discrete event systems[END_REF], [START_REF] Yoo | Polynomial-time verification of diagnosability of partially-observed discrete-event systems[END_REF], the product construction is symmetric in the sense that A 2 is a copy of A as well. Our A 2 does not contain the f transitions, which is a minor difference complexity-wise, but in practice this can be useful to reduce the size of the product.

Moreover, reducing Problem 2 to emptiness checking of Büchi automata is interesting in many respects:

• the proof (see [START_REF] Cassez | Fault diagnosis with static or dynamic diagnosers[END_REF]) of Theorem 3 is easy and short; algorithms for checking Büchi emptiness are wellknown and correctness follows easily as well; • this also implies that standard tools from the modelchecking/verification community can be used to check for diagnosability. There are very efficient tools to check for Büchi emptiness (e.g., SPIN [START_REF] Holzmann | Software model checking with spin[END_REF]). Numerous algorithms, like on-the-fly algorithms [START_REF] Couvreur | On-the-fly emptiness checks for generalized büchi automata[END_REF] have been designed to improve memory/time consumption (see [START_REF] Schwoon | A note on on-the-fly verification algorithms[END_REF] for an overview). Also when the DES is not diagnosable a counter-example is provided by these tools. The input languages (like PROMELA for SPIN) that can be used to specify the DES are more expressive than the specification languages of some dedicated tools 5 like DESUMA/UMDES [START_REF] Ricker | Desuma: A tool integrating giddes and umdes[END_REF] (notice that the comparison with DESUMA/UMDES concerns only the diagnosability algorithms; DESUMA/UMDES can perform a lot more than checking diagnosability). From Theorem 3, one can also conclude that diagnosability amounts to bounded diagnosability: indeed if A is diagnosable, there can be no accepting cycles of faulty states in B; in this case there cannot be a faulty run of length more than 2 • |Q| 2 in B. Thus Problem 2 reduces to a particular instance of Problem 1 which was already stated in [START_REF] Yoo | Polynomial-time verification of diagnosability of partially-observed discrete-event systems[END_REF]:

Theorem 4 ([6]): A is diagnosable if and only if A is (2 • |Q| 2 )-diagnosable.
This appeals from some final remarks on the algorithms we should choose to check diagnosability: for the particular case of ∆ = 2 • |A| 2 , solving Problem 1 (a reachability problem) can be done in time 2•|A| 2 •|A| 2 i.e., O(|A| 4 ) whereas solving directly Problem 2 as a Büchi emptiness problem can be done in O(|A| 2 ). Thus the extra-cost of using a reachability algorithm is still reasonable.

The Büchi-emptiness algorithm used to solve Problem 2 can also be used to solve Problem 1 for a given ∆ and automaton A with set of states Q: if ∆ ≥ 2 • |Q| 2 , then we check wether A is diagnosable and this gives the answer to Problem 1; otherwise, if ∆ < 2 • |Q| 2 , we check wether A is ∆-diagnosable but in polynomial time. Hence Problem 1 5 UMDES was the only publicly available tool which could be found by a Google search. can be solved in polynomial time O(|A| 4 ).

Finally, solving Problem 3 can be done by a binary search solving iteratively ∆-diagnosability problems starting with ∆ = 2 • |A| 2 . Thus Problem 3 can be solved in O(|A| 4 ). Using a different approach, Problem 3 was reported to be solvable in O(|Q| 3 ) in [START_REF] Yoo | Computation of fault detection delay in discrete-event systems[END_REF].

In the sequel we recall the algorithm for checking diagnosability for TA and establish a counterpart of Theorem 4 for TA.

V. ALGORITHMS FOR TIMED AUTOMATA

We first recall how to check ∆-diagnosability for TA which first appeared in [START_REF] Tripakis | Fault diagnosis for timed automata[END_REF].

A. Problem 1

Let t be a fresh clock not in X.

Let A 1 (∆) = ((L × {0, 1}) ∪ {Bad}, (l 0 , 0), X ∪ {t}, Σ τ , E 1 , Inv 1 ) with: • ((ℓ, n), g, λ, r, (ℓ ′ , n)) ∈ E 1 if (ℓ, g, λ, r, ℓ ′ ) ∈ E, λ ∈ Σ ∪ {τ }; • ((ℓ, 0), g, τ, r ∪ {t}, (ℓ ′ , 1)) ∈ E 1 if (ℓ, g, f, r, ℓ ′ ) ∈ E; • Inv 1 ((ℓ, n)) = Inv(ℓ); • for ℓ ∈ L, ((ℓ, 1), t ≥ ∆, τ, ∅, Bad) ∈ E 1 and A 2 = (L, l 0 , X 2 , Σ τ , E 2 , Inv 2 ) with: • X 2 = {x 2 | x ∈ X} (clocks of A are renamed); • (ℓ, g 2 , λ, r 2 , ℓ ′ ) ∈ E 2 if (ℓ, g, λ, r, ℓ ′ ) ∈ E, λ ∈ Σ ∪ {τ }
with: g 2 is g where the clocks x in X are replaced by their counterpart x 2 ; r 2 is r with the same renaming;

• Inv 2 (ℓ) = Inv(ℓ). Consider A 1 (∆) × A 2 .
A faulty state of A 1 (∆) × A 2 is a state of the form (((ℓ, 1), v), (ℓ ′ , v ′ )) i.e., where the state of A 1 is faulty. Let Runs ≥∆ (A 1 (∆) × A 2 ) be the runs of A 1 (∆) × A 2 s.t. a faulty state of A 1 is encountered and s.t. at least ∆ time units have elapsed after this state. If this set is not empty, there are two runs, one ∆-faulty and one non-faulty which give the same observation. Moreover, because t is reset exactly when the first fault occurs, we have t ≥ ∆. Conversely, if a state of the form (((ℓ, 1), v), (ℓ ′ , v ′ )) with v(t) ≥ ∆ is reachable, then there are two runs, one ∆faulty and one non-faulty which give the same observation. Location Bad in A 1 is thus reachable exactly if A is not ∆-diagnosable. Let D be A 1 (∆) × A 2 with the final set of locations F D = {Bad} and R D = ∅.

Theorem 5 ([8]): A is ∆-diagnosable iff L * (D) = ∅. Checking reachability of a location for TA is PSPACEcomplete [START_REF] Alur | A theory of timed automata[END_REF]. More precisely, it can be done in linear time on the region graph. The size of the region graph of D is

(2 • |L| 2 + |L|) • (2|X| + 1)! • 2 2|X|+1 • K 2|X| • ∆
where K is the maximal constant appearing in A. Hence:

Corollary 1: Problem 1 can be solved in PSPACE for TA.

B. Problem 2

As for the untimed case, we build an automaton D, which is special version of A 1 (∆) × A 2 . Assume A 1 is defined as before omitting the clock t and the location Bad. In the timed case, we have to take care of the following real-time related problems [START_REF] Tripakis | Fault diagnosis for timed automata[END_REF]:

• some runs of A 2 might prevent time from elapsing from a given point in time. In this case, equation ( 1) cannot be satisfied but this is for an artificial reason: for ∆ large enough, there will be no ∆ faulty run in A 1 × A 2 because A 2 will block the time. In this case we can claim that A is diagnosable but it is not realistic; • a more tricky thing may happen: A 1 could produce a Zeno run 6 after a fault occurred. This could happen by firing infinitely many τ transitions in a bounded amount of time. If we declare that A is not diagnosable but the only witness run is a Zeno run, it does not have any physical meaning. Thus to declare that A is not diagnosable, we should find a non-Zeno witness which is realizable, and for which time diverges. To cope with the previous dense-time related problems we have to ensure that the two following conditions are met: C 1 : A 2 is timelock-free i.e., A 2 cannot prevent time from elapsing; this implies that every finite nonfaulty run of A 2 can be extended in a time divergent run. We can assume that A 2 satisfies this property or check it on A 2 before checking diagnosability; C 2 : for A to be non-diagnosable, we must find an infinite run in A 1 × A 2 for which time diverges. C 2 can be enforced by adding a third timed automaton Div(x) and synchronizing it with A 1 × A 2 . Let x be a fresh clock not in X. Let Div(x) = ({0, 1}, 0, {x}, E, Inv) be the TA given in Fig. 2. If we use F = ∅ and R = {1} for Div(x), any accepted run is time divergent. Let D = (A 1 × A 2 ) × Div(x) with F D = ∅ and R D is the set of states where A 1 is in a faulty state and Div(x) is location 1. The following theorem is the TA counterpart of Theorem 3: [START_REF] Alur | A theory of timed automata[END_REF]. Thus deciding diagnosability is in PSPACE.

Theorem 6 ([8]): A is diagnosable iff L ω (D) = ∅. Deciding whether L ω (A) = ∅ for TA is PSPACE- complete
The reachability problem for TA can be reduced to a diagnosability problem [START_REF] Tripakis | Fault diagnosis for timed automata[END_REF]. Let A be a TA on alphabet Σ and End a particular location of A. We want to check whether End is reachable in A. It suffices to build A ′ on the alphabet Σ τ,f by adding to A the following transitions: (End, TRUE, λ, ∅, End) for λ ∈ {τ, f }. Then: A ′ is not diagnosable iff End is reachable in A. It follows that:

Theorem 7 ( [START_REF] Tripakis | Fault diagnosis for timed automata[END_REF]): Problem 2 is PSPACE-complete for TA. We can draw another conclusion from the previous theorem: if a TA A is diagnosable, there cannot be any cycle with faulty states in the region graph of A 1 ×A 2 ×Div(x). Indeed, otherwise, by Theorem 1, there would be a non-Zeno word in A 1 × A 2 × Div(x) itself 7 . Let α(A) denote the size of the region graph RG(A 1 ×A 2 ×Div(x)). If A is diagnosable, then (P 1 ): a faulty state in RG(A 1 ×A 2 ×Div(x)) can be followed by at most α(A) (faulty) states. Notice that a faulty state cannot be followed by a state (s, r) where r is an unbounded region of A, as this would give rise to a non-Zeno word in A 1 × A 2 × Div(x). Hence (P 2 ): all the regions following a faulty state in RG(A 1 × A 2 × Div(x)) are bounded. As the amount of time which can elapse within a region is less than 1 time unit 8 , this implies that the duration of the longest faulty run in A 1 × A 2 × Div(x) is less than α(A). Actually as every other region is a singular region9 , it must be less than (α(A)/2) + 1. Thus we obtain the following result:

Theorem 8: A is diagnosable if and only if A is (α(A)/2) + 1-diagnosable.
As diagnosability can be reduced to ∆-diagnosability for TA:

Corollary 2: Problem 1 is PSPACE-complete for TA. Problem 3 can be solved by a binary search and is also in PSPACE for TA. Although Problem 1 and Problem 2 are PSPACE-complete for timed automata, the price to pay to solve Problem 2 as a reachability problem is much higher than solving it as a Büchi emptiness problem: indeed the size of the region graph of A 1 (α(A)) × A 2 is the square of the size of the region graph of A 1 × A 2 × Div(x) which is already exponential in the size of A. Time-wise this means a blow up from 2 n to 2 n 2 which is not negligible as in the discrete case.

VI. CONCLUSION

The main conclusions we can draw from the previous presentation are two-fold.

From a theoretical viewpoint, it shows that the fault diagnosis algorithms for DES and for TA are essentially the same: in both cases, diagnosability can be reduced to Büchi emptiness; and also to bounded diagnosability. The interesting point is that the complexity of the algorithms are the same for DES and TA except that for timed automata, the complexity measure is space (Table I). From a practical viewpoint, it clearly shows that the model-checking algorithms and tools developed in the model-checking/verification community can be used to solve the diagnosability problems; these tools usually have a very expressive specification language (e.g., Promela/Spin [START_REF] Holzmann | Software model checking with spin[END_REF], UPPAAL [START_REF] Behrmann | A tutorial on UPPAAL[END_REF] or KRONOS [START_REF] Bozga | Kronos: A model-checking tool for real-time systems[END_REF]) and very efficient data structures/implementations (e.g., [START_REF] Schwoon | A note on on-the-fly verification algorithms[END_REF] or [START_REF] Behrmann | UPPAAL implementation secrets[END_REF]).

We can also use the results in Table I to guide our choice of algorithms for checking diagnosability. Let Reach denote the reachability algorithm for checking ∆-diagnosability and Buchi denote the Büchi emptiness algorithm for checking diagnosability:

• time-wise, solving the diagnosability problem for a finite automaton using Reach is a bit more expensive than using Buchi, but the difference is not drastic; • for a timed automaton A it is totally different: spacewise the amount of space required by Reach is the square of the amount of space required by Buchi. Time-wise this means a worst case blow up from 2 |A| 2 to 2 |A| 4 . It is thus clear that one should use the Büchi emptiness algorithm in this case. Checking Büchi emptiness for TA is efficiently implemented in a version of KRONOS (Profounder) [START_REF] Tripakis | Checking timed buchi automata emptiness on simulation graphs[END_REF] and in UPPAAL-TiGA [START_REF] Behrmann | Uppaal-tiga: Time for playing games![END_REF], the game version of UPPAAL [START_REF] David | UPPAAL-TiGA 2009 -Towards Realizable Strategies[END_REF].

The previous results show that model-checking tools (both for finite and timed automata) are suitable to solve the diagnosis problems, and provide expressive specification languages and efficient algorithms and tools.

  4 a 1.0 b 2.7 c) = abc. In this paper we write timed words as 0.4 a 1.0 b 2.7 c • • • where the real values are the durations elapsed between two letters: thus c occurs at global time 4.1.

Figure 1 .

 1 Figure 1. The Timed Automaton A(α)

Figure 2 .

 2 Figure 2. Timed Automaton Div(x)

This is easy to define when building A 1 × A 2 .

A Zeno run is a run with infinitely many discrete steps the duration of which is bounded.

Note that this is true because we add the automaton Div(x). Otherwise an infinite run in the region graph of a TA does not imply a time divergent run in the TA A itself.

We assume the constants are integers.

A singular region is a region in which time elapsing is not possible e.g., defined by x = 0 ∧ y ≥ 1.