TY - JOUR
T1 - On implicational bases of closure systems with unique critical sets
AU - Adaricheva, K.
AU - Nation, J. B.
N1 - Funding Information:
The first draft of the paper was written during the first author’s visit to the University of Hawai’i, supported by the AWM-NSF Travel Mentor Grant N 0839954 . The warm and encouraging atmosphere of the Department of Mathematics of UofH is highly appreciated. The work on the paper was also inspired by the communication with V. Duquenne and E. Boros.
Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.
PY - 2014/1/10
Y1 - 2014/1/10
N2 - We present results inspired by the study of closure systems with unique critical sets. Many of these results, however, are of a more general nature. Among those is the statement that every optimum basis of a finite closure system, in D. Maier's sense, is also right-side optimum. New parameters for the size of the binary part of a closure system are established. We introduce the K-basis of a closure system, which is a refinement of the canonical basis of V. Duquenne and J.L. Guigues, and discuss a polynomial algorithm to obtain it. The main part of the paper is devoted to closure systems with unique critical sets, and some subclasses of these where the K-basis is unique. A further refinement 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. Consequently, closure systems without D-cycles can be effectively recognized. While the E-basis achieves an optimum in one of its parts, the optimization of the others is an NP-complete problem.
AB - We present results inspired by the study of closure systems with unique critical sets. Many of these results, however, are of a more general nature. Among those is the statement that every optimum basis of a finite closure system, in D. Maier's sense, is also right-side optimum. New parameters for the size of the binary part of a closure system are established. We introduce the K-basis of a closure system, which is a refinement of the canonical basis of V. Duquenne and J.L. Guigues, and discuss a polynomial algorithm to obtain it. The main part of the paper is devoted to closure systems with unique critical sets, and some subclasses of these where the K-basis is unique. A further refinement 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. Consequently, closure systems without D-cycles can be effectively recognized. While the E-basis achieves an optimum in one of its parts, the optimization of the others is an NP-complete problem.
KW - Acyclic Horn formulas
KW - Canonical basis
KW - Closure systems
KW - Duquenne-Guigues basis
KW - Finite semidistributive lattices
KW - Lattices of closed sets
KW - Lattices without D-cycles
KW - Minimum basis
KW - Optimum basis
KW - Shortest CNF-representation
KW - Shortest DNF-representation
KW - Shortest representations of acyclic hypergraphs
KW - Stem basis
KW - Unit basis
UR - http://www.scopus.com/inward/record.url?scp=84888004041&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84888004041&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2013.08.033
DO - 10.1016/j.dam.2013.08.033
M3 - Article
AN - SCOPUS:84888004041
VL - 162
SP - 51
EP - 69
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
SN - 0166-218X
ER -