Maria Del Mar Amador

MD Nadia Vandenberghe

MD Nawel Berhoune

Jean-Philippe Camdessanché

PhD Sophie Gronier

MD Emilien Delmont

PhD Claude Desnuelle

PhD Pascal Cintas

MD Sophie Pittion

MD Sarah Louis

MD Jean- Philippe Camdessanché

MD Sophie Demeret

MD Timothée Lenglet

MD Vincent Meininger

PhD François Salachas

MD Pierre-François Pradat

PhD Gaëlle Bruneteau
email: gaelle.bruneteau@psl.aphp.fr

Unusual association of amyotrophic lateral sclerosis and myasthenia gravis: a dysregulation of the adaptive immune system ?

Keywords: Amyotrophic lateral sclerosis, myasthenia gravis, immunology, neuromuscular transmission

Introduction

Amyotrophic lateral sclerosis (ALS) is a rapidly progressive neurodegenerative disorder involving motor neurons. To date, there are no specific tests or biological markers to confirm the diagnosis [START_REF] Chio | Motor neuron disease in 2014. Biomarkers for ALS--in search of the Promised Land[END_REF], which remains based on clinical and electrophysiological findings together with exclusion of potentially treatable conditions presenting with similar symptoms, such as myasthenia gravis (MG). This rare autoimmune neuromuscular disorder is characterized by a defective transmission of nerve impulses to muscles. Here, we report seven patients from the French cohort of ALS patients with a concomitant diagnosis of ALS and MG. In the light of the current literature on this unusual association, we discuss diagnostic difficulties and pathophysiological mechanisms.

Patients and Methods

We conducted a retrospective review of cases referred with a concomitant diagnosis of ALS and MG, between 2002 and 2014, to one of the 18 French reference centers for ALS. These departments are specialist tertiary referral centers for motor neuron diseases and utilize standardized diagnostic pathways according to French [START_REF] Vandenberghe | Ancillary exams in the diagnosis of amyotrophic lateral sclerosis[END_REF] and European guidelines [START_REF] Andersen | EFNS guidelines on the clinical management of amyotrophic lateral sclerosis (MALS)--revised report of an EFNS task force[END_REF].

Patients with atypical motor neuron disorders, including those with concomitant other neurological diseases, are systematically recorded. The French cohort comprised 4757 patients in 2014. The neurologists of these centers were asked to identify all patients with an associated diagnosis of ALS and MG. For all patients with a recorded diagnosis of concomitant ALS and MG, detailed information on the neurological signs and symptoms, laboratory results and electrophysiological data were collected from review of the clinical charts. Each case was then classified according to the revised El Escorial World Federation of Neurology criteria for the diagnosis of ALS, which requires evidence of upper and lower motor neuron degeneration and spreading of signs and symptoms to different anatomic regions (brainstem, cervical, thoracic and lumbosacral spinal cord) [START_REF] Brooks | El Escorial revisited: revised criteria for the diagnosis of amyotrophic lateral sclerosis[END_REF]. The diagnosis of MG was made based on clinical and paraclinical findings [START_REF] Berrih-Aknin | Diagnostic and clinical classification of autoimmune myasthenia gravis[END_REF]. Suggestive clinical features were weakness with exacerbation by exercise and variability of symptoms, as well as improvement after cholinesterase inhibitor treatment (neostigmine or edrophonium test). Laboratory tests supporting the diagnosis of MG were the detection of specific autoantibodies and a significant decrement (> 10%) evidenced by RNS tests. This study was approved by the local ethics committee according to the French regulations.

Results

Patients' characteristics 5

Seven patients with a concomitant diagnosis of ALS and MG were included in the study.

Patients' characteristics are summarized in Table 1 (detailed case reports are available as Supplementary material). After careful review of clinical records, six patients (four males, two females, median age 56) met the diagnosis criteria for both ALS and MG (Table 2).

Median delay between onset of the two conditions was 19 months (6-319 months). Limb onset of ALS symptoms was reported in 83% of the patients. Localization of MG initial symptoms was ocular in 50% cases, generalized in 33% and bulbar in 17%.

Patients with ALS as inaugural disease

In three cases (patient 2, 6 and 7), ALS diagnosis was established before the occurrence of MG first symptoms. In this subgroup of patients, median age at onset was 39 (range 34-89).

ALS symptoms began in the bulbar region in one case and in the lumbar region in two.

Median delay between ALS onset and occurrence of first MG symptoms was 27 months (range 6-71). Concomitant diagnosis of MG was suspected based upon the occurrence of ocular symptoms (fluctuating ptosis or diplopia) in two cases; ocular symptoms and dramatic worsening of swallowing difficulties with marked diurnal variations, in one case. All three patients had positive testing for AChR-ab and significant decrement after RNS.

Patients with MG as inaugural disease

In three cases (patients 1, 3 and 5) MG diagnosis preceded ALS diagnosis. Median age at MG diagnosis was 72 (range 40-77). All patients had a positive testing for AChR-ab and a positive response to acetylcholinesterase inhibitor. In two cases a significant decrement was observed after RNS in at least one muscle. Median delay between MG initial symptoms and ALS onset was 11 months (range 8-319). The diagnosis of concomitant ALS was based upon the occurrence of a progressive limb weakness with pyramidal signs, and a diffuse neurogenic pattern on needle electromyography study.

Biological false positivity for AChR-ab

One case (patient 4) was retrospectively classified as a biological false positive for AChR-ab.

In this patient, AChR-ab were detected during the diagnostic work-up of typical bulbar-onset ALS. Cholinesterase inhibitor therapy started in association with riluzole induced no improvement in motor symptoms, and the patient died shortly after treatment initiation.

Discussion

Here, we report the largest series to date of patients with a concomitant diagnosis of ALS and MG. After careful review, six patients met the diagnostic criteria for both disorders. In three, ALS first symptoms occurred several months or years after the diagnosis of MG. In that situation, the main problem lies in not mistakenly attribute worsening of the patient's condition to MG. Marked muscle atrophy may occasionally be present in MG [START_REF] Brownell | Neurogenic muscle atrophy in myasthenia gravis[END_REF][START_REF] Samuraki | Myasthenia gravis presenting with unusual neurogenic muscle atrophy[END_REF] and fasciculation can be seen as a side effect of cholinesterase inhibitor therapy. Conversely, the presence of pyramidal signs should attract attention and the diagnosis of concomitant ALS should be considered if EMG evaluation shows acute and chronic denervation outside of motor deficit territories. In three other patients, the diagnosis of MG was made several years after ALS onset, with attention being drawn by marked diurnal variations and ocular symptoms, unusual in the context of motor neuron disorder. Two of them were young-onset ALS-patients (<45), with relatively slow disease progression. It is to note that, in one patient (No. 6), MG symptoms were mild and disappeared spontaneously after several months, without specific treatment. Albeit rare, prolonged (more than a few years) remissions can be seen without treatment in MG patients [8], and unusually long spontaneous remission, as observed in our patient, has been described in ocular myasthenia [START_REF] Al-Hashel | An adult patient with ocular myasthenia and unusually long spontaneous remission[END_REF].

