Cette thèse contribue à l’étude de la fiabilité et de la sécurité-innocuité des systèmes informatisés, modélisés par des systèmes à événements discrets. Les principales contributions concernent la théorie des Systèmes de Contrôle (notés C Systems) et l’approche par Monitoring des modèles.Dans la première partie de la thèse, nous étudions la théorie des Systèmes de Contrôle qui combine et étend de façon significative, les systèmes de réécriture de la théorie des langages et le contrôle supervisé. Un système de contrôle est une structure générique qui contient deux composants : le composant contrôlé et le composant contrôlant qui restreint le comportement du composant contrôlé. Les deux composants sont exprimés en utilisant le même formalisme comme des automates ou des grammaires. Nous considérons différentes classes de systèmes de contrôle basés sur différents formalismes comme, par exemple, les automates, les grammaires, ainsi que leurs versions infinies et concurrentes. Ensuite, une application de cette théorie est présentée. Les systèmes de contrôle basés sur les automates de Büchi sont utilisés pour vérifier par model-checking, des propriétés définissant la correction sur des traces d’exécution spécifiées par une assertion de type nevertrace.Dans la seconde partie de la thèse, nous investiguons l’approche de monitoring des modèles dont la théorie des systèmes de contrôle constitue les fondations formelles. Le principe pivot de cette approche est la «spécification de propriétés comme contrôleur». En d’autres termes, pour un système, les exigences fonctionnelles, d’une part, et des propriétés, d’autre part, sont modélisées et implantées séparément, les propriétés spécifiées contrôlant le comportement issu des exigences fonctionnelles. De cette approche découle ainsi deux techniques alternatives, respectivement nommées monitoring de modèle et génération de modèle. Cette approche peut être utilisée de diverses manières pour améliorer la fiabilité et la sécurité-innocuité de divers types de systèmes. Nous présentons quelques applications qui montrent l’intérêt pratique de cette contribution théorique. Tout d’abord, cette approche aide à prendre en compte les évolutions des spécifications des propriétés. En second lieu, elle fournit une base théorique à la sécurité fonctionnelle, popularisée par la norme IEC 61508. En troisième lieu, l’approche peut être utilisée pour formaliser et vérifier l’application de guides de bonnes pratiques ou des règles de modélisation appliquées par exemple pour des modèles UML.Ces résultats constituent les bases pour des études futures de dispositifs plus perfectionnés, et fournissent une nouvelle voie pour s’assurer de la fiabilité et de la sécurité-innocuité des systèmes / This thesis contributes to the study of reliability and safety of computer and software systems which are modeled as discrete event systems. The major contributions include the theory of Control Systems (C Systems) and the model monitoring approach.In the first part of the thesis, we study the theory of control systems which combines and significantly extends regulated rewriting in formal languages theory and supervisory control. The control system is a generic framework, and contains two components: the controlled component and the controlling component that restricts the behavior of the controlled component. The two components are expressed using the same formalism, e.g., automata or grammars. We consider various classes of control systems based on different formalisms, for example, automaton control systems, grammar control systems, and their infinite versions and concurrent variants. After that, an application of the theory is presented. The Büchi automata based control system is used to model and check correctness properties on execution traces specified by nevertrace claims.In the second part of the thesis, we investigate the model monitoring approach whose theoretical foundation is the theory of control systems. The key principle of the approach is “property specifications as controllers”. In other words, the functional requirements and property specification of a system are separately modeled and implemented, and the latter one controls the behavior of the former one. The model monitoring approach contains two alternative techniques, namely model monitoring and model generating. The approach can be applied in several ways to improve reliability and safety of various classes of systems. We present some typical applications to show its strong power. First, the approach provides better support for the change and evolution of property specifications. Second, it provides the theoretical foundation of safety-related systems in the standard IEC 61508 for ensuring the functional validity. Third, it is used to formalize and check guidelines and consistency rules of UML.These results lay out the foundations for further study of more advanced control mechanisms, and provide a new way for ensuring reliability and safety

Dans ce mémoire de recherche-création en littératures de langue française, j’aborde la question des rapports entre les procédés de réécriture (par exemple, l’intertextualité, l’intratextualité et l’autotextualité, mais aussi les figures de la répétition et de la correction) et l’effet de défamiliarisation (ou de distanciation) au moyen d’un essai sur le roman Mercier et Camier de Samuel Beckett et d’une création littéraire de mon cru : un livre-objet constitué de trente et une feuilles non paginées et non reliées, sur lesquelles je réécris autant de fois l’incipit de Bouvard et Pécuchet, de Gustave Flaubert, en recourant à une mise en page qui défie le mode de lecture linéaire. Autant mon essai que ma création s’appliquent à montrer que les procédés de réécriture peuvent être employés pour produire un effet de défamiliarisation visant la fonction représentative de la littérature. / In this creative Master’s Thesis in French Literature, I addess the issue of the relationship between processes of rewriting (eg, intertextuality, intratextuality and autotextuality, but also the figures of repetition and correction) and defamiliarization (or the distancing effect) by the means of an essay on the novel Mercier et Camier by Samuel Beckett and of a literary creation of my own, consisting of thirty-one unbounded and unpaginated sheets, on which I rewrote as many times the incipit of Bouvard et Pecuchet by Gustave Flaubert in a layout that defies linear reading. Both my essay and my creation intend to show that processes of rewriting can be used to defamiliarize the representative function of literature.

L’œuvre de Nelly Arcan s’inscrit dans un pan de la littérature contemporaine accueillant les monstres comme figures de la transgression qui, par leur é-normité, interrogent la norme dont ils s’écartent. Ces êtres à la fois fascinants et inquiétants hantent la littérature depuis les récits fondateurs de la mythologie antique. Arcan, à l’instar de plusieurs femmes auteurs, recourt au procédé de la réécriture de plusieurs grands mythes grecs dans Folle (2004) et À ciel ouvert (2007). Dans les deux récits, elle met en scène des personnages en fuite qui, face à leur destin néfaste, se métamorphosent en femmes-monstres et en hommes-monstres. Les personnages masculins empruntent des traits à Jason, Narcisse et Pygmalion, mais sont, par leur déviance sexuelle et leur propension à la domination, beaucoup plus monstrueux que leurs modèles antiques. Contaminées par la monstruosité des hommes qu’elles aiment jusqu’à l’annihilation de soi, les protagonistes des deux récits affichent certains traits de Médée, de Méduse et des Amazones, tirant parti de la puissance de ces figures nocives pour donner une leçon aux personnages masculins. Elles acquièrent ainsi de nouveau leur statut de sujet. Dans ce mémoire, il s’agira, par le biais de la mythocritique, des théories de la réécriture et de l’effet-personnage, d’étudier les causes, le processus et les effets du « devenir-monstre » des personnages féminins et d’examiner la reconfiguration de mythes antiques par Arcan. En s’intéressant à la greffe des mythes antiques sur les personnages arcaniens, au déplacement et au renversement des mythèmes caractéristiques des figures prédécesseures, cette recherche espère montrer comment Nelly Arcan dissèque les relations de couple qui mènent au « devenir-monstre » des partenaires. Il ressortira de cette analyse une vision apocalyptique du vivre ensemble, entre hommes et femmes, qui rejoue l’ancienne « guerre des sexes » que l’on croyait terminée. / Nelly Arcan’s body of work is in line with a trend in contemporary writing to represent the monster as a transgressive figure, which, through its own “e-normity,” steps out of the norm and questions it. Both fascinating and unnerving, the monster has haunted literature since the tales of ancient mythology came into existence. Following the steps of many women writers, Arcan rewrites numerous Greek myths in Folle (2004) and À ciel ouvert (2007). These novels narrate the stories of characters who transform into monsters due to their ill-fated destinies. The male characters are inspired by Jason, Narcissus and Pygmalion. However, their sexual deviance and tendency to dominate make them much more monstrous than their ancient models. Contaminated by the monstrosity of the men they love to the point of self-annihilation, Arcan’s female protagonists share some characteristics with Medea, Medusa and the Amazons. They gain power from these dangerous mythological figures to teach lessons to the monstrous males, thereby claiming possession of their own subjectivities. Using literary approaches such as mythocritique, theories of rewriting, and theories of character, this research will focus on the causes, processes and effects of the female characters’ “becoming-monster” and will study Arcan’s reconfiguration of ancient myths. Through an examination of the merging of these myths and an analysis of the displacement and upending of their distinctive mythemes, this master’s thesis hopes to show how Arcan dissects love relationships that lead to the “becoming-monster” of the partners involved. This analysis will bring out Arcan’s apocalyptic vision of co-habitation, a vision which re-enacts the war of the sexes that we thought ended long ago.

Le tournant des XXe et XXIe siècles coïncide avec l’essor de la littérature fantasy, héritière de nombreuses formes littéraires et cinématographiques. Plusieurs œuvres de ce corpus récent procèdent au renouvellement des paramètres conventionnels de la fantasy. Pierre Bottero prend part à cet effort par le truchement de la figure singulière d’une femme, Ellana, appartenant à la guilde des marchombres, et dont la quête de liberté renvoie à la recherche de dépassement de l’auteur. Après l’écriture de La Quête d’Ewilan (2003) et Les Mondes d’Ewilan (2005), Bottero se détourne en effet de la tradition tolkiénienne et de la légende arthurienne afin de mettre au point Le Pacte des marchombres, une trilogie qui relate l’émancipation du personnage d’Ellana par sa pratique d’une écriture « poétique ». Le présent mémoire explore les potentialités de l’écriture fantasy qui se déploient au sein du récit Ellana (2006), premier volet de la dernière trilogie de Bottero. Ellana relève d’une pratique particulière de l’écriture transfictionnelle – le prequel – qui s’effectue à rebours. Bottero substitue à la figure de Merlin, mythe fondateur de ses premières trilogies, celle d’Ellana, qui en vient à jouer un rôle central au sein du cycle alavirien. Nous mettons en relief les principaux traits du genre fantasy dans le but d’identifier les topoï qu’Ellana reconduit ou transgresse. Parallèlement, nous procédons à l’étude de l’imaginaire bottérien dont la figure d’Ellana est tributaire. En faisant de la protagoniste une figure mythique, l’auteur construit l’image d’un féminin à la fois sauvage et gracieux que rien n’empêche de vivre indépendamment des hommes. / Fantasy literature, heiress of many literary and cinematographic forms, has developed rapidly at the turn of the XXth and XXIst centuries. In this recent corpus, several works concur to the renewal of the conventional parameters of fantasy. Pierre Bottero takes part in this joint action through a singular feminine figure, Ellana, who belongs to the marchombre guild, and whose freedom quest refers to the author’s goal to dispel the commonplaces of fantasy genre. Indeed, after the writing of La Quête d’Ewilan (2003) and Les Mondes d’Ewilan (2005), Bottero moves away from tolkienian tradition and arthurian legend in order to create Le Pacte des marchombres, a trilogy relating the emancipation of Ellana’s figure by the way of a “poetical” writing practice. This thesis searches for fantasy writing’s potentialities that are observable in the book Ellana (2006), first volume of Bottero’s final trilogy. Ellana comes under a particular transfictional writing practice – the prequel – that is done back to front. While the first trilogies of Bottero are based on Merlin’s myth, the author changes the focus to Ellana’s figure who plays a pivotal role in the alavirian cycle. We highlight the main features of the fantasy genre with the aim to identify the topoï that Ellana renews or infringes. At the same time, we set about studying the botterian imaginary that Ellana’s figure is dependent on. By turning the protagonist into a mythical figure, the author builds the image of a wild yet graceful feminine that nothing prevents from living apart from men.

De nos jours, des masses de données sont publiées à grande échelle dans des formats numériques. Une part importante de ces données a une structure complexe, typiquement organisée sous la forme d'arbres (les documents du web, comme HTML et XML, étant les plus représentatifs) ou de graphes (en particulier, les bases de données du Web Sémantique structurées en graphes, et exprimées en RDF). Exploiter ces données complexes, qu'elles soient dans un format d'accès Open Data ou bien propriétaire (au sein d'une compagnie), présente un grand intérêt. Le faire de façon efficace pour de grands volumes de données reste encore un défi. Les vues matérialisées sont utilisées depuis longtemps pour améliorer considérablement l'évaluation des requêtes. Le principe est q'une vue stocke des résultats pre-calculés qui peuvent être utilisés pour évaluer (une partie d') une requête. L'adoption des techniques de vues matérialisées dans le contexte de données du web que nous considérons est particulièrement exigeante à cause de la complexité structurelle et sémantique des données. Cette thèse aborde deux problèmes liés à la gestion des données du web basée sur des vues matérialisées. D'abord, nous nous concentrons sur le problème de sélection des vues pour des ensembles de requêtes RDF. Nous présentons un algorithme original qui, basé sur un ensemble de requêtes, propose les vues les plus appropriées à matérialiser dans la base des données. Ceci dans le but de minimiser à la fois les coûts d'évaluation des requêtes, de maintenance et de stockage des vues. Bien que les requêtes RDF contiennent typiquement un grand nombre de jointures, ce qui complique le processus de sélection de vues, notre algorithme passe à l'échelle de centaines de requêtes, un nombre non atteint par les méthodes existantes. En outre, nous proposons des techniques nouvelles pour tenir compte des données implicites qui peuvent être dérivées des schémas RDF sans complexifier davantage la sélection des vues. La deuxième contribution de notre travail concerne la réécriture de requêtes en utilisant des vues matérialisées XML. Nous commençons par identifier un dialecte expressif de XQuery, correspondant aux motifs d'arbres avec des jointures sur la valeur, et nous étudions des propriétés importantes de ces requêtes, y compris l'inclusion et la minimisation. En nous fondant sur ces notions, nous considérons le problème de trouver des réécritures minimales et équivalentes d'une requête exprimée dans ce dialecte, en utilisant des vues matérialisées exprimées dans le même dialecte, et nous fournissons un algorithme correct et complet à cet effet. Notre travail dépasse l'état de l'art en permettant à chaque motif d'arbre de renvoyer un ensemble d'attributs, en prenant en charge des jointures sur la valeur entre les motifs, et en considérant des réécritures qui combinent plusieurs vues. Enfin, nous montrons comment notre méthode de réécriture peut être appliquée dans un contexte distribué, pour la dissémination efficace d'un corpus de documents XML annotés en RDF. / Data is being published in digital formats at very high rates nowadays. A large share of this data has complex structure, typically organized as trees (Web documents such as HTML and XML being the most representative) or graphs (in particular, graph-structured Semantic Web databases, expressed in RDF). There is great interest in exploiting such complex data, whether in an Open Data access model or within companies owning it, and efficiently doing so for large data volumes remains challenging. Materialized views have long been used to obtain significant performance improvements when processing queries. The principle is that a view stores pre-computed results that can be used to evaluate (possibly part of) a query. Adapting materialized view techniques to the Web data setting we consider is particularly challenging due to the structural and semantic complexity of the data. This thesis tackles two problems in the broad context of materialized view-based management of Web data. First, we focus on the problem of view selection for RDF query workloads. We present a novel algorithm, which, based on a query workload, proposes the most appropriate views to be materialized in the database, in order to minimize the combined cost of query evaluation, view maintenance and view storage. Although RDF query workloads typically feature many joins, hampering the view selection process, our algorithm scales to hundreds of queries, a number unattained by existing approaches. Furthermore, we propose new techniques to account for the implicit data that can be derived by the RDF Schemas and which further complicate the view selection process. The second contribution of our work concerns query rewriting based on materialized XML views. We start by identifying an expressive dialect of XQuery, corresponding to tree patterns with value joins, and study some important properties for these queries, such as containment and minimization. Based on these notions, we consider the problem of finding minimal equivalent rewritings of a query expressed in this dialect, using materialized views expressed in the same dialect, and provide a sound and complete algorithm for that purpose. Our work extends the state of the art by allowing each pattern node to return a set of attributes, supporting value joins in the patterns, and considering rewritings which combine many views. Finally, we show how our view-based query rewriting algorithm can be applied in a distributed setting, in order to efficiently disseminate corpora of XML documents carrying RDF annotations.

L’exode rural des Maori suivant la seconde guerre mondiale a bouleversé le paysage socioculturel néo-zélandais. Cette thèse explore une de ses conséquences directes : l’émergence de gangs maori comme tentative de re-territorialisation de l’espace environnant dans une logique de différentiation par rapport à l’ordre établi. La rupture avec la ville européenne et les traditions ancestrales maori s’imposait. Le gang dit « maori » ne pouvait, et ne peut plus, dès lors être pensé dans le prolongement du tribalisme et du bellicisme maori pré-colonial, analyse figeant le Maori dans des considérations essentialistes. Cette thèse présente le gang maori comme un produit historique contingent et vise, sans cautionner l’approche essentialiste, à déterminer les effets de cette posture analytique sur les pratiques quotidiennes du membre de gang, ainsi que ses rapports au public.Les gangs, qui souhaitaient inventer un espace qui leur était propre, finirent par admettre leur héritage maori, si bien que les membres allaient non seulement réécrire l’histoire de leur organisation en lui trouvant d’autres origines, mais aussi celle du passé maori pré-colonial en y introduisant des éléments propres au gang de rue contemporain / The Maori urban drift after the Second World War has deeply altered New Zealand’s sociocultural landscape. This thesis explores one of its direct aftermath: the emergence of Maori gangs as an attempt to reterritorialise the surrounding space in a logic of differen-tiation from the established order. Therefore, breaking off with the European city and Maori ancestral traditions was required. In this respect, so called “Maori” gangs could and can no longer be thought as the extension of Maori tribalism and precolonial belli-cism. This type of analysis freezes the Maori into essentialist considerations. This thesis introduces the Maori gang in its historical contingent dimension and aims – without sup-porting the essentialist approach – at pinpointing its very effects on gang members’ daily practices and also on their relationship with wider society.The same gangs that wanted to create their own space ended up acknowledging their Maori heritage. As a result, the members were not only to rewrite the history of their or-ganisation, as they found out other origins, but also precontact Maori history as they in-troduced elements that are typical of contemporary street gangs

Ce mémoire est constitué de 3 parties.La NP-complétude de la satisfaction de combinaisons booléennes de contraintes de sous-arbres est démontrée dans l'article [Ven87] ; la partie I de ce mémoire étudie dans quelle mesure l'ajout de contraintes régulières laisse espérer conserver la complexité NP. Ce modèle étendu définit une nouvelle classe de langages dont l'expressivité est comparée à celle des Rigid Tree Automata [JKV11]. Puis un début de formalisation des t-dags est donné.Les patterns ont été étudiés, principalement du point de vue des contraintes sur les données qu'ils demandent. La partie II de ce mémoire les étudie plus finement, en mettant de côté les données. Les squelettes sont définis en tant qu'intermédiaire de calcul et le fait que leur syntaxe caractérise leur sémantique est démontré. Puis un lemme de pompage est donné dans un cas restreint, un autre dans le cas général est étudié et conjecturé. Ensuite des fragments de combinaisons booléennes de patterns sont comparés en expressivité pour terminer avec l'étude de la complexité des problèmes de model-checking, satisfaisabilité et DTD-satisfaisabilité sur les dits fragments.Le contenu de la partie III constitue l'article [FMS11], c'est la démonstration de la caractérisation des langages des automates fortement déterministes de niveau 2 par des systèmes d'équations récurrentes caténatives. Celle-ci utilise, entre autres, des techniques de réécriture, la notion d'inconnues non-réécrivables et les ordres noethériens. Cette caractérisation constitue le cas de base de la récurrence démontrée dans [Sén07]. / This thesis is in 3 parts.The NP-completeness of satisfiability of boolean combinations of subtree constraints is shown in the article [Ven87] ; in the part I of this thesis, we study whether adding regular contraints lets hope for keeping the same complexity. This extended model defines a new class of languages which is compared in expressivity to the Rigid Tree Automata [JKV11]. Then a begining of formalisation of the t-dags is developped.The patterns have been studied mainly from the point of view of the constraints they demand on the data. The part II of this thesis study them more finely, by putting aside the data. The skeletons are defined as calculus intermediate and the characterisation holding between their syntax and their semantics is shown. Then a pumping lemma is prooved in a restreict case, another one is conjectured in the most general case. Then fragments of boolean combinations of patterns are compared in expressivity, this parts ends with the study of complexity of model-checking, satisfiability and DTD-satisfiability on these fragments.The content of part III constitutes the article [FMS11], it is the demonstration of the characterisation of strongly-deterministic 2-level pushdown automata by recurrent catenative equation systems. This proof uses in particular, some rewriting techniques, unrewritable unknowns and noetherian orders. This characterisation provides the base case of the recurrence shown in [Sén07].

Peaks andThe main subject of this thesis is diagram rewriting.This is a generalisation to dimension~$2$ of word rewriting (in dimension~$1$). In a first time, we give the first convergent diagrammatic presentation of the PRO of linear maps in arbitrary field. Then we study the convergent diagrammatic presentation of matrix of isometries of $RR^n$. We focus especially on a rule similar to the Yang-Baxter equation, described by a certain map $h$. We use the confluence of critical the parametric diagrams, To study the algebraic properties of $h$, Finally, we present the $Sigma$-diagrams, an alternative approach for calculation in bialgebras. We illustrate this approach with examples. The last two chapters have been already published: Diagram rewriting for orthogonal matrices: a study of critical peaks, avec Yves Lafont, Lecture Notes in Computer Science 5117, p. 232-245, 2008 Properties of co-operations: diagrammatic proofs, Mathematical Structures in Computer Science 22(6), p. 970-986, 2012. / The main subject of this thesis is diagram rewriting.This is a generalisation to dimension~$2$ of word rewriting (in dimension~$1$). In a first time, we give the first convergent diagrammatic presentation of the PRO of linear maps in arbitrary field. Then we study the convergent diagrammatic presentation of matrix of isometries of $RR^n$. We focus especially on a rule similar to the Yang-Baxter equation, described by a certain map $h$. We use the confluence of criticalthe parametric diagrams, To study the algebraic properties of $h$, Finally, we present the $Sigma$-diagrams, an alternative approach for calculation in bialgebras. We illustrate this approach with examples. The last two chapters have been already published: Diagram rewriting for orthogonal matrices: a study of critical peaks, avec Yves Lafont, Lecture Notes in Computer Science 5117, p. 232-245, 2008 Properties of co-operations: diagrammatic proofs, Mathematical Structures in Computer Science 22(6), p. 970-986, 2012.

L’objectif principal de cette thèse est l’étude et la formalisation de nouvelles constructions permettant d’augmenter l’expressivité du filtrage et des langages à base de règles en général. Ceci est motivé par le développement de Tom, un système qui enrichit les langages impératifs comme Java et C avec des constructions de haut niveau comme le filtrage et les stratégies. Une première extension que l’on propose est la notion d’anti-patterns, i.e. des motifs qui peuvent contenir des symboles de complément. Nous définissons de manière formelle la sémantique des anti-patterns dans le cas syntaxique et modulo une théorie équationnelle arbitraire. Puis nous étendons la notion classique de filtrage entre les motifs et les termes clos au filtrage entre les anti-patterns et les termes clos (anti-filtrage). Ensuite, nous proposons plusieurs extensions aux constructions de filtrage fournies par Tom. La condition pour l’application d’une règle devient une conjonction ou disjonction de contraintes de filtrage et d’anti-filtrage ainsi que d’autres types de conditions. Les techniques classiques de compilation du filtrage ne sont pas bien adaptées à ces conditions complexes. On propose donc une nouvelle méthode de compilation basée sur des systèmes de réécriture contrôlés par des stratégies. Nous avons complètement réécrit le compilateur de Tom en utilisant cette technique. Tous ces éléments rassemblés constituent un environnement pour décrire et implémenter des transformations de manière élégante et concise. Pour promouvoir son utilisation dans des projets à grand échelle, on développe une technique pour extraire automatiquement des informations structurelles à partir d’une hiérarchie de classes Java. Cela permet l’intégration du filtrage offert par Tom dans n’importe quelle application Java / The main objective of this thesis is the study of new constructs and formalisms that increase the expressivity of pattern matching and rule based languages in general. This is motivated by the development of Tom, a system that adds high level constructs such as pattern matching and strategies to languages like Java and C. A first extension that we propose is the notion of anti-patterns, i.e. patterns that may contain complement symbols. We define formally the semantics of anti-patterns both in the syntactic case and modulo an arbitrary equational theory. We then extend the classical notion of matching between patterns and ground terms to matching between anti-patterns and ground terms. We further propose several extensions to the matching constructs provided by Tom. Consequently, the condition for the application of a rule becomes a combination of matching and anti-matching constraints together with other types of conditions. Classical compilation techniques for pattern matching are not very well suited for these complex conditions. Therefore we propose a new compilation method based on rewrite systems controlled by strategies, which provides a high level of modularity. Tom’s compiler has been rewritten from scratch using this technique. All this constitutes a software environment for expressing transformations in a clear and concise way. To promote its use in large scale applications, we propose an approach for extracting automatically structural information from arbitrary Java hierarchies. This allows a seamless integration of Tom’s pattern matching facilities in any application

Le langage XML est devenu un standard de représentation et d'échange de données à travers le web. Le but de la réplication de données au sein de différents sites est de minimiser le temps d'accès à ces données partagées. Cependant, différents problèmes sont liés à la sécurisation de ces données. Le but de cette thèse est de proposer des modèles de contrôles d'accès XML qui prennent en compte les droits de lecture et de mise-à-jour et qui permettent de surmonter les limites des modèles qui existent. Nous considérons les langages XPath et XQuery Update Facility pour la formalisation des requêtes d'accès et des requêtes de mise-à-jour respectivement. Nous donnons des descriptions formelles de nos modèles de contrôles d'accès et nous présentons des algorithmes efficaces pour le renforcement des politiques de sécurité spécifiées à la base de ces modèles. L'autre partie de cette thèse est consacrée à l'étude pratique de nos propositions. Nous présentons notre système appelé SVMAX qui met en oeuvre nos solutions, et nous conduisons une étude expérimentale basée sur une DTD réelle pour montrer son efficacité. Plusieurs systèmes de bases de données natives (systèmes de BDNs) ont été proposés récemment qui permettent une manipulation efficace des données XML en utilisant la plupart des standards du W3C. Nous montrons que notre système SVMAX peut être intégré facilement et efficacement au sein d'un large ensemble de systèmes de BDNs. A nos connaissances, SVMAX est le premier système qui permet la sécurisation des données XML conformes à des DTDs arbitraires (récursives ou non) et ceci en moyennant un fragment significatif de XPath et une classe riche d'opérations de mise-à-jour XML / XML has become a standard for representation and exchange of data across the web. Replication of data within different sites is used to increase the availability of data by minimizing the access's time to the shared data. However, the safety of the shared data remains an important issue. The aim of the thesis is to propose some models of XML access control that take into account both read and update rights and that overcome limitations of existing models. We consider the XPath language and the XQuery Update Facility to formalize respectively user access queries and user update operations. We give formal descriptions of our read and update access control models and we present efficient algorithms to enforce policies that can be specified using these models. Detailed proofs are given that show the correctness of our proposals. The last part of this thesis studies the practicality of our proposals. Firstly, we present our system, called SVMAX, that implements our solutions and we conduct an extensive experimental study, based on real-life DTD, to show that it scales well. Many native XML databases systems (NXD systems) have been proposed recently that are aware of the XML data structure and provide efficient manipulation of XML data by the use of most of W3C standards. Finally, we show that our system can be integrated easily and efficiently within a large set of NXD systems, namely BaseX, Sedna and eXist-db. To the best of our knowledge, SVMAX is the first system for securing XML data in the presence of arbitrary DTDs (recursive or not), a significant fragment of XPath and a rich class of XML update operations