L’objectif de cette thèse est d’obtenir des algorithmes sous linéaire permettant de répondre à des problèmes de décision dans les bases de données XML. Plus précisément, on s’inspire du property testing, pour décider approximativement si un arbre d’arité non bornée est valide par rapport à une DTD ; ou plus généralement si un tel arbre est reconnu par un automate d’arbre.Nous avons d’abord étudié le cas simple des mots, c’est-à-dire l’appartenance approchée d’un mot à un langage régulier défini par un automate non-déterministe. Sous la distance d’édition entres les mots, nous proposons un algorithme (ou tester) résolvant l’appartenance approchée en un temps polynomial : en la taille de l’automate aussi bien qu’en la précision (où le paramètre d’erreur). Nous avons aussi amélioré le précédent algorithme d’Alon, Krivelevich, Newman, et Szegedy, (2000) pour l’approximation de l’appartenance à un langage régulier modulo la distance de Hamming. Notre amélioration consiste à rendre cet algorithme polynomial en la taille de l’automate non-déterministe. Ensuite nous avons considéré l’appartenance approchée d’un arbre à un automate d’arbre sous la distance d’édition standard. Notre algorithme résout ce problème avec une complexité en temps exponentielle en la hauteur de l’arbre. Enfin nous avons considéré la validation approchée de DTD par rapport à la « strong edit distance » ; et nous obtenons dans ce cas un algorithme polynomial en la hauteur de l’arbre. Nous complétons nos résultats en prouvant une borne inférieure linéaire en la taille de l’arbre, pour la complexité de tout algorithme décidant l’appartenance approchée d’un arbre à une DTD, sous la strong edit distance. / Inspired by property testing, our objective is to obtain sublinear algorithms for deciding properties of XML databases approximatively. More precisely, we investigate the properties of whether an unranked tree is valid for a DTD, or more generally, whether it is recognized by a tree automaton. We start our studies by the simpler case of words and we considered the approximate membership problem for word non-deterministic automata. For this problem, we provide an efficient tester that runs in polynomial time in the size of the input automata and the error precision. We also improve the previous [Alon, Krivelevich, Newman, and Szegedy, 2000b] approximate membership tester for regular languages modulo the Hamming distance, so that it runs in polynomial time in the size of the input automata. Secondly, we study approximate membership testing for tree automata modulo the standard edit distance, and obtain a tester with run time exponential in the input tree depth. Next we consider approximate DTD validity modulo the strong edit distance. We then provide a tester that depends polynomially on the height of the tree. Finally, modulo the strong edit distance, we prove a linear lower bound on the depth of the input tree.

Fondée en 1095 près de Briey, l'abbaye de chanoines réguliers de Saint-Pierremont étend au XIIe et XIIIe siècles son temporel à une grande partie du Pays-Haut (région située au nord du département actuel de Meurthe-et-Moselle), une partie de l'ouest de département de la Moselle, nord-est de la Meuse, et jusqu'en Belgique. A partir des archives de cette abbaye (plusieurs cartulaires, deux fonds d'archives, un nécrologe), particulièrement utiles pour la connaissance de l'histoire de la région de Briey à partir du XIIe siècle, la présente étude s'intéresse aux structures foncières et à l'économie rurale dans la région de Briey, entre la fin du XIe siècle et le début du XIVe siècle. Sont tour à tour évoqués : le peuplement et l'occupation du sol ainsi que les puissances foncières en place avant la fondation de Saint-Pierremont ; l'évolution et la structure du temporel de cette abbaye ; le paysage, l'habitat et les puissances foncières aux XIIe et XIIIe siècles ; l'organisation des structures foncières seigneuriales et paysannes ; les activités agraires. Comment, dans cet espace rural, se répartissent les possessions foncières des dominants laïcs et ecclésiastiques et les exploitations paysannes ? Quelles sont les structures de ses possessions ? Placé entre le Verdunois d'un côté et le Pays messin de l'autre, le pays de Briey a-t-il une identité propre ou subit-il l'influence de ses deux puissants voisins? Cette étude s'accompagne de l'édition complète du livre foncier de l'abbaye, datant de la fin du XIIIe et du début du XIVe siècle, source textuelle irremplaçable pour la connaissance d'une partie du temporel de Saint-Pierremont et de la structure des exploitations paysannes de la région de Briey / Pas disponible / Not available

