Ce travail porte sur les séries à coefficients entiers positifs, sur les séries N-rationnelles et est centré autour de deux types de questions : le problème de la hauteur d'étoile et l'étude des propriétés des distributions de longueurs des codes. On étudie le problème de la hauteur d'étoile de séries rationnelles particulières : les séries N-rationnelles en une variable. On caractérise de différentes façons les séries N-rationnelles qui sont de hauteur d'étoile 1, et on donne un critère permettant de décider de la hauteur d'étoile d'une classe importante de séries N-rationnelles en une variable. L'étude de la hauteur d'étoile des séries N-rationnelles en une variable repose sur l'utilisation des propriétés de leurs représentations par des matrices. On établit, en particulier, à partir d'un résultat d'Handelman, une caractérisation du rayon spectral d'une matrice compagnon irréductible à coefficients entiers positifs. On étudie, ensuite, les distributions de longueurs des codes circulaires et des codes préfixes. On prouve trois nouveaux résultats concernant les codes circulaires. On généralise, dans plusieurs directions, la caractérisation des distributions de longueurs des codes circulaires établie dans le cas d'un alphabet fini par Schützenberger. D'une part, on remplace l'alphabet fini par un alphabet quelconque dont les éléments ont des poids, ce qui permet d'étendre le résultat à deux distributions de longueurs. D'autre part, on restreint les conditions, ce qui permet d'établir la décidabilité dans le cas d'une distribution finie. On donne une nouvelle formulation de cette caractérisation. Ce résultat, établi par des méthodes combinatoires, met en évidence la décidabilité dans le cas d'une distribution finie. On établit une condition nécessaire et suffisante pour qu'une suite d'entiers positifs soit la distribution de longueur d'un code circulaire maximal sur un alphabet fini. Enfin, on met en évidence les liens entre les séries génératrices des codes préfixes rationnels et une classe de séries N-rationnelles : les DOL-séries. On donne une condition suffisante pour qu'une suite N-rationnelle soit la distribution de longueurs d'un code rationnel préfixe maximal sur un alphabet à k lettres.

Cette thèse porte sur la construction d'algorithmes et de programmes parallèles qui s'adapte automatiquement à la plate-forme d'exécution (nombre de processeurs, vitesses des processeurs, ...) et ce, de manière dynamique inconsciente (en anglais oblivious). La construction que nous proposons est basée sur la technologie développée au sein de l'équipe Moais consistant au couplage récursif et dynamique : d'un algorithme séquentiel (qui minimise le nombre d'opérations, mais pas le temps parallèle) ; et d'un algorithme parallèle à grain fin (qui minimise le temps parallèle sur un nombre non borné de ressources, mais pas le nombre d'opérations). Les deux algorithmes sont entrelacés à la volée par un ordonnancement à grain fin de type vol de travail. Outre une analyse théorique du couplage (borne inférieure, optimalité asymptotique), nous proposons une implantation " générique " que nous instancions sur différents exemples (un nouvel algorithme parallèle adaptatif de calcul des préfixes, algorithmes adaptatifs de fusion, de partition et tris, plusieurs algorithmes adaptatifs de la librairie standard C++). Dans cette thèse, nous proposons aussi un nouvel algorithme parallèle statique optimal du calcul des préfixes.

The paper reviews the prefix re-  as it appears in the French language today. As a widely recurrent morpheme with a significance that sometimes completely separates the verb from its base and other times seems almost indiscernible, its properties can be hard to grasp for the non-native learner. While focusing on verbs that lack the common meaning of iteration that the prefix re- usually entails, the paper identifies thirteen lexical definitions of prefixed verbs that reference the base verb as synonymous. Of these thirteen instances, the paper attempts to distinguish the different qualities of the two verb pairs sentir and ressentir, and emplir and remplir respectively, by conducting a series of pragmatic researches. It arrives to the conclusion that the prefix re- presents a difference, if not in sense then in register or actuality, largely dependent of its context. However, said difference is sometimes so subtle that certain contexts allow for the use of either verb.

Cette étude présente une typologie générale des prédicats de mouvement du hongrois. Elle reflète une perception objective et simple du mouvement et de l'espace qui correspond le mieux à la réalité du monde. Le travail s'inscrit dans le cadre de la théorie des classes d'objets développée par Gaston Gross que nous avons appliquée au hongrois, langue non indo-européenne. Du point de vue morphologique, les prédicats de mouvement correspondent à des prédicats verbaux, des prédicats nominaux et, en nombre moins important, des adjectifs prédicatifs. Notre classification s'appuie sur des propriétés sémantiques comme la directionnalité, le mode, le lieu de destination, le but, le lieu source, l'intentionnalité et des propriétés aspectuelles des différents types de mouvement. Ces propriétés sémantiques sont complétées par des propriétés morpho-syntaxiques nécessaires au traitement automatique. <br />La composante contrastive de notre étude nous a permis, d'une part, à l'aide de la traduction, de proposer une meilleure description des classes de prédicats du hongrois et, d'autre part, de relever les différences morpho-syntaxiques et combinatoires spécifiques des deux langues dans l'expression du mouvement, comme le rôle des préfixes verbaux, des compléments locatifs ainsi que l'importance des prédicats nominaux.