Retrospectively, we only identified six cases with co-occurrence of ALS and MG during a twelve years period. Even if we cannot exclude that some cases may not have been referred to one of the French reference centers for ALS, this association seems rare, as supported by the small number of similar cases reported in the literature [START_REF] Naik | Unusual occurrence of amyotrophic lateral sclerosis in myasthenia gravis[END_REF][START_REF] Pinto | Amyotrophic lateral sclerosis patients and ocular ptosis[END_REF][START_REF] Restivo | ALS and myasthenia: An unusual association in a patient treated with riluzole[END_REF]. The combination of these two rare diseases may be a by chance association. However, it has recently been suggested that several preexisting autoimmune diseases, including MG, were associated with a small increased risk of ALS [START_REF] Turner | Autoimmune disease preceding amyotrophic lateral sclerosis: an epidemiologic study[END_REF]. There are evidences of systemic immune alterations in ALS patients, with immunologic activation in blood cells linked with ALS disease state and rate of progression [START_REF] Zhang | Evidence for systemic immune system alterations in sporadic amyotrophic lateral sclerosis (sALS)[END_REF][START_REF] Henkel | Regulatory T-lymphocytes mediate amyotrophic lateral sclerosis progression and survival[END_REF]. Several studies also showed that immunoglobulins from ALS patients can affect NMJ functional characteristics [START_REF] Appel | Immunoglobulins from animal models of motor neuron disease and from human amyotrophic lateral sclerosis patients passively transfer physiological abnormalities to the neuromuscular junction[END_REF][START_REF] Shaughnessy | Amyotrophic lateral sclerosis: serum factors enhance spontaneous and evoked transmitter release at the neuromuscular junction[END_REF][START_REF] Uchitel | Immunoglobulins from amyotrophic lateral sclerosis patients enhance spontaneous transmitter release from motor-nerve terminals[END_REF]. Furthermore, a proportion of ALS patients have serum antibodies directed against various targets, including the membrane protein LRP4 [START_REF] Tzartos | LRP4 antibodies in serum and CSF from amyotrophic lateral sclerosis patients[END_REF], an autoantigen implicated in some MG cases [START_REF] Higuchi | Autoantibodies to low-density lipoprotein receptor-related protein 4 in myasthenia gravis[END_REF][START_REF] Zhang | Autoantibodies to lipoprotein-related protein 4 in patients with double-seronegative myasthenia gravis[END_REF][START_REF] Pevzner | Anti-LRP4 autoantibodies in AChR-and MuSKantibody-negative myasthenia gravis[END_REF]. The role of riluzole in the development of MG in subjects suffering from ALS has also been discussed [START_REF] Restivo | ALS and myasthenia: An unusual association in a patient treated with riluzole[END_REF], as "myasthenia" has been reported as a possible adverse event during riluzole treatment in controlled ALS trials (http://www.accessdata.fda.gov). The effect of riluzole on the function of muscle AChR has been investigated in vitro using electrophysiological techniques.

Riluzole induced AChR block, with a faster and stronger block for AChR foetal isoform containing a γ-subunit, which is re-expressed along the entire muscle fiber after denervation.

However, the adult AChR isoform was blocked by riluzole only with acetylcholine applications far outlasting the typical duration of synaptic events. Furthermore, in the same study, treatment of ALS patients with riluzole did not impair nerve-muscle transmission explored by RNS tests [START_REF] Deflorio | Riluzole blocks human muscle acetylcholine receptors[END_REF].

Finally, in one case retrospectively classified as biological "false positive", significant serum titer of AChR-ab (2.4 nmol/l, N<0.5) was detected during ALS diagnostic work-up, in the absence of clinical signs suggestive of MG. Although AChR-ab are considered as highly specific for the diagnosis of MG, biological false positivity has been rarely reported in patients with motor neuron disorders [START_REF] Abbott | False positive anti-acetylcholine receptor antibodies in motorneurone disease[END_REF][START_REF] Appel | Amyotrophic lateral sclerosis. Associated clinical disorders and immunological evaluations[END_REF][START_REF] Ashizawa | False positive anti-acetylcholine receptor antibodies in motorneurone disease[END_REF][START_REF] Mittag | False-positive immunoassay for acetylcholine-receptor antibody in amyotrophic lateral sclerosis[END_REF][START_REF] Okuyama | Amyotrophic lateral sclerosis with antiacetylcholine receptor antibody[END_REF][START_REF] Mehanna | Amyotrophic lateral sclerosis with positive anti-acetylcholine receptor antibodies. Case report and review of the literature[END_REF]. In some patients who had received snake venom as a therapy, cross-reacting antibodies were responsible for technical false positivity [START_REF] Ashizawa | False positive anti-acetylcholine receptor antibodies in motorneurone disease[END_REF][START_REF] Mittag | False-positive immunoassay for acetylcholine-receptor antibody in amyotrophic lateral sclerosis[END_REF]. In the absence of snake venom therapy (as in our case), the frequency of AChR-ab positivity in MND patients was evaluated about 5% [START_REF] Appel | Amyotrophic lateral sclerosis. Associated clinical disorders and immunological evaluations[END_REF][START_REF] Ashizawa | False positive anti-acetylcholine receptor antibodies in motorneurone disease[END_REF]. In some patients, AChR-ab titers may fluctuate during the progression of ALS [START_REF] Ashizawa | False positive anti-acetylcholine receptor antibodies in motorneurone disease[END_REF][START_REF] Okuyama | Amyotrophic lateral sclerosis with antiacetylcholine receptor antibody[END_REF]. The mechanism by which AChR-ab are produced in some ALS cases is unknown. It may be related to the morphological alterations of neuromuscular junctions that are present from early disease stage [START_REF] Vinsant | Characterization of early pathogenesis in the SOD1(G93A) mouse model of ALS: part II, results and discussion[END_REF][START_REF] Bruneteau | Endplate denervation correlates with Nogo-A muscle expression in amyotrophic lateral sclerosis patients[END_REF] and associated with clinically detectable impairment of neuromuscular transmission in up to 53% of ALS patients [START_REF] Killian | Decremental motor responses to repetitive nerve stimulation in ALS[END_REF][START_REF] Wang | Prognostic value of decremental responses to repetitive nerve stimulation in ALS patients[END_REF]. Positive cholinesterase inhibitor test has also been reported in ALS cases [START_REF] Mulder | Myasthenic syndrome in patients with amyotrophic lateral sclerosis[END_REF]. In the context of ALS, the diagnosis of concomitant MG should thus be discussed only in the presence of suggestive clinical features (i.e. ocular symptoms and marked variability of symptoms).

In conclusion, the co-occurrence of ALS and MG is rare and requires strict diagnostic criteria.

In particular, the clinician should be aware that serum antibodies directed against autoantigens implicated in MG may also be found in some ALS cases. Morphological changes of neuromuscular junctions are also present in ALS which may be responsible for significant impairment of neuromuscular transmission and transient response to acetylcholinesterase inhibitors in some patients. The unusual association of these two diseases may be driven by dysregulation of the adaptive immune system in both conditions.

a

  Each case was classified according to the revised El Escorial World Federation of Neurology criteria for the diagnosis of ALS [4]. b None of the patients had undergone therapy with modified snake venom as an alternative treatment for ALS. c The diagnosis of MG was made based on suggestive clinical features and paraclinical findings, including variable weakness, improvement after cholinesterase inhibitor treatment, detection of specific autoantibodies and significant decrement evidenced by RNS tests [5]. d Positive edrophonium test. Spontaneous clinical remission of ocular MG symptoms after a few months, without any relapse over the follow-up period of 12 years.

Table 1 : Clinical characteristics of patients recorded in the database with a concomitant diagnosis of ALS and MG

 1

	Patient No.	Gender	Age at first symptoms (inaugural condition)	Inaugural condition recorded	Associated immune-mediated disease	Delay between onset of conditions (months)	Site of onset of ALS symptoms	Regions with EMG neurogenic pattern
	1	F	72	MG	No	11	UL proximal	UL/LL/bulbar
	2	M	34	ALS	No	71	UL distal	UL/LL/bulbar
	3	M	40	MG	No	319	UL proximal	UL/LL
	4	F	88	MG + ALS	No	0	Bulbar	UL/LL/bulbar
	5	M	77	MG	Basedow's	8	LL distal	UL/LL/bulbar
					disease
	6	F	39	ALS	No	27	Bulbar	UL/LL
	7	M	89	ALS	No	6	LL distal	UL/LL

ALS: Amyotrophic Lateral Sclerosis, MG : Myasthenia gravis, EMG: needle electromyography, UL: upper limbs, LL: lower limbs, AChR-ab : antibodies against acetylcholine receptor, CMAP : compound motor action potential, IVIG: Intravenous immunoglobulin, RNS test: repetitive nerve stimulation test at slow stimulus rate (3-5Hz), AChE inhibitors: acetylcholinesterase inhibitors, ND: not done.

Table 1 (continued) ALS classification a MG initial symptoms AChR-ab level (nmol/l) CMAP decrement at RNS test (%) Response to AchE inhibitors Immune- directed therapy Riluzole b

 1

	Final
	diagnosis
	after
	review a, c

Table 2 : Characteristics of patients meeting the diagnostic criteria for both ALS and MG Total n=6 ALS as inaugural condition n=3 MG as inaugural condition n=3 Median age (range), years

 2

		56 (34-89)	39 (34-89).	72 (40-77)
	Gender, male/female	4/2	2/1	2/1
	Inaugural condition ALS, n (%)	3 (50) 3 (50)	-	-

Localization of MG initial symptoms

Ocular, n (%) Bulbar, n (%) Generalized, n (%) 33) 2 (67) 0 (0) 1 ( 33)

