Supernovas, supervolcanos… nuclear reactors. An unpredictable wide-scale destruction of nuclear power plants from relativistic neutrons

Florent PIROTflorent.pirot@coleurope.eu +33 6 80 21 70 73

Abstract : Recent astrophysical discoveries, including actinid-rich stars and protostars close to a black hole, as well as geophysical research (for instance the proximity of zirconium and barytine mines, stable decay products of major fission products, to volcanic areas), allow to confirm, rearrange and expand the hypothesis first developed by J M Herndon in the 1990s by adaptating it fully to star cores and linking it to volcanism. I offer a contradiction of the R-process and of the chondritic model for the Earth s composition: I claim that U and Th chains are not synthetized in supernovas, but at the origin of stars and planetary cores, offer a link between nuclear fission and fusion through ternary fission processes, claim that supernovaes are the main factor for super volcanic eruptions (explaining volcano clusters) and suggest that neutrons expelled by supernovas, accelerated by the disappearance of attraction forces, constitute accelerated matter explaining gravitational waves. These neutrons are obviously able to destroy as well nuclear plants on a large perimeter.

The « actinid boost » is a long-time issue which can be resolved -so is the issue of "volcano clusters". Some stars have been confirmed to be uranium and thorium-rich. The ash of the St Helens volcano was depleted in U238 and Th232 (Strauss, Sherman, Pehl 1981). This is confirmed by spectral research, see for instance [START_REF] Hill | The Hamburg/ESO R-process Enhanced Star survey (HERES) XI. The highly r-process-enhanced star CS 29497-004[END_REF] as well as Barbuy et al (2011). Both teams found U and Thrich stars and used the classical theory to assess that these stars are very old. They may on the contrary be extremely recent agglomerates of matter.

Type 1A supernovas are evidence : the passing of a big star close to a very small one mean that the small one will receive much more neutrons as well as hydrogen captured by gravity than it is accustomed to in its internal nuclear equilibrium ; thus it reacts extremely violently, and goes hypercritical. The bright light of Type 1A supernovaes confirms that dwarf stars are mostly made of U & Th (as well as of the Bi209 from the Np237 chain), failed to light up and thus did not accumulate the much needed hydrogen moderator and fusion fuel. The amount of unfissioned U and Th explains extremely well the brightness of these supernovaes which are highly dominated by fission whereas other supernovaes are more equilibrated between fission and fusion (as the internal U and Th core collides with the outer sphere at detonation, compressing it and fusing it). 2004) also note a possible antineutrino confirmation of fission in the Earth's core. G.J. MacDonald (1988) also notes findings of dihydrogen gas in the Kola borehole in Russian territory. Last point, the findings that zirconium and barytine mines are concentrated near old extinct volcanoes or hydrothermal areas are a good confirmation that these elements are the stable decay products of nuclear fissions underground. This is also shown by the explosive nature of "tornillos" associated with magma production in subduction areas that can easily be compared to the typical signal of underground nuclear tests. These element can allow us to reconstitute a planetary and stellar motor for temporary increases of fission and fusion, where the fuel for fusion is provided by ternary fission processes, explaining the accumulation of dihydrogen as well as other light elements close to the Earth's surface. The discovery that barytine and zirconium mines are located close to old volcanoes confirms that nuclear fission is the motor for magmatic formation and explains the contribution of water to explosive increases of magma in subduction magmatic chambers, as water brought by subduction is the perfect incident neutron moderator for nuclear fission supercriticities propped up sometimes by the impact of neutrons from nuclear supercriticities in stars. It suggests a direct link between novas, supernovas and volcanism. This is also confirmed by the high intensity of the antineutrino flux in KamLAND, close to a subduction area of the Pacific belt.

The discovery by the team of James Head ( 2011) of an intense volcanism on Mercury also confirms the heavy interaction between solid U/Th planetary cores and neutrons from the permanent fission processes in stars. Mars, where iron oxyde is significant, can be opposed to Venus, with a lot of basalt and volcanoes (where the planet seems an immense volcano bubble), and thus Mercury certainly was even more active but has, in a way, "expired" because of too much neutron fallouts from the Sun burning fast its actinids. The organisation of the Solar System seems in a way to show that in the proto disk, much more compressed, iron separated the dense U and Th chains on one side and the lighter elements on the other (reproducing in reverse the Aston curve), where actinids have likely accumulated in the planets closer to the Sun (this is also confirmed by research by Laura Schaefer and Bruce Fegley Jr (2003) showing lead and bismuth snow on Venus). Mars is in an intermediary position, where iron from fusion processes in the proto disk would have already accumulated. Gases, partly fused, from ternary fission processes, have been mostly expelled beyond, on the form of giant gas planets. The chondritic asteroid belt would represent a rupture zone (for instance from the impact of an massive object like a very small star) where iron would have been the interface in the proto disk, explaining thus that the iron-rich chondrites do not match the content of planetary cores closer to the Sun. This again suggests a vast amount of U and Th in the cores of planets (as suggested initially by J M Herndon 1 ).

It is obvious that gas bubbles would not alone survive close to a black hole. A much heavier star core, made with actinids, would however resist the permanent attraction of the black hole. The recent discovery of proto stars close to a black hole is an excellent confirmation that stars are not made with light elements but with heavy, radioactive actinids, compressed up to a permanent fission reactor thanks to the strength of gravity, where complex nuclear reactions create the hydrogen fuel (tritium for instance is an unfrequent fission product from ternary fission) for the parallel nuclear fusion process and the thermalisation of neutrons, whereas gravity also slows down neutrons.

Positrons from the capture of helium-4 nucleii of actinid decay and ternary fission products (where lighter elements capturing an alpha particle decay by emitting a positron) are one element as they conjoin with neutrons and beta particles of fission products to create hydrogen. Fission products beta particle decay is also crucial and demonstrates here its "usefulness" in the global star cycle.

Tritium from ternary fission also is a source for helium-3 which then produces protons through neutron impacts, an explanation for protons in cosmic rays. Ternary fission also rarely produces mere protons which may directly combine with electrons to produce hydrogen. Fission products and their transmutation are a key in production of other elements together with nuclear fusion of for instance helium-4 from ternary fission products (in combination with the electrons of fission 1 I discard any relation with his claims on « chemtrails » and « geoengineering »... products beta decay). Hence ternary fission is key in providing the usual nuclear fusion cycle with its fuel. I claim that light elements in stars are solely the product of nuclear fission, ternary fission products and radioactive decay, through combinations of the elementary particles in a context of high gravity forces and temperature, and of course slow capture of neutrons, which also contributes obviously to the diversity of heavy elements beyond the iron limit of the Aston curve, from fission product activation combinated with radioactive decay.

Neutron stars are also an excellent way to see the expulsion of all fission product matter outwards in violent hypercriticity events where only neutrons remain at the end, agglomerated and compressed by their own gravity forces.

A thermonuclear reactor at equilibrium is obvious, where interactions with nearby supernovas are a major and essential factor in star divergence onto supernova through intakes of neutrons and other elements (hydrogen and helium gas for instance) disrupting the internal equilibrium, and "waves of supernovaes" from one star to another (one future example could be Saiph, variable supergiant red star near Barnard's Loop, where the variations of magnitude are a good indicator of the recent impact of neutrons from the supernova that created Barnard's Loop, or maybe another cloud of gas in the Orion constellation). These neutrons are major constituents of the masses of accelerated matter that explain gravitational waves (which is also confirmed by the recent confirmation of gravitational waves in association with the collision of neutron stars, likely to expel a lot of neutrons at impact and implosion under themselves).

It also appears that supernovas close to Earth like the one giving birth to Barnard's Loop are linked to supervolcanoes, in this case the Huckleberry Ridge Tuff and Cerro Galan supervolcanos.

Neutrons from the Lagoon Nebula may also be linked. It may be possible to envision a better datation by linking Lagoon Nebula initial blast to Barnard's, which could have happened closer to each other than thought until now, and a method for predicting supervolcanoes from supernovaes.