Internet est constitué de milliers de systèmes autonomes (Autonomous Systems, AS) qui échangent des informations de routage grâce au protocole BGP (Border Gateway Protocol). Chaque AS attend des autres qu'il lui donne des informations de routage correctes, et leur accorde donc une confiance totale. Le détournement de préfixe (prefix hijacking) exploite cette confiance afin d'introduire des routes falsifiées. Les techniques qui détectent cette attaque génèrent un nombre important d'alertes, composé de faux positifs résultant d'opérations de routage courantes. Dans cette dissertation, nous cherchons à trouver la cause principale de ces alertes, de manière indubitable. A cette fin, d'une part, nous réduisons le nombre d'alertes en analysant en profondeur ces réseaux, dont nous dérivons une série de structures qui reflètent les pratiques standard de routage du monde réel, et en considérant le risque associé à ces structures lors une attaque par détournement. D'autre part, nous utilisons des bases de données auxiliaires qui nous permettent de connaître la raison derrière un évènement de routage, qui n'est, en général, connue que du propriétaire du réseau. Précisément, nous regardons les préfixes à origines multiples (Multiple Origin AS, MOAS), et mettons en évidence une classification nous permettant d'éliminer 80% des alertes. Nous présentons un cas réel où un MOAS coïncide avec du spam et des sites d'arnaque en ligne. Nous étudions les préfixes non-disjoints, et présentons un prototype permettant d'éliminer 50% des alertes sub-MOAS.Nous explorons l'espace IP non assigné, cherchons des adresses IP joignables, et localisons une grande quantité de spam et des sites d'arnaques en ligne. / The Internet is composed of tens of thousands Autonomous Systems (ASes) that exchange routing information using the Border Gateway Protocol (BGP). Consequently, every AS implicitly trusts every other ASes to provide accurate routing information. Prefix hijacking is an attack against the inter-domain routing infrastructure that abuses mutual trust in order to propagate fallacious routes. The current detection techniques pathologically raise a large number of alerts, mostly composed of false positives resulting from benign routing practices. In this Dissertation, we seek the root cause of routing events beyond reasonable doubts. First, we reduce the global number of alerts by analyzing false positive alerts, from which we extract constructs that reflect real-world standard routing practices. We then consider the security threat associated with these constructs in a prefix hijacking scenario. Second, we use a variety of auxiliary datasets that reflect distinct facets of the networks involved in a suspicious routing event in order to closely approximate the ground-truth, which is traditionally only known by the network owner. Specifically, we investigate Multiple Origin AS (MOAS) prefixes, and introduce a classification that we use to discard up to 80% of false positive. Then we show a real-world case where a MOAS coincided with spam and web scam traffic. We look at prefix overlaps, clarify their global use, and present a prototype that discards around 50% of false positive sub-MOAS alerts. Finally, we explore the IP blackspace, study the routing-level characteristics of those networks, find live IP addresses, and uncover a large amount of spam and scam activities.

La résolution du problème d'allocation de charge représente un enjeu important dans l'exploitation des machines parallèles. Nous faisons d'abord une étude bibliographique de ce problème dans le cadre des architectures à mémoire distribuée en mettant l'accent sur l'allocation dynamique, plus précisément sur l'équilibrage et la régulation de charges régulières. Une stratégie originale de régulation basée sur un calcul de préfixe généralisé est proposée. Elle s'avère à la fois correcte, exacte et indépendante du réseau d'interconnexion de processeurs. Un noyau de régulation de charge basé sur cette stratégie est développé. Nous poursuivons ensuite avec une analyse de son temps total d'exécution. Nous trouvons qu'une loi de probabilité de Gumbel modélise le temps maximal d'exécution. A partir de ce résultat nous inférons des politiques d'initiation et de décision pour la mise en oeuvre de là stratégie proposée. L'algorithme de régulation ainsi obtenu est donc efficace. Une application de simulation des phénomènes mécaniques, déformation-recristallisation à chaud des agrégats polycristallins, est développée. Pour cette application dynamique nous utilisons le noyau de régulation de charge avec les politiques d'initiation et décision proposés. L'algorithme complet s'avère en pratique correct, stable et efficace.

