On implicational bases of closure systems with unique critical sets

K. Adaricheva, J. B. Nation

Research output: Contribution to journalArticle

9 Citations (Scopus)

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 languageEnglish
Pages (from-to)51-69
Number of pages19
JournalDiscrete Applied Mathematics
Volume162
DOIs
Publication statusPublished - Jan 10 2014

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

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On implicational bases of closure systems with unique critical sets'. Together they form a unique fingerprint.

  • Cite this