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.
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.