What Topology tells us about Diagnosability in Partial Order Semantics

Stefan Haar (1, 2)

1 LSV - Laboratoire Spécification et Vérification [Cachan]
2 MEXICO - Modeling and Exploitation of Interaction and Concurrency

From a partial observation of the behaviour of a labeled Discrete Event System, \emph{fault diagnosis} strives to determine whether or not a given ''invisible'' fault event has occurred. The \emph{diagnosability problem} can be stated as follows: does the labeling allow for an outside observer to determine the occurrence of the fault, no later than a bounded number of events after that unobservable occurrence ? When this problem is investigated in the context of concurrent systems, partial order semantics adds to the difficulty of the problem, but also provides a richer and more complex picture of observation and diagnosis. In particular, it is crucial to clarify the intuitive notion of ''\emph{time after fault occurrence}". To this end, we will use a unifying metric framework for event structures, providing a general topological description of diagnosability in both sequential and nonsequential semantics for Petri nets.

Déscription topologique de diagnosticabilité dans des sémantiques séquentielles et non-séquentielles des Réseaux de Petri.

Mots clés: Event structures; Discrete event systems; diagnosis; Petri nets; events; observability; partial order semantics; Event structures.

Domaines: Autre [cs.OH]

Stefan Haar. What Topology tells us about Diagnosability in Partial Order Semantics. [Research Report] RR-7593, INRIA. 2011. ⟨inria-00583666⟩