La reconstruction phylogénétique vise à reconstituer l'histoire évolutive d'un ensemble d'espèces sous forme d'un arbre. Parmi les méthodes de reconstruction, le problème Maximum de Parcimonie (MP) consiste à trouver un arbre binaire dont les feuilles sont associées à des séquences de caractères données, et qui minimise le score de parcimonie. Les méthodes de résolution existantes de ce problème NP-complet s'attachent généralement à appliquer des méthodes heuristiques traditionnelles, comme des algorithmes gloutons et de recherche locale. L'une des diffcultés du problème repose sur la manipulation d'arbres et la définition de voisinages d'arbres.<br />Dans cette thèse, nous nous intéressons en premier lieu à l'amélioration des techniques de résolution du problème MP basées sur un algorithme de descente. Après avoir montré de manière empirique les limites des voisinages existants, nous introduisons un voisinage progressif qui évolue au cours de la recherche afin de limiter l'évaluation de voisins infructueux lors d'une descente. L'algorithme obtenu est ensuite hybridé à un algorithme génétique utilisant un croisement d'arbres spécifique fondé sur les mesures de distance entre chaque couple d'espèces dans l'arbre. Cet algorithme mémétique exhibe des résultats très compétitifs, tant sur des jeux de test tirés de la littérature que sur des jeux générés aléatoirement.

La recherche de structures arborescentes fréquentes, également appelée fouille d'arbres, au sein de bases de données composées de documents semi-structurés (e.g. XML) est une problématique actuellement très active. Ce processus trouve de nombreux intérêts dans le contexte de la fouille de données comme par exemple la construction automatique d'un schéma médiateur à partir de schémas XML, ou bien l'analyse des structures des sites Web afin d'étudier son usage ou modifier son contenu.<br /><br />L'objectif de cette thèse est de proposer une méthode d'extraction d'arborescences fréquentes. Cette approche est basée sur une représentation compacte des arborescences cherchant à diminuer la consommation de mémoire dans le processus de fouille. En particulier, nous présentons une nouvelle technique de génération d'arborescences candidates visant à réduire leur nombre. Par ailleurs, nous proposons différents algorithmes pour valider le support des arborescences candidates dans une base de données selon divers types de contraintes d'inclusion d'arbres : induite, incrustée et floue. Finalement nous appliquons nos algorithmes à des jeux de données synthétiques et réels et nous présentons les résultats obtenus.

Cette thèse est consacrée à l'étude des décalages, ou encore systèmes dynamiques symboliques, définis sur certains monoïdes finiment présentés, $Z^d$ d'une part et les arbres d'autre part. Le principal résultat concernant les décalages multidimensionnels établit que tout décalage effectif de dimension d est obtenu par facteur et sous-action projective d'un décalage de type fini de dimension d+1. De ce résultat nous déduisons que les décalages S-adiques multidimensionnels donnés par une suite effective de substitutions sont sofiques. Sur les décalages d'arbres nous montrons un théorème de décomposition, qui permet d'écrire une conjugaison entre deux décalages d'arbres quelconques comme une suite finie d'opérations élémentaires, les fusions entrantes et les éclatements entrants. De ce théorème, associé à la commutation des fusions entrantes, nous déduisons la décidabilité du problème de conjugaison entre deux décalages d'arbres de type fini. Nous nous intéressons ensuite à la classe des décalages d'arbres sofiques, qui sont exactement ceux reconnus par des automates d'arbres montants dans lesquels tous les états sont à la fois initiaux et finaux. Nous montrons l'existence d'un unique automate d'arbres déterministe, réduit, irréductible et synchronisé qui reconnaît un décalage d'arbres sofique. Enfin nous montrons que l'appartenance à la sous-classe des décalages d'arbres AFT est décidable

Dans cette thèse, nous proposons une architecture logicielle (SemTAG) permettant de réaliser un calcul sémantique pour grammaires d'Arbres Adjoints. Plus précisément, cette architecture fournit un environnement permettant de construire une représentation sémantique sous-spécifiée (Predicate Logic Unplugged (Bos, 1995)) à partir d'une grammaire et d'un énoncé.<br /><br />Afin de faciliter la gestion de grammaires de taille réelle, la plate-forme SemTAG intègre un compilateur de métagrammaires. Le rôle de ce compilateur est de produire semi-automatiquement une grammaire à partir d'une description factorisée. Cette description correspond à (a)~une hiérarchie de fragments d'arbres et (b)~des combinaisons de ces fragments au moyen d'un langage de contrôle. De plus, chaque arbre ainsi produit peut être équipé d'une interface syntaxe / sémantique à la (Gardent et Kallmeyer, 2003).<br /><br />La construction sémantique est réalisée à partir du résultat de l'analyse syntaxique. Cette analyse est fournie par un analyseur syntaxique tabulaire généré automatiquement à partir de la grammaire d'entrée au moyen du système DyALog (De La Clergerie, 2005). Cet analyseur produit une forêt de dérivation, qui encode toutes les dérivations, et à partir desquelles les unifications des indexes sémantiques sont extraites.<br /><br />Cette plate-forme a été évaluée en termes de couverture sémantique sur la test-suite TSNLP.

