Complexity of deciding detectability in discrete event systems

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Complexity of deciding detectability in discrete event systems

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Complexity of deciding detectability in discrete event systems

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

20205 - Automation and control systems

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Automatica

ISSN

0005-1098

e-ISSN

—

Svazek periodika

93

Číslo periodika v rámci svazku

July

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

5

Strana od-do

257-261

Kód UT WoS článku

000436916200027

EID výsledku v databázi Scopus

2-s2.0-85044569159