My PhD has been supervised by Prof. Lhouari Nourine. It has been conducted at the LIMOS (UCA, Clermont-Ferrand, France). The manuscript can be found here and a handout of the slides here.

Abstract

Knowledge Space Theory (KST) is a field of mathematical psychology which aims to assess and represent students knowledge. Its core structures, knowledge spaces, are equivalent to closure systems (or lattices). Apart from KST, closure systems are used in numerous fields of computer science such as Formal Concept Analysis, propositional logic, database theory, combinatorial optimization or argumentation theory for instance. Because of their size, closure systems are often encoded with compact representations such as implications or meet-irreducible elements. In this thesis, we focus on two problems regarding closure systems and their representations.

We begin with the problem of translating between the two representations of a closure system. This famous open problem generalizes hypergraph dualization. Our approach here is to hierarchically decompose a set of implications with partitioning operations called (acyclic) splits. We deduce a recursive characterization of the meet-irreducible elements of the associated closure system. As a consequence, we obtain new types of closure systems for which the translation can be done in output-quasipolynomial time using hypergraph dualization.

Next, we study forbidden sets in closure systems. Here, the tasks we handle is the enumeration of the closed sets (the sets in the closure system) that are admissible and preferred (minimal or maximal admissible) with respect to a family of forbidden sets. With the help of dualization in lattices, we obtain several intractability results. On the positive side, we derive output-polynomial time algorithms under various restrictions concerning the Caratheodory number, forbidden pairs and forbidden co-pairs of elements.

Publications

  • Translating between the representations of a ranked convex geometry.
    O. Defrain, L. Nourine and S. Vilmin.
    To appear in Discrete Mathematics [arXiv]
  • Towards declarative comparabilities: application to functional dependencies.
    L. Nourine, J.-M Petit, and S. Vilmin.
    Submitted [arXiv]

Conferences

  • Enumerating maximal consistent closed sets in closure systems.
    L. Nourine and S. Vilmin.
    Upcoming in ICFCA 2021 [arXiv]
  • Hierarchical decompositions of dihypergraphs.
    L. Nourine, and S. Vilmin.
    In ICTCS 2020 (CEUR, Vol-2756, pages 158-171) [arXiv]

Workshop & Seminars

  • Dihypergraph decomposition: application to closure system representations.
    WEPA 2020 (December), FCA4AI 2020 (August, CEUR, Vol-2729, pages 31-44) [CEUR]
    Online.
  • Translating between the representations of a ranked convex geometry.
    WEPA 2019 (October).
    Awaji Island, Japan
  • Translating between the representations of a lattice.
    Séminaire des doctorants.
    LIMOS, Clermont-Ferrand, France, June 2019.
  • Introduction to lattice theory.
    Séminaire AlCoLoCo.
    LIMOS, Clermont-Ferrand, France, November 2018.
  • Horn minimization.
    FCA4KD (Formal Concept Analysis for Knowledge Discovery).
    HSE, Moscow, Russia, June 2018.