Complexity of deciding detectability in discrete event systems
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F18%3A00488849" target="_blank" >RIV/67985840:_____/18:00488849 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.automatica.2018.03.077" target="_blank" >http://dx.doi.org/10.1016/j.automatica.2018.03.077</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.automatica.2018.03.077" target="_blank" >10.1016/j.automatica.2018.03.077</a>
Alternative languages
Result language
angličtina
Original language name
Complexity of deciding detectability in discrete event systems
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
20205 - Automation and control systems
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Automatica
ISSN
0005-1098
e-ISSN
—
Volume of the periodical
93
Issue of the periodical within the volume
July
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
5
Pages from-to
257-261
UT code for WoS article
000436916200027
EID of the result in the Scopus database
2-s2.0-85044569159