Skip to Main content Skip to Navigation
Conference papers

Manifestability Verification of Discrete Event Systems

Lina Ye 1, 2, 3 Philippe Dague 4, 3 Lulu He 2
2 VALS - LRI - Vérification d'Algorithmes, Langages et Systèmes (LRI)
LRI - Laboratoire de Recherche en Informatique
3 MEXICO - Modeling and Exploitation of Interaction and Concurrency
Inria Saclay - Ile de France, LSV - Laboratoire Spécification et Vérification
Abstract : Fault diagnosis is a crucial and challenging task in the automatic control of complex systems, whose efficiency depends on the diagnosability property of a system, allowing one to determine with certainty whether a given fault has effectively occurred based on the available observations. However, this is a quite strong property that generally requires a high number of sensors. Consequently, it is not rare that developing a diagnosable systemis too expensive. In this paper, we analyze a new system property called manifestability, that represents the weakest requirement on observations for having a chance to identify on line fault occurrences and can be verified at design stage. Intuitively, this property makes sure that a faulty system has at least one future behavior after fault occurrence observably distinguishable from all normal behaviors. Then, we propose an algorithm with PSPACE complexity to automatically verify it for finite automata. Furthermore, we prove that the problem of manifestability verification itselfis PSPACE-complete. The experimental results show the feasibility of our algorithm from a practical point of view. Then, we extend our approachto real-time systems modeled by timed automata.To do this, we redefine manifestability by taking into account time constraints and we prove that this problem for timed automata is undecidable.
Complete list of metadata
Contributor : Philippe Dague Connect in order to contact the contributor
Submitted on : Monday, June 7, 2021 - 4:32:18 PM
Last modification on : Tuesday, November 30, 2021 - 7:54:46 PM
Long-term archiving on: : Wednesday, September 8, 2021 - 7:20:43 PM


Files produced by the author(s)


  • HAL Id : hal-02425146, version 1


Lina Ye, Philippe Dague, Lulu He. Manifestability Verification of Discrete Event Systems. DX 2019 - 30th International Workshop on Principles of Diagnosis, Nov 2019, Klagenfurt, Austria. pp.1-9. ⟨hal-02425146⟩



Record views


Files downloads