Nous nous intéressons par le problème de la sémantique des mises à jour et de la cohérence des bases de données dans différents contextes comme les documents XML et les services web. En effet, des difficultés particulières sont à prévoir lors de la mise à jour d'une base ayant des contraintes à respecter, car, des données originalement cohérentes par rapport aux contraintes peuvent devenir incohérentes suite aux mises à jour. Dans une première partie de notre travail, nous considérons la mise à jour et le maintien de la cohérence d'une base de données XML par rapport au type (ou schéma) ainsi que par rapport aux contraintes d'intégrité. Nous abordons ce problème de différentes manières. Tout d'abord, nous proposons une procédure de validation incrémentale par rapport aux contraintes, évitant de revalider les parties du document qui n'ont pas été touchées par les mises à jour. Cette approche traite aussi bien le cas des contraintes de schéma que le cas des contraintes d'intégrité. Dans ce cadre, les listes de mises à jour qui violent la validité sont rejetées. Quand la validation incrémentale échoue, c'est-à-dire, quand une mise à jour viole le type, deux propositions de traitement sont faites\,: (A) Une routine de correction est activée pour adapter le document XML au type tout en prenant en compte la mise à jour. La mise à jour a donc une priorité par rapport aux données déjà stockées. (B) Une routine propose une adaptation du type du document, de façon à accepter le document mis à jour en préservant la validité des autres documents originalement valides et non soumis à la mise à jour. Dans ce cas, la mise à jour est prioritaire et les contraintes peuvent être modifiées. Une deuxième partie du travail considère la construction d'une plate-forme d'aide à la spécification, à l'implémentation et à la manipulation de services. L'idée de pouvoir spécifier et modifier des compositions de services nous a amené à la définition du langage PEWS (\textit{Path Expressions for Web Services}), ayant une sémantique formelle bien définie et permettant la spécification du comportement des interfaces des services web simples ou composés. Pour pouvoir tester statiquement des propriétés liées à la composition des services, nous proposons l'utilisation de la théorie des traces et les graphes de dépendances.

Nous étudions des classes d'automates à états finis calculant sur les arbres, étendus par des contraintes permettant de tester des égalités et diségalités entre sous-arbres. Nous nous concentrons sur des automates d'arbres à contraintes globales où les tests sont opérés en fonction des états que l'automate atteint lors de ses calculs. De tels automates ont été introduit dans le cadre de travaux sur les documents semi-structurés. Nous procédons ici à une comparaison détaillée en expressivité entre ces automates et d'autres modèles permettant de réaliser des tests similaires, comme les automates à contraintes entre frères ou les automates d'arbres avec une mémoire auxiliaire. Nous montrons comment de tels automates peuvent être utilisés pour vérifier des propriétés de sécurité sur les protocoles cryptographiques. Les automates d'arbres ont déjà été utilisés pour modéliser les messages échangés lors d'une session d'un protocole. En ajoutant des contraintes d'égalité, nous pouvons décrire précisement des sessions qui utilisent à plusieurs reprises un même message, évitant ainsi une approximation trop grande. Nous répondons ensuite positivement au problème de la décision du vide des langages reconnus par les automates à contraintes globales. En montrant que leur expressivité est très proche de celle des automates opérant sur des représentations de termes par des graphes orientés acycliques, nous en déduisons une procédure de décision du vide en temps non-déterministe doublement exponentiel. Finalement, nous étudions le problème de la décision du vide pour des automates à contraintes globales pour lesquels on autorise des contraintes dites de clé, exprimant intuitivement que tous les sous arbres d'un certain type dans un arbre en entrée sont distincts deux à deux. Le type des clés est classiquement utilisé pour représenter un identifiant unique, comme un numéro de sécurité sociale.Nous décrivons alors une procédure de décision du vide de complexité non-élementaire. Nous montrons que cette procédure est très robuste, et qu'il est possible d'étendre les automates avec des contraintes supplémentaires, comme des contraintes de comptage ou des tests locaux, tout en préservant la décidabilité du vide. / We study here several classes of finite state automata running on trees, extended with constraints that allow to test for equalities or disequalities between subterms. We focus on tree automata with global constraints where the tests are done depending on the states reached by the automaton on its runs. Such automata were introduced in studies on semi-structured documents. We do here a detailed comparison between those automata and other models that allow to operate similar tests, like tree automata with constraints between brothers, or tree automata with an auxiliary memory. We show how such automata may be used to verify security properties on cryptographic protocols. Tree automata have already been used to modelize the messages exchanged during a protocol session. By adding equality constraints, we can describe precisely protocol sessions that use a same message several times, hence avoiding an approximation. Then, we answer positively the decision problem of the emptiness of the languages recognized by tree automata with global constraints. By showing that their expressivity is very close from the one of the automata operating on directed acyclic graphs representations of terms, we infer an emptiness decision procedure in double exponential non-deterministic time. Finally, we study the emptiness decision problem for automata with global constraints where we authorize "key constraints", that intuitively allow that all subtrees of a given type in an input tree are distincts. We give an emptiness decision procedure of non-primitive recursive complexity. Key constraints are classicaly used to represent a unique identifier. We describe a non-primitive recusrive emptiness decision procedure. We show that this procedure is very robust and that it allows to extend the automata with additionnal constraints, like counting constraints or local tests, while preserving decidability.

