화학공학소재연구정보센터
Automatica, Vol.101, 290-295, 2019
Complexity of detectability, opacity and A-diagnosability for modular discrete event systems
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. (C) 2018 Elsevier Ltd. All rights reserved.