Complexity of detectability, opacity and A-diagnosability for modular discrete event systems

Result code in 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>
Alternative codes found
RIV/61989592:15310/19:73595331
Result on the web
<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>

Result language
angličtina
Original language name
Complexity of detectability, opacity and A-diagnosability for modular discrete event systems
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Similar results(10)