Les langages réguliers, langages calculés par automates finis, sont parmi les objets les plus simples de l'informatique théorique. Cette thèse étudie plusieurs modèles de calculs: le calcul parallèle avec les circuits booléens, le traitement en flot de documents structurés, et la maintenance d'information sur une structure soumise à des mises à jour incrémentales. Pour ce dernier modèle, les structures auxiliaires sont soit stockées en RAM, soit représentées par des bases de données mises à jour par des formules logiques. Cette thèse étudie les ressources nécessaires pour calculer des classes de langages réguliers dans chacun de ces modèles. Les méthodes employées exploitent l'interaction entre algèbre, logique et combinatoire, en mettant notamment à profit la théorie des semigroupes finis. Cette approche de la complexité s'est notamment montrée extrêmement fructueuse dans le cadre des circuits booléens, où les langages réguliers jouent un rôle central. Cette angle de recherche a été cristallisé par Howard Straubing dans son livre "Finite Automata, Formal Logic, and Circuit Complexity'', où il émet la conjecture que tout langage régulier définissable par une formule arbitraire d'un fragment de logique peut être réécrite en utilisant uniquement des prédicats simples, c'est-à-dire réguliers. Le premier but de ce manuscrit est de prouver cette conjecture dans le cas du fragment Sigma2 de la logique du premier-ordre avec une seule alternance de quantification. Un deuxième résultat propose une description de la complexité en espace, dans le modèle de flot, pour vérifier des propriétés régulières sur des arbres. Une attention particulière est portée aux propriétés vérifiables en espace constant et logarithmique. Un troisième objectif est de décrire tous les langages réguliers d'arbres pouvant être maintenus incrémentalement en temps constant en RAM. Enfin, une dernière partie porte sur le développement de formules logiques efficaces pour maintenir tous les langages réguliers dans le modèle relationnel.
M. Sylvain SALVATI Université de Lille Directeur de thèse, M. Howard STRAUBING Boston College Rapporteur, M. Arnaud DURAND Université Paris-Diderot Rapporteur, M. Charles PAPERMAN Université de Lille Examinateur, M. Michaël CADILHAC DePaul University Examinateur, Mme Sophie TISON Université de Lille Examinatrice, Mme Cristina SIRANGELO Université Paris Cité Examinatrice, M. Damien POUS ENS Lyon Examinateur.
Thesis of the team LINKS defended on 05/07/2024
français
English