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 Carathéodory number, forbidden pairs and forbidden co-pairs of elements.

Committee:
Kira Adaricheva - Professor - Hoftstra University, Hempstead - Rapporteur
Karel Bertet - Maître de conférence - Université de la Rochelle - Rapporteur
Sergeï Kuznetsov - Professor - Higher School of Economics, Moscou - Rapporteur
Arnaud Mary - Maître de conférence - Université Lyon 1 - Examinateur
Jean-Marc Petit - Professeur des universités - Université Lyon 1 - Examinateur
Lhouari Nourine - Professeur des universités - Université Clermont Auvergne - Directeur