Automatic generation of optimal reductions of distributions
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...
Saved in:
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2019
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/106419 http://hdl.handle.net/10220/47943 http://dx.doi.org/10.1109/TAC.2018.2828105 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-106419 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-1064192019-12-06T22:11:17Z Automatic generation of optimal reductions of distributions Masopust, Tomáš Su, Rong Lin, Liyong Wonham, W. Murray School of Electrical and Electronic Engineering Complexity Co-observability DRNTU::Engineering::Electrical and electronic engineering 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 work, we address the problem of generating (optimal) reductions of distributions automatically. A (partial) solution to this problem is provided, which consists of 1) an incremental algorithm for the production of candidate reductions and 2) 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. Accepted version 2019-04-01T02:27:52Z 2019-12-06T22:11:17Z 2019-04-01T02:27:52Z 2019-12-06T22:11:17Z 2018 Journal Article Lin, L., Masopust, T., Wonham, W. M., & Su, R. (2019). Automatic generation of optimal reductions of distributions. IEEE Transactions on Automatic Control, 64(3), 896-911. doi:10.1109/TAC.2018.2828105 0018-9286 https://hdl.handle.net/10356/106419 http://hdl.handle.net/10220/47943 http://dx.doi.org/10.1109/TAC.2018.2828105 en IEEE Transactions on Automatic Control © 2018 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: https://doi.org/10.1109/TAC.2018.2828105 16 p. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
country |
Singapore |
collection |
DR-NTU |
language |
English |
topic |
Complexity Co-observability DRNTU::Engineering::Electrical and electronic engineering |
spellingShingle |
Complexity Co-observability DRNTU::Engineering::Electrical and electronic engineering Masopust, Tomáš Su, Rong Lin, Liyong Wonham, W. Murray Automatic generation of optimal reductions of distributions |
description |
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 work, we address the problem of generating (optimal) reductions of distributions automatically. A (partial) solution to this problem is provided, which consists of 1) an incremental algorithm for the production of candidate reductions and 2) 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. |
author2 |
School of Electrical and Electronic Engineering |
author_facet |
School of Electrical and Electronic Engineering Masopust, Tomáš Su, Rong Lin, Liyong Wonham, W. Murray |
format |
Article |
author |
Masopust, Tomáš Su, Rong Lin, Liyong Wonham, W. Murray |
author_sort |
Masopust, Tomáš |
title |
Automatic generation of optimal reductions of distributions |
title_short |
Automatic generation of optimal reductions of distributions |
title_full |
Automatic generation of optimal reductions of distributions |
title_fullStr |
Automatic generation of optimal reductions of distributions |
title_full_unstemmed |
Automatic generation of optimal reductions of distributions |
title_sort |
automatic generation of optimal reductions of distributions |
publishDate |
2019 |
url |
https://hdl.handle.net/10356/106419 http://hdl.handle.net/10220/47943 http://dx.doi.org/10.1109/TAC.2018.2828105 |
_version_ |
1681047862381641728 |