Concevoir et mettre en oeuvre des méthodes pour la spécification, l'analyse et la vérification de logiciels et de systèmes sont les principaux moteurs des activités de recherche présentées dans ce manuscrit. Dans ce cadre, nos travaux se positionnent dans la catégorie dite des méthodes formelles appartenant à la communauté plus large du génie logiciel. A l'interface des travaux théoriques et applicatifs, notre objectif est de contribuer aux méthodes permettant d'assurer la correction et la sûreté des systèmes (fonctionnalité, sécurité, fiabilité, ...) en développant ou en améliorant des langages de spécification, des techniques et des outils permettant leur analyse formelle. Dans ce but, nous nous sommes attaché dans cette thèse à proposer et à étudier un cadre formel permettant la définition de politiques de sécurité et la vérification de leurs propriétés. A cet effet, nous avons proposé un cadre pour la spécification de politiques de sécurité basé sur une approche modulaire dans laquelle une politique est vue comme la composition d'un modèle de sécurité et d'une configuration. Nous avons investigué les possibilités offertes par de telles spécifications lorsque les modèles sont exprimés au moyen de contraintes du premier ordre et les configurations au moyen de programmes logiques. En particulier, nous avons proposé un algorithme permettant de transformer une politique exprimée dans un modèle donné vers une autre politique équivalente (au sens où elle engendre les mêmes autorisations) exprimée dans un autre modèle. Dans un second temps, nous nous sommes proposé de tenir compte des aspects dynamiques de la configuration d'une politique vue comme un état du système sur lequel la politique est mise en oeuvre et où chaque action est associée à une procédure de modification des états. Nous avons proposé un langage formel simple pour spécifier séparément les systèmes et les politiques de sécurité puis avons donné une sémantique des spécifications exprimées dans ce cadre sous la forme de systèmes de réécriture. Nous nous sommes ensuite attachés à montrer que les systèmes de réécriture obtenus permettent l'étude de propriétés de sécurité. Dans une troisième partie, nous nous sommes focalisé sur les mécanismes permettant la mise en oeuvre de politiques de sécurité dans les réseaux. Dans ce cadre, nous avons proposé une spécification des firewalls et de leurs compositions basée sur les automates d'arbres et les systèmes de réécriture puis avons montré en quoi ces spécifications nous permettent d'analyser de façon automatique les politiques de sécurité sous-jacentes. / Designing and applying formal methods for specifying, analyzing and verifying softwares and systems are the main driving forces behind the work presented in this manuscript. In this context, our activities fall into the category of formal methods belonging to the wider community of software engineering. At the interface between theoretical and applied research, our aim is to contribute to the methods ensuring the correction and the safety of systems (security, reliability, ...) by developing or by improving specification languages, techniques and tools allowing their formal analysis. In this purpose, we became attached in this thesis to propose and to study a formal framework allowing the specification of security policies and the verification of their properties. We first proposed a framework for specifying security policies based on a modular approach in which policies are seen as a composition of security models and configurations. We investigated the possibilities opened by such specifications when models are expressed by means of first order constraints and configurations by means of logical programs. In particular, we proposed an algorithm allowing the transformation of a security policy expressed in a given model towards another equivalent policy expressed in another model. Secondly, we suggested taking into account dynamic aspects of policy configurations which can be seen as states of the system on which the policy is applied and where each action is associated with a procedure of states modification. We proposed a simple formal language to specify separately systems and security policies and then gave a semantics of specifications expressed in this framework under the form of rewriting systems. We then attempted to show that the obtained rewriting systems allow the analysis of security properties. In the third part, we focused on mechanisms enforcing security policies in networks. In this context, we proposed a specification of firewalls and their compositions based on tree automata and rewriting systems and then showed how these specifications allow us to analyze in an automatic way the underlying security policies.