ALS: Amyotrophic Lateral Sclerosis, MG : Myasthenia Gravis


Eric Fabre

Loïc Hélouët

Engel Lefaucheux

Hervé Marchand

Diagnosability of Repairable Faults

published or not. The documents may come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

In its standard version [START_REF] Sampath | Failure diagnosis using discreteevent models[END_REF], the diagnosis problem for discrete event systems starts with a dynamic system A with runs of two types : some runs are safe (they contain no fault event), and the others are faulty. More generally, one may assume a regular property P on runs of A. This property P is generally absorbing, in the sense that once P is satisfied by some partial run (like the fact of being faulty) it remains true in all extensions of that run. System A is supposed to perform some hidden run u, which is partially observed by an external supervisor : only some events of the hidden run u are visible, possibly through some filtering operation, and the other events of u are silent. The problem then consists is deciding whether the hidden run u satisfies the property P of interest given the observed sequence and the model of A. Specifically, assuming at some point u satisfies P, one would like to detect it in bounded time. If this is feasible for all runs satisfying P, the system is declared diagnosable.

Property P can be seen as an abstraction on the behaviors of A, which are partially observed. Diagnosability then amounts to detecting when P holds. One may further be interested in deciding in bounded time after time t whether P holds or not at time t. A dual version of the problem relates to opacity: one would like to ensure that property P (a "secret") is never detectable by an external observer. Beyond its simple statement, the diagnosis problem thus has numerous implications in terms of security and of safety.

In the present paper, we examine the case of non persistent properties P, or non persistent faults, i.e. P may hold only on segments of the hidden run u. Diagnosing P thus means being able to detect that P holds in bounded time after it becomes true, and in any case before P vanishes.

All authors are with the SUMO team of INRIA Rennes, Campus de Beaulieu, 35042 Rennes cedex, France name.surname@inria.fr Section II recalls standard results about the classical notion of diagnosability. The diagnosability for repairable faults, named T-diagnosability, is presented in Section III. It is proved that deciding T-diagnosability is PSPACE-complete. Section IV expresses that when both faults and repairs are T-diagnosable, one is able to count fault occurrences in the hidden run u. Finally, Section V relates these results to previous contributions on the topic.

II. SETTING AND KNOWN RESULTS

A. Diagnosis and diagnoser

A finite automaton over alphabet Σ is a tuple A = (S, Σ, T, s 0 ), where S is a finite set of states, s 0 ∈ S is the initial state, and T ⊆ S × Σ × S is a set of transitions. Transitions take the form t = (s, α, s ) and we denote s -(t) = s, σ (t) = α, s + (t) = s . Paths of A are finite sequences of transitions u = t 1 ...t n such that s + (t i ) = s -(t i+1 ), and runs of A are paths rooted at s 0 : s -(t 1 ) = s 0 . We denote s -(u) = s -(t 1 ), s + (u) = s + (t n ), and σ (u) = σ (t 1 )...σ (t n ) the sequence of labels associated to a path u. The language of A is the set of label sequences produced by runs of A : L(A) = {σ (u), u run of A}. An automaton is deterministic iff ∀s, α, (s, α, s ) ∈ T ∧ (s, α, s ) ∈ T ⇒ s = s .

Our starting point for the diagnosis problem, and without loss of generality, is a deterministic automaton A. Let us partition states of A into two subsets S = S N S F , and let us name S N normal (or safe) states and S F faulty states, to help intuition. The faulty language of A is derived from faulty runs, i.e. runs that terminate in a faulty state: L F (A) = {σ (u), u run of A, s + (u) ∈ S F } ⊆ L(A). The normal (safe) language of A is defined similarly, and denoted L N (A). As A is deterministic, σ establishes a one to one correspondence between runs of A and words of its language L(A), so

L N (A)∩L F (A) = / 0, or L N (A) L F (A) = L(A).
In this section, we assume that faults are permanent in A. Namely, there is no reachable path u in A such that s -(u) ∈ S F and s + (u) ∈ S N . Equivalently, the faulty language of A is saturated in L(A) :

L F (A) Σ * ∩ L(A) = L F (A).
The diagnosis problem assumes partially observed systems, so we partition the label set Σ in two disjoint sets of observable and unobservable labels: Σ = Σ o Σ u . The projection on observable labels Π : Σ * → Σ * o is defined as the monoid morphism generated by Π(α) = α whenever α ∈ Σ o and Π(α) = ε otherwise (ε = empty word). The observable (or visible) language of A is defined as L o (A) = Π(L(A)). For technical reasons commented later, we define the inverse projection Π -1 as follows :

∀w ∈ Σ * o , Π -1 (w) = {v ∈ L(A) : Π(v) = w} ∩ Σ * Σ o (1)
i.e. we restrict the standard inverse projection to words of L(A) that finish with an observable letter 1 .

From a run u performed by A, or equivalently from the word v = σ (u), one only observes the visible actions i.e. the word w = Π(v) = σ o (u) ∈ L o (A), where σ o = Π • σ . The diagnosis consists in deciding whether a fault has occurred in system A given this observed sequence w. A diagnoser for A can be seen as a function ∆ : L o (A) → {N, F,U} where

∆(w) =    N iff Π -1 (w) ⊆ L N (A) F iff Π -1 (w) ⊆ L F (A) U otherwise (2)
Letters N, F,U stand for "normal," "faulty," and "uncertain," (or "ambiguous") as it clearly appears above.

