Reduction of distributions and its applications
Liyong Lin, Simon Ware, Rong Su, Walter Murray Wonham · 2017
In this work, a notion of reduction of distributions is proposed as a technical tool for improving the complexity of decomposability verification and supporting parallel verification of decomposability, by exploiting the rich structures of distributions. We provide some results that reduce the search space of candidate reductions, as a first step towards efficiently computing optimal reductions. It is then shown that a distribution has a reduction if and only if a particular candidate reduction is indeed a reduction. We then provide a sound substitution-based proof technique that can be used for (automatic) reduction verification. Techniques for refuting candidate reductions are also provided. We then explain an application of the decomposability verification problem in the lower bound proofs for the problem of supervisor decomposition and the problem of existence of decentralized supervisor.