Complexity of deciding detectability in discrete event systems
From MaRDI portal
Abstract: Detectability of discrete event systems (DESs) is a question whether the current and subsequent states can be determined based on observations. Shu and Lin designed a polynomial-time algorithm to check strong (periodic) detectability and an exponential-time (polynomial-space) algorithm to check weak (periodic) detectability. Zhang showed that checking weak (periodic) detectability is PSpace-complete. This intractable complexity opens a question whether there are structurally simpler DESs for which the problem is tractable. In this paper, we show that it is not the case by considering DESs represented as deterministic finite automata without non-trivial cycles, which are structurally the simplest deadlock-free DESs. We show that even for such very simple DESs, checking weak (periodic) detectability remains intractable. On the contrary, we show that strong (periodic) detectability of DESs can be efficiently verified on a parallel computer.
Recommendations
- On verification of D-detectability for discrete event systems
- The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete
- Deciding detectability for labeled Petri nets
- Generalized detectability for discrete event systems
- Complexity of detectability, opacity and A-diagnosability for modular discrete event systems
Cites work
- Complexity of Verifying Nonblockingness in Modular Supervisory Control
- Complexity of universality and related problems for partially ordered NFAs
- Computational Complexity
- Delayed Detectability of Discrete Event Systems
- Detectability of Discrete Event Systems
- Finite-automaton aperiodicity is PSPACE-complete
- Generalized detectability for discrete event systems
- Languages of R-trivial monoids
- Nondeterministic Space is Closed under Complementation
- Observability of discrete event dynamic systems
- The method of forced enumeration for nondeterministic automata
- The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete
- Verification complexity of a class of observational properties for modular discrete events systems
Cited in
(17)- On verification of D-detectability for discrete event systems
- Trajectory detectability of discrete-event systems
- Generalized detectability for discrete event systems
- Matrix approach to detectability of discrete event systems
- An improved approach for verifying delayed detectability of discrete-event systems
- Analysis of strong and strong periodic detectability of bounded labeled Petri nets
- On the verification of detectability for timed discrete event systems
- Verification complexity of a class of observational properties for modular discrete events systems
- Detectability of labeled weighted automata over monoids
- scientific article; zbMATH DE number 7350780 (Why is no real title available?)
- On detectability of labeled Petri nets and finite automata
- A Unified Method to Decentralized State Detection and Fault Diagnosis/prediction of Discrete-event Systems
- The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete
- scientific article; zbMATH DE number 166937 (Why is no real title available?)
- Complexity of detectability, opacity and A-diagnosability for modular discrete event systems
- Deciding detectability for labeled Petri nets
- Verification of C-detectability using Petri nets
This page was built for publication: Complexity of deciding detectability in discrete event systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1797011)