Cette thèse est une description des marqueurs verbaux de lètὲɣὲ (téké) langue bantu parlée au Gabon (B71a). Les marqueurs verbaux étudiés sont : le préfixe verbal (marque d’accord), le marqueur de négation kâ…ŋí, les particules énonciatives mâ et mí et la finale verbale. De nombreux linguistes bantouistes considèrent ce domaine d’étude (marqueurs verbaux) comme étant complexe, c’est le cas de Guarisma (2000). Le nombre de marqueurs verbaux en est une des raisons de cette complexité. Il est difficile d’assigner un rôle à certains morphèmes. Elle s’inscrit dans le cadre Théorique des Opérations Prédicatives et Enonciatives (TOPE), élaboré par Culioli et ses collaborateurs, voir Culioli (1990,1999a). L’étude de ces morphèmes montre que chacun marque une opération linguistique spécifique. / This thesis is a description of verbal markers in lètὲɣὲ (Téké), a Bantu language spoken in Gabon (B 71a). The verbal markers studied are: the verbal prefix (mark of agreement), the negation marker kâ ... ŋí, the enunciating particles mâ and mí and the verbal final. Many Bantuist linguists consider this field of study (verbal markers) to be complex, as is the case with Guarisma (2000). The number of verbal markers is one of the reasons for this complexity. This work is conducted within the framework of the Theory of the Predicative and Enunciative Operations developed by Culioli (1990) and his collaborators. The enunciative study of these elements shows that each of them marks a specific linguistic operation.

Cette thèse étudie la problématique de l’indexation et de la recherche dans les tables de hachage distribuées –Distributed Hash Table (DHT). Elle propose un système de stockage distribué des résumés de documents en se basant sur leur contenu. Concrètement, la thèse utilise les Filtre de Blooms (FBs) pour représenter les résumés de documents et propose une méthode efficace d’insertion et de récupération des documents représentés par des FBs dans un index distribué sur une DHT. Le stockage basé sur contenu présente un double avantage, il permet de regrouper les documents similaires afin de les retrouver plus rapidement et en même temps, il permet de retrouver les documents en faisant des recherches par mots-clés en utilisant un FB. Cependant, la résolution d’une requête par mots-clés représentée par un filtre de Bloom constitue une opération complexe, il faut un mécanisme de localisation des filtres de Bloom de la descendance qui représentent des documents stockés dans la DHT. Ainsi, la thèse propose dans un deuxième temps, deux index de filtres de Bloom distribués sur des DHTs. Le premier système d’index proposé combine les principes d’indexation basée sur contenu et de listes inversées et répond à la problématique liée à la grande quantité de données stockée au niveau des index basés sur contenu. En effet, avec l’utilisation des filtres de Bloom de grande longueur, notre solution permet de stocker les documents sur un plus grand nombre de serveurs et de les indexer en utilisant moins d’espace. Ensuite, la thèse propose un deuxième système d’index qui supporte efficacement le traitement des requêtes de sur-ensembles (des requêtes par mots-clés) en utilisant un arbre de préfixes. Cette dernière solution exploite la distribution des données et propose une fonction de répartition paramétrable permettant d’indexer les documents avec un arbre binaire équilibré. De cette manière, les documents sont répartis efficacement sur les serveurs d’indexation. En outre, la thèse propose dans la troisième solution, une méthode efficace de localisation des documents contenant un ensemble de mots-clés donnés. Comparé aux solutions de même catégorie, cette dernière solution permet d’effectuer des recherches de sur-ensembles en un moindre coût et constitue est une base solide pour la recherche de sur-ensembles sur les systèmes d’index construits au-dessus des DHTs. Enfin, la thèse propose le prototype d’un système pair-à-pair pour l’indexation de contenus et la recherche par mots-clés. Ce prototype, prêt à être déployé dans un environnement réel, est expérimenté dans l’environnement de simulation peersim qui a permis de mesurer les performances théoriques des algorithmes développés tout au long de la thèse. / This thesis examines the problem of indexing and searching in Distributed Hash Table (DHT). It provides a distributed system for storing document summaries based on their content. Concretely, the thesis uses Bloom filters (BF) to represent document summaries and proposes an efficient method for inserting and retrieving documents represented by BFs in an index distributed on a DHT. Content-based storage has a dual advantage. It allows to group similar documents together and to find and retrieve them more quickly at the same by using Bloom filters for keywords searches. However, processing a keyword query represented by a Bloom filter is a difficult operation and requires a mechanism to locate the Bloom filters that represent documents stored in the DHT. Thus, the thesis proposes in a second time, two Bloom filters indexes schemes distributed on DHT. The first proposed index system combines the principles of content-based indexing and inverted lists and addresses the issue of the large amount of data stored by content-based indexes. Indeed, by using Bloom filters with long length, this solution allows to store documents on a large number of servers and to index them using less space. Next, the thesis proposes a second index system that efficiently supports superset queries processing (keywords-queries) using a prefix tree. This solution exploits the distribution of the data and proposes a configurable distribution function that allow to index documents with a balanced binary tree. In this way, documents are distributed efficiently on indexing servers. In addition, the thesis proposes in the third solution, an efficient method for locating documents containing a set of keywords. Compared to solutions of the same category, the latter solution makes it possible to perform subset searches at a lower cost and can be considered as a solid foundation for supersets queries processing on over-dht index systems. Finally, the thesis proposes a prototype of a peer-to-peer system for indexing content and searching by keywords. This prototype, ready to be deployed in a real environment, is experimented with peersim that allowed to measure the theoretical performances of the algorithms developed throughout the thesis.

