Complexity of detectability, opacity and A-diagnosability for modular discrete event systems
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F19%3A00501542" target="_blank" >RIV/67985840:_____/19:00501542 - isvavai.cz</a>
Nalezeny alternativní kódy
RIV/61989592:15310/19:73595331
Výsledek na webu
<a href="http://dx.doi.org/10.1016/j.automatica.2018.12.019" target="_blank" >http://dx.doi.org/10.1016/j.automatica.2018.12.019</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.automatica.2018.12.019" target="_blank" >10.1016/j.automatica.2018.12.019</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Complexity of detectability, opacity and A-diagnosability for modular discrete event systems
Popis výsledku v původním jazyce
Modular discrete event systems are modeled as a parallel composition of finite automata. While deciding weak detectability, opacity, and A-diagnosability for monolithic systems is PSPACE-complete, the complexity for modular systems is unknown. We show that for modular systems the problems are EXPSPACE-complete, and hence there is neither a polynomial-time nor a polynomial-space algorithm solving them. While the upper bound is a natural modification of the PSPACE algorithms for monolithic systems, the lower bound requires a novel and nontrivial construction. We further discuss a case where the complexity drops to PSPACE-complete.
Název v anglickém jazyce
Complexity of detectability, opacity and A-diagnosability for modular discrete event systems
Popis výsledku anglicky
Modular discrete event systems are modeled as a parallel composition of finite automata. While deciding weak detectability, opacity, and A-diagnosability for monolithic systems is PSPACE-complete, the complexity for modular systems is unknown. We show that for modular systems the problems are EXPSPACE-complete, and hence there is neither a polynomial-time nor a polynomial-space algorithm solving them. While the upper bound is a natural modification of the PSPACE algorithms for monolithic systems, the lower bound requires a novel and nontrivial construction. We further discuss a case where the complexity drops to PSPACE-complete.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2019
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ů
Údaje specifické pro druh výsledku
Název periodika
Automatica
ISSN
0005-1098
e-ISSN
—
Svazek periodika
101
Číslo periodika v rámci svazku
March
Stát vydavatele periodika
NL - Nizozemsko
Počet stran výsledku
6
Strana od-do
290-295
Kód UT WoS článku
000458941700033
EID výsledku v databázi Scopus
2-s2.0-85059456260