On implicational bases of closure systems with unique critical sets

• Published in: Discrete Applied Mathematics 2014-01, Vol.162, p.51-69
• Main Authors: Adaricheva, K., Nation, J.B.
• Format: Article
• Language: English
• Subjects: Acyclic Horn formulas; Algorithms; Binary systems; Canonical basis; Closure systems; Closures; Duquenne–Guigues basis; Finite semidistributive lattices; Lattices of closed sets; Lattices without [formula omitted]-cycles; Mathematical analysis; Minimum basis; Optimization; Optimum basis; Polynomials; Shortest CNF-representation; Shortest DNF-representation; Shortest representations of acyclic hypergraphs; Stem basis; Unit basis
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2013.08.033

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.