Acyclicité des hypergraphes et liens avec la logique sur les structures relationnelles finies
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
This thesis contains contributions to hypergraph theory and finite model theory, with hypergraph acyclicity as the central notion. We consider it first from a structural point of view. We introduce the notion of join tree with disjoint branches and we show that it enables to characterize gamma-acyclicity. We also obtain characterizations of gamma and beta-acyclicity in terms of elimination rules. Then we are concerned with definability and complexity issues inspired by rule-based characterizations. If f(xl,. . . ,xd) is a first-order formula, the property defined by fin terms of "destructive" rules corresponds to the structures from which we can remove step by step elements el,. . . , ed satisfying f(el,. . . ,ed) until we obtain the empty structure. Depending on d and the quantifiers used in f, we obtain a classification between the cases that are able to express NP-complete properties and those expressing only PTIME properties. Finally, we are interested in the extension preservation theorem on classes of acyclic finite structures. Atserias, Dawar and Grohe hâve proved in 2005 that this theorem is satisfîed for classes of finite structures of arity at most 2 and acyclic in the graph sense. We estimate precisely how much this theorem can be generalized for arbitrary arities and acyclicity notions of hypergraphs : we prove that it is satisfied on every class of finite structures with a gamma-acyclic k-quotient which is closed by substructure and disjoint union, and that it is false in the beta-acyclic case.
Abstract FR:
Cette thèse contient des contributions à la théorie des hypergraphes et à la théorie des modèles finis, avec pour notion centrale l'acyclicité des hypergraphes. On la considère tout d'abord d'un point de vue structurel. On introduit la notion d'arbre de jointure à branches disjointes et on montre qu'elle permet de caractériser la gamma-acyclicité. On obtient aussi des caractérisations de la gamma et de la bêta-acyclicité en termes de règles d'élimination. On se penche alors sur des questions de définissabilité et complexité inspirées des caractérisations par règles. Etant donnée une formule du premier ordre f(xl,. . . ,xd), la propriété définie en termes de règles dites "destructrices" à partir de f correspond aux structures pour lesquelles on peut retirer pas à pas des éléments el,. . . , ed satisfaisant f(el,. . . ,ed) jusqu'à obtenir la structure vide. En fonction de d et des quantificateurs utilisés dans f, on obtient une classification entre les cas capables d'exprimer des propriétés NP-complètes et ceux n'exprimant que des propriétés dans PTIME. Pour finir, on s'intéresse au théorème de préservation par extension pour des classes de structures finies acycliques. Atserias, Dawar et Grohe ont montré en 2005 que ce théorème est satisfait pour des classes de structures finies d'arité au plus 2 et acycliques au sens des graphes. On évalue de façon précise à quel point ce théorème peut être généralisé pour des arités quelconques et les notions d'acyclicité des hypergraphes : on prouve qu'il est satisfait sur toute classe de structures finies à k-quotient gamma-acyclique qui est close par sous-structure et union disjointe, et que ceci est faux dans le cas bêta-acyclique.