A diagnoser can be derived from an observer (or state estimator) of A. This observer is built in two steps. The first step is the

Σ o -closure of A. The Σ o -closure (to the left) of A is defined as B = Red Σ o (A) = (S, Σ o , T , s 0 ) where (s, α, s ) ∈ T iff there exists a path u = t 1 ...t n in A such that σ o (t 1 ...t n-1 ) = ε, σ o (t n ) = α, s -(u) = s and s + (u) = s .
Intuitively, there is a transition from s to s in T iff there exists a path from s to s with a single observable action labeling the last transition of the path. The Σ o -closure of A is an ε-reduction assuming all labels of Σ u are first replaced by ε in A. The second step is the determinization of the resulting B, performed by standard subset construction. Let D = Det(B) = (Q, Σ o , T , q 0 ) where Q = 2 S , q 0 = {s 0 } and t = (q, α, q ) ∈ T iff q = {s ∈ S : ∃s ∈ q, (s, α, s ) ∈ T }. Of course, both B and D can be trimmed to their reachable part.

Observe that L(D) = L(B) = L o (A). D is a state estimator of A in the following sense : let w ∈ L o (A), as D is deterministic, there exists a unique path r in D such that σ o (r) = w. The final state q = s + (r) ∈ Q of path r in D satisfies q = s + (σ -1 o (w)) ∈ 2 S in A, i.e. it contains all states of A that are reachable by runs that produce the observed sequence w and that stop immediately after the last observable transition. This last condition explains the specific definition of Π -1 and the choice of the Σ o -closure of A to the left. Let us call q ∈ Q = 2 S a normal subset iff q ⊆ S N , a faulty subset iff q ⊆ S F , and an uncertain (or ambiguous) subset otherwise. D yields a diagnoser for A as follows : ∆(w) is the type of

q = s + (σ -1 o (w)) in D. By extension, D is often called the diagnoser of A : D = Diag(A) = Det(Red Σ o (A)).
Due to determinization, D can be exponentially larger than A and should not be used for online diagnosis. One should use instead a recursive state estimation driven by the observed sequence w, which has linear complexity in the size of w and A. D can thus be considered as a precompiled version of the diagnosis for all possible observed sequences.

B. Remarks and extensions

Let A 1 , A 2 be two automata, with A i = (S i , Σ i , T i , s 0,i ), their synchronous product (or simply product for short) is the automaton

A 1 × A 2 = (S 1 × S 2 , Σ 1 ∪ Σ 2 , T 1 ⊗ T 2 , (s 1,0 , s 2,0 ))
1 Alternatively, we can define L(A) as words that terminate with a letter of Σ o , or equivalently by assuming faulty states in A that can only be reached by visible transitions, which does not reduce the generality of the setting.

where transitions in T 1 ⊗ T 2 are triples ((s 1 , s 2 ), α, (s 1 , s 2 )) such that

(s 1 , α, s 1 ) ∈ T 1 ∧ (s 2 , α, s 2 ) ∈ T 2 for α ∈ Σ 1 ∩ Σ 2 (s 1 , α, s 1 ) ∈ T 1 ∧ s 2 = s 2 ∈ S 2 for α ∈ Σ 1 \ Σ 2 s 1 = s 1 ∈ S 1 ∧ (s 2 , α, s 2 ) ∈ T 2 for α ∈ Σ 2 \ Σ 1
Faulty runs in A are often not identified by a partition on states, but rather by the firing of some transition carrying a "fault" label f ∈ Σ u . This can be recast in the previous setting as follows. Consider the deterministic and complete memory automaton M = ({N, F}, Σ, T, N) where (N, f , F) is the unique transition of T producing a state change. The product A × M does not change the language of A, but performs a state augmentation that keeps track of the firing of a faulty transition in A. The label N or F now attached to states of A × M defines a partition of the state set that characterizes faulty runs. This technique was generalized in [START_REF] Jéron | Supervision patterns in discrete event systems diagnosis[END_REF] to detect/diagnose runs satisfying some regular pattern of labels, rather than the simple firing of a transition labeled by f .

When faults are non permanent in A, that is when there exist transitions from S F to S N , one may nevertheless be interested in detecting that some transient fault has occurred. This can again be captured by an obvious transform of A into A , that adds memory to states of A to propagate the fact that a fault occurred sometime in the past. With the assumption that A is deterministic, this amounts to saturating the fault language of A: L F (A ) = L F (A) Σ * ∩ L(A). This idea is a variant of the pattern recognition of [START_REF] Jéron | Supervision patterns in discrete event systems diagnosis[END_REF]. It was used in [START_REF] Jiang | Diagnosis of repeated/intermittent failures in discrete event systems[END_REF] to track the occurrence of k transient faults. It is also present in [START_REF] Contant | Diagnosis of intermittent faults[END_REF] under the names of O-diagnosis (detection of the occurrence of a fault) and I-diagnosis (detection of the occurrence of a repair). All these notions are thus variants of the classical diagnosis approach, even if they are recast in the context of transient failures. In [START_REF] Contant | Diagnosis of intermittent faults[END_REF], the authors propose a "memory automaton" that can be composed with a specification to remember occurrences of faults and repairs. However, even if fault repair is considered, their automaton propagates the information that a fault occurred. In the next section, we consider a different setting, where diagnosis is considered as accurate if it detects a fault before it is repaired.

C. Diagnosability

Let us recall the notion of diagnosability for permanent faults, i.e. when A has no transition from S F to S N . For simplicity, we assume that A is Σ o -live : an observable transition is reachable from any state of A. Intuitively, A is diagnosable iff, whenever it reaches S F , this is detected/diagnosed after a finite number of extra observations. Formally, A is diagnosable iff

∀v 1 ∈ L F (A), ∃n ∈ N, ∀v 1 v 2 ∈ L(A), [ |v 2 | o ≥ n ⇒ Π -1 • Π(v 1 v 2 ) ⊆ L F (A) ] (3)
where Def.

|v 2 | o is the length of Π(v 2 ).
(3) states that a system is diagnosable iff, when uncertainty appears after a faulty run, it does not hold forever. Observe that the diagnosis may nevertheless remain uncertain for an arbitrarily long time, even for a diagnosable system, as long as no fault occurs (see Fig. 1). Conversely, A is not diagnosable iff after some faulty run uncertainty can never be resolved :

∃v 1 ∈ L F (A), ∀n ∈ N, ∃v 1 v 2 ∈ L(A), [ |v 2 | o ≥ n ∧ Π -1 • Π(v 1 v 2 ) ∩ L N (A) = / 0 ] (4)
The last term in (4) can be rephrased as This result was proved in [START_REF] Jiang | A polynomial time algorithm for diagnosability of discrete event systems[END_REF]. The only if part is obvious as the presence of an ambiguous cycle allows one to build an arbitrarily long suffix v 2 to a faulty word v 1 by repeating the cycle, while having this faulty word v 1 v 2 equivalent to a safe one v . This proves non-diagnosability. The if part uses the finiteness of A, as a long enough suffix v 2 necessarily contains a (faulty) cycle of B that can be matched to an observationally equivalent safe/normal cycle of B.

∆(Π(v 1 v 2 )) = U or equivalently ∃ v ∈ L N (A), Π(v 1 v 2 ) = Π(v ).
The original version of Proposition 1 actually relied on a twin machine directly built from A and not from B = Red Σ o (A). Proposition 1 clearly yields a polynomial (quadratic) test for the diagnosability of A.