The high temperature of stars around SN1987A even more suggests that the dramatic event provided neutrons to the fission core of these stars. The sudden relapse of gravity when a star explodes could act as a propulsive power for its own fission and fusion neutrons, which may gain speed up to close to the speed of light. All the VEI 6 volcanic eruptions in the 20 th Century can be linked to supernovas which happened close to Earth in recent times : G1.9+0.3 happened approximatively in 1898 according to recent research and this event can be linked to the Santa Maria (VEI 6) and Montagne Pelée (VEI 4) eruptions of 1902 as well as the beginning of the activity of Novarupta (1912, VEI 6 2 ) and of the Cerro Azul (1903, which led to a VEI 6 eruption in 1932 after a succession of volcanic events). SN 1987A may be linked to the Pinatubo eruption of 1991 (VEI 6), Hudson in Chile (1991, VEI 5+) as well as Rabaul (1990Rabaul ( -1995) ) and Unzen volcanos (1991). For the Samalas supervolcano in 1257 (see Lavigne et al (2013) as well as Oppenheimer ( 2003)), SN1006 could be the ideal explanation (in which the magma would have accumulated during a longer period than usual, leading to a bigger eruption than in the VEI 6 cases discussed above). SN1054 and SN1181, after SN1006, may also have contributed if the Indonesian archipelago was on their side at impact. SN 1604 may be linked to a lengthy accumulation of magma leading to the Mount Tambora supereruption (with the possible supplementary contribution of Cas A), and can even be linked locally to events such as the small volcanic eruptions that actually took place in the graniticuraniferous-rich Mercantour massif in the French Alps, recorded in 1612 after the disappearance of an entire village into a crater of "flames" (a plaque still commemorates the event in the Cians with the inscription "Hic omnes disparuerunt recquiesant in pace -1612") and another lava flow recorded at the same time (again in the Cians in the Raton mountain near the Dôme du Barrot)see [START_REF] Rossi | Editions des Régionalismes The feasibility and implications of nuclear georeactors in Earth's core-mantle boundary region[END_REF]. SN1604 also coincides with highly destructive eruptions in the Mediterranean area (Vesuvius 1631, Kolumbo (Santorini area) 1650 and Etna 1669). It actually makes sense that light may be refracted and slowed down for instance in the Milky Way because of clouds of refractive materials with no similar effect on fast neutrons so that neutrons come earlier, hence linking Type 1a SN1006 with the Mount Baekdu supervolcano in 946 (where the magnitude of a Type 1A supernova explains the magnitude and quickness of development of the event). Of course as always it is a precise side of the planet that is blown and thus a cluster of eruptions in a localized area, e.g. one continent, ensue. Spontaneous fission of U238 underground, as well as the periodic increases of solar activity, should be related to less powerful eruptions... The SN1987A-triggered wave of eruptions in the Pacific matches the K431 accident in Vladivostok area in August 1985. Light from the supernova could easily have been slowed down for a few years by refractive material. We see the first seismic activity in the Nevado del Ruiz in early September 1985 (yet it can be expected that underground nuclear fission, propped up by supernova neutrons, takes nevertheless months or years to diverge to above criticity threshold, because molten down matter will go up, reducing pressure and thus increasing critical mass, every time the natural reactor accelerates). The K431 nuclear attack submarine was, according to reports, surfacing and in refueling at the moment of the blast, and hence unshielded from fast neutrons by layers of water. A bad manipulation in refueling would have officially triggered the supercriticity, nevertheless a simple melting down of the core could have been expected, yet the supercriticity was explosive. For that reason, and because it is in the target area for SN1987A and matches the beginning of volcanic activity in the Nevado del Ruiz, I suggest that fast neutrons coming from SN1987A came on August 10 and destroyed the K431 reactor.

Conclusion :

The cross section for fission at very elevated neutron speeds of all actinids including U238, Th232 are rising due to second-chance fission, i.e. (n, 2nf), third-chance fission, etc. and giant dipole resonance. It is obvious that the impact of a significant neutron wave will result in the destruction of all working nuclear reactors in a wide area. SN1987A was, compared with Kepler's Star or Tycho's Star, magnitudes less powerful. Nuclear reactors can be expected to be destroyed by the impact, not simply molten down, and the catastrophe should happen simultaneously in reactors on a wide area, e.g. continent-wide. Such waves cannot be predicted. Clouds of dark matter may make it for instance impossible to see dwarf stars that are in the path of giant red stars, and Type 1A are the most neutron-rich supernovas.

It is impossible to shield completely nuclear reactors but building very large pools of water above and on top of current nuclear plants could be a partial remedy, yet the structure must be solid enough to avoid any chance of an explosion bringing flows of water on a molten nuclear core. It is a good for a bad. The alternative is to use dihydrogen tanks all around confinment areas, with the obvious fire risk and the clear target it represents for terrorism, yet that light gas should not totally enter in contact with the core in case the confinment is broken by a blast and the moderating effect on neutrons would be much more limited. In future times all new nuclear plants should be built deep underground and all employees should control the plant from a significant distance, allowing that any explosion of the plant be solely an underground earthquake without any human casualty (and I also personally campaign for the generalization of subcritical designs, cooled with helium, using U238 and its decay products, i.e. mine tailings U234, Th230...). The costs for building underground plants will be very significant, reducing significantly the competitiveness of nuclear energy. States using nuclear energy for e.g. aircraft carriers should look for alternatives, e.g. low energy nuclear reactions and lasers, and the same comment applies for space missions with onboard nuclear reactors.

Bibliography :

Measurement of radioactivity in mount st. helens volcanic ash by x/γ ray spectrometry, M. G. Strauss, I. S. Sherman, R. H. Pehl, 1981, IEEE Transactions in Nuclear Science, 28, 1

« However, there are also abundant data for magma interactions leading to disequilibrium assemblages over a range of time scales leading up to the 1912 eruption. » Hammer et al(2002)


Loig Jezequel
email: loig.jezequel@irisa.fr

Eric Fabre
email: eric.fabre@irisa.fr

Turbo Planning

Keywords: discrete event systems, planning, weighted automata, turbo algorithms, distributed algorithms

The complexity of planning problems comes from the size of the state graph of the systems, which suggests to consider factored (or distributed) solutions. We previously proposed a solution of this kind which revealed to be very efficient on problems where components have a sparse interaction. This work explores a step further in this direction. The idea is to extend the celebrated turbo algorithms, extremely successful to decode large-scale sparse error correcting codes. The paper proposes an adaptation of this technique to the setting of cost-optimal factored planning, and illustrates its behavior on large randomly generated systems.

INTRODUCTION

Planning consists of driving a system from an initial state to a goal state by organizing a set of actions. It corresponds, in fact, to control when all actions are controllable. Traditionally, planning has been solved using "best first" search algorithms such as A * [START_REF] Hart | A formal basis for the heuristic determination of minimum cost paths[END_REF]). However, recently, the intrinsic concurrency of planning problems has been exploited to represent plans (solutions) by partial orders of actions rather than sequences of actions [START_REF] Blum | Fast planning through planning graph analysis[END_REF]). The interest of this approach is to significantly reduce the size of the space to explore for finding a solution. Finally, in the last few years, solutions have been proposed for finding these plans as partial orders of actions in a modular way [START_REF] Amir | Factored planning[END_REF]). This approach is called factored planning. It exploits the fact that in many planning problems some variables are almost independent. This allows one to solve these problems by parts. In the worst case, factored planning has the same complexity as planning. However, it can grant significant efficiency gain: the parts (or components) of a problem are in general exponentially smaller than the original problem.

In [START_REF] Fabre | Distributed optimal planning: an approach by weighted automata calculus[END_REF] we proposed a new approach to factored planning. This approach was based on weighted automata calculus and on a message passing algorithm in networks of such automata. An important innovation of this approach with regards to previous results is that it allows one to perform cost-optimal factored planning. In other words it allows not only to find a plan but to find the best one. In [START_REF] Fabre | Cost-optimal factored planning: Promises and pitfalls[END_REF] we proposed an implementation of our approach and tested it on classical planning benchmarks, showing that this approach is of interest in practice. However, this approach works only for problems where the graph defined by the interactions between components is a tree. This restriction, even if it is natural for propagating constraints, is quite strong. It significantly reduces the number of problems on which our method can be used.

There exists, though, a family of algorithms which give astonishingly good results when dealing with complex interaction graphs (containing cycles) with sparse interaction. These algorithms are mostly known for their use in coding theory [START_REF] Berrou | Near shannon limit error-correcting coding and decoding: Turbo-codes[END_REF]). They are closely related [START_REF] Mceliece | Turbo decoding as an instance of pearl's belief propagation algorithm[END_REF]) to Pearl's belief propagation algorithm [START_REF] Pearl | Reverend bayes on inference engines: A distributed hierarchical approach[END_REF]), which is well-known in the artificial intelligence community. Nowadays, turbo algorithms are used with great success in many areas, but few results exist explain their efficiency, in particular in our setting.

This paper is a study of turbo algorithms in the context of factored planning. Our goal is to show that these algorithms are of interest in the domains of planning and of cost-optimal planning). We recall, however, that planning has been proved to be a PSPACE-complete problem [START_REF] Bylander | Complexity results for planning[END_REF]). So there will necessarily exist cases where turbo algorithms will not be that efficient. We first formally describe the problems we address (Section 2). Then we consider the use of turbo algorithms for solving factored planning problems (Section 3) and their costoptimal counterpart (Section 4). In each case experimental results are provided that demonstrate the interest of investigating the use of turbo algorithms in the domain of planning.

MESSAGE PASSING ALGORITHMS FOR COST-OPTIMAL FACTORED PLANNING

