Duality for the existential fragment of first-order logic on words
Dualité pour le fragment existentiel de la logique du premier ordre sur les mots
Résumé
This thesis fits in the area of research that investigates the application of topological duality methods to problems that appear in theoretical computer science. One of the eventual goals of this approach is to derive results in computational complexity theory by studying appropriate topological objects which characterise them. The link which relates these two seemingly separated fields is logic, more precisely a subdomain of finite model theory known as logic on words. It allows for a description of complexity classes as certain families of languages, possibly non-regular, on a finite alphabet. Very few is known about the duality theory relative to fragments of first-order logic on words which lie outside of the scope of regular languages. The contribution of our work is a detailed study of such a fragment. Fixing an integer k ≥ 1, we consider the Boolean algebra BΣ1[Nu_k ]. It corresponds to the fragment of logic on words consisting in Boolean combinations of sentences defined by using a block of at most k existential quantifiers, letter predicates and uniform numerical predicates of arity l ∈ {1, ..., k}. We give a detailed study of the dual space of this Boolean algebra, for any k ≥ 1, and provide several characterisations of its points. In the particular case where k = 1, we are able to construct a family of ultrafilter equations which characterise the Boolean algebra BΣ1[Nu_1 ].
Cette thèse s’intéresse à l’application de méthodes de dualité topologique à des problèmes de l’informatique théorique. Un des objectifs finaux de cette démarche est l’obtention de résultats en théorie de la complexité, via l’étude d’objets topologiques caractérisant les différentes classes de complexité. La logique est ce qui est à l’interface entre ces deux domaines en apparence très éloignés, plus particulièrement un sous domaine de la théorie des modèles finis : la logique sur les mots. Il est possible de donner une description de certaines classes de complexité comme des familles de langages, potentiellement non réguliers, sur un alphabet fini. Très peu de résultats de dualité sont connus pour les fragments de la logique du premier ordre sur les mots décrits par des langages qui sortent du cadre régulier. Notre contribution est l’étude détaillée d’un tel fragment. Pour un entier k ≥ 1 fixé, nous considérons l’algèbre de Boole BΣ1[Nu_k ]. Celle-ci correspond au fragment de logique sur les mots consistant en les combinaisons Booléennes de propositions définies en utilisant un bloc d’au plus k quantificateurs existentiels, les prédicats sur les lettres et les prédicats numériques uniformes d’arité l ∈ {1, ..., k}. Nous fournissons une étude détaillée de l’espace dual à cette algèbre de Boole, pour tout k ≥ 1, et nous donnons plusieurs caractérisations de ses points. Dans le cas particulier où k = 1, nous sommes capables de construire une famille d’équations ultrafiltre qui caractérise l’algèbre de Boole BΣ1[Nu_1 ].
Origine : Fichiers produits par l'(les) auteur(s)
