Thèse (M.A.)--Université Laval, 2007. / Bibliogr.: f. [31]-32. Publié aussi en version électronique dans la Collection Mémoires et thèses électroniques.

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.

Ce document présente différents outils pour représenter et manipuler des ensembles infinis de n-uplets d'arbres appelés langages de n-uplets d'arbres. Nous avons choisi la programmation logique comme formalisme pour décrire les langages de n-uplets d'arbre (c.à.d. les relations) et les techniques de transformations de programmes pour calculer les opérations sur ceux-ci. Dans un premier temps on étudie une classe de relations closes par la plupart des opérations ensemblistes, la classe des relations pseudo-régulières. Grâce à un lien entre programmes logiques et systèmes de réécriture, nous définissons des classes de systèmes de réécriture conditionnelle dont la clôture transitive est une relation pseudo-régulière. On applique ce résultat pour donner une classe décidable de formules du premier ordre basées sur le prédicat de joignabilité où R est un système de réécriture conditionnel pseudo-régulier. Ensuite on étend ce résultat au second ordre, les variables du second ordre étant interprétées comme des relations. A partir d'un algorithme général original décidant de la satisfiabilité de formules du second ordre sous certaines conditions, nous représentons une instance des variables du second ordre en système de réécriture conditionnel. On montre que ce travail peut permettre la synthèse automatique de programme. Dans un dernier temps, nous utilisons des sur-approximations pour des tests d'inconsistances. A cet effet, nous utilisons une classe de programmes logiques non réguliers dont le test du vide est décidable pour effectuer la sur-approximation. Nous appliquons finalement cette méthode à la vérification de protocoles cryptographiques.

Les coupes agglomérées et en mosaïque constituent deux stratégies d'aménagement qui diffèrent grandement de par la quantité ainsi que la configuration des habitats résiduels à l'échelle du paysage. Par ailleurs, des différences dans la configuration de la forêt résiduelle engendrent, entre autres, la création de bordures d'origine anthropique, celles-ci pouvant affecter la qualité des peuplements forestiers ainsi que le comportement des espèces animales associées aux forêts mûres et surannées. Le premier chapitre de ce mémoire a pour objectif de documenter de quelle manière le groupe fonctionnel des excavateurs primaires de cavités répond (1) à la quantité de forêts résiduelles à l'échelle du paysage, (2) à la configuration des peuplements forestiers résiduels à l'échelle du paysage et (3) à la rétention d'attributs de structure caractérisant les forêts surannées (arbres vivants de grand diamètre, chicots et débris ligneux) dans les peuplements résiduels des patrons de coupes agglomérées et en mosaïque. Le deuxième chapitre de ce mémoire vise quant à lui (1) à déterminer quelles sont les caractéristiques des arbres utilisés pour l'alimentation du Pic à dos rayé (Picoides dorsalis), (2) à déterminer si les pics s'alimentent en fonction de la disponibilité des bons substrats d'alimentation dans les bordures de coupes et (3) à caractériser le patron de déplacement des pics lors de leur quête alimentaire à proximité des lisières. L'aire d'étude se situe dans la zone de la pessière noire à mousses, dans la région du Nord-du-Québec (49° 12' à 50° 09' de latitude nord et 75°09' à 76° 37' de longitude ouest). Dans le cadre du premier chapitre, nous avons échantillonné neuf espèces d'oiseaux excavateurs de cavités dans 160 stations réparties également entre les peuplements résiduels des coupes agglomérées et en mosaïque. L'échantillonnage a été réalisé avec les méthodes des points d'écoute et des points d'appel dans le but de détecter le plus grand nombre d'individus possible. Les attributs de structure ainsi que les variables du paysage ont également été caractérisés pour chacune des stations. En ce qui concerne le deuxième chapitre, nous avons réalisé des suivis focaux de pics à dos rayé à l'intérieur de 18 bordures de coupes. Un inventaire des arbres morts sur pied et au sol a également été réalisé dans les lisières où des suivis focaux ont été préalablement réalisés. Nos résultats montrent que le Pic à dos rayé et la Mésange à tête brune (Poecile hudsonicus) avaient une occurrence plus forte dans les habitats résiduels des coupes en mosaïque alors que le Pic Flamboyant (Colaptes auratus) était plus abondant dans les habitats linéaires des coupes agglomérées. De plus, autant les variables locales que celles du paysage étaient importantes pour les espèces à l'étude. D'autre part, bien que les bons substrats d'alimentation pour le Pic à dos rayé étaient plus abondants à proximité des lisières, les pics évitaient tout de même de s'alimenter à cet endroit. Finalement, bien que les habitats linéaires des coupes agglomérées sont susceptibles de représenter des habitats sub-optimaux, ils sont néanmoins utilisés par la majorité des espèces à l'étude. Ainsi, la rétention, de façon permanente, de ces habitats linéaires ainsi que de massifs forestiers de plus grande superficie pourrait améliorer les conditions forestières et ainsi faire en sorte de maintenir ce groupe important d'espèces en zones aménagées. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : excavateurs primaires de cavités, pics, coupes en mosaïque, coupes agglomérées

