Automatic generation of optimal reductions of distributions
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F19%3A00502163" target="_blank" >RIV/67985840:_____/19:00502163 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1109/TAC.2018.2828105" target="_blank" >http://dx.doi.org/10.1109/TAC.2018.2828105</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/TAC.2018.2828105" target="_blank" >10.1109/TAC.2018.2828105</a>
Alternative languages
Result language
angličtina
Original language name
Automatic generation of optimal reductions of distributions
Original language 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 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
20205 - Automation and control systems
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
IEEE Transactions on Automatic Control
ISSN
0018-9286
e-ISSN
—
Volume of the periodical
64
Issue of the periodical within the volume
3
Country of publishing house
US - UNITED STATES
Number of pages
16
Pages from-to
896-911
UT code for WoS article
000460415600002
EID of the result in the Scopus database
2-s2.0-85045751913