Searching for Ribbon-Shaped Paths in Fair Transition Systems
Open Access
- 30 March 2022
- book chapter
- Published by Springer Nature
- p. 543-560
Abstract
Diagnosability is a fundamental problem of partial observable systems in safety-critical design. Diagnosability verification checks if the observable part of system is sufficient to detect some faults. A counterexample to diagnosability may consist of infinitely many indistinguishable traces that differ in the occurrence of the fault. When the system under analysis is modeled as a Büchi automaton or finite-state Fair Transition System, this problem reduces to look for ribbon-shaped paths, i.e., fair paths with a loop in the middle.In this paper, we propose to solve the problem by extending the liveness-to-safety approach to look for lasso-shaped paths. The algorithm can be applied to various diagnosability conditions in a uniform way by changing the conditions on the loops. We implemented and evaluated the approach on various diagnosability benchmarks.Keywords
This publication has 16 references indexed in Scilit:
- The nuXmv Symbolic Model Checker2014
- Secure information flow by self-compositionMathematical Structures in Computer Science, 2011
- SAT-Based Model Checking without Unrolling2011
- Liveness Checking as Safety CheckingElectronic Notes in Theoretical Computer Science, 2002
- A polynomial algorithm for testing diagnosability of discrete-event systemsIEEE Transactions on Automatic Control, 2001
- Model Checking2001
- Checking Safety Properties Using Induction and a SAT-Solver2000
- Diagnosability of discrete-event systemsIEEE Transactions on Automatic Control, 1995
- Temporal and Modal Logic1990
- Temporal reasoning under generalized fairness constraints1985