Automatic generation of optimal reductions of distributions

0502163 - MÚ 2019 RIV US eng J - Článek v odborném periodiku
Lin, L. - Masopust, Tomáš - Wonham, W. M. - Su, R.
Automatic generation of optimal reductions of distributions.
IEEE Transactions on Automatic Control. Roč. 64, č. 3 (2019), s. 896-911. ISSN 0018-9286. E-ISSN 1558-2523
Institucionální podpora: RVO:67985840
Klíčová slova: complexity * co-observability * decentralized supervisor synthesis
Obor OECD: Automation and control systems
Impakt faktor: 5.625, rok: 2019
https://ieeexplore.ieee.org/document/8340848

A reduction of a source distribution is a collection of smaller sized distributions that are collectively equivalent to the source distribution with respect to the property of decomposability. That is, an arbitrary language is decomposable with respect to the source distribution if and only if it is decomposable with respect to each smaller sized distribution (in the reduction). The notion of reduction of distributions has previously been proposed to improve the complexity of decomposability verification. In this paper, we address the problem of generating (optimal) reductions of distributions automatically. A (partial) solution to this problem is provided, which consists of an incremental algorithm for the production of candidate reductions and a reduction validation procedure. In the incremental production stage, backtracking is applied whenever a candidate reduction that cannot be validated is produced. A strengthened substitution-based proof technique is used for reduction validation, while a fixed template of candidate counter examples is used for reduction refutation, put together, they constitute our (partial) solution to the reduction verification problem. In addition, we show that a recursive approach for the generation of (small) reductions is easily supported.
Trvalý link: http://hdl.handle.net/11104/0294116