Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/106419
Title: Automatic generation of optimal reductions of distributions
Authors: Masopust, Tomáš
Su, Rong
Lin, Liyong
Wonham, W. Murray
Keywords: Complexity
Co-observability
DRNTU::Engineering::Electrical and electronic engineering
Issue Date: 2018
Source: 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
Series/Report no.: IEEE Transactions on Automatic Control
Abstract: 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.
URI: https://hdl.handle.net/10356/106419
http://hdl.handle.net/10220/47943
ISSN: 0018-9286
DOI: 10.1109/TAC.2018.2828105
Rights: © 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
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:EEE Journal Articles

Files in This Item:
File Description SizeFormat 
automaticgeneration_liyong.pdf2.22 MBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 5

1
checked on Sep 3, 2020

WEB OF SCIENCETM
Citations 50

1
checked on Oct 18, 2020

Page view(s) 50

51
checked on Oct 21, 2020

Download(s) 50

22
checked on Oct 21, 2020

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.