Lifted Inference Beyond First Order Logic

The thesis focuses on Weighted First-Order Model Counting (WFOMC), which consists in computing the sum of the weights of the models of a First-Order Logic (FOL) sentence over a finite domain. WFOMC is used for probabilistic inference in many Statistical Relational Learning models, and it provides a general framework for enumerative combinatorics. The main problem with WFOMC is that in its general form it is computationally intractable (#P-complete). Therefore, there is significant interest in identifying logical fragments in which it can be performed in polynomial time. Such fragments are said to be domain liftable, and the main one is the two-variable fragment of FOL extended with counting quantifiers (C^2). Nevertheless, there are certain properties such as acyclicity and connectivity that cannot be expressed even in FOL. Addressing this limitation, the thesis shows how to expand the expressive power and domain liftability of C^2 by incorporating external constraints on specific relations: it demonstrates the preservation of domain liftability when restricting one binary relation to be a directed acyclic graph, or a connected undirected graph, or an undirected or directed tree/forest. These different cases are all obtained using a general methodology, which we call counting by splitting. The thesis also highlights how this approach can be used for counting various combinatorial structures, including phylogenetic networks and connected colored graphs. It also uses combinatorial problems to evaluate the algorithms empirically.