Thèse de doctorat : Informatique : Nancy 1 : 2007. / Titre provenant de l'écran-titre. Bibliogr.

Le développement du Web a motivé l’apparition de nombreux types de formats de données semi-structurées pour les problèmes liés aux technologies du Web, comme le traitement des documents ou la gestion de base de données.Nous étudions ici la conversion des données semi-structurées d’un schéma à un autre. Pour le traitement de documents, c’est la technologie XML qui offre la solution la plus puissante à ce problème. En XML, les données semi-structurée sont des arbres de données dont les schémas peuvent être définis par des automates d’arbres avec contraintes sur les valeurs de données. Les transformations de documents sont spécifiées en XSLT, un langage fonctionnel muni de requêtes logiques XPath. Le cœur de XSLT correspond aux transducteurs d’arbres à macros avec navigation par requêtes XPath.Nous proposons de nouveaux algorithmes pour l’apprentissage des transducteurs d’arbres, basés sur des méthodes d’inférence grammaticale. Nous abordons la restriction de schéma, l’anticipation (lookahead), ou la concaténation dans la sortie.1. Nous donnons une forme normale et un algorithme d’apprentissage dans le modèle de Gold avec des ressources limitées pour les transducteurs d’arbres de haut en bas déterministes avec une inspection de domaine régulière.2. Nous montrons comment apprendre des fonctions rationnelles, décrites par les transducteurs de mots déterministes avec anticipation. Nous proposons une nouvelle forme normale qui permet un apprentissage avec des ressources polynomiales.3. Pour les transducteurs arbre-vers-mot linéaires, qui permet la concaténation dans sa sortie, nous présentons une forme normale, et montrons comment décider l’équivalence en temps polynomial. / Since the arrival of the Web, various kinds of semi-structured data formats were introduced in the areas of computer science and technology relevant for the Web, such as document processing, database management, knowledge representation, and information exchange. In this thesis, we study the conversion of semi-structured data from one schema to another.For document processing, the most powerful solutions to this problem were proposed by the XML technology. In the XML format, semi-structured data is restricted to data trees, so that schemas can be defined by tree automata, possibly enhanced by constraints on data values. Document transformations can be defined in XSLT, a purely functional programming language with logical XPath queries. The core of XSLT are macros tree transducers with navigation by XPath queries.We contribute new learning algorithms on tree transducers, that are based on methods from grammatical inference. We address three limitiations of previous approaches: schema restrictions, lookaheads, and concatenation in the output.1. For deterministic top-down tree transducers with regular domain inspection, we show a normal form and a Gold style learning algorithm in with limited resources.2. We show how to learn rational functions, described by deterministic transducers of words with lookahead. We propose a new normal form for such transducers which provides a compromise between lookahead and state minimization, that leads to a learning algorithm in Gold’s learning model with polynomial resources.3. For linear tree-to-word transducers with concatenation in the output, we present a normal form and show how to decide equivalence in polynomial time.

