On verification of D-detectability for discrete event systems

DOI10.1016/J.AUTOMATICA.2021.109884MaRDI QIDQ2065231zbMATH OpenOpenAlexFDO

Authors Jiří Balun, Tomáš Masopust

Publication date 7 January 2022

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.07312

zbMATH Keywords

complexitydetectabilitydiscrete event systemsfinite automatastate estimationverification

Mathematics Subject Classification ID

Observers (93B53) Discrete event control/observation systems (93C65)

Abstract: Detectability has been introduced as a generalization of state-estimation properties of discrete event systems studied in the literature. It asks whether the current and subsequent states of a system can be determined based on observations. Since, in some applications, to exactly determine the current and subsequent states may be too strict, a relaxed notion of D-detectability has been introduced, distinguishing only certain pairs of states rather than all states. Four variants of D-detectability have been defined: strong (periodic) D-detectability and weak (periodic) D-detectability. Deciding weak (periodic) D-detectability is PSpace-complete, while deciding strong (periodic) detectability or strong D-detectability is polynomial (and we show that it is actually NL-complete). However, to the best of our knowledge, it is an open problem whether there exists a polynomial-time algorithm deciding strong periodic D-detectability. We solve this problem by showing that deciding strong periodic D-detectability is a PSpace-complete problem, and hence there is no polynomial-time algorithm unless PSpace = P. We further show that there is no polynomial-time algorithm deciding strong periodic D-detectability even for systems with a single observable event, unless P = NP. Finally, we propose a class of systems for which the problem is tractable.

Recommendations

• Generalized detectability for discrete event systems
• Complexity of deciding detectability in discrete event systems
• Deciding detectability for labeled Petri nets
• The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete
• Detectability in stochastic discrete event systems

Cites work

• Complexity of deciding detectability in discrete event systems
• Complexity of detectability, opacity and A-diagnosability for modular discrete event systems
• Complexity of universality and related problems for partially ordered NFAs
• Complexity of Verifying Nonblockingness in Modular Supervisory Control
• Computational Complexity
• Delayed Detectability of Discrete Event Systems
• Detectability of Discrete Event Systems
• Discrete-Time and Discrete-Space Dynamical Systems
• Estimation and inference in discrete event systems. A model-based approach with finite automata
• Finite-automaton aperiodicity is PSPACE-complete
• Generalized detectability for discrete event systems
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• Languages of R-trivial monoids
• Nondeterministic Space is Closed under Complementation
• Observability of discrete event dynamic systems
• Opacity of discrete event systems and its applications
• Partially ordered automata and piecewise testability
• 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

(14)

• Verification complexity of a class of observational properties for modular discrete events systems
• Trajectory detectability of discrete-event systems
• Detectability of networked discrete event systems
• Complexity of deciding detectability in discrete event systems
• Verification of C-detectability using Petri nets
• Analysis of strong and strong periodic detectability of bounded labeled Petri nets
• On detectability of labeled Petri nets and finite automata
• The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete
• An improved approach for verifying delayed detectability of discrete-event systems
• Generalized detectability for discrete event systems
• Verification of k-Step and Definite Critical Observability in Discrete-Event Systems
• On the verification of detectability for timed discrete event systems
• Detectability in stochastic discrete event systems
• Detectability of discrete event systems with dynamic event observation

This page was built for publication: On verification of D-detectability for discrete event systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2065231)