Basis Coverability Graph for Partially Observable Petri Nets with Application to Diagnosability Analysis

Engel Lefaucheux (1, 2) , Alessandro Giua (3, 4) , Carla Seatzu (4)

1 LSV - Laboratoire Spécification et Vérification [Cachan]
2 SUMO - SUpervision of large MOdular and distributed systems
3 LSIS - Laboratoire des Sciences de l'Information et des Systèmes
4 DIEE - Department of Electrical and Electronic Engineering [University of Cagliari]

Petri nets have been proposed as a fundamental model for discrete-event systems in a wide variety of applications and have been an asset to reduce the computational complexity involved in solving a series of problems, such as control, state estimation, fault diagnosis, etc. Many of those problems require an analysis of the reachability graph of the Petri net. The basis reachability graph is a condensed version of the reachability graph that was introduced to efficiently solve problems linked to partial observation. It was in particular used for diagnosis which consists in deciding whether some fault events occurred or not in the system, given partial observations on the run of the system. However this method is, with very specific exceptions, limited to bounded Petri nets. In this paper, we introduce the notion of basis coverability graph to remove this requirement. We then establish the relationship between the coverability graph and the basis coverability graph. Finally, we focus on the diagnosability and stochastic diagnosability problems: we show how the basis coverability graph can be used to get efficient algorithms when such problems are decidable.

Domaines: Informatique [cs]

Engel Lefaucheux, Alessandro Giua, Carla Seatzu. Basis Coverability Graph for Partially Observable Petri Nets with Application to Diagnosability Analysis. Petri Nets 2018 - International Conference on Applications and Theory of Petri Nets and Concurrency, Jun 2018, Bratislava, Slovakia. pp.164-183, ⟨10.1007/978-3-319-91268-4_9⟩. ⟨hal-01882129⟩