A polynomial algorithm for testing diagnosability of discrete-event systems
From MaRDI portal
An algorithm for testing the diagnosability of a system presented via a (nondeterministic) finite state automaton \(G=( X, \Sigma , \delta , x_{0})\) (\(X\) is the set of states , \(\Sigma\) is the set of event labels, \(\delta \subseteq X \times \Sigma \times X\) is the transition relation, \(x_{0}\) is the initial state) is proposed under the suppositions that the language generated by \(G\) is live, there does not exist any cycle consisting of unobservable events only, the failures are presented via the failure assignment function \(\psi : \Sigma \to \{ F \} \cup \{ \emptyset \}\) (\(F\) is a finite set of failure types) and any failure event is an unobservable one. The proposed algorithm is based on the design of a machine \(G_{0}\) being a special type of the transitive closure of \(G\), and on the analysis of cycles of the Cartesian product of \(G_{0}\) with itself (with inputs of both copies joined together). Reviewer's comments: 1. The formula in Definition 1 is incorrect, since it is of the form \((\forall\dots)\dots (\forall\dots) \Rightarrow\dots\;\). Since Definition 1 is the basic one for the reviewed paper this blunder makes it difficult to understand the problem that is solved. 2. To make the comparison of the complexity of the proposed algorithm with the results of M. Sampath (published about eight years ago), it would not be out of place to outline briefly the problem he solved and the results he obtained.
Recommendations
Cited in
(84)- Games for synthesis of controllers with partial observation.
- Verification complexity of a class of observational properties for modular discrete events systems
- Predictability of fuzzy discrete event systems
- Empirical studies in the size of diagnosers and verifiers for diagnosability analysis
- Detection and mitigation of classes of attacks in supervisory control systems
- Trajectory detectability of discrete-event systems
- Codiagnosability of discrete event systems revisited: a new necessary and sufficient condition and its applications
- On-the-fly diagnosability analysis of bounded and unbounded labeled Petri nets using verifier nets
- Diagnosability of repairable faults
- Decentralized diagnosis of fuzzy discrete-event systems
- Robust diagnosis of discrete event systems against intermittent loss of observations
- Failure diagnosis for distributed stochastic discrete event systems
- State-based fault diagnosis of discrete-event systems with partially observable outputs
- Intermittent fault diagnosability of discrete event systems: an overview of automaton-based approaches
- Analysis of strong and strong periodic detectability of bounded labeled Petri nets
- Diagnosability verification using LTL model checking
- Robustly distributed diagnosis of discrete-event systems and its application to alipay transaction systems
- Diagnosability of fair transition systems
- Diagnosis and degradation control for probabilistic systems
- Selective monitoring
- Diagnosability analysis of hybrid systems cast in a discrete-event framework
- A tale of two diagnoses in probabilistic systems
- Diagnosis and opacity problems for infinite state systems modeled by recursive tile systems
- Verification of robust diagnosability for partially observed discrete event systems
- Online minimization of sensor activation for supervisory control
- Diagnosability of intermittent sensor faults in discrete event systems
- Active acquisition of information for diagnosis and supervisory control of discrete event systems
- Minimal diagnosis and diagnosability of discrete-event systems modeled by automata
- An improved approach for verifying delayed detectability of discrete-event systems
- Initial-state detectability and initial-state opacity of unambiguous weighted automata
- A general framework for diagnosis of discrete event systems subject to sensor failures
- Marking diagnosability verification in labeled Petri nets
- Diagnosability enforcement in labeled Petri nets using supervisory control
- Decentralized diagnosis of discrete event systems subject to permanent sensor failures
- Disjunctive fault prediction of decentralized discrete event systems: verification, predictor design and K-copredictability
- Diagnosability of discrete event systems subject to permanent sensor failures
- Decentralized fault prognosis of discrete event systems with guaranteed performance bound
- Comments on ``Polynomial time verification of decentralized diagnosability of discrete event systems versus ``Decentralized failure diagnosis of discrete event systems: complexity clarification
- A discrete event systems approach to network fault management: detection and diagnosis of faults
- scientific article; zbMATH DE number 5811833 (Why is no real title available?)
- Comments on "Observability of discrete event dynamic systems" by C. M. Ozveren and A.S. Willsky
- Detection of unmodelled anomalous behaviours via localized controllers for condition systems
- Symbolic Execution Based Model Checking of Open Systems with Unbounded Variables
- A new algorithm for testing diagnosability of fuzzy discrete event systems
- Selective monitoring
- Design of light weight exact discrete event system diagnosers using measurement limitation: case study of electronic fuel injection system
- Computation of minimal diagnosis bases of discrete-event systems using verifiers
- Diagnosability of discrete faults with uncertain observations
- Abstractions Refinement for Hybrid Systems Diagnosability Analysis
- Computation of the delay bounds and synthesis of diagnosers for decentralized diagnosis with conditional decisions
- Diagnosability analysis of patterns on bounded labeled prioritized Petri nets
- Diagnosis of deep discrete-event systems
- A Unified Method to Decentralized State Detection and Fault Diagnosis/prediction of Discrete-event Systems
- Discrete-event systems fault diagnosis
- Generalized detectability for discrete event systems
- Supervisory control to maximize mean time to failure in discrete event systems
- Distributed diagnosis of discrete-event systems under dynamic event observations
- Probabilistic verification of diagnosability for a certain class of timed stochastic systems
- A language-based diagnosis framework for permanent and intermittent faults
- Searching for ribbon-shaped paths in fair transition systems
- On the verification of detectability for timed discrete event systems
- A semi-symbolic diagnoser for fault diagnosis of bounded labeled Petri nets
- Matrix approach to I-detectability of partially observed discrete event systems
- Diagnosis and supervision: model-based approaches
- Diagnosability of labeled \(\mathfrak{D}_{\mathfrak{p}}\)-automata
- Obfuscation mechanism for simultaneous public event information release and private event information hiding in discrete event systems
- Tamper-tolerant diagnosability analysis and tampering detectability in discrete event systems under cost constraints
- Silent closure based pair verifier for fault pattern diagnosis of discrete event systems
- An approximation-based incremental SMT approach for diagnosability analysis of real-time systems
- Computation of minimal event bases that ensure diagnosability
- Multi-decision diagnosis: decentralized architectures cooperating for diagnosing the presence of faults in discrete event systems
- Polynomial verification for safe codiagnosability of decentralized fuzzy discrete-event systems
- Polynomial-time verification of pattern diagnosability for timed discrete event systems
- Reliable decentralized failure diagnosis of discrete event systems using single-level inference
- Diagnosability verification for automata and Petri nets: can we do better?
- Fault diagnosis of discrete event systems based on partially observable events and states
- Accurate approximate diagnosis of (controllable) stochastic systems
- Event counting of partially-observed discrete-event systems with uniformly and nonuniformly bounded diagnosis delays
- Prognosis of \(\omega\)-languages for the diagnosis of *-languages: a topological perspective
- Polynomial-time verification of diagnosability of fuzzy discrete event systems
- Detectability in stochastic discrete event systems
- Codiagnosability and coobservability under dynamic observations: transformation and verification
- Diagnosis of behaviors of interest in partially-observed discrete-event systems
- Abstraction-based failure diagnosis for discrete event systems
This page was built for publication: A polynomial algorithm for testing diagnosability of discrete-event systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4540472)