This section describes the problem we address in this paper: factored planning. It also presents a previouslyexplored way to solve this problem using an instance of a message passing algorithm.

Factored planning problems

As its name suggests, a factored planning problem is a planning problem represented by a set of subproblems or factors. If planning problems are represented by finite automata, factored planning problems are represented by networks of automata (that are themselves a synchronous product of automata).

Formally, a planning problem can be modeled as an automaton A = (S, Σ, T, I, F ) where S is a finite set of states, Σ is a finite set of labels (or actions), T ⊆ S ×Σ×S is a transition relation, I ⊆ S is a set of initial states, and F ⊆ S is a set of final states. The elements of T are denoted by t = (t -, σ, t + ). The goal in such a problem is to find an accepted path in A. That is, a sequence of transitions p = t 1 . . . t n such that:

∀1 ≤ i < n, t + i = t - i+1
(it is a path), t - 1 ∈ I, and t + n ∈ F (it is accepted). Such an (accepted) path is associated with an (accepted) word σ(p) = σ 1 . . . σ n . Notice that in the case of a deterministic automaton, any accepted word corresponds to a single accepted path. In the following, the language L(A) of an automaton A is the set of its words.

It is possible to define a notion of composition of such automata, called the synchronous product. Given two automata A 1 and A 2 , their synchronous product A 1 × A 2 is the automaton A such that:

S = S 1 × S 2 , Σ = Σ 1 ∪ Σ 2 , T = T Σ1∩Σ2 ∪ T Σ1\Σ2 ∪ T Σ2\Σ1 , I = I 1 × I 2 , and F = F 1 × F 2 . Where T Σ1∩Σ2 = {((s 1 , s 2 ), σ, (s 1 , s 2 )) : σ ∈ Σ 1 ∩ Σ 2 ∧ (s 1 , σ, s 1 ) ∈ T 1 ∧ (s 2 , σ, s 2 ) ∈ T 2 } is a set of shared transitions, and T Σ1\Σ2 = {((s 1 , s 2 ), σ, (s 1 , s 2 )) : σ ∈ Σ 1 \ Σ 2 ∧(s 1 , σ, s 1 ) ∈ T 1 ∧s 2 ∈ S 2 } (resp. T Σ2\Σ1 symmetrically defined) is a set of private transitions from A 1 (resp. A 2 ).
A factored planning problem is then an automaton A = A 1 × . . . × A n represented by its factors (or components) A 1 . . . A n . The goal is to find a tuple of paths (p 1 , . . . , p n ), one for each component, such that there exists a path p in A with the property that ∀1 ≤ i ≤ n, σ(p) |Σi = σ i (p i ) (where w |Σ represents w with all labels not in Σ removed). If possible, this has clearly to be done without computing A as it is in general exponentially larger than its components.

Any factored planning problem is associated with its interaction graph. This graph is defined as follows: its vertices are the automata that constitute the problem and its edges are such that there is an edge between A i and A j if and only if j = i and Σ i ∩ Σ j = ∅ (in this case A i and A j are said to be neighbors).

It is possible to consider planning problems with costs associated with transitions by a cost function c : T → R + . This allows one to associate costs to paths: the cost of a path p = t 1 . . . t n would be 1≤i≤n c(t i ). Synchronous product is also well-defined for automata with costs: it is sufficient to add costs of shared actions. The goal will be to find paths with minimal cost or tuples of compatible paths minimizing the sum of the costs of the elements of the tuples. In this case, one speaks about cost-optimal planning or cost-optimal factored planning.

Message passing algorithm

Previously [START_REF] Fabre | Distributed optimal planning: an approach by weighted automata calculus[END_REF]), we proposed a modular method for solving factored planning problems efficiently. This method, based on the use of message passing algorithms in networks of automata, along with its limitations, is briefly recalled in the following. The rest of the paper aims at trying to handle these limitations. For simplicity of presentation, from now on automata are considered to be minimal (this allows one to identify automata and languages). Notice that the message passing algorithm exists for weighted automata as well, allowing one to solve cost-optimal factored planning problems. Issues pertaining to minimization of weighted automata are discussed in [START_REF] Fabre | Cost-optimal factored planning: Promises and pitfalls[END_REF].

The message passing algorithm relies on the synchronous product and a second operation, called projection. This operation is defined as follows:

P Σ (A) = MIN(RED Σ\Σ (A)).
Here, MIN is a minimization operation. And RED Σ\Σ is a Σ \ Σ -reduction operation.

The interesting fact relating projection and factored planning is that for A = A 1 × . . . × A n , the projection A i = P Σi (A) contains exactly the paths of A i which are part of a solution to A:

• any path p i of A i is such that a path p exists in A verifying σ(p) |Σi = σ i (p i ), and • any path p of A is such that a path p i exists in A i verifying σ i (p i ) = σ(p) |Σi .
Thus, computing A i is of interest for solving a factored planning problem.

Consider the following algorithm (Algorithm 1):

forall A i do forall j ∈ N (i) do M i,j ← P Σj (A i ) until stabilization do select an M i,j M i,j ← P Σj (A i × Π k∈N (i),k =j M k,i ) forall A i do A i ← A i × Π j∈N (i) M j,i
It takes as input a factored planning problem A given as a set of automata {A 1 , . . . , A n }. When it converges, Algorithm 1 returns a collection of A i which are such that

L(A i ) ⊆ L(A i ) ⊆ L(A i ).
The principle of Algorithm 1 is to propagate some messages (the M i,j ) between the different automata. The message M i,j (sent from i to j) carries information about the constraints of the system on A j via A i . The set N (i) is the set of neighbors of A i : j ∈ N (i) if and only if there is an edge between A i and A j in the interaction graph of the problem.

The convergence of this message passing algorithm is strongly related to the interaction graph of the problems considered. As soon as the interaction graph of a factored planning problem has a tree shape, the message passing algorithm can be proven to converge. Moreover, it can be shown that the A i computed by the algorithm are such that A i = A i ; however, when the interaction graph is not a tree, nothing is ensured.

Solution extraction

If Algorithm 1 converges, one can extract a solution to the factored planning from the A i . When the interaction graph is a tree this is straightforward: it suffices to chose a path p i in any A i = A i . Then a path p j compatible with p i is chosen in each A j such that j ∈ N (i). This can be done by computing p i × A j . Then for each j a path p k compatible with p j is chosen in each A k such that k ∈ N (j) and k = i. This process continues until a path has been found in each component. Recall that for all i, A i = A i and since the interaction graph is a tree, one can ensure that the tuple of paths found is indeed a solution of the factored planning problem under consideration.

When the interaction graph is not a tree, one can not ensure that A i = A i . And, even if this is the case, one can not ensure that a solution will be found using the method described above. Finding a solution may require the use of backtracking. At some step of the extraction, one may be unable to choose a path p j in an A j , compatible with the paths p i1 , . . . , p i k in its neighbors. This would require the modification of at least one of the p i (and potentially the paths that where used for computing p i ).

In the remainder of the paper we (mostly experimentally) examine turbo algorithms, which basically consists of executing Algorithm 1 on problems where the interaction graph is not a tree.

TURBO ALGORITHMS FOR CONSTRAINT SOLVING

The idea when using turbo algorithms for solving planning problems is to abandon the quest for the exact A i = P Σi (A) by applying Algorithm 1 on problems with cycles of interaction. Rather, the objective is to compute a good refinement (in the sense that it contains fewer plans) A i of each A i . Recall that, in all cases, this refinement will be an over-approximation of A i : it will always contain all local plans that are part of a solution of the problem considered.

The interest of computing these refinements -rather than directly searching for a solution from the A i -is to reduce the necessity for backtracking by removing paths that are clearly not part of distributed solutions and by ensuring local consistency. A path in A i will at least be compatible with a path in each of its neighbors.

This section recalls some known results about turbo algorithms for constraint solving, and shows how these results relate to the specific case of planning. Finally our experimental setting is presented and experimental results are given.

Conditions for convergence

In [START_REF] Fabre | Convergence of the turbo algorithm for systems defined by local constraints[END_REF] turbo algorithms are studied in detail for the case of "systems defined by local constraints". Factored planning problems belong to this class of systems. Hence, if a partial order exists on automata that verify the following axioms: ∃I, ∀A, A I,

(1) ∀A 1 , A 2 , A 3 , A 1 A 2 ⇒ A 1 × A 3 A 2 × A 3 , (2) ∀A 1 , A 2 , ∀Σ, A 1 A 2 ⇒ P Σ (A 1 ) P Σ (A 2 ),
(3) then existence of a unique stabilization point for Algorithm 1 on any factored planning problem is ensured (Lemma 7 of [START_REF] Fabre | Convergence of the turbo algorithm for systems defined by local constraints[END_REF]). Axiom 1 ensures the existence of a least informative system, Axiom 2 ensures that synchronous product adds the same amount of information to all systems, and Axiom 3 ensures that projection does not add information. The idea behind these axioms is that applying Algorithm 1 to a factored planning problem will result into messages having a decreasing evolution with respect to .