Nous proposons une méthode pour aider les administrateurs des applications XML dans la tâche de faire évoluer des schémas en préservant la cohérence de la base de données sans la modifier.<br />L'utilisateur donne au système ce qu'il souhaite comme nouveau document devant être accepté par le schéma.<br />À partir de ce document, le système construit des schémas candidats, qui d'une part préservent la validité de la base de documents et, d'autre part augmentent la classe de documents acceptée par le schéma.<br />L'approche est implantée par un algorithme appelé GREC. <br />Cet algorithme utilise l'automate d'arbre A qui accepte le langage défini par le schéma pour trouver les informations nécessaires à la modification. <br />Plus précisément, il utilise les expressions régulières des règles de transitions de A pour proposer les candidats.<br />Ainsi, les modifications sont faites sur les graphes qui représentent les automates d'états finis construits à partir des expressions régulières concernées.<br />Les expressions régulières engendrées par GREC représentent des schémas présentés à l'utilisateur afin qu'il choisisse le plus adapté à la sémantique de son application.

En Abitibi, à l'ouest du Québec, l'exploitation forestière a été, et reste encore, le moteur de l'économie de la région. Cette activité forestière a laissé des empreintes sur le paysage forestier qui se caractérise par une augmentation de la proportion des peuplements feuillus. En effet, au 20ème siècle et en ce début du 21ème siècle, la récolte des conifères dans les peuplements mixtes ou à dominance résineuse a marqué le développement de l'industrie forestière. Les peuplements résiduels sont aujourd'hui envahis par les feuillus e.g. le peuplier faux-tremble (processus d'enfeuillement). En conséquence, on observe une diminution de la proportion des conifères aux échelles du peuplement et du paysage. Ces activités anthropiques (i.e. Coupes) sont-elles seules à l'origine de la modification de ce paysage ou l'augmentation de la fréquence de ces coupes? Pour tenter de répondre à cette question et mieux comprendre la dynamique de l'enfeuillement sur les argiles de l'Abitibi, nous avons comparé l'effet de la coupe et du feu sur les attributs (composition, structure et diversité) des peuplements. Ensuite, nous avons analysé l'influence de la composition d'origine sur ces attributs. Nos résultats montrent que la composition des tremblaies issues de feu et de coupes d'origine mixte ou résineuse est actuellement comparable. Seule la régénération diffère sensiblement. Les tremblaies d'origine résineuses renferment une proportion élevée de sapin baumier et de peuplier baumier comparativement à celles d'origine mixte dominées par le peuplier faux-tremble. La diversité alpha et bêta ne montrent pas de différences marquées. Seule la structure des tremblaies dégage une tendance. Les tremblaies issues de feu et de composition d'origine résineuse se caractérisent par une abondance de gaules et de grosses tiges. Celles issues de coupes d'origine mixte, renferment plus de perches et de chicots de toutes grosseurs. Ces résultats montrent que le type, l'intensité et la fréquence des coupes adoptées avant l'avènement de l'ère industrielle, n'aurait pas significativement altéré les attributs des tremblaies. Contrairement, de nos jours, l'industrialisation de l'exploitation forestière semble modifier significativement les attributs des peuplements en Abitibi. À l'issue de ces travaux, notre compréhension de la dynamique des tremblaies dans la plaine argileuse reste fragmentaire et très limitée. Une analyse plus approfondie est nécessaire pour mieux cerner la dynamique des tremblaies de la plaine argileuse d'Abitibi. Cette analyse devra viser à quantifier la perte de superficie de peuplements résineux au profit de tremblaies et identifier les processus à la base de cette dynamique. En outre, une analyse spatio-temporelle des communautés végétales à l'intérieur des tremblaies et à l'échelle du paysage abitibien permettrait de quantifier les écarts entre les proportions actuelles et historiques, et d'élaborer des stratégies d'aménagement adaptées au contexte régional. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Enfeuillement, Peuplier faux-tremble, Composition, Structure, Diversité, Argile, Perturbation, Feu, Coupe, Abitibi.