La modélisation et la simulation de dynamiques spatiales, en particulier pour l'étude de l'évolution de paysages ou de problématiques environnementales pose la question de l'intégration des différentes formes de représentation de l'espace au sein d'un même modèle. Ocelet est une approche de modélisation de dynamiques spatiales basée sur le concept original de graphe d'interaction. Le graphe porte à la fois la structure d'une relation entre entités d’un modèle et la sémantique décrivant son évolution. Les relations entre entités spatiales sont ici traduites en graphes d'interactions et ce sont ces graphes que l'on fait évoluer lors d'une simulation. Les concepts à la base d'Ocelet peuvent potentiellement manipuler les deux formes de représentation spatiale connues, celle aux contours définis (format vecteur) ou la discrétisation en grille régulière (format raster). Le format vecteur est déjà intégré dans la première version d'Ocelet. L'intégration du format raster et la combinaison des deux restaient à étudier et à réaliser. L'objectif de la thèse est d'abord étudier les problématiques liées à l'intégration des champs continus et leur représentation discrétisée en pavage régulier, à la fois dans le langage Ocelet et dans les concepts sur lesquels il repose. Il a fallu notamment prendre en compte les aspects dynamiques de cette intégration, et d'étudier les transitions entre données géographiques de différentes formes et graphe d'interactions à l'aide de concepts formalisés. Il s'est agi ensuite de réaliser l'implémentation de ces concepts dans la plateforme de modélisation Ocelet, en adaptant à la fois son compilateur et son moteur d'exécution. Enfin, ces nouveaux concepts et outils ont été mis à l'épreuve dans trois cas d'application très différents : deux modèles sur l’île de la Réunion, le premier simulant le ruissellement dans le bassin versant de la Ravine Saint Gilles s'écoulant vers la Côte Ouest de l'île, l’autre simulant la diffusion de plantes invasives dans les plaines des hauts à l'intérieur du Parc National de La Réunion. Le dernier cas décrit la spatialisation d'un modèle de culture et est appliqué ici pour simuler les rendements de cultures céréalières sur l’ensemble de l’Afrique de l’Ouest, dans le contexte d'un système d'alerte précoce de suivi des cultures à l'échelle régionale. / The modelling and simulation of spatial dynamics, particularly for studying landscape changes or environmental issues, raises the question of integrating different forms of spatial representation within the same model. Ocelet is an approach for modelling spatial dynamics based on the original concept of interaction graph. Such a graph holds both the structure of a relation between entities of a model and the semantics describing its evolution. The relationships between spatial entities are here translated into interaction graphs and these graphs are made to evolve during a simulation. The concepts on which Ocelet is based can potentially handle two known forms of spatial representation: shapes with contours (vector format) or regular grid cells (raster). The vector format is already integrated in the first version of Ocelet. The integration of raster and the combination of the two remained to be studied and carried out. The aim of the thesis is to first study the issues related to the integration of continuous fields and their representation by regular tiling, both in the Ocelet language and the concepts on which it is based. The dynamic aspects of this integration had to be taken into account and transitions between different forms of geographic data and interaction graphs had to be studied in the light of the concepts formalized. The concepts were then implemented in the Ocelet modelling platform, with the adaptation of both its compiler and runtime. Finally, these new concepts and tools were tested in three very different cases: two models on Reunion Island, the first simulating runoff in Ravine Saint Gilles watershed in the West Coast of the island, the other simulating the spread of invasive plants in the high plains inside the Reunion National Park. The last case describes the spatialisation of a crop model and is applied here to simulate the cereal crop yields in West Africa, in the context of an early warning system for regional crop monitoring.

La première partie de la thèse porte sur les graphes de Steinhaus réguliers. On commence par obtenir une nouvelle preuve du théorème de Dymacek, selon lequel toute matrice de Steinhaus associée à un graphe pair est bisymétrique, en exhibant une relation entre les éléments de l'antidiagonale d'une matrice de Steinhaus et les degrés des sommets du graphe associé. Ce théorème est ensuite utilisé pour montrer que toute matrice de Steinhaus associée à un graphe régulier de degré impair admet une grande sous-matrice multisymétrique. On étudie alors les matrices de Steinhaus multisymétriques, en particulier celles dont le graphe associé admet une certaine régularité. Cette étude permet enfin de vérifier jusqu'à 1500 sommets une conjecture de Dymacek, qui annonce que le graphe complet à deux sommets K2 est le seul graphe de Steinhaus régulier de degré impair, améliorant ainsi d'un facteur 12 la borne précédemment connue (117 sommets).<br />La seconde partie porte sur les triangles de Steinhaus dans Z/nZ. En 1978 Molluzzo pose le problème de savoir si, pour tout n≥1 et pour toute longueur admissible m, il existe une suite balancée de longueur m dans Z/nZ, c'est-à-dire une suite dont le triangle de Steinhaus associé contienne chaque élément de Z/nZ avec la même multiplicité. On donne ici une réponse complète et positive au Problème de Molluzzo dans tout groupe cyclique d'ordre une puissance de 3. Plus généralement, on construit une infinité de suites balancées dans tout groupe cyclique d'ordre impair. Ces résultats, qui sont les premiers obtenus sur ce problème dans Z/nZ avec n>3, proviennent de l'étude des triangles de Steinhaus des suites arithmétiques dans les groupes cycliques.