There is an obvious partial order on automata verifying these axioms:

A 1 A 2 if and only if L(A 1 ) ⊆ L(A 2 ).
If, in addition to the existence of a partial order verifying axioms 1, 2, and 3, the number of possible automata is bounded, convergence of Algorithm 1 is ensured within a finite number of steps on any factored planning problem. Messages decrease for and there is a bounded number of possible messages (Theorem 3 of Fabre ( 2003)).

It is, however, not the case that the number of languages (and thus of automata) over a given alphabet is bounded. Thus, it is not possible to ensure convergence of Algorithm 1 on any factored planning problem. In fact, there are examples of such problems for which convergence is not achieved. Consider, for example, the problem in Figure 1. This problem has no solution: reaching the goal in A 1 implies the firing of an α, which implies the firing of a γ in A 3 and thus a β in A 2 , which enforces the firing of a second α in A 1 and thus a second γ, and so on.

A 1 α β A 2 β γ A 3 γ α
Fig. 1. A factored planning problem such that turbo algorithms do not converge.

Ensuring convergence in all cases

One needs however to decide convergence in all cases. This can be achieved by using a notion of distance d between languages and decide convergence as soon as the messages are stable up to some constant with respect to this distance. In other words, Algorithm 1 will stop as soon as the updating of each message M i,j results in the new message M i,j such that d(M i,j , M i,j ) ≤ , for some small .

Denote by L n (A) = {w ∈ L(A) : |w| = n} the set of words of length n belonging to L(A). A distance which seems reasonable is then the following:

d(A 1 , A 2 ) = ∞ n=0 1 2 n 1 Ln(A1) =Ln(A2)
where 1 L =L = 1 as soon as L = L and 0 in other cases.

Using this distance almost corresponds to looking only at words under a given length for checking convergence. As for any alphabet, the set of words of length smaller than is finite, and any update of messages in Algorithm 1 can only remove words from the considered message, convergence is granted using this distance. Moreover, in any planning problem, there exists a bound (difficult to compute in a modular way) such that if in a component there exists no plan with length smaller than this bound, the problem has no solution. This ensures that convergence with respect to this distance (using a correct bound) is sufficient for deciding the absence of a solution.

Experimental results

In this section we present experimental results obtained by running Algorithm 1 on randomly generated factored planning problems for which interaction graphs have cycles. Our goal is to estimate if the over-approximations of the A i computed by the message passing algorithm are of interest for planning. That is, if they allow us to find solutions with few backtrackings.

In all our experiments we randomly generated some factored planning problems. This is done by choosing a shape for the interaction graph of the problem, and then, for each node of this graph, randomly generating an automaton. These automata have up to 20 states and up to three time as much transitions. Each automaton shares 2 different labels with each of its neighbors in the interaction graph. Once a problem is generated, we check if it is not trivially solvable (that is no solution can be found without backtracking). If it is not trivially solvable we check if it is solvable by searching for a path in the full product A of the component automata. Only problems which are not trivially solvable but still have a solution are considered for our experiments (doing this we select the 5-10% "most complicated" problems among the ones we generate).

Experiment 1: automata on a circle. For our first experiment we chose a configuration of problems know to be favorable for turbo methods: a circle. Its setting is as follows: we consider a circle of n random automata A 0 , . . . , A n-1 such that ∀0 ≤ i < n one has Σ i ∩ Σ (i+1)%n = ∅ (here % stands for modulo) and ∀j, |i -j| > 1 it is the case that Σ i ∩Σ j = ∅. We call an iteration an update of all messages. Iterations are performed following the circle, as depicted in Figure 2 for five automata. Such iterations are repeated until stabilization of the messages.As soon as stabilization is reached an attempt to find a solution is initiated. It is done using the method presented in Section 2.3 without using backtracking. For this reason it is not always the case that a solution will be found. Our goal using this method is to get an idea of the quality of the computed A i : if in many cases a solution is found, it is likely that in practice few backtracking steps will be needed for finding solutions from updated automata. Figure 3 presents results obtained in this setting for circles of 3 to 15 automata. In each case, 50 cycles were considered. For each circle size the percentage of problems for which convergence occurred in 1, 2, or 3 iterations is represented, as well as the percentage of problems in which a solution has been found. We limited our experiments to cycles of 15 automata because of the time consuming method used for selecting problems. We however performed some experiments with larger circles, as Algorithm 1 is able to handle them. The results are presented in Figure 4. For each value of n, 50 cycles were generated but no selection was done among them. Due to the limitations presented above, we cannot give the percentage of cases where a solution was found. Experiment 2: automata on a tetrahedron. We considered problems with 4 automata (generated as described above) for which the interaction graph is a tetrahedron. An iteration is performed by updating each message exactly once. These updates being done along a path in the interaction graph which takes each edge only once in each direction. This is shown on Figure 5. 2:

A 0 A 1 A 2 A 3 A 4 1: M0,1 2: M1,
1: A0 A1 A1 A2 A2 A3 A3 A0 A0 A2 A2 A1 A1 A3 A3 A2 A2 A0 A0 A3 A3 A1 A1 A0
Fig. 5. Automata on a tetrahedron (left) and order of message updates during an iteration (right).

In this setting we obtained the following results for 50 "difficult" test cases (selected as described above): a quick convergence in all cases (2% within 1 iteration, 52% within 2 iterations, 42% within 3 iterations, and 4% within 4 iterations), and a solution found with no backtracking in 85% of the cases. The slightly slower convergence could come from the way iterations are performed, which may be less efficient than in the circles of automata.

All these results lead us to believe that using the message passing algorithm directly on problems for which the interaction graph is not a tree may give good results as soon as the interactions are sufficiently sparse. In particular, searching for solutions in problems updated by Algorithm 1 using backtracking may allow us to find a solution with few backtracks: in our experiments a solution was frequently found with no backtracking at all.

TURBO ALGORITHMS FOR COST-OPTIMAL PLANNING

In this section we propose solutions for applying turbo algorithms to systems with quantitative aspects.The main issue to deal with is that cycles in the interaction graphs usually make cost being counted several times along an execution of Algorithm 1.

Necessity of a normalization

Consider the example in Figure 6. During the updates of messages, the cost of α will grow unbounded. This example shows that in any factored planning problem where costs of solutions are not null, it is hopeless to expect to see any stabilization of messages. This suggests the need for a normalization procedure after any synchronous product, in order to keep costs of a path within a reasonable scope.

A 1 α, 1 β, 0 A 2 β, 0 γ, 0 A 3 α, 0 γ, 0
Fig. 6. An example where stabilization is not possible.

In our setting, one can imagine two ways for normalizing an automaton: either (1) adding a constant to the cost of each path, or (2) dividing the cost of each path by a constant. The main default of ( 2) is that it changes the difference of costs between paths. In our case where costs are additive, it may result in choosing the wrong path. For example, see Figure 7: originally the best solution consisted of firing an α in each automaton, but after dividing the costs of paths in A 1 by c = 3, the best solution is a firing of β in each automaton. By contrast (1) gives small costs to local paths which already have the smallest costs. It concentrates the smallest costs on the paths that are potentially part of a cost-optimal solution. In this way, constraint solving will be helped by costs (paths with very high costs do not have to be considered) and solution extraction should also be improved (the smallest cost path in each automaton will likely be part of a solution, while the random path considered in the previous case has no particular reason of being part of a solution). For these reasons we will use (1) rather than (2).

In the next part we describe concretely how to add a cost to each path of a weighted automaton. We also suggest a possible constant to use for normalization.

A 1 α, 3 β, 6 A 2 α, 3
β, 1 Fig. 7. Dividing costs is not acceptable.

Normalization procedure

The idea of our normalization procedure is to add a constant to the cost of each path of the automaton that is being normalized. A simple way to do this is to add the constant as an cost to each initial state of the considered automaton (a cost which will be added to any path starting from this state). However, this may lead to automata where there is a huge negative initial cost and a huge cost for each path. Thus, we suggest that once the cost has been added to the initial cost it is propagated throughout the automaton, so that costs of transitions do not grow too much. This can be done by pushing this cost towards final states, using algorithms similar to the weight pushing algorithm from [START_REF] Mohri | Handbook of Weighted Automata[END_REF].

A possible normalization constant is the cost of a shortest path minus one. Using this constant ensures that, after each normalization, the cost of the shortest path(s) is one. This has the interest of guaranteeing that a normalized automaton with no negative costs on transitions always exists.

Using this normalization it is very likely that no stabilization will be reached when applying Algorithm 1 to systems with costs. The fact is that normalization (as expected) only stabilizes paths with smallest costs. To decide when the execution of Algorithm 1 should stop on a given problem, a distance, similar to the one proposed in Section 3.2, can be used.

Experimental results