Les perturbations naturelles sont aujourd'hui reconnues comme étant des parties intégrantes de la dynamique des forêts, voire même essentielles à la diversité et au fonctionnement des écosystèmes. C'est pourquoi depuis quelques années, on croit que la meilleure façon de conserver la biodiversité et les fonctions essentielles des écosystèmes forestiers soumis aux pratiques d'aménagement serait d'émuler les processus de perturbation naturelle se déroulant dans les forêts non aménagées. Bien que l'importance des perturbations intermédiaires soit de plus en plus reconnue, la plupart des travaux sur l'émulation des perturbations naturelles s'est concentrée sur le feu. Toutefois, un aménagement basé sur la compréhension des régimes des perturbations naturelles ne peut pas être axé exclusivement sur la dynamique des feux, ignorant le rôle des perturbations moins sévères ou survenant à de plus petites échelles. Les épidémies de la tordeuse des bourgeons de l'épinette (TBE) constituent après les feux, la plus importante perturbation affectant la forêt boréale. Certains auteurs ont souligné des similitudes entre les épidémies sévères de la TBE et la coupe avec protection de la régénération et des sols (CPRS). Ces deux perturbations s'attaquent aux arbres matures en affectant peu ou pas la régénération préétablie et les sols. Pour arriver à modifier un aménagement forestier afin qu'il s'approche davantage d'un processus naturel, il est essentiel de caractériser précisément les différences et les similarités entre perturbations naturelle et anthropique. Nous proposons, dans le cadre de cette étude, de comparer les effets des CPRS à ceux des épidémies de la TBE dans les peuplements résineux de la sapinière à bouleau blanc dans la région de la Gaspésie. Puisqu'une éclaircie pré-commerciale (EPC) est systématiquement faite après chaque CPRS, et qu'il n'est pas possible de départager les effets de ces deux pratiques, la CPRS et l'EPC constituent ensemble la perturbation anthropique étudiée. Pour mieux comprendre les phénomènes écologiques impliqués dans ces deux types de perturbation, l'étude a été réalisée à deux échelles, soit celle du peuplement et celle du paysage. À l'échelle du peuplement, 10 stations issues de CPRS effectuées en 1989 et 10 stations sévèrement affectées par la plus récente épidémie de la TBE ont été étudiées. L'échantillonnage de données de végétation a permis d'évaluer les effets de ces perturbations sur l'abondance de matière organique telle que les chicots, les débris ligneux, les arbres résiduels, ainsi que la régénération retrouvée une quinzaine d'années après les perturbations. À l'échelle du paysage, l'interprétation de photographies aériennes a permis de caractériser la taille, la forme, et la distribution spatiale des ouvertures créées par ces perturbations. Les résultats obtenus montrent que les espèces compagnes du sapin baumier, soit l'épinette blanche et le bouleau à papier, ont été favorisées par l'épidémie de la TBE, tandis que les CPRS+EPC semblent plutôt favoriser la dominance du sapin. Les peuplements issus de l'épidémie présentent plus d'éléments structuraux tels que les arbres résiduels, les chicots et les débris ligneux en plus de présenter plus de variabilité horizontale sur le plan de la densité des tiges de plus de 2 m de haut. Les peuplements issus de CPRS+EPC présentent une plus grande diversité d'espèces d'arbre pour les strates inférieures alors que les peuplements issus de l'épidémie montrent une plus grande diversité pour les strates supérieures. Ainsi, nos résultats suggèrent que l'on devrait tenter de préserver les espèces compagnes lors de l'aménagement des forêts dominées par le sapin baumier, ainsi que certains éléments structuraux essentiels au fonctionnement des écosystèmes. De cette façon, il sera possible de conserver la variabilité naturelle et la biodiversité végétale et animale de ces forêts, et ainsi favoriser la résilience de ces écosystèmes. À l'échelle du paysage, contrairement à ce que l'on s'attendait, les ouvertures créées par la TBE ont des formes plus régulières que celles créées par les CPRS. Par contre, étant donné leur taille grandement supérieure, les ouvertures créées par les CPRS ont tout de même moins de bordure par unité de surface. Ces résultats suggèrent que l'agrégation des unités de coupe devrait être limitée, comme dans le cas des coupes mosaïques. Par contre, les coupes mosaïques telles que pratiquées aujourd'hui, se font à une échelle trop grossière par rapport à la fine mosaïque créée par l'épidémie de la TBE.