Proof of covering minimality by generalizing the notion of independence
- 作者: Chukhrov I.1
-
隶属关系:
- Institute of Computer Aided Design
- 期: 卷 11, 编号 2 (2017)
- 页面: 193-203
- 栏目: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/212679
- DOI: https://doi.org/10.1134/S1990478917020053
- ID: 212679
如何引用文章
详细
A method is proposed for obtaining lower bounds for the length of the shortest cover and complexity of the minimal cover based on the notion of independent family of sets. For the problem of minimization of Boolean functions, we provide the functions and construct coverings by faces of the set of unit vertices for which the suggested lower bounds can be achieved in the case of five or more variables. The lower bounds, based on independent sets, are unreachable and cannot be used as sufficient conditions for minimality of such functions.
作者简介
I. Chukhrov
Institute of Computer Aided Design
编辑信件的主要联系方式.
Email: chip@icad.org.ru
俄罗斯联邦, Vtoraya Brestskaya ul. 19/18, Moscow, 123056