As in the case of factored planning, we generated costoptimal factored planning problems for our experiments. The automata generated have the same characteristics as before and random costs on transitions. We still consider the "difficult" problems only by eliminating the ones with no solutions or trivial solutions.

In all our experiments, the condition for stopping the algorithm is now stability of the cost-optimal solution in each component.In order to select a solution we proceed as follows. First choose a locally cost-optimal solution p 0 in A 0 , and send it to its neighbors as before. Then a locally cost-optimal solution compatible with p 0 is chosen in each neighbor, and propagated as well. This is done until a solution is found in each component, or no compatible solution can be found in a component. We still do not perform backtracking. If a solution is found, one searches for a cost-optimal solution using a centralized approach and compares the costs of the two solutions, in order to estimate the quality of that found with the turbo approach.

Experiment 1: automata on a circle. We look at circles of 3 to 7 components, trying 20 different circles in each case. We do not test as many problems as for the no-costs case because generating difficult problems requires much more time in practice when there is costs (minimization of weighted automata may not terminate, and not minimizing increases a lot the computation time in many cases). We thus focus on the percentage of solution found, and in the cases where a solution is found, on the quality of this solution. Results for this experiment are presented in Figure 8. Among solutions found with turbo methods are represented the amount of solutions which are optimal or of a given quality (x-y% means that the cost of the solution found is between x% (exclusive) and y% greater than the cost of a cost-optimal solution). Experiment 2: automata on a tetrahedron. We also generated problems where automata are one a tetrahedron, as in the case with no costs. The results obtained on 50 such problems are the following: quick convergence speed in almost all cases (except in one experiment, stabilization was always reached after 2 or 3 iterations), and a solution found without backtracking in 68% of our experiments. Among the 34 solutions found, 17 where optimal.

The experimental results obtained here by applying turbo algorithms to factored cost-optimal planning problems for which the interaction graph is not a tree led us to believe that these algorithms are of interest. In particular, we frequently obtained optimal or close-to-optimal solutions in "difficult" problems. Moreover, these solutions were found within times comparable to what we obtained in [START_REF] Fabre | Cost-optimal factored planning: Promises and pitfalls[END_REF] for factored cost-optimal planning problems when the interaction graph was a tree.

CONCLUSION

In this paper we presented very encouraging experimental results on the use of turbo algorithms for factored planning and cost-optimal factored planning. In the case of constraint solving, the algorithms converged in very few iterations on many test cases. Moreover, in almost all cases, solutions have been obtained quickly on networks of up to 50 small automata, which are hardly manageable using a centralized approach. This corresponds to finding a path in an automaton with up to 10 50 states. In the case of cost-optimal planning the algorithms converged in few iterations as well. The solutions obtained were frequently optimal, or close-to-optimal. This can be explained by the fact that the costs of solutions which are not likely to be optimal diverge along execution of the algorithm. One should, however, consider these results carefully as they were obtained using a random problem generator. It may be the case that on real problems, turbo algorithms converge slowly, or do not filter sufficiently many wrong plans to ensure a quick isolation of a solution after convergence. However, we believe that the experimental results presented in this paper show that turbo algorithms may render accessible problems that are otherwise intractable with standard centralized approaches. This should, at least, be a reason for considering these algorithms in the context of planning.

Among possible future work, we would like to understand more precisely the cases in which turbo algorithms are efficient. In particular, it would be useful, given a factored planning problem, to be able to decide whether or not turbo algorithms may reasonably be applied. Interaction graphs where the only cycles are very large are a known example. However, in the case of planning other parameters than the shape of interaction have to be taken into account. A way to measure the quantity of information in an automaton, and, in particular, the quantity of information added to an automaton after having taken its synchronous product with another automaton, would be useful.

Fig. 2 .

 2 Fig. 2. Interaction graph and propagation of messages during one iteration for 5 automata. Numbers on the left of messages indicate the order of updates.

Fig. 3 .

 3 Fig. 3. Experimental results for circles of 3 to 15 automata.

Fig. 4 .

 4 Fig. 4. Experimental results for large circles.

Fig. 8 .

 8 Fig. 8. Results for circles of 3 to 7 weighted automata.


Eric Fabre
email: fabre@irisa.fr

Loig Jezequel
email: loig.jezequel@eleves.bretagne.ens-cachan.fr

On the construction of probabilistic diagnosers ⋆

This paper revisits the notions of observer and diagnoser, and adapts them to probabilistic automata, in a setting of weighted automata computations. In the non stochastic case, observers and diagnosers are obtained by standard elementary steps, as state augmentation, epsilon-reduction and determinization. It is shown that these steps can be adapted to probabilistic automata, and algorithms to perform them efficiently are provided. In particular, the determinization is related to a standard filtering equation that recursively computes the conditional distribution of the current state given past observations. New notions of probabilistic observers and diagnosers are provided and compared to previous constructions, and simpler derivations of the latter are proposed.

INTRODUCTION

Consider a plant modeled as a finite state machine (FSM) or automaton A, with action alphabet Σ. As usual, we assume that the plant is partially observed, i.e. the actions in Σ o ⊆ Σ are observed when they fire, while those in Σ u = Σ \ Σ o fire silently. When A runs, it produces the visible word w ∈ Σ * o formed by concatenating the visible actions that were fired in this run. An observer of A is a deterministic FSM O on alphabet Σ o , and a labelling function φ on its states, satisfying the following property: given any w ∈ Σ * o produced by A, let q be the unique state of O reached by following w, then the label φ(q) ⊆ S gives all possible states where A could be given that w has been observed. In other words, (O, φ) is a state estimator of A under the form of a FSM. A diagnoser is a slightly more subtle notion. Assuming that some transitions of A are faulty and the others are safe, the diagnoser D is another deterministic FSM on alphabet Σ o , with labelling function ψ on its states. On the unique state q of D reached by w ∈ Σ * o , the label ψ(q) now gives a diagnosis value: "fault" if all trajectories of A that could have produced w contain a faulty transition, "safe" if none of them contain a faulty transition, and "uncertain" in the remaining cases. The diagnoser was initially proposed in [START_REF] Sampath | Diagnosability of discrete-event systems[END_REF] as a simple way to test diagnosability, i.e. the fact that a fault occurrence can be detected with a bounded number of observations after it has occurred. More efficient (polynomial) techniques were later proposed for this test in [START_REF] Yoo | Polynomial-time verification of diagnosability of partially observed discreteevent systems[END_REF], based on the so-called twinmachine, and avoiding the expensive construction of a diagnoser (exponential). This paper examines the extension of the notions of observer and diagnoser to probabilistic automata: the objective is thus to build a deterministic FSM that outputs ⋆ This work was partly supported by the European Community's 7th Framework Programme under project DISC (DIstributed Supervisory Control of large plants), Grant Agreement INFSO-ICT-224498. the probability distribution on states, or on the diagnosis value, given any observed sequence w ∈ Σ * o . Of course, for a given w, one could (and should) rather use recursive algorithms to compute these conditional distributions, for example the discrete event system version of the Kalman filter. Nevertheless, as "precompiled" versions of these filters, the probabilistic observers and diagnosers have some theoretical interest. At least for defining notions like probabilistic observability/diagnosability. Their construction sheds some light on techniques for performing elementary transforms on weighted automata, that in turn clarify previous contributions to the topic and allow their generalization to more complex settings.

Previous constructions of probabilistic diagnosers were proposed in [START_REF] Thorsley | Diagnosability of stochastic discrete-event systems[END_REF]; [START_REF] Thorsley | Diagnosability of stochastic discrete-event systems under unreliable observations[END_REF]. They proceed by attaching transition probability matrices to a classical diagnoser. This is a half way to a true probabilistic diagnoser, since conditional distributions still have to be computed for a given w ∈ Σ * o (while in a classical diagnoser, one just reads out the desired value). Our objective here is to show that the elementary steps in the derivation of an ordinary diagnoser can be recast in the setting of probabilistic automata, with minor and meaningful adaptations. In passing, this will clarify previous constructions, and will take us further by precomputing as well the conditional probabilities that can be reached. The probabilistic diagnoser proposed here is thus a standard probabilistic automaton, with transition weights taken in a well defined semiring, and of the same nature as A, at the expense of not always being a finite state machine.

The paper first recalls basic steps on the construction of observers and diagnosers (Section 2), then studies their counterpart for weighted (probabilistic) automata, showing that they lead to the desired conditional distributions (Section 3). The relation to previous works is then detailed in Section 4.

AUTOMATA, OBSERVERS, DIAGNOSERS

This section decomposes the construction of a diagnoser into three elementary steps, and shows that diagnosers and observers are similar objects.

Automata

