On implicational bases of closure systems with unique critical sets

K. Adaricheva, J. B. Nation

    Research output: Contribution to journal › Article

    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

    Fingerprint

    Critical Set
    Closure
    Polynomials
    Computational complexity
    Polynomial Algorithm
    Refinement
    Cycle
    Canonical Basis
    NP-complete problem
    Binary
    Optimization

    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

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

    In: Discrete Applied Mathematics, Vol. 162, 10.01.2014, p. 51-69.

    Research output: Contribution to journal › Article

    Adaricheva, K & Nation, JB 2014, 'On implicational bases of closure systems with unique critical sets', Discrete Applied Mathematics, vol. 162, pp. 51-69. https://doi.org/10.1016/j.dam.2013.08.033
    Adaricheva K, Nation JB. On implicational bases of closure systems with unique critical sets. Discrete Applied Mathematics. 2014 Jan 10;162:51-69. https://doi.org/10.1016/j.dam.2013.08.033
    Adaricheva, K. ; Nation, J. B. / On implicational bases of closure systems with unique critical sets. In: Discrete Applied Mathematics. 2014 ; Vol. 162. pp. 51-69.
    @article{c8f9beed43e74e06a7468319f6ab89d1,
    title = "On implicational bases of closure systems with unique critical sets",
    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.",
    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",
    author = "K. Adaricheva and Nation, {J. B.}",
    year = "2014",
    month = "1",
    day = "10",
    doi = "10.1016/j.dam.2013.08.033",
    language = "English",
    volume = "162",
    pages = "51--69",
    journal = "Discrete Applied Mathematics",
    issn = "0166-218X",
    publisher = "Elsevier",

    }

    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 -

    Access to Document