### Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 51-69 |

Number of pages | 19 |

Journal | Discrete Applied Mathematics |

Volume | 162 |

DOIs | |

Publication status | Published - Jan 10 2014 |

### Fingerprint

### Keywords

- Acyclic Horn formulas
- Canonical basis
- Closure systems
- Duquenne-Guigues basis
- Finite semidistributive lattices
- Lattices of closed sets
- Lattices without D-cycles
- Minimum basis
- Optimum basis
- Shortest CNF-representation
- Shortest DNF-representation
- Shortest representations of acyclic hypergraphs
- Stem basis
- Unit basis

### ASJC Scopus subject areas

- Applied Mathematics
- Discrete Mathematics and Combinatorics

### Cite this

*Discrete Applied Mathematics*,

*162*, 51-69. https://doi.org/10.1016/j.dam.2013.08.033

**On implicational bases of closure systems with unique critical sets.** / Adaricheva, K.; Nation, J. B.

Research output: Contribution to journal › Article

*Discrete Applied Mathematics*, vol. 162, pp. 51-69. https://doi.org/10.1016/j.dam.2013.08.033

}

TY - JOUR

T1 - On implicational bases of closure systems with unique critical sets

AU - Adaricheva, K.

AU - Nation, J. B.

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 -