Les automates d'arbres et leurs applications à la vérification forment le tronc commun de cette thèse. Dans la première parie, nous définissons une plate forme de model-checking complète [...] La seconde partie se penche sur un aspect important des automates que nous utilisons: leur contraintes [...] Finalement, nous étudions également les automates d'arbres cheminants [...] Nous améliorons leur conversion en automates parallèles, et nous développons une procédure de semi décision de leur vacuité, à la fois efficace et précise / Tree automata, and their applications to verification from the common thread of this thesis In the first part, we definie a complete model-cheking framework.[...] The second part focus on an important aspect of the automata involved: constraints.[...] Finaly, we also study the very different variety of tree-walking automata which have tight connections with navigational languages on semi-structured documents.

La confidentialité des données est devenue primordiale en statistique. Une méthode souvent utilisée pour diminuer le risque de réidentification est la génération de jeux de données partiellement synthétiques. On explique le concept de jeux de données synthétiques, et on décrit une méthode basée sur les forêts aléatoires pour traiter les variables catégoriques. On s’intéresse à la formule qui permet de faire de l’inférence avec plusieurs jeux synthétiques. On montre que l’ordre des variables à synthétiser a un impact sur l’estimation de la variance des estimateurs. On propose une variante de l’algorithme inspirée du concept de confidentialité différentielle. On montre que dans ce cas, on ne peut estimer adéquatement ni un coefficient de régression, ni sa variance. On montre l’impact de l’utilisation de jeux synthétiques sur des modèles d’équations structurelles. On conclut que les jeux synthétiques ne changent pratiquement pas les coefficients entre les variables latentes et les variables mesurées. / Confidential data are very common in statistics nowadays. One way to treat them is to create partially synthetic datasets for data sharing. We will present an algorithm based on random forest to generate such datasets for categorical variables. We are interested by the formula used to make inference from multiple synthetic dataset. We show that the order of the synthesis has an impact on the estimation of the variance with the formula. We propose a variant of the algorithm inspired by differential privacy, and show that we are then not able to estimate a regression coefficient nor its variance. We show the impact of synthetic datasets on structural equations modeling. One conclusion is that the synthetic dataset does not really affect the coefficients between latent variables and measured variables.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Le programme de recherches présenté dans cette synthèse s'inscrit dans la double problématique de l'étude des langages d'arbres et de l'apprentissage automatique à partir de données arborescentes. <br /> À la base de ce travail se trouve la question de l'accès et de la manipulation automatique d'informations au format XML au sein d'un réseau d'applications réparties dans internet. La réalisation de ces applications est toujours du ressort de programmeurs spécialistes d'XML et reste hors de portée de l'utilisateur final. De plus, les développements récents d'internet poursuivent l'objectif d'automatiser les communications entre applications s'échangeant des flux de données XML. Le recours à des techniques d'apprentissage automatique est une réponse possible à cette situation. <br /> Nous considèrons que les informations sont décrites dans un langage XML, et dans la perspective de ce mémoire, embarquées dans des données structurées sous forme arborescente. Les applications sont basées alors sur des opérations élémentaires que sont l'interrogation ou les requêtes dans ces documents arborescents ou encore la transformation de tels documents. <br /> Nous abordons alors la question sous l'angle de la réalisation automatique de programmes d'annotation d'arbres, permettant de dériver des procédures de transformation ou d'exécution de requêtes. Le mémoire décrit les contributions apportées pour la manipulation et l'apprentissage d'ensembles d'arbres d'arité non bornée (comme le sont les arbres XML), et l'annotation par des méthodes de classification supervisée ou d'inférence statistique.