III. DIAGNOSABILITY OF REPAIRABLE FAULTS

A. Diagnosis and T-diagnosability

We still consider a Σ o -live deterministic automaton A, and now assume that some faults in A can be repaired, i.e. A contains transitions from S F to S N , or equivalently that the fault language L F (A) is not saturated. The diagnosis of an observed sequence w = σ o (u) produced by some run u of A is defined as in [START_REF] Jéron | Supervision patterns in discrete event systems diagnosis[END_REF]. However, we reinforce the diagnosability criterion for A by requiring that, when some fault occurs, it is still detected in finite time, but also before it is repaired.

Let us first introduce some notation. We denote by

L min F = {vα ∈ L F (A) v / ∈ L F (A) ∧ α ∈
Σ} the set of minimal faulty words of A, i.e. words that correspond to a run ending with a transition from a normal state to a faulty one in A. For a word

v 1 ∈ L F (A), let v 1 → v 1 v 2 ∈ L F (A) denote the continuous presence of a fault along v 2 . Formally, v 1 → v 1 v 2 ∈ L F (A) iff ∀ v 2 ≤ v 2 , v 1 v 2 ∈ L F (A)
, where ≤ denotes the prefix relation on words.

Formally, an automaton A is timely diagnosable (Tdiagnosable for short) iff

∀ v 1 ∈ L min F (A), ∃ n ∈ N, ∀ v 1 v 2 ∈ L(A), [ |v 2 | o ≥ n ⇒ ∃ v 2 ≤ v 2 : v 1 → v 1 v 2 ∈ L F (A) ∧ Π -1 • Π(v 1 v 2 ) ⊆ L F (A) ] (5)
T-diagnosability differs from Def. (3) mainly by requiring that the fault that appears in v 1 remains for the whole execution of prefix v 2 . This notion is illustrated in Fig. 2, that depicts several observationally equivalent runs, and shows observation times at which a correct diagnosis/detection can be produced (before repair). Observe that if faults are not repairable,

v 1 ∈ L min F (A) implies that v 1 → v 1 v 2 ∈ L F (A) for every v 2 ,

B. Vanishing faults and repairs

T-diagnosability seems to be a reasonable first step towards the ability to count fault occurrences. Unfortunately, this is not the case as it is already apparent in Fig. 2 : an automaton with such equivalent runs can be T-diagnosable, and nevertheless the same observed sequence matches a run with one fault (top) and one with two faults (bottom). The situation is even worse. Let us call a vanishing fault a fault that occurs and is repaired in the silent part of a run of A (i.e. between two observations), and similarly for a vanishing repair. Then automaton A can exhibit runs with an arbitrary number of vanishing faults and repairs without losing its Tdiagnosability.

This is illustrated by the example in Fig. 4 It is quite counter-intuitive that the "immediate" detection of the fault occurring at v 1 = ab 2 actually relies on the detection of the fault that took place previously, at v 1 = a. This phenomenon is due to the fact that T-diagnosability, just as diagnosability, only refers to runs that stop at a visible transition. Everything that happens between observations is almost ignored. For permanent faults, this is harmless: it only shifts the detection by one observation. For repairable faults, it introduces odd phenomena. A natural way to make fault detection causal (and to open the way to a counting of faults) is thus to forbid the existence of vanishing repairs

∃ v = v 1 v 2 α ∈ L(A) : v 1 ∈ L F (A) ∧ v 1 v 2 ∈ L N (A) ∧ α ∈ Σ ∧ v 1 v 2 α ∈ L F (A) ∧ Π(v 2 ) = ε (6)
and of vanishing faults

∃ v = v 1 v 2 α ∈ L(A) : v 1 ∈ L N (A) ∧ v 1 v 2 ∈ L F (A) ∧ α ∈ Σ ∧ v 1 v 2 α ∈ L N (A) ∧ Π(v 2 ) = ε (7)
Under these assumptions, at most one transition from S F to S N or from S N to S F can take place between two visible events. Let us say that fault detection is causal when observations following the fault enable its detection, so the detection does not depend on observations that occurred strictly before the fault as in the pathological cases above. Such causality can then be expressed as follows.

Proposition 2: Assuming ( 6) and (7), A is T-diagnosable if and only if

∀ v 1 ∈ L min F,o (A) ∪ L min F,u (A)Σ * u Σ o , ∃ n ∈ N, ∀ v 1 v 2 ∈ L(A), [ |v 2 | o ≥ n ⇒ ∃ v 2 ≤ v 2 : v 1 → v 1 v 2 ∈ L F (A) ∧ v 1 v 2 ∈ Σ * Σ o ∧ Π -1 • Π(v 1 v 2 ) ⊆ L F (A) ] (8)
where L min F,o (A) = L min F (A) ∩ Σ * Σ o represent minimal faulty runs that terminate with a visible event, and L min F,u (A) = L min F (A) \ L min F,o (A) represent those that terminate with a silent event.

Proof: The extra condition v 1 v 2 ∈ Σ * Σ o requires that the fault detection takes place at the moment one gets an observation. This could have been introduced in (5) without loss of generality, as silent events at the end of v 2 are useless to the criterion Π -1 • Π(v 1 v 2 ) ⊆ L F (A). So the only novelty lies in the first term. Recall that L min F (A) = L min F,o (A) L min F,u (A). Words v 1 ∈ L min F,o (A) are considered by both ( 5) and (8). But words v 1 ∈ L min F,u (A) in ( 5) are replaced by words v 1 ∈ L min F,u (A)Σ * u Σ o in (8). In other words, for faults that occur silently, detection takes places after the next visible event.

Only if part. Assume A is T-diagnosable, and let v 1 ∈ L min F,u (A)Σ * u Σ o . v 1 decomposes uniquely as v 1 = v 0 u 3 where v 0 is the L min F,u part and u 3 the extension in Σ * u Σ o . v 0 further decomposes as v 0 = u 1 u 2 where u 2 is the longest silent suffix of v 0 . Thanks to ( 6) and ( 7), one has that u 1 ∈ L N (A), and u 1 u 2 → u 1 u 2 u 3 ∈ L F (A). As A is diagnosable and v 0 ∈ L min F (A), let us take any long enough extension v 2 ≥ u 3 for the fault detection in Def. [START_REF] Kozen | Lower bounds for natural proof systems[END_REF], and let

v 2 ≤ v 2 , v 2 ∈ Σ * Σ o be the detection time. One can not have v 2 < u 3 because in that case Π(v 0 v 2 ) = Π(v 0 ) = Π(u 1 ) and u 1 ∈ L N (A)
. So the detection of the fault can not occur before the extra observation lying at the end of u 3 . Since v 2 ≥ u 3 , one has v 2 = u 3 v 2 and v 0 → v 0 u 3 v 2 ∈ L F (A). This proves the existence of a detection time v 2 after v 1 = v 0 u 3 which satisfies (8).

If part. Assume A satisfies (8) and let v 1 ∈ L min F,u (A). v 1 decomposes uniquely as v 1 = u 1 u 2 where u 2 is the longest silent suffix of v 1 . Thanks to ( 6) and ( 7), one has

v 1 ∈ L N (A). Let v 1 v 2 ∈ L(A), with v 2 long enough, in particular |v 2 | o ≥ 1. One can write v 2 = u 3 u 4 with u 3 ∈ Σ * u Σ o .
Thanks to ( 6) and (7) again, one has

