Toutes les illustrations qui ponctuent cette thèse ont été réalisées par Chantal Poirier. Elles ont été insérées dans le texte selon un ordre méticuleusement aléatoire. / Le texte qui suit, malgré son libellé onomastique (le nom « John Cage »), son orientation disciplinaire (la « théorie littéraire ») et sa visée thématique (« la révision du commentaire critique »), se place d’emblée dans une posture d’écriture et de création. Il consiste à proposer comme point de départ l’identité de la forme textuelle et de sa dérivation métatextuelle, en d’autres mots : de la voix citée et analysée avec l’autre voix citante et analysante. Cette prémisse dérive elle-même d’une confrontation locale : les spécificités et les idiosyncrasies de la textualité mise en place par John Cage à partir des années quarante (partitions littéraires des recueils Silence et A Year from Monday, mésostiches de M et X, réécritures et « writing through » d’Empty Words…). En effet, l’examen par la théorie littéraire d’un corpus aussi disséminé et « néologique » que l’est celui de John Cage pousse son rédacteur à poser la question de sa propre écriture (« autoréflexivité ») et à rendre possible une réalisation artistique personnelle (« performativité »). C’est donc à travers la contingence d’une langue et d’une subjectivité au travail que la théorisation (textuelle) du texte cherche ici à s’élucider et à s’écrire. Le travail commence par installer les modalités à la fois circulaires et circulatoires de la théorie littéraire, une tension rhétorique et épistémologique qu’il identifie sous le nom d’« aporie autoréflexive » (le texte théorique est concerné par la question de lui-même). Il s’efforce ensuite d’analyser la nouveauté de l’œuvre littéraire cagienne, en empruntant un schéma dialectique et antagoniste : d’un côté, une « textualité-objet », originale et orthographique, de l’autre, une « textualité-sujet », disséminante et intertextuelle, anarchique et jubilatoire. Enfin, le texte propose la révision, la recomposition, la « réécriture » du commentaire critique sur les bases nouvelles d’une textologie autoréflexive et performative — une indiscipline d’écriture qui utilise sciemment les coordonnées linguistiques de son élocution (néologie, typographisme, procédés citationnels…) et qui fait place sans camouflage ou refoulement à la personnalité intertextuelle, contextuelle, métissée du rédacteur. Par l’entremise d’une sorte d’« exemplarité textuelle » (Cage), ce travail insiste pour une synthèse à la fois productive et expressive des voix analysées et analysantes dans les études littéraires. On verra que, par moments, cette proposition implique que le texte se marginalise. / The following text, despite its onomastic labelling (the name “John Cage”), its disciplinary orientation (“literary theory”), and its thematic aim (“the revision of the literary commentary”), positions itself as a writing and creative venture. It starts by stating the strict identity of texts and metatexts, in other words, of the quoted, analyzed voice, with the quoting, analyzing other voice. This premise derives from a specific confrontation: the specificities and idiosyncrasies of John Cage’s literary production since the late 1940s (the literary scores from the anthologies Silence and A Year from Monday, the mesostics from M and X, the rewritings and “Writing through’s” from Empty Words…). Indeed, the examination by literary theory of a body of work as disseminated and “neological” as John Cage’s encourages the literary critic or theoretician to ask the question of his own writing (“self-reflexivity”) and also to make possible an original artistic realization (“performativity”). It is therefore through the possibilities of a language and of a subjectivity at work that the (textual) theorization of texts tries herein to elucidate and to write itself. This work starts by setting up the modalities both circular and circulatory of literary theory—a rhetorical and epistemological tension that will be identified as the “self-reflexive aporia” (the theoretical text is primarily concerned by the question of itself). It then tries to analyze the novelty of Cage’s literary work, using a dialectical and antagonistic configuration: on one hand, an “objective textuality”, original and orthographical; on the other hand, a “subjective textuality”, disseminating and intertextual, anarchic and unrestrained. Finally, this text proposes the revision, recomposition and “rewriting” of the critical commentary on the basis of a new self-reflexive and performative textology. That is: a sort of undiscipline in writing that knowingly manoeuvres the linguistic coordinates of its elocution (neology, typographism, quotation processes…) and that does not try to conceal or repress the intertextual, contextual, heterogenous and disparate personality of its author. Through a sort of “textual exemplarity” (Cage), this work insists on a synthesis both productive and expressive between the voices analyzing and the voices being analyzed. We will see accordingly that this proposition implies, from time to time, that the text be marginalized.

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.

This theoretical and historiographical thesis examines the theoretical work of the Translation Studies scholar André Lefevere. It focuses primarily on the analysis of Lefevere's work in the context of the development of Translation Studies (particularly in connection with the development of Descriptive Translation Studies, the formation of the "Manipulation School" and the cultural and sociological turns in Translation Studies). The paper covers Lefevere's theoretical underpinnings, the gradual development of his theoretical model and his contribution to the development of the discipline, with special regard to the integration of sociocultural aspects into translation research. Also included is an overview of the most significant critical responses to Lefevere's work and of the applications of his model in practical research.

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.