On verification of strong periodic D-detectability for discrete event systems

0537723 - MÚ 2022 RIV NL eng C - Konferenční příspěvek (zahraniční konf.)
Balun, J. - Masopust, Tomáš
On verification of strong periodic D-detectability for discrete event systems.
IFAC-PapersOnLine. Volume 53, Issue 4 - Proceedings of 15th IFAC Workshop on Discrete Event Systems WODES 2020. Amsterdam: Elsevier, 2020 - (Basilio, J.), s. 263-268. ISSN 2405-8963.
[15th Workshop on Discrete Event Systems (WODES 2020). Rio de Janeiro (BR), 11.11.2020-13.11.2020]
Grant CEP: GA ČR(CZ) GC19-06175J
Institucionální podpora: RVO:67985840
Klíčová slova: discrete event systems * finite-state automata * detectability * verification * complexity
Obor OECD: Automation and control systems
https://doi.org/10.1016/j.ifacol.2021.04.025

Detectability of discrete event systems was introduced as a generalization of other state-estimation properties. It asks whether the current and subsequent states of a system can be determined based on observations. To exactly determine the current and subsequent states may be too strict, therefore a relaxed notion of D-detectability was introduced. Four variants of D-detectability were defined: strong (periodic) D-detectability and weak (periodic) D-detectability. While deciding weak (periodic) D-detectability follows from deciding detectability (is PSpace-complete) and there is a polynomial-time algorithm deciding strong D-detectability, the case of strong periodic D-detectability is open. We answer this question by showing that there is no polynomial-time algorithm, unless P=PSPACE. There is no such algorithm even for systems having only a single observable event, unless P = NP.
Trvalý link: http://hdl.handle.net/11104/0315577