Critical Observability for Automata and Petri Nets

DOI10.1109/TAC.2019.2912484MaRDI QIDQ5211340zbMATH OpenOpenAlexWikidataFDO

Authors Tomáš Masopust

Publication date 28 January 2020

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Observability (93B07) Discrete event control/observation systems (93C65)

Abstract: Critical observability is a property of cyber-physical systems to detect whether the current state belongs to a set of critical states. In safety-critical applications, critical states model operations that may be unsafe or of a particular interest. De Santis et al. introduced critical observability for linear switching systems, and Pola et al. adapted it for discrete-event systems, focusing on algorithmic complexity. We study the computational complexity of deciding critical observability for systems modeled as (networks of) finite-state automata and Petri nets. We show that deciding critical observability is (i) NL-complete for finite automata, that is, it is efficiently verifiable on parallel computers, (ii) PSPACE-complete for networks of finite automata, that is, it is very unlikely solvable in polynomial time, and (iii) undecidable for labeled Petri nets, but becoming decidable if the set of critical states (markings) is finite or co-finite, in which case the problem is as hard as the non-reachability problem for Petri nets.

Recommendations

• Continuous Petri nets: observability and diagnosis
• Observable liveness of Petri nets
• On reachability in autonomous continuous Petri net systems
• Observability of continuous Petri nets with infinite server semantics
• On observability of automata networks via computational algebra
• Observability analysis of bounded Petri net systems via a matrix approach
• On detectability of labeled Petri nets and finite automata
• scientific article; zbMATH DE number 6936858
• Observability of place/transition nets
• Structural Liveness of Immediate Observation Petri Nets

Cited in

(3)

• scientific article; zbMATH DE number 6027053 (Why is no real title available?)
• Optimal control strategy for k-level opaque systems based on the optimization method of multi-selection problems at each stage
• Detectability, opacity and declassification of timed DESs with release observation mechanism

This page was built for publication: Critical Observability for Automata and Petri Nets

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