The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete

DOI10.1016/J.AUTOMATICA.2017.03.023MaRDI QIDQ2409237zbMATH OpenOpenAlexFDO

Authors Kuize Zhang

Publication date 11 October 2017

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.automatica.2017.03.023

zbMATH Keywords

discrete event systemfinite automatonPSPACE-hardnessweak (periodic) detectability

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Discrete event control/observation systems (93C65)

Recommendations

• Complexity of deciding detectability in discrete event systems
• On verification of D-detectability for discrete event systems
• Deciding detectability for labeled Petri nets
• Generalized detectability for discrete event systems
• On detectability of labeled Petri nets and finite automata

Cites work

• An introduction to formal languages and automata.
• Delayed Detectability of Discrete Event Systems
• Detectability of Discrete Event Systems
• Finite-automaton aperiodicity is PSPACE-complete
• Generalized detectability for discrete event systems
• Observability of discrete event dynamic systems
• Supervisory Control of a Class of Discrete Event Processes

Cited in

(15)

• Complexity of detectability, opacity and A-diagnosability for modular discrete event systems
• Deciding detectability for labeled Petri nets
• Trajectory detectability of 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
• Complexity of deciding detectability in discrete event systems
• On verification of D-detectability for discrete event systems
• A Unified Method to Decentralized State Detection and Fault Diagnosis/prediction of Discrete-event Systems
• Matrix approach to detectability of discrete event systems
• An improved approach for verifying delayed detectability of discrete-event systems
• Initial-state detectability and initial-state opacity of unambiguous weighted automata
• Path detectability verification for time-dependent systems with application to flexible manufacturing systems
• Detectability of labeled weighted automata over monoids
• On the verification of detectability for timed discrete event systems

This page was built for publication: The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete

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