Please use this identifier to cite or link to this item:
Title: Automatic generation of optimal reductions of distributions
Authors: Masopust, Tomáš
Su, Rong
Lin, Liyong
Wonham, W. Murray
Keywords: Complexity
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.
ISSN: 0018-9286
DOI: 10.1109/TAC.2018.2828105
Schools: School of Electrical and Electronic Engineering 
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:
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

Citations 50

Updated on Apr 13, 2024

Web of ScienceTM
Citations 50

Updated on Oct 30, 2023

Page view(s)

Updated on Apr 14, 2024

Download(s) 50

Updated on Apr 14, 2024

Google ScholarTM




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