v 1 → v 1 u 3 ∈ L F (A). As v 1 u 3 ∈ L min F,u (A)Σ * u Σ o and u 4 is long enough, there exists a prefix u 4 ≤ u 4 such that v 1 u 3 → v 1 u 3 u 4 ∈ L F (A) and ∆(Π(v 1 u 3 u 4 )) = F. Taking v 2 = u 3 u 4 thus
satisfies the conditions of (5).

C. A T-diagnosability test

As in Section II-C, one can consider the converse of (5). Specifically, A is not T-diagnosable iff

∃v 1 ∈ L min F (A), ∀n ∈ N, ∃v 1 v 2 ∈ L(A) : |v 2 | o ≥ n, (9) ∀v 2 ≤ v 2 , v 1 → v 1 v 2 ∈ L F (A) ∨ Π -1 • Π(v 1 v 2 ) ⊆ L F (A)
In words, A is not T-diagnosable whenever it is possible to find a minimal faulty sequence v 1 and arbitrarily long extensions v 2 such that along the longest faulty prefix v 2 ≤ v 2 of v 2 , the detection of the fault can not occur.

It is worth noticing that the twin-machine idea used to check the diagnosability of permanent faults is not sufficient to check the T-diagnosability of repairable faults. The main obstacle comes from the fact that T-diagnosability can not be characterized by pairs of equivalent runs. It is rather a global property on classes of equivalent runs in A. This is illustrated in Fig. 5, where unobservable transitions are depicted as dashed arrows (Σ o = {a}). This automaton is not T-diagnosable. However, by checking only pairs of equivalent runs, one always finds a time where ambiguity seems to vanish. For example, considering only the top and central loops, a 3n+1 seem to be detection times for the faults that appear in these runs. To reveal that T-diagnosability does not hold, one would have to check triples of equivalent runs here. And it is quite easy to design examples where triples are not sufficient and one needs to escalate to quadruples of equivalent runs to reveal the non T-diagnosability, etc. This suggests a non polynomial complexity of the T-diagnosability test. The idea of the twin-machine construction is to check whether a faulty run can create an ambiguity that can never be resolved. For repairable faults, this ambiguity signal can be directly derived from Diag(A), the diagnoser of A. Consider the (deterministic) automaton G = A × Diag(A). Diag(A) is a deterministic automaton over alphabet Σ o ⊆ Σ, and L(Diag(A)) = L o (A). So L(G) = L(A) : the construction of G performs a simple state augmentation on A, without changing its behavior (just like the memory automaton mentioned above). This state augmentation attaches an ambiguity status to each state of A as follows. States of G take the form (s, q) ∈ S × Q where Q = 2 S . So they can be labeled by elements in {N, F} × {N,U, F} : for example (s, q) is of type (N,U) iff s ∈ S N and q is uncertain. L N (A) and L F (A) are easily identifiable in G as words terminating in a state of type (N, .) or (F, .) respectively. A state (s, q) is said to be minimally faulty iff s is the terminal state of a run v 1 ∈ L min F (A). Theorem 1: With notation above, A is not T-diagnosable if and only if there exists a reachable minimally faulty state (s, q) ∈ S × Q in G such that (s, q) is of type (F, N) or (F,U) and either 1) there exists a state (s , q ) of type (N, N) or (N,U) 2) or there exists a cycle of (F,U) states that is reachable from (s, q) through a (possibly empty) sequence of (F, N) states followed by a sequence of (F,U) states.

Proof: By construction of G, observe that if word v ∈ L(A) reaches state s in A, then word v reaches state (s, q) in G and ∆(Π(v)) is the type of state q ∈ Q, either N, F or U.

For the only if part, consider the witness v 1 ∈ L min F (A) of non T-diagnosability in (9), which reaches state (s, q) in G. (s, q) is necessarily of type (F, N) or of type (F,U), as if (s, q) is of type (F, F) then the correct diagnosis is output with v 2 = ε. For a given n, let v 2 be the extension of v 1 satisfying (9), and let v 2 be the longest prefix of v 2 such that v 1 → v 1 v 2 ∈ L F (A). All along v 2 , the correct diagnosis can not be output, so G only crosses states of type (F, N) or (F,U). States of type (F, N) come first (if they exist), then (after the first observable event in v 2 ) one only crosses states of type (F,U) as at least one faulty run lies in the inverse projection. If there exists a ∈ Σ such that v 2 a ≤ v 2 , then v 1 v 2 a reaches state (s , q ) which is either of type (N, N) or of type (N,U). (N, F) is not possible as this would mean that the correct diagnosis was produced for v 1 v 2 . This makes point 1 in the theorem. If point 1 never occurs for any n, this means that in the discussion above one always has v 2 = v 2 . As G is finite, it then contains a cycle with at least one observable event (recall that n counts observations). This cycle is thus made of (F,U) states, which makes point 2 in the theorem.

The if part can be derived in a similar manner, starting from conditions in the theorem and building a witness v 1 and the associated v 2 for every n satisfying (9).

D. Complexity of T-diagnosability

Theorem 2: Deciding whether an automaton A is Tdiagnosable is a PSPACE-complete problem.

Proof: First, we can easily show that T-diagnosability belongs to PSPACE. Following the result of Theorem 1, A is not T-diagnosable iff one can find a witness cycle of type (F,U) or a witness state of type (N, N) or (N,U) reachable after a minimally faulty sequence ending in a state of type (F, N) or (F,U) in G. First of all, the size of G is at most 2 |A| .|A|. To witness a minimally faulty sequence ending in a (F, N) of (F,U) state, one only needs to non-deterministically explore paths of size smaller than 2 |A| .|A|, which can be done with polynomial memory size (to remember current state and whether previous state is faulty). Then, to witness ambiguous cycles or moves to (N, N) or (N,U) states, one can again non-deterministically explore paths of G of size smaller than 2 |A| .|A| with polynomial memory. Hence, finding witness paths for non-T-diagnosability is a NPSPACE process, and using Savitch's theorem, and remembering that PSPACE is closed under complementation, this shows that T-diagnosability is in PSPACE.

q i q 0 q f f 1 f 2 . . . f n r q 1 0 • • • q 2 0 q n 0 q 1 q 2 q n q 1 1 q 2 1 q 2 2 q n 1 . . . q n n f u 1 u 2 u n r Σ A 1 A 2 A n
The second step of the proof shows hardness of the problem by reduction from a language inclusion problem, which is known to be PSPACE-complete [START_REF] Kozen | Lower bounds for natural proof systems[END_REF]. The problem can be formulated as follows: given A 1 , ..., A n some deterministic finite automata, i∈1..n L(A i ) = / 0 ? Let n ∈ N and for 1 ≤ i ≤ n, A i = (S i , Γ, T i , q i 0 , F i ) be some deterministic finite automaton on alphabet Γ. We build the finite automaton A = (S, Σ, T, q 0 ) (see Figure 6) where:

• Σ = Γ ∪ {u 1 , . . . u n } ∪ { f , , , r} • S = {q i , q 0 , q f , r}∪{ f i | i ∈ 1..n}∪{q j i | i, j ∈ 1..n∧ j ≥ i} ∪ 1≤i≤n S i • T = {(q 0 , f , q f ), (q i , , q 0 )( f n , r, r), (r, , r), (q f , , f 1 )} ∪ {( f i , , f i+1 ) | i ∈ 1..n -1} ∪ {(q f , a, q f ) | a ∈ Σ} ∪ {(q 0 , u i , q i 0 ) | i ∈ 1..n} ∪ {(q i i , , q i i | i ∈ 1..n} ∪ {(q, , q i 1 ) | q ∈ F i , i ∈ 1..n} ∪ {(q j i , , q j i+1 | 1 ≤ i < j ≤ n} ∪ 1≤i≤n T i The set of safe states is S N = {q i , q f , r} ∪ {q i i | i = 1 . . . n}. The set of faulty states is S \ S N . We set Σ o = Γ ∪ { , , r}.
We claim that A is T-diagnosable if and only if i∈1..n L(A i ) = / 0. First, remark that after observing w m for m ≤ n, the current run is either in state f m or in q j m for j ≥ m such that A j accepts w.

Suppose that A is T-diagnosable. Let w ∈ Σ * , v 1 be the unique run of A such that σ (v 1 ) = f w . As v 1 is a minimal faulty run, there exists m ≤ n such that the run

v 1 v 2 with σ (v 1 v 2 ) = f w m verifies Π -1 • Π(v 1 v 2 ) ⊆ L F (A).
From our earlier remark, as q m m is safe, it means that A m does not accept w. As this is true for every w ∈ Σ * , i∈1..n L(A i ) = / 0. Conversely suppose that i∈1..n L(A i ) = / 0. Let v 1 be a minimal faulty run. Only two cases can appear: either v 1 is the word v 1 = which ends in the faulty state q 0 , or v 1 is of the form v 1 = f w . If v 1 = , then we know that A is in q 0 which is faulty and we can claim the fault. In the second case s + (v 1 ) = f 1 and σ (v 1 ) = f w with w ∈ Σ * . As i∈1..n (A i ) = / 0, there exists i ∈ 1..n such that w ∈ L(A i ). Consider the run v 1 v 2 with σ (v 1 v 2 ) = f w i , this run ends in f i and was not repaired in between. Moreover, thanks to the earlier remark, for every j > i such that A j accepts w, runs with the same observation w i ends in state q j i for j ≥ i. Thus, even if w is recognized by A k for some k < i, no run visiting a state of A k and with observation w i exists. As A i does not accept w and as the states q j i for j > i are faulty, Π -1 •Π(v 1 v 2 ) ∈ L F (A). Thus the fault can be claimed. As this is true for every minimal faulty run v 1 , A is Tdiagnosable.

IV. COUNTING FAULTS

As faults are not permanent, counting the number of faults occurring at runtime is a useful information: even if a system is able to repair all occurrences of faults, a too large number of faults may indicate a major failure. To count faults, an immediate idea is to maintain a fault counter that is incremented each time the diagnoser goes from N to F and from U to F. Even if a diagnosis can be triggered in time, i.e. before the fault is repaired, T-diagnosability is not sufficient to correctly count faults along a trajectory. Fig. 2 reveals that this can not work as counting moves of the diagnoser from {N,U} to F in this example would detect two faults, while v has only one fault and v has two. Conversely, counting only moves from N to F or from U to F leads to minoring the real number of faults that occurred in some runs. This section considers extra conditions that enable counting. A fault counter C of an automaton A is a function from Σ * o to N such that: for every run v ∈ L(A), letting k v be the number of fauls in v, C(Π(v)) ∈ {k v -1, k v }. An automaton A is fault countable if there exists a fault counter of A.

Given an automaton A, q, q ∈ Q, k ∈ N and a ∈ Σ o , we write q → a,k A q if there is a path in A from q to q of unobservable events except for the last transition labeled by a with k faulty transitions.

Proposition 3: Assuming that there is no vanishing repairs/faults in A, deciding if A is fault countable w.r.t. F is in NLOGSPACE.

Proof: Let A = (S, Σ, T, s 0 ) be an automaton. As there is no vanishing repairs/faults, if q → a,k A q , then k ≤ 1. We build the following variant of the twin automaton A C = (S C , Σ, T C , {s 0 , s 0 , 0}) where:

• S C = S × S × {-1, 0, 1, ⊥}, • ((q 1 , q 2 , n), a, (q 1 , q 2 , m)) ∈ T C iff q 1 → a,k A q 1 , q 2 → a,k A q 2 and -if n = ⊥, then m = ⊥, -if n = ⊥ and n + k -k ∈ {-1, 0, 1}, then m = n - k + k , -if n = ⊥ and n + k -k ∈ {-1, 0, 1}, then m = ⊥. ∆ (v) = N ∆ (v.v F k+1 ) We hence have N A (v.v F k+1 ) = N ∆ (v) = k,

V. RELATED WORK

The diagnosis of such transient faults has been considered in [START_REF] Contant | Diagnosis of intermittent faults[END_REF], which proposed four notions of diagnosability. One of them ("O-diagnosability") consists in detecting the occurrence of a transient fault, even after it has been repaired, which amounts to saturating L F (A) (see Section II-B). Symmetrically, the "I-diagnosability" aims at detecting the occurrence of a repair, even if fault(s) followed, which amounts to inverting the roles of S F and S N , or to saturating the safe language L N (A). Both notions thus match the standard (or historical) notion of diagnosability for a slightly modified version of A. In the same manner, the notions of "P-diagnosability" and "R-diagnosability" are dual of one another, so our work should only be compared to the notion of "P-diagnosability" proposed by [START_REF] Contant | Diagnosis of intermittent faults[END_REF].

This notion of "P-diagnosability" states that after the occurrence of a fault, it is always possible to detect the fact that the system is currently faulty, based on the observation (even though the fault has been repaired in the past). Our notion of T-Diagnosability is then stronger than P-diagnosability, as we require that detection fault occur before they are repaired. It is then easy to show that whenever a system is T-diagnosable then it is also P-diagnosable. Compared to [START_REF] Jiang | Diagnosis of repeated/intermittent failures in discrete event systems[END_REF] the notion of [1 • • • K]-diagnosability of simply the K diagnosability, we introduce a sufficient condition under which it is possible to exactly count the number of faults that occurred in the system. Furthermore, similarly to [START_REF] Contant | Diagnosis of intermittent faults[END_REF], in the definitions of diagnosability introduced in [START_REF] Jiang | Diagnosis of repeated/intermittent failures in discrete event systems[END_REF], the authors do not request the detection of the fault before its repair.

VI. CONCLUSION

We have proposed a notion of "timely-diagnosability" that requires the detection (in bounded time) of transient faults after they occur, and before they are repaired. This notion was defined for a deterministic partially observed automaton. While this choice allows one to express most properties in terms of faulty and safe languages, it leads to quite complicated criteria for T-diagnosability, as in Theorem 1. It could be interesting to define T-diagnosability for non-deterministic automata, and to explore whether criteria simplify. For example, it is likely that in the absence of vanishing faults and of vanishing repairs, T-diagnosability is preserved by Σ o -closure. Also, while the T-diagnosability of faults relies on a complicated criterion, it is likely that systems which are both T-diagnosable for faults and for repairs are much easily characterized. This subclass is quite interesting, as it corresponds to systems where all changes of state class are detected in bounded time, and in any case before they change again. So ambiguity, when it appears, can not last forever.

T-diagnosability is stronger than the P-diagnosability of [START_REF] Contant | Diagnosis of intermittent faults[END_REF] in the sense that the latter does not require that a transient fault be detected before it is repaired. Nevertheless, it is likely that P-diagnosability remains PSPACE complete, but this still has to be proved.

Besides these immediate perspectives, the future of this work is definitely in the direction of quantitative analysis. Being able to characterize exactly, after a bounded delay, in which state class lies system A is a very strong property. A more relevant question would be to determine how likely it is that A is in S N or S F given partial observations, and whether this relative certainty passes some threshold in a bounded time after system A has changed class.

Fig. 2 .

 2 Fig.2. A faulty word v and two equivalent words v , v . The observed labels are represented as pins, and the faulty zones as grey rectangles. Detections correspond to times (in number of observations) where all equivalent words are faulty.

Fig. 3 Fig. 3 .

 33 Fig. 3 illustrates the notion of T-diagnosability. Safe (resp. faulty) states are represented as white (resp. black) patches. One has Σ = {a, b, c, d} and Σ o = {a}. Ignoring the grayed

Fig. 4 .

 4 Fig. 4. An arbitrary number of vanishing faults and repairs may exist in a T-diagnosable automaton.

Fig. 5 .

 5 Fig.5. This system is not T-diagnosable, but this is not apparent if only pairs of equivalent runs are considered.

Fig. 6 .

 6 Fig. 6. PSPACE-hardness of T-diagnosability. Red states are faulty, and blue states normal states.

Fig. 7 .

 7 Fig.7. Here the automaton is T-diagnosable w.r.t. N but not w.r.t. F, moreover the sequence of verdicts emitted by ∆ is NUUN. However, after reading aa we know a single fault happened for sure.

  [START_REF] Jéron | Supervision patterns in discrete event systems diagnosis[END_REF] | o , instead of counting all transitions. It makes more sense to have an observable criterion to decide when to collect the diagnosis. And when A has no unobservable cycle, which is generally assumed when one uses |v| instead of |v| o , this rephrasing is harmless. Secondly, one generally assumes a uniform value of n covering all faulty words v 1 . Again, taking account the finiteness of A, this uniform bound comes for free once (3) holds. Fig.1. Normal/faulty states are represented as white/black dots. The dashed line represents an unobservable transition. This automaton is diagnosable: after it reaches the faulty state, it can only produce a b which characterizes the occurrence of the fault. Nevertheless, driven by sequence a n , the diagnoser outputs U n . So uncertainty can be arbitrarily long.

	a
	a	b

This expression slightly differs from more frequent ones (for ex.

[START_REF] Sampath | Failure diagnosis using discreteevent models[END_REF]

), but remains equivalent in essence. First, Definition (3) counts only visible transitions in |v

  Red Σ o (A), the twin machine of A is obtained as C = B × B. A run in C is a pair of runs of B that are observationally equivalent, from which one can recover a pair (v, v ) of observationally equivalent words of L(A). C has S × S as state set, so states of C can be called normal/safe, faulty or uncertain/ambiguous, as in D, the diagnoser of A. An ambiguous cycle in C is a reachable cycle that only goes through ambiguous (pairs of) states.Proposition 1: A is diagnosable iff its twin machine C has no ambiguous cycle.

This new formulation expresses that one can find an arbitrary long extension v 2 of some faulty word v 1 which is observationally equivalent (or equivalent for short) to a safe word v of A, denoted by v 1 v 2 ∼ o v . As faults are permanent, any prefix of the safe word v is also safe. Def. (4) thus opens the way to a polynomial test for (non-)diagnosability: one can build a twin-machine that recognizes pairs of runs made of a faulty one v 1 v 2 and an equivalent (w.r.t observation) safe one v , and thus check how long uncertainty can last.

Consider B =

ACKNOWLEDGEMENTS

The authors would like to thank Francois Godi, Xavier Montillet and Chen Qian, master students at ENS Rennes, for interesting discussions that led to this work.

This construction is of size at most 4.|A| 2 . Remark that the third component of the automaton keeps the difference of the number of faults by the two followed runs as long as this difference is not strictly greater than 1. It then raises ⊥ if the difference gets bigger than 1.

We will now show that A is count diagnosable if and only if no state of the form (q, q , ⊥) is reachable, which can be tested in NLOGSPACE.

Let us suppose that there exists q, q ∈ S such that (q, q , ⊥) is reachable. Let v be a run reaching (q, q , ⊥). We suppose (q, q , ⊥) to be the first state of v which third component is a ⊥. By construction of our twin product, we can associate v to two runs v 1 and v 2 of A with same observation and such that one of the two run (say v 1 ) committed at least two more faults than the other. Consequently, suppose there exists a fault counter C, let k be the number of faults in v 1 (v 2 has thus less than k -2 faults), let c = C(Π(v 1 )), then c ≤ k -2 and c ≥ k -1 by definition of a fault counter, which is not possible. Therefore A is not fault countable.

Conversely, if A is not fault countable. Then there exists w ∈ Σ * o such that no correct value can be given. By definition of a fault counter, this means that there exists two runs v 1 and v 2 such that w = Π(v 1 ) = Π(v 2 ) and the number of faults in v 1 is at least two more than the number of fault in v 2 . Let v be the run in V C following the two runs v 1 and v 2 , this run end in a state

Remark that this proof does not immediately give the construction of a fault counter for the automaton. We will say that an automaton is T-Diagnosable w.r.t. N if repairs can be faithfully detected. Intuitively, this property can be checked by inversion of safe and faulty states, an then checking T-diagnosability of the so-obtained system. Consider the Diagnosis function ∆ : L o (A) → {N, F,U} defined by [START_REF] Jéron | Supervision patterns in discrete event systems diagnosis[END_REF].

We define the function F ∆ from L o (A) to N as follows: Let µ ∈ L o (A) and ρ ∈ (N +U + F) * the associated sequence of verdict emitted by ∆. Let ρ ∈ (N + F) * be the projection of ρ on the verdicts {N, F}, then F ∆ (µ) is the number of occurrences of pairs NF that appear in ρ . Intuitively, F ∆ is a function that will be used to count the number of faults the diagnoser is able to detect. We can define similarly function N ∆ , counting the number of detected repairs, by inverting N and F in the previous definition.

Given a run u of A, F A (u) denotes the number of times A moves from a normal state to a faulty state in u and

Intuitively, this proposition states that we can build from the diagnoser a function that counts the number of times the system becomes faulty (resp. is repaired) with a difference of at most 1. Furthermore, the difference is null as soon as the fault (resp repair) is diagnosed by the diagnoser. Proof: We proceed by induction. The base case is v = ε. In this case, N A (v) = 0 and N ∆ (Π(v)) = 0 as s o ∈ N and

, and

. )))) = U, meaning that the diagnoser is still not able to say that the system is repaired and in that case

For the remaining sub-sequence up to v N k+1 either the diagnoser can only emit the verdict N or the verdict U as the corresponding sequence is not faulty and thus the function N ∆ () is not incremented. The proof showing that the function F ∆ () is also incremented by 1 after v.v N k+1 while reading v F k+1 is symmetric to the previous case by replacing N by F and vice-versa. Now, consider the case where

ends on a normal state. We have ∆(v) ∈ {N,U}, and s k ∈ N.

Consider the extension of v with a sequence of faulty states v F k+1 . As s k is in N, as v F k+1 starts with a faulty state and as we have no vanishing repair and A is T-diag w.r.t N, we have N A (v) = N ∆ (v). As v F k+1 is a sequence of faulty states,