Our starting point is a non-deterministic automaton A = (S, Σ, I, δ), with S the state set, I ⊆ S possible initial states, action alphabet Σ and transition function δ : S × Σ → 2 S . The latter extends naturally into δ : 2 S × Σ * → 2 S by union on the first variable and by iteration on the second. As usual, the action alphabet is partitioned into Σ = Σ o ⊎ Σ u , observable and unobservable (or silent, or invisible) labels, resp. The transition set of A is denoted as

T = {(s, α, s ′ ) ∈ S × Σ × S : s ′ ∈ δ(s, α)}, and for a transition t = (s, α, s ′ ), we denote s -(t) = s, s + (t) = s ′ , σ(t) = α . A path or trajectory π of A is a sequence of transitions π = t 1 . . . t n such that s -(t 1 ) ∈ I and s + (t i ) = s -(t i+1 ), for 1 ≤ i < n. We adopt notation s -(π) = s -(t 1 ), s + (π) = s + (t n ), σ(π) = σ(t 1 ) . . . σ(t n ) and σ o (π) = Π Σo (σ(π)) where Π Σo is the natural projection of Σ * on Σ * o .
The language of A is L(A) = {σ(π) : π path of A}, and its observable language is L o (A) = Π Σo (L(A)).

Observer

Given Σ = Σ o ⊎ Σ u , an observer of A is obtained by first performing an ǫ-reduction, and then determinizing the result: Obs(A) = Det(Red(A)). ǫ-reduction. The ǫ-reduction A ′ = Red(A) = (S, Σ o , I ′ , δ ′ ) amounts to bypassing all transitions of A labeled by Σ u (or equivalently the generic silent label ǫ). It can be performed either to the left (of visible events), or to the right. Without loss of generality, we present the latter here (see Fig. 1). It is defined by δ ′ (s, α) = δ(s, αΣ * u ) ∪ w∈αΣ * u δ(s, w) where δ(s, w) is the extension by iteration of δ to the sequence of actions w : δ(s, wv) = δ(δ(s, w), v). For the initial states, one has I ′ = δ(I, Σ * u ) ∪ s∈I δ(s, Σ * u ). Observe that the resulting automaton A ′ has the same states as A, operates on the reduced alphabet Σ o , but is generally non-deterministic. By construction, one has

L(A ′ ) = L o (A).
The ǫ-reduction to the right accounts for the fact that after some visible label, system A may evolve silently and thus change state. It is thus suited for state estimation. For diagnosis purposes, the reduction to the left is often preferred, to account for properties of trajectories stopped immediately after the last observable event (see discussion below). Technically, this is a minor difference that does not impact the constructions below. Determinization. The determinization A ′′ = Det(A ′ ) = (Q, Σ o , q 0 , δ ′′ ) of A ′ is obtained by the standard subset construction. One has Q = 2 S , q 0 = I ′ , and the unique new state q ′ = δ ′′ (q, α) is defined as q ′ = δ ′ (q, α) ∪ s∈q δ ′ (s, α). Not all states in 2 S are reachable, so one often directly takes for Q the reachable part of 2 S , starting from q 0 = I ′ and exploring recursively the δ ′ (q, α) for all α ∈ Σ o until no new q is found (Fig. 2). This step is known to have an exponential space complexity, in the worst case. Automaton A ′′ directly yields a state estimator, or an observer of A, by taking φ(q) = q. α α α α q q q' Figure 2. Determinization. The dashed arrow represents a transition not labeled by α.

Diagnoser

For diagnosers, one first associates types to the transitions of A. This is done simply by setting T = T 1 ∪ ... ∪ T K , where each T k gathers transitions of "type k". Notice that the T k need not be disjoint, although the literature generally makes this assumption [START_REF] Cassandras | Introduction to Discrete Event Systems[END_REF]; [START_REF] Sampath | Diagnosability of discrete-event systems[END_REF]): transition types are usually interpreted as distinct failure modes.

To build a diagnoser, the fisrt step consists in augmenting the states of A with some memory µ ⊆ {1, ..., K} to keep track of transition types that have been fired along the trajectory. This yields Ā = ( S = S×2 {1,...,K} , Σ, I ×{∅}, δ) where

(s ′ , µ ′ ) ∈ δ((s, µ), α) ⇔ s ′ ∈ δ(s, α) µ ′ = µ ∪ {k : (s, α, s ′ ) ∈ T k } (1)
Equivalently, this can be seen as computing the synchronous product of A with K elementary memory automata. The memory automaton for T k only has two states 0 and 1, and {1, ..., K} as label set. It is deterministic and complete, and the only transition from 0 to 1 is labeled by k. Transitions of A must of course be relabeled by their type before the synchronous product can be computed, using types as labels. Details are left to the reader.

The second step simply consists in computing an observer for the augmented automaton Ā. Given

w ∈ L o (A) ⊆ Σ * o
and the unique state q reached by w in Obs( Ā), the K

diagnosis functions ψ k , 1 ≤ k ≤ K, are defined by ψ k (q) = T k seen if ∀(s, µ) ∈ q, k ∈ µ T k not seen if ∀(s, µ) ∈ q, k ∈ µ T k uncertain otherwise (2)

Remarks

(1) This construction reveals that building a diagnoser boils down to building an observer. Without loss of generality, one can directly assume that states of A are partitioned into S = S 1 ⊎ ... ⊎ S L with L = 2 K , corresponding to the 2 K possible values of the memory in Ā. The diagnosis then reduces to checking whether all final states compatible with observation w ∈ L o (A) lie into the union of some selected S l .

(2) If one is only interested in diagnosing independently the occurrence of each T k , it is simpler to build K diagnosers, one for each T k , by augmenting A with a simpler binary memory. In terms of complexity, this saves an exponential in K. The diagnoser derived above is much more powerful, since it can also test for the simultaneous presence of several transition types in the trajectories explaining an observed word w.

(3) The ǫ-reduction to the left is often preferred to derive a diagnoser, since one is generally interested in the occurrence or not of some transition type before the last observation of w (and not necessarily in the silent moves that follow w). This is simply a matter of interpretation, since all silent transitions following w may impose that type T k is fired at some point. (4) Some contributions introduced so-called "observation filters" [START_REF] Thorsley | Diagnosability of stochastic discrete-event systems[END_REF]

PROBABILISTIC OBSERVERS

Given Remark (1) above, we limit ourselves to building probabilistic observers, assuming a partition S = S 1 ⊎ ... ⊎ S L on states of the probabilistic automaton A. The goal is to derive another probabilistic automaton able to compute the probability that A reaches state type S l , given some observed word w ∈ L o (A). We show that this can be achieved as above, by extending ǫ-reduction and determinization to probabilistic automata.

Probabilistic automaton

We define it as A = (S, Σ, P 0 , P) where P 0 : S → [0, 1] is an initial probability on states, with initial states I = supp(P 0 ) 1 , and P : S×Σ×S → [0, 1] a transition probability, i.e. ∀s ∈ S, P(s, •, •) is a probability distribution (over labels and next states, given the current state s). Transitions are given by T = supp(P), and the transition function by δ(s, α) = supp(P(s, α, •)). Notice that this definition assumes that A is live, for simplicity. One can generalize the setting to halting systems, by means of a special stopping label in Σ leading to a trap state s t from which no more transition is allowed (P(s t , •, •) = 0). For a path π = t 1 ...t n one has P(π) = P(t 1 )...P(t n ). And the language of A is defined as the formal power series L(A) = w∈Σ * L(A, w)•w where L(A, w) = π, σ(π)=w P 0 (s -(π))P(π).

Probabilistic observer

Given partitions Σ = Σ o ⊎ Σ u and S = S 1 ⊎ ... ⊎ S L , the objective is to derive a deterministic probabilistic

1 supp = support of automaton O = (Q, Σ o , P O 0 , P O )
, and a labeling φ : Q → P(L) of its states, where P(L) is the set of probability distributions over {1, ..., L}. Given w ∈ Σ * o produced by A, and q ∈ Q the unique state reached by w in O, we want φ(q, l) = P(A stops in S l |w was observed).

To specify the meaning of "stops," one needs an appropriate definition of stopping time. We adopt the following : A stops immediately before the production of the next observation, assuming A is Σ o -live i.e. can produce a new observation with positive probability from any reachable state. Specifically, to make this sound as a true stopping time, A stops when it has been decided that the next step would produce an observation, but it is not yet decided which one2 . This definition allows one to consume all silent steps after each observation. It contrasts with the usual choice of stopping immediately after an observable transition, which is slightly easier to handle and thus has often been chosen. It corresponds to the "optimistic" assumption that the system does not evolve silently by itself. Or at least that this evolution is ignored until there is evidence of it. Technically, the only impact is on the ǫreduction below, performed to the right (our case) instead of to the left.

We define the stopped language of A as follows: for a path π we take P s (π) = P 0 (s -(π))P(π)P(s + (π), Σ o , S), where P(s + (π), Σ o , S) is the probability of firing an observable transition from state s + (π). Then L s (A, w) = π, σ(π)=w P s (π) and the stopped language of A is