Cette thèse constitue une étude sémantique du préfixe verbal s- des verbes russes issus d'emprunts. Elle applique une approche théorique dérivée principalement de la Linguistique Cognitive Slave [LCS]. Quatre problèmes de recherche ont été identifiés : (i) la combinaison du préfixe s- avec les verbes russes issus d'emprunts ; (ii) la question de la préfixation vide ; (iii) la productivité du préfixe s- des verbes russes issus d'emprunts par rapport à la productivité concurrentielle du préfixe russe po- ; et (iv) l'hypothèse de Pallomorphe s-l-nu-. La méthodologie mise en place est à la fois qualitative et quantitative. La méthode qualitative concerne les recherches en bibliothèque et les recherches en ligne de sources d'expressions russe, française, allemande et anglaise, de même que des enquêtes effectuées par l'entremise d'un questionnaire et de fréquentes consultations de linguistes d'origine russe. La méthode quantitative comporte une recherche sur Google afin de déterminer le nombre de résultats obtenus à partir d'un choix de 82 verbes issus d'emprunts contenant le préfixe s-. Le nombre de résultats ainsi obtenus donne une indication de la fréquence relative avec laquelle ces verbes apparaissent dans la base de données Google en langue russe. Les résultats ont été classés sur une échelle de Likert, allant d'une fréquence « extrêmement faible » à une fréquence « extrêmement élevée ». Des 82 verbes issus d'emprunts contenant le préfixe s- utilisés pour cette recherche, 28 se sont avérés d'un usage « extrêmement élevé » ou « élevé ». Notre analyse ultérieure de ces 28 verbes a révélé que le préfixe s- pouvait avoir l'un des trois sens suivants : spatial, temporel ou amalgame. De ces 28 verbes, 15 ont un sens spatial dominant, 9 ont un sens temporel dominant et 4 sont dans la catégorie dite « amalgame ». En bref, leur sens spatial prédomine. Enfin, les quatre problèmes de recherche identifiés au début de notre étude ont été systématiquement abordés.

Nous proposons une technique de dépliage pour vérifier les systèmes concurrents infinis bien structurés. Certaines propriétés d'intérêt comme la bornitude, la couverture et la terminaison sont décidables grâce à la bonne structure de ces systèmes. D'autre part, le dépliage réduit efficacement l'explosion combinatoire en exploitant l'ordre partiel entre les événements des systèmes concurrents. Nous proposons une modélisation par structure d'événements pour des systèmes bien structurés élémentaires, tels les compteurs et les files de communication. Le dépliage d'un réseau de structures d'événements étant une structure d'événements, nous proposons ensuite une approche hiérarchique à la modélisation et à la vérification des systèmes, qui préserve la bonne structure. Enfin, nous proposons une technique d'élimination des événements redondants. La mise en œuvre de notre approche dans l'outil ESU nous permet de conclure à son efficacité. / We propose an unfolding technique for verifying concurrent infinite-state systems that are well-structured. Some properties of interest such as boundedness, coverability and termination are decidable thanks to the well-structure of these systems. Moreover, the unfolding effectively reduces the combinatorial explosion by exploiting the partial order between events of concurrent systems. We propose a modelization using event structures for basic well-structured systems, such as counters and communication channels. As the unfolding of a synchronized product of event structures is an event structure, we obtain a hierarchical approach to modeling as well as to verifying systems, which preserves the well-structure. Finally, we propose a technique for eliminating redundant events. The implementation of our approach in the ESU tool allows us to conclude on its efficiency.