Complexity of deciding detectability in discrete event systems

0488849 - MÚ 2019 RIV NL eng J - Článek v odborném periodiku
Masopust, Tomáš
Complexity of deciding detectability in discrete event systems.
Automatica. Roč. 93, July (2018), s. 257-261. ISSN 0005-1098. E-ISSN 1873-2836
Institucionální podpora: RVO:67985840
Klíčová slova: discrete event systems * finite automata * detectability
Obor OECD: Automation and control systems
Impakt faktor: 6.355, rok: 2018
https://www.sciencedirect.com/science/article/pii/S0005109818301730

Detectability of discrete event systems (DESs) is a question whether the current and subsequent states can be determined based on observations. Shu and Lin designed a polynomial-time algorithm to check strong (periodic) detectability and an exponential-time (polynomial-space) algorithm to check weak (periodic) detectability. Zhang showed that checking weak (periodic) detectability is PSpace-complete. This intractable complexity opens a question whether there are structurally simpler DESs for which the problem is tractable. In this paper, we show that it is not the case by considering DESs represented as deterministic finite automata without non-trivial cycles, which are structurally the simplest deadlock-free DESs. We show that even for such very simple DESs, checking weak (periodic) detectability remains intractable. On the contrary, we show that strong (periodic) detectability of DESs can be efficiently verified on a parallel computer.
Trvalý link: http://hdl.handle.net/11104/0283371