L s (A) = w∈Σ * L s (A, w) • w. The observable language of A is given by L o (A) = w∈Σ * o L o (A, w) • w where L o (A, w) = v∈Σ * ,ΠΣ o (v)=w L s (A, v).
(3)

ǫ-reduction

We look for a probabilistic automaton

A ′ = Red(A) = (S, Σ o , P ′ 0 , P ′ ) such that L(A ′ ) = L o (A ′ ) = L o (A)
. Structurally, the automaton will be the same as in the non probabilistic case, and obtained by ǫ-reduction to the right. The difficulty lies in the computation of transition probabilities, since an unbounded number of silent steps may be performed until A decides to stop (and then fire a visible transition). This requires to integrate probabilities over a possibly infinite set of silent paths. Equivalently, the sum appearing in Eq. ( 3) above may contain infinitely many terms. This difficulty can be circumvented in at least two simple manners.

Method 1. The first one is through a set of three graph rewriting rules, depicted in Fig. 3. The first and main one (top) removes at once all M silent transitions going out of a given state (b). To an incoming transition t k = (a k , α k , p k , b) one adds direct jumps to states c 1 , ..., c M with respective probabilities p k q 1 , ..., p k q M , all of them carrying the same label α k (possibly ǫ). Then the probability of t k is updated into q = q 1 + ... + q M is the probability to fire an ǫ-transition from b. One may have p ′ k = 0, and in that case t k vanishes. The probabilities of the N non-silent transitions going out of b, if there are any, are renormalized by r ′ n = r n /(1q) (notice that N = 0 when q = 1). The semantics of Rule 1 assumes that all transitions connected to b are processed at once; all transitions in the figure are distinct, but the states a k , b, c m , and d n need not be different. Rule 1 also applies to update the initial probability, assuming for example that a 1 is a dummy initial node assigning to b its initial probability. The second rule (center) simply gathers two transitions that carry the same label into a single one, by summing their probabilities. This situation may occur after the application of Rule 1, and allows one to recover a graph depicting a true probabilistic automaton (technically, our definition does not capture duplicate transitions). Rule 2 applies also to silent transitions, to initial probabilities, and captures the case where a and b are the same state. Finally, Rule 3 (bottom) removes a silent loop of probability p K at some state a, and renormalizes all the outgoing transitions of a, including silent ones, by p ′ i = p i /(1p K ). The Σ o liveness of A guarantees that p K < 1. Again, all outgoing transitions are distinct in the picture, but states b 1 , ..., b K-1 need not. Theorem 1. Let automaton A + be obtained from A by applying some rules of Fig. 3 (and such that Rule 2 is not applicable anymore). Then

p ′ k = p k * (1 -q) where p 2 p 1 1 p K p K-1 p 1 ... a b 1 b K-1 p' K-1 p' 1 ... a α, α, a b p 2 p 1 a b α, + d N a K p K q 1 q M r 1 r N a 1 d 1 c M c 1 p 1 ... ... ... b a 1 a K c 1 c M d 1 d N 1 p' p 1 q 1 1 p M q p q K 1 p K M q p' K r' N
L o (A + ) = L o (A).
Proof. For this proof, we slightly enlarge the definition of a probabilistic automaton and allow the existence of several transitions with the same label between two given states. Denoting by A the initial automaton and by A + the result obtained by firing one of the rules, the objective is to prove the preservation of the stopped language:

L o (A) = L o (A + ).
Clearly, Rule 2 does not change the stopped language of A: for some w ∈ Σ * o , if L o (A, w) needs a path π of A using once the upper arrow (a, α, p 1 , b), it needs as well path π ′ obtained by replacing this transition by (a, α, p 2 , b), and conversely. The overall contribution to L o (A, w) of these two paths will be the same as if the two transitions are merged into (a, α, p 1 + p 2 , b). The same reasoning holds for several consecutive uses of these transitions in a given path π.

We now examine Rule 3. Assume some path π 0 contributing to L o (A, w) crosses state a once and does not use transition t K = (a, ǫ, p K , a): so π 0 = π ′ π ′′ , s + (π ′ ) = a = s -(π ′′ ), where π ′′ contains at least one transition. Then all paths π n = π ′ (t K ) n π ′′ contribute as well to L o (A, w), and their total contribution is P 0 (s -(π ′ ))P(π ′ ) 1 1-pK P(π ′′ )P(s + (π ′′ ), Σ o , S), which is what one would obtain after Rule 3 has been applied, since π ′′ is not empty: the coefficient 1 1-pK is incorporated into the probability of the first transition of π ′′ . If π 0 terminates in state a, that is if π ′′ is empty and π 0 = π ′ , let us assume that there exist visible transitions rooted at a (otherwise the contribution of π 0 to L o (A, w) vanishes). Then P s (π 0 ) = P 0 (s -(π 0 ))P(π 0 )P(a, Σ o , S). Again, the total contribution of the π n = π 0 (t K ) n will be P 0 (s -(π 0 ))P(π 0 ) 1 1-pK P(a, Σ o , S), which is the same before and after the application of Rule 3, since the coefficient 1 1-pK is introduced in the cost of the visible transitions rooted at state a. Again, the same reasoning holds if π 0 crosses several times state a.

Regarding Rule 1, the same reasonings can again be applied to paths crossing state b, and either stopping there or continuing their way.

2 Corollary 2. Starting from A, the rules in Fig. 3 have a unique stationary point A ′ = Red(A), which is the ǫreduction of A.

Proof. When no more rule is applicable, one has the graph of a true probabilistic automaton (Rule 2 does not apply), where no node has silent outgoing transitions. Ignoring probabilities, Rules 1,2,3 clearly compute the ǫ-reduction (to the right) of the non-stochastic case, which gives uniqueness of A ′ . From Theorem 1 one has L o (A ′ ) = L o (A), but since A ′ has no silent transition, one has

L o (A ′ ) = L(A). 2
The ǫ-reduction by this method has complexity O(|S| 3 ).

Method 2.

An alternate method to perform the ǫreduction consists in computing the probabilities P ǫ (s, s ′ ) for any s, s ′ ∈ S, probabilities to reach s ′ from s in A through silent trantisions:

P ǫ (s, s ′ ) = π, σ(π) ∈ Σ * u s -(π) = s, s + (π) = s ′ P(π) (4)
This is actually the difficult step where infinite sums may appear. Automaton A ′ is then obtained by P ′ (s, α, s ′ ) =

s ′′ ∈S P(s, α, s ′′ )P ǫ (s ′′ , s ′ )P(s ′ , Σ o , S), and with a similar equation for the initial probability P ′ 0 . The transition matrix P ǫ can be obtained easily through a Floyd-Warshall procedure. The latter is usually applied to compute minimum distances between all pairs of nodes in a graph. By replacing the (min, +) setting by the (+, * ) setting, one obtains a simple way to integrate probabilities over all paths relating two nodes [START_REF] Mohri | Generic epsilon-removal and input epsilon-renormalization algorithms for weighted transducers[END_REF]; [START_REF] Cortes | Efficient computation of the relative entropy of probabilistic automata[END_REF]). Specifically, denoting S = {s 1 , ..., s N }, one defines P ǫ n (s, s ′ ) as in (4), excepted that the sum is limited to paths that go through states in {s 1 , ..., s n }. So P ǫ 1 (s, s ′ ) = P(s, Σ u , s ′ ). One then has

P ǫ n+1 (s, s ′ ) = P ǫ n (s, s n+1 )P ǫ n (s n+1 , s n+1 ) * P ǫ n (s n+1 , s ′ ) (5) P ǫ n (s n+1 , s n+1 ) * = 1 1 -P ǫ n (s n+1 , s n+1 ) (6)
where ( 6) represents the probability of performing an arbitrary number of loops at s n+1 . Again, the complexity of the ǫ-reduction by this method is O(|S| 3 ).

Determinization

