Automatic Generation of Optimal Reductions of Distributions

DOI10.1109/TAC.2018.2828105MaRDI QIDQ4629851zbMATH OpenOpenAlexWikidataFDO

Authors Liyong Lin, Tomáš Masopust, Rong Su, W. Murray Wonham

Publication date 28 March 2019

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.11034

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Discrete event control/observation systems (93C65)

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.

Recommendations

• Probabilistic autoreductions
• Algorithms for the construction of optimizing distributions
• Optimal Quantization for Distribution Synthesis
• Finding Reductions Automatically
• scientific article; zbMATH DE number 4064746
• scientific article; zbMATH DE number 2090703
• Reduction of Distributions: Definitions, Properties, and Applications
• scientific article; zbMATH DE number 418920
• Automatic generation of numerical redundancies for nonlinear constraint solving

Cited in

(3)

• Toward automating the discovery of decreasing measures
• Optimal supervisory control with mean payoff objectives and under partial observation
• Finding Reductions Automatically

This page was built for publication: Automatic Generation of Optimal Reductions of Distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629851)