Les langages réguliers sont des langages qui ont été largement étudiés, notamment du point de vue de leurs propriétés de clôture ensembliste : l'ensemble des langages réguliers (pour un alphabet donné) forme une algèbre de Boole close par concaténation et étoile de Kleene. Ces propriétés ne se généralisent pas toutes à l ensemble des langages algébriques qui est un sur-ensemble de l'ensemble des langages réguliers. Notamment les langages algébriques ne sont pas clos par intersection. Pour engendrer ces langages, nous utilisons les grammaires déterministes de graphes. Une grammaire de graphes est un système fini de récriture d'hypergraphes finis. Par récriture itérée à partir d'un non-terminal, la grammaire engendre un graphe régulier dont les traces forment un langage algébrique. En définissant une relation de synchronisation entre ces grammaires, on montre que l'on peut définir des sous-ensembles stricts de langages algébriques non-ambigus qui forment des algèbres de Boole effectives contenant les langages réguliers. Nous donnons également des conditions suffisantes pour que ces algèbres booléennes soient closes par concaténation et étoile de Kleene.

L’analyse d’accessibilité est une des composantes de l’analyse de modèles. Elle consiste à modéliser un système complexe par trois ensembles : le langage initial, le langage des configurations indésirables et un système de réécriture. Le langage initial et le langage des configurations indésirables sont des ensembles de termes. Un terme est un mot mais construit à partir de symboles d’arités supérieures à 1. Le système de réécriture représente la dynamique du système complexe. C’est un ensemble de règles qui permettent d’obtenir un nouveau terme à partir d’un terme original. Pour effectuer une analyse d’accessibilité à partir de cette modélisation, on peut calculer l’ensemble des configurations accessibles. Cet ensemble aussi appelé ensemble des descendants est obtenu en appliquant le système de réécriture sur le langage initial jusqu’à ne plus obtenir de nouveaux termes. Une fois l’ensemble des descendants calculé, il reste à faire l’intersection entre celui-ci et l’ensemble des configurations indésirables. Si cette intersection est vide, alors il n’y a pas de configuration indésirable accessible, sinon les configurations présentes dans cette intersection sont accessibles. Cependant, l’ensemble des descendants n’est pas calculable dans le cas général. Pour contourner ce problème, nous calculons une sur-approximation des descendants. Ainsi, si l’intersection est vide, cela signifie toujours qu’aucune configuration indésirable n’est accessible. A contrario, s’il existe un terme dans l’intersection, il n’est pas possible de déterminer s’il s’agit d’un faux positif ou d’une configuration indésirable accessible. La précision de la sur-approximation est alors déterminante. / Reachability analysis is part of model checking. It consists to model complex systems by three sets : initial language, unwanted configurations and rewrite system. The initial language and the unwanted configurations language are sets of terms. Terms are words which are construct with symbols that have an arity that can be greater than 1. The rewrite system represent the dynamic of the complex system. It is a set of rules that permit from a initial term to obtain a new term. One of the approaches to analyze reachability from this modelling is to compute the set of reachable configurations. This set which is called set of descendants is obtained by applying the rewrite system on the initial language until obtaining no more new terms. After the set of descendants is computed, we need to compute the intersection between this set and the unwanted configurations set. If this intersection is empty then there is no unwanted configuration reachable, else the configurations in this intersection are reachable. However, the set of descendants is not computable in the general case. To bypass this problem, we compute an over-approximation of descendants.Now, if the intersection is empty, we keep proving that no unwanted configuration is reachable. Nevertheless, if the intersection is not empty, it is not possible to know if it comes from false-positives or form unwanted reachable configurations. So, the precision of the over-approximation is decisive.

Dans le cadre des théories stables, il a été prouvé qu'une courbe pseudolinéaire était toujours, spécifiquement, linéaire (ce qui correspond dans ce cadre également à localement modulaire): on peut alors caractériser la géométrie de l'ensemble associé, qui est soit projective (avec le type associé à la courbe non-trivial et modulaire), soit affine (quand le type est non-modulaire) sur un corps gauche; lorsque le type associé est trivial, la géométrie est dégénérée. Cela nous permet donc de déduire de la simple pseudolinéarité d'un type la structure de l'ensemble sous-jacent: cette thèse étend ce résultat au cadre des théories simples, ce qui nous permettra à nouveau de détermé de la théorie), mais en se restreignant au cas où k < 4 / In the context of stable theories, it has been proven that a plane curve which is pseudolinear must be linear; it is then possible to deduce the geometry of the associated set, which is either projective (when the type associated to the plane curve is non-trivial and modular), or affine (when the type is non-modular) on a division ring; if the associated type is trivial, the geometry is degenerate. This means we can infer, from a type's pseudolinearity, the structure of the underlying set; this thesis extends this result to the context of simple theories, allowing us to determine the set's geometry (with several differences to account for the fact that the theory is simple and not stable) if we restrict ourselves to k < 4

Les travaux présentés dans ce mémoire, portent essentiellement sur la théorie géométrique des systèmes dynamiques. Ils sont regroupés dans deux sections distinctes qui couvrent l'essentiel de mes recherches :<ul><li> L'étude de la dynamique et de la morphologie des homéomorphismes des surfaces,</li><li>L'utilisation de méthodes géométriques dans l'étude de certaines équations aux dérivées partielles apparaissant en mécanique et en hydrodynamique.</li></ul>Ce mémoire récapitule les travaux de dix-neuf articles groupés par thèmes et présentés dans l'ordre chronologique de leur élaboration.

.

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