The determinization of a probabilistic automaton A ′ = (S, Σ o , P ′ 0 , P ′ ) can be derived from the standard determinization procedure of weighted automata, that adapts the recursive subset construction given in the previous section [START_REF] Mohri | Weighted automata algorithms[END_REF]; [START_REF] Murer | On the determinization of weighted automata[END_REF]; [START_REF] Buchsbaum | On the determinization of weighted finite automata[END_REF]). One has 1] and can be infinite. P ′′ 0 assigns probability 1 to the unique state q 0 = {(s, P ′ 0 (s)) : s ∈ supp(P ′ 0 )}. Successive states are obtained recursively as follows. Let q = {(s 1 , p 1 ), ..., (s

A ′′ = Det(A ′ ) = (Q, Σ o , P ′′ 0 , P ′′ ) where Q ⊂ 2 S×[0,
M , p M )} ∈ Q and α ∈ Σ o , one has δ ′′ (q, α) = q ′ = {(s ′ 1 , p ′ 1 ), ..., (s ′ N , p ′ N )} iff {s ′ 1 , ..., s ′ N } = δ ′ ({s 1 , ..., s M }, α) = ∅, and for 1 ≤ n ≤ N p ′′ n = 1≤m≤M p m • P ′ (s m , α, s ′ n ) (7) p ′ n = p ′′ n /C where C = 1≤k≤N p ′′ k (8)
P ′′ (q, α, q ′ ) = C (9)
Proposition 3. Let δ ′′ (q 0 , w) = q = {(s 1 , p 1 ), ..., (s M , p M )} ∈ Q in A ′′ for some w ∈ Σ * o , then

p m = P(A ′ is in state s m |w was observed) (10)
Proof. This is obviously true at q o for w = ǫ. Assume it is true at q = δ ′′ (q o , w) and let q ′ = δ ′′ (q, α). Eq. ( 7) is a standard filtering equation for A ′ (based on Bayes rule and the Markov property), so p ′′ n is the probability that A ′ produces α ∈ Σ o and reaches state s n ∈ S given that w was observed. Consequently, C is the probability to fire α given w was observed, and the p ′ n give the conditional probability of the current state of A ′ given the observed sequence wα.

2

As a corollary, if A ′ = Red(A), p m is also the probability that A stops in s m given that w was observed, which almost makes A ′′ an observer. Since one reads in q the conditional distribution on S given some observation w ∈ Σ * o , one easily derives the conditional distribution over the indexes {1, ..., L} corresponding to the partition S = S 1 ⊎ ... ⊎ S L . Notice also that L(A ′′ ) = L(A ′ ) = L o (A).

Example. Figure 4 illustrates the determinization procedure. This simple example seems to suggest that the conditional probabilities appear as extra information attached to a standard (i.e. non-probabilistic) observer. This is not the case, and the determinization procedure may very well not terminate, as revealed by the counter-example in Fig. 5. While for weighted automata taking values in the (R + , min, +) semiring there exist sufficient conditions to guarantee termination (see the twin property in [START_REF] Mohri | Finite-state transducers in language and speech processing[END_REF]), to our knowledge it is still not clear what these conditions could be for probabilistic automata.

...

Probabilistic diagnoser

Using the same technique as in the previous section, a probabilistic diagnoser for A is nothing else than a probabilistic observer on an augmented automaton Ā, that keeps track of which transitions types have been crossed along the run of A :

P((s, µ), α, (s ′ , µ ′ )) = P(s, α, s ′ ) • 1 I µ ′ =µ∪{i:(s,α,s ′ )∈Ti} (11)
From the conditional distribution on states of Ā given some observation w ∈ Σ * o , one then easily derives the conditional distribution on memory values µ, and further on transition classes T k that were crossed by A.

Remark.

case of "observation filters," that randomly modify the labels of Σ produced by transitions of A, can be processed in a similar manner as in Remark 4 of Section 2.3. The slight difference here is that a given observed label β ∈ Λ ∪ {ǫ} may correspond to several underlying transition types T k , that have different probabilities. This case is captured simply as follows: one replaces the deterministic memory represented by the 1 I term in (11) by a "randomized" memory. Specifically, given T = T 1 ∪ ... ∪ T K and for µ ′ = µ ⊎ µ", (11) becomes P((s, µ), β, (s

′ , µ ′ )) = P(s, β, s ′ ) • P( k∈µ" T k ∧ k ∈µ ′ Tk |(s, β, s ′ ))
. The first term is the probability to move from s to s ′ and produce label β, the second one is the (conditional) probability that this move crosses a transition lying in all T k for k ∈ µ", and in none of the T k for k ∈ µ ′ .

RELATION TO PREVIOUS WORK

Alternate probabilistic diagnosers were proposed by [START_REF] Thorsley | Diagnosability of stochastic discrete-event systems[END_REF], as a way to extend the definition of diagnosability to the stochastic case. The latter expresses that, after some failure has occurred, the probability that it is not detected tends to zero as the number of observations increases. The authors also assumed noisy observations, i.e. random observation masks, that randomly turn the label of a transition into some observed one (possibly ǫ, to account for a loss). As we have shown, both random observations and the specific aspects of diagnosis introduce no extra difficulty: the problem is essentially that of building a probabilistic observer, and the diagnosability issue can be expressed as an observability issue. Reformulated as such, the contruction proposed in [START_REF] Thorsley | Diagnosability of stochastic discrete-event systems[END_REF] corresponds to a standard (non-stochastic) observer, enriched with transition probability matrices. Specifically, between states q = {s 1 , ..., s M } and q ′ = {s ′ 1 , ..., s ′ N } of the observer, and for a transition (q, α, q ′ ), the authors compute the M × N transition matrix containing elements P(s ′ n , α|s m ). The latter corresponds to the probability of jumping from s m to s n in A by first crossing some ǫ-transitions and then a visible transition producing α. So this corresponds to an ǫ-reduction to the left, or equivalently to taking as stopping time the firing of a visible transition. Technically, the probabilistic observer obtained in that way can be considered as a weighted automaton where the weight of each transition lies in a semiring of matrices. The advantage of this probabilistic observer is of course its finiteness. The drawback is that processings at this stage are not finished, and the diagnosability/observability test then amounts to exploring the recurrent components of Markov chains defined the above transition probabilities. By contrast, the definition of probabilistic observer provided here is based on standard constructions for the ǫ-reduction and for the determinization of weighted automata. And we have simply emphasized that the recursion computing the determinization was exactly the stochastic filtering equation that one needs in order to compute posterior probabilities on states given observations. The drawback is of course that the construction may not yield a finite structure. It is not clear which definition of a probabilistic observer is best to check observability. Probably a mixture of both. Unless smarter (i.e. less complex) strategies can be found, as it is the case in the non-probabilistic setting.

For technical reasons, [START_REF] Thorsley | Diagnosability of stochastic discrete-event systems[END_REF] was limited to stochastic automata without unobservable cycles (and deterministic once ǫ-transitions are removed). These limitations were relaxed in [START_REF] Thorsley | Diagnosability of stochastic discrete-event systems under unreliable observations[END_REF], although the construction is still hard to follow. The essential difficulty lies in the computation of the ǫ-reduction. The latter is classical for weighted automata. See for example [START_REF] Mohri | Generic epsilon-removal and input epsilon-renormalization algorithms for weighted transducers[END_REF] for a generic form in the case of k-closed semirings, which unfortunately do not capture the case of probabilistic automata. More precise complexity bounds can also be found there. The idea of recycling minimumlength algorithms, that explore all paths, into integration algorithms, that sum quantities over all paths, is however present in [START_REF] Cortes | Efficient computation of the relative entropy of probabilistic automata[END_REF], and adapts well to probabilistic automata. We have also proposed here a somehow simpler graphical way to perform this reduction. The determinization was proposed in [START_REF] Mohri | Finite-state transducers in language and speech processing[END_REF][START_REF] Mohri | Weighted automata algorithms[END_REF], see also [START_REF] Buchsbaum | On the determinization of weighted finite automata[END_REF]; [START_REF] Murer | On the determinization of weighted automata[END_REF]. The finiteness of the resulting automaton, that is the "determinizability," depends very much on the nature of the underlying semiring. In the much studied tropical semiring (R + , min, +), sufficient conditions like the twin property guarantee that the algorithm terminates. However, to our knowledge, sufficient conditions that would be permissive enough are still missing for probabilistic automata.

CONCLUSION

We have shown that the construction of a diagnoser could be split into elementary steps, as the removal of observation filters, the introduction of memory, and then the construction of an observer. The latter being obtained by performing an ǫ-reduction, followed by a determinization. These operations translate almost immediately to the stochastic case, by considering probabilistic automata as weighted automata taking values in a specific semiring. We have shown that the ǫ-reduction could be performed in two ways, and proposed the less frequent reduction to the right, that allows the system to evolve silently after each observation, which was not the case in existing settings. We have proposed an alternate solution to compute the ǫ-reduction, and shown that the standard determinization procedure for weighted automata actually implements a filtering equation. Hopefully, this decomposition will allow one to get a clearer view on where the true difficulties lie in such constructions, and on what extensions can be reached simply. For example, by changing the (R, +, ×) semiring for (R, max, +), one can easily derive another notion of diagnoser that would provide the maximum probability diagnosis given some observed string.

Figure 1 .

 1 Figure 1. Epsilon-reduction to the right. Dashed arrows represent silent (epsilon) transitions.

Figure 3 .

 3 Figure 3. Rewriting rules that perform the ǫ-reduction.Dashed lines represent silent transitions.

Figure 4 .

 4 Figure 4. A probabilistic automaton (left) and its determinized version (right).

Figure 5 .

 5 Figure 5. Determinization may not terminate.

For systems that have final states and stopping probabilities, one can choose to assimilate (or not) the choice to terminate in some state to the production of an observation, for the definition of the stopping time.