0519325 - MÚ 2021 RIV US eng J - Journal Article
Masopust, Tomáš
Critical observability for automata and Petri nets.
IEEE Transactions on Automatic Control. Roč. 65, č. 1 (2020), s. 341-346. ISSN 0018-9286. E-ISSN 1558-2523
R&D Projects: GA ČR(CZ) GC19-06175J
Institutional support: RVO:67985840
Keywords : critical observability * automata * Petri nets
OECD category: Automation and control systems
Impact factor: 5.792, year: 2020
Method of publishing: Limited access
https://doi.org/10.1109/TAC.2019.2912484

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, (ii) PSPACE-complete for networks of finite automata, 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.
Permanent Link: http://hdl.handle.net/11104/0304320