Circuits de provenance pour les arbres et les instances quasi-arborescentes

Abstract

<p>L’évaluation de requêtes en logique monadique du second ordre (MSO) est de faible complexité sur les arbres et les instances quasi-arborescentes (c’est-à-dire de largeur d’arbre bornée), alors qu’elle est difficile sur les instances arbitraires. Ce résultat a été étendu à certaines tâches liées à l’évaluation de requêtes, comme compter les résultats d’une requête ou évaluer des requêtes sur des arbres probabilistes. Nous voyons le comptage et l’évaluation probabiliste comme deux cas particuliers du problème plus général consistant à calculer des résultats de requête enrichis avec des informations de provenance.Cet article présente une construction de provenance pour les arbres et les instances quasi-arborescentes, en expliquant comment calculer en temps linéaire une représentation de la provenance sous forme de circuit pour les requêtes MSO. Nous montrons comment cette provenance se rattache aux définitions habituelles des semianneaux de provenance sur les instances relationnelles, quand bien même nous la calculons d’une manière inhabituelle, en passant par des automates d’arbres : nous établissons cette connexion au travers de définitions intrinsèques de la provenance pour des semianneaux généraux, qui ne dépendent pas des détails opérationnels de l’évaluation de la requête. Nous montronscomment cette provenance permet de capturer des résultats existants pour le comptage et l’évaluation probabiliste sur les arbres et les instances quasi-arborescentes, et nous en déduisons de nouvelles conséquences pour l’évaluation de requêtes sur diverses représentations <br/>probabilistes.Cet article a été accepté à ICALP 2015. Cette version intègre certains changements mineurs. Par ailleurs, son appendice est inédite et contient du contenu technique et des preuves supplémentaires.</p>