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

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-01882129
Contributor : Engel Lefaucheux <>
Submitted on : Wednesday, September 26, 2018 - 3:52:32 PM
Last modification on : Tuesday, July 9, 2019 - 4:48:39 PM
Long-term archiving on : Thursday, December 27, 2018 - 6:35:39 PM

File

covgraph.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

518

Files downloads

112