On implicational bases of closure system with unique critical sets
| dc.contributor.author | Adaricheva, Kira | |
| dc.contributor.author | Nation, J.B. | |
| dc.date.accessioned | 2016-02-09T09:08:20Z | |
| dc.date.available | 2016-02-09T09:08:20Z | |
| dc.date.issued | 2013 | |
| dc.description.abstract | We show that every optimum basis of a nite closure system, in D. Maier's sense, is also right-side optimum, which is a parameter of a minimum CNF representation of a Horn Boolean function. New parameters for the size of the binary part are also established. We introduce the K-basis of a general closure system, which is a re nement of the canonical basis of V. Duquenne and J.L. Guigues, and discuss a polynomial algorithm to obtain it. We study closure systems with unique critical sets, and some subclasses of these where the K-basis is unique. A further re nement in the form of the E-basis is possible for closure systems without D-cycles. There is a polynomial algorithm to recognize the D-relation from a K-basis. Thus, closure systems without D-cycles can be e ectively recognized. While the E-basis achieves an optimum in one of its parts, the optimization of the others is an NP-complete problem | ru_RU |
| dc.identifier.citation | Adaricheva Kira, Nation J.B.; 2013; On implicational bases of closure system with unique critical sets; arXiv.org | ru_RU |
| dc.identifier.uri | http://nur.nu.edu.kz/handle/123456789/1209 | |
| dc.language.iso | en | ru_RU |
| dc.rights | Attribution-NonCommercial-ShareAlike 3.0 United States | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-sa/3.0/us/ | * |
| dc.subject | Research Subject Categories::MATHEMATICS | ru_RU |
| dc.subject | finite closure system | ru_RU |
| dc.title | On implicational bases of closure system with unique critical sets | ru_RU |
| dc.type | Article | ru_RU |