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

Cette thèse adresse les problèmes d'universalité et de complétude computationelle pour plusieurs modèles de calcul inspirés par la biologie. Il s'agit principalement des systèmes d'insertion/effacement, réseaux de processeurs évolutionnaires, ainsi que des systèmes de réécriture de multi-ensembles. Les résultats décrits se classent dans deux catégories majeures : l'étude de la puissance de calcul des opérations d'insertion et d'effacement avec ou sans mécanismes de contrôle, et la construction des systèmes de réécriture de multi-ensembles universels de petite taille. Les opérations d'insertion et d'effacement consistent à rajouter ou supprimer une sous-chaîne dans une chaîne de caractères dans un contexte donné. La motivation pour l'étude de ces opérations vient de la biologie, ainsi que de la linguistique et de la théorie des langages formels. Dans la première partie de ce manuscrit nous examinons des systèmes d'insertion/effacement correspondant à l'édition de l'ARN, un processus qui insère ou supprime des fragments de ces molécules. Une particularité importante de l'édition de l'ARN est que le endroit auquel se font les modifications est déterminé par des séquences de nucléotides se trouvant toujours du même côté du site de modification. En termes d'insertion et d'effacement, ce phénomène se modéliserait par des règles possédant le contexte uniquement d'un seul côté. Nous montrons qu'avec un contexte gauche de deux caractères il est possible d'engendrer tous les langages rationnels. D'autre part, nous prouvons que des contextes plus longs n'augmentent pas la puissance de calcul du modèle. Nous examinons aussi les systèmes d’insertion/effacement utilisant des mécanismes de contrôle d’application des règles et nous montrons l'augmentation de la puissance d'expression. Les opérations d'insertion et d'effacement apparaissent naturellement dans le domaine de la sécurité informatique. Comme exemple on peut donner le modèle des grammaires gauchistes (leftist grammar), qui ont été introduites pour l'étude des systèmes critiques. Dans cette thèse nous proposons un nouvel instrument graphique d'analyse du comportement dynamique de ces grammaires. La deuxième partie du manuscrit s'intéresse au problème d'universalité qui consiste à trouver un élément concret capable de simuler le travail de n'importe quel autre dispositif de calcul. Nous commençons par le modèle de réseaux de processeurs évolutionnaires, qui abstrait le traitement de l'information génétique. Nous construisons des réseaux universels ayant un petit nombre de règles. Nous nous concentrons ensuite sur les systèmes de réécriture des multi-ensembles, un modèle qui peut être vu comme une abstraction des réactions biochimiques. Pour des raisons historiques, nous formulons nos résultats en termes de réseaux de Petri. Nous construisons des réseaux de Petri universels et décrivons des techniques de réduction du nombre de places, de transitions et d'arcs inhibiteurs, ainsi que du degré maximal des transitions. Une bonne partie de ces techniques repose sur une généralisation des machines à registres introduite dans cette thèse et qui permet d'effectuer plusieurs tests et opérations en un seul changement d'état / The present thesis considers the problems of computational completeness and universality for several biologically-inspired models of computation: insertion-deletion systems, networks of evolutionary processors, and multiset rewriting systems. The presented results fall into two major categories: study of expressive power of the operations of insertion and deletion with and without control, and construction of universal multiset rewriting systems of low descriptional complexity. Insertion and deletion operations consist in adding or removing a subword from a given string if this subword is surrounded by some given contexts. The motivation for studying these operations comes from biology, as well as from linguistics and the theory of formal languages. In the first part of the present work we focus on insertion-deletion systems closely related to RNA editing, which essentially consists in inserting or deleting fragments of RNA molecules. An important feature of RNA editing is the fact that the locus the operations are carried at is determined by certain sequences of nucleotides, which are always situated to the same side of the editing site. In terms of formal insertion and deletion, this phenomenon is modelled by rules which can only check their context on one side and not on the other. We show that allowing one-symbol insertion and deletion rules to check a two-symbol left context enables them to generate all regular languages. Moreover, we prove that allowing longer insertion and deletion contexts does not increase the computational power. We further consider insertion-deletion systems with additional control over rule applications and show that the computational completeness can be achieved by systems with very small rules. The motivation for studying insertion-deletion systems also comes from the domain of computer security, for the purposes of which a special kind of insertion-deletion systems called leftist grammars was introduced. In this work we propose a novel graphical instrument for visual analysis of the dynamics of such systems. The second part of the present thesis is concerned with the universality problem, which consists in finding a fixed element able to simulate the work any other computing device. We start by considering networks of evolutionary processors (NEPs), a computational model inspired by the way genetic information is processed in the living cell, and construct universal NEPs with very few rules. We then focus on multiset rewriting systems, which model the chemical processes running in the biological cell. For historical reasons, we formulate our results in terms of Petri nets. We construct a series of universal Petri nets and give several techniques for reducing the numbers of places, transitions, inhibitor arcs, and the maximal transition degree. Some of these techniques rely on a generalisation of conventional register machines, proposed in this thesis, which allows multiple register checks and operations to be performed in a single state transition

Notre thèse a pour ambition de faire émerger un niveau linguistique supérieur à la phrase et dont la prise encompte est indispensable à toute caractérisation et compréhension de ce qu’est un texte. A ce titre, lapragmatique, comme science du dire, est sans doute la plus à même de fournir une caractérisationsatisfaisante de ce niveau. Dans sa conception gricéenne, elle a mis en avant un principe de coopération etl’existence de maximes conversationnelles, sans approfondir, ni même discuter, le niveau auquel ce principeet ces maximes seraient attachés, celui-là même de contribution, alors que c’est précisément cette notion-ciqui, a priori, et quand on considère la maxime de quantité, est de fait un ensemble de phrases (ou mêmed’énoncés), ensemble qui certes peut à l’occasion se réduire à un(e) seul(e) énoncé (phrase) mais qui, dansla plupart des cas, définit un niveau langagier intermédiaire entre l’énoncé et la totalité de ce qui est dit dansl’échange.La thèse montre alors principalement que ces contributions sont des ensembles de phrases satisfaisant descontraintes pragmatiques, avec, entre autres, une contrainte de complétude forte, issue de la maxime dequantité, que l’on pose comme heuristique. De fait, les textes sont des contributions (plus précisément desmacro-contributions constituées de micro-contributions) et doivent être décrits comme tels. L’étudeempirique, appliquée au roman de formation, de la pertinence textuelle, de l'intégration textuelle et de ladisposition textuelle met à jour un certain nombre de phénomènes qui caractérisent le texte en tant que tel. / The main purpose of our thesis is to study and uncover a linguistic level superior to sentence’s level andwhich must inevitably be considered before any determination and understanding of the nature of a text. IfPragmatics (the science of saying and meaning) is undoubtedly the key to reach this goal, due to theemergence of the notion of contribution in the formulation of conversational maxims by Paul Grice, the thesisshows that this rather clandestine emergence and the consequent confusion between utterance’s level andthe level of contribution must be replaced among other things : i) by a full recognition of contributions as setsof utterances satisfying pragmatic constraints, among which is the constraint of completeness (maxim ofquantity); ii) by the recognition of the fact that texts are contributions and must be described as such; iii) bythe recognition of the fact that (macro-)contributions may include (micro-)contributions; iv) by the empiricalstudy of contributional and textual relevance, textual integration and textual organization.This thesis combines thus a contribution to the linguistics of contributions and a contributional approach toboth text theory and Bildungsroman.

Aujourd’hui, le processus de conception de produits fait face à une mondialisation des marchés, conduit par des équipes géographiquement distribuées. Ces équipes sont ainsi amenées à travailler ensemble afin de concevoir ces produits nouveaux. Les activités de conception ont donc évolué au fil du temps pour pouvoir constamment répondre aux nouvelles contraintes industrielles, de la même manière que les processus de fabrication se sont adaptés aux marchés. Ainsi, afin de faciliter les phases de travail en commun, de nouvelles stratégies de gestion de la collaboration, notamment à travers de nouveaux systèmes d’information, sont mises en place. Ces systèmes d’information sont nombreux et prennent différentes formes, ce qui rend souvent difficiles la sélection et le pilotage de ces derniers. Or, pour les équipes projet, la gestion de ces nouveaux outils informatiques fait partie intégrante des éléments clés du processus de conception de produits. Ainsi, dans le cadre de nos travaux, nous nous focalisons sur l’aide au pilotage de l’ingénierie collaborative en mode projet pour la conception et le développement de produits matériels techniques. Notre objectif est d’aider le chef projet à mieux gérer son projet en utilisant au moment adéquat l’outil d’aide à la collaboration le plus adapté. Dans nos travaux, nous avons souligné la nécessité d’utiliser un indicateur quantitatif de pilotage de la conception collaborative. Cet indicateur apporte ainsi une approche complémentaire de l’évaluation de la pertinence de la collaboration en cours, en prenant en compte son impact sur l’évolution du projet. Le calcul de cet indicateur s’appuie sur une métrique spécifique et concerne l’évolution de la complétude de la donnée CAO. De plus, nous avons montré que ce nouvel indicateur peut être intégré à une approche organisationnelle de type PLM afin de faciliter le stockage des données et le calcul de la complétude, cette dernière étant liée aux outils utilisés et aux jalons projet. / Today, product design process is facing a market globalization led by distributed teams. Moreover, the international market context in which the companies evolves, leads them to work in large multi-disciplinary collaborative teams using in collaborative practices. In this context, product design process is led by the integration and optimization of stakeholders’ collaboration. Thus, to facilitate collaboration steps, new management strategies are defined and new information systems can be used. These information systems are numerous and take various forms, leading to difficulties for companies to select one of them and manage them. However, to the design teams, the management and the choice of those are key elements of the product design process.Toward this ends, in the present thesis, we focalize our research on the topic of collaborative design project management. Our objective is to assist the project leader to better manage her or his product design project using optimal collaborative tool all along the design project. We have underlined the necessity to use quantitative and non-intrusive indicator during the management of collaborative design phases in order to subjective evaluation. The tracking of this indicator is performed in parallel to the existing approaches of the evaluation of the suitability of the collaboration. It defines the impact of the collaboration steps on the design project evolution. The computation of this indicator is based on a precise metric which details the completeness of the CAD model based on the used collaborative tools and the project milestones. Moreover, we have showed that this new indicator can be integrated to an organizational approach, as a PLM, to facilitate data storage and completeness computation.

Les Systèmes d'Information (SI) de même domaine d'activité gèrent de nombreux concepts similaires. Ces concepts peuvent être analysés et généralisés dans des abstractions informatiques qui seront réutilisées lors de nouveaux développements. De telles abstractions sont appelées Composants Métier (CM). Cependant, il est souvent difficile d'expliciter des critères clairs de réutilisation, en particulier la manière dont on peut identifier, spécifier, organiser et en grande partie automatiser la réutilisation de ces CM. Les contributions de cette thèse adressent cette problématique et s'articulent autour de trois principaux résultats. La première contribution concerne un modèle de CM de nature processus appelé « CMP ». Ce modèle est centré sur les propriétés fonctionnelles des composants. L'accent est mis sur la complétude et la variabilité de la solution exprimée sous la forme de quatre vues complémentaires intégrant des points de variation. Le travail réalisé sur les mécanismes de spécification de la variabilité a abouti à un profil UML pouvant être utilisé pour modéliser non seulement des processus réutilisables mais aussi des processus flexibles. Une deuxième contribution s'inscrit dans le cadre de la proposition d'un processus permettant la spécification d'un CMP selon le modèle proposé. Dans ce processus, nous définissons un ensemble de règles de construction, de traduction et de cohérence qui assurent la traçabilité des artefacts produits tout au long du cycle de développement. Une troisième contribution concerne la proposition de directives qui assistent l'ingénieur de SI lors de la réutilisation de CMP. L'accent est particulièrement mis sur la proposition d'un formalisme de documentation et de classification de CMP validé dans le cadre d'un environnement de stockage de composants. Nous proposons également un processus d'imitation intégré à la méthode de développement Symphony et permettant de tirer partie de la spécification d'un CMP lors de la conception d'un SI. L'ensemble des propositions est accompagné d'outils et d'expérimentations utilisateurs servant de supports de validation et de mise en œuvre des travaux réalisés.

Les patrons d'ingénierie ont été introduits afin de capitaliser et de réutiliser des savoirs et savoir-faire. Dans l'ingénierie logicielle, leur usage est aujourd'hui reconnu, à tous les niveaux (analyse, conception, ...), comme un gage de qualité. Outre une solution, un patron comporte également de nombreuses informations, en langage naturel, décrivant des contraintes et/ou variantes. Dans cette thèse, nous nous intéressons à l'activité de réutilisation des patrons (que nous appelons « imitation ») d'analyse ou de conception pour lesquels la solution est donnée sous la forme de spécifications orientées objet. L'imitation consiste en une adaptation et une intégration de cette solution par l'ingénieur d'applications qui tiennent compte des autres informations contenues dans le patron. Ainsi, nous dégageons trois axes que nous considérons comme les piliers d'une bonne imitation : la complétude, la variabilité et la généricité des solutions.<br />Nous proposons une nouvelle forme de définition des solutions qui s'appuie sur l'utilisation de plusieurs vues (fonctionnelle, dynamique et statique) ainsi que sur l'utilisation d'un méta-modèle permettant d'une part d'exprimer à partir de la vue fonctionnelle, la variabilité de la solution (fonctionnalités obligatoires, facultatives, optionnelles ou alternatives) et d'autre part d'exprimer l' « essence » de la solution sous la forme de propriétés génériques définissant les bornes des adaptations permises lors de l'imitation. Un processus d'imitation dédié ainsi qu'un premier outillage basé sur l'approche IDM (Ingénierie Dirigée par les Modèles) sont également proposés aux ingénieurs d'applications.

Les nouveaux supports d'exécution que sont les grilles de processeurs<br />apparaissent aujourd'hui comme une alternative économiquement viable aux grands systèmes de calcul centralisés. De grands projets nationaux comme GRID5000 sont basés sur ce concept de machines réparties. Ce changement du paysage du calcul parallèle haute performance a créé une nouvelle demande d'algorithmes spécifiques pour tirer le meilleur parti des ressources déployées. Pour concevoir ces algorithmes et démontrer leur efficacité, il faut s'appuyer sur des modèles qui tentent de décrire fidèlement le comportement réel des machines tout en restant suffisamment simples à manipuler. Dans cette thèse, nous avons étudié deux modèles parmi les plus importants pour ces nouveaux supports et nous avons fourni des algorithmes polynomiaux optimaux, des algorithmes d'approximations garantis, ou des preuves de NP-complètudes le cas échéant.

Les schématisations de termes permettent de représenter des ensembles infinis de termes ayant une structure similaire de manière finie et compacte. Dans ce travail, nous étudions certains aspects liés à l'utilisation des schématisations de termes en déduction automatique, plus particulièrement dans les méthodes de démonstration de théorèmes du premier ordre par saturation. Après une brève étude comparée des formalismes de schématisation existants, nous nous concentrons plus particulièrement sur les termes avec exposants entiers (ou I-termes). Dans un premier temps, nous proposons une nouvelle approche permettant de détecter automatiquement des régularités dans les espaces de recherche. Cette détection des régularités peut avoir plusieurs applications, notamment la découverte de lemmes nécessaires à la terminaison dans certaines preuves inductives. Nous présentons DS3, un outil qui implémente ces idées. Nous comparons notre approche avec d'autres techniques de généralisation de termes. Notre approche diffère complètement des techniques existantes car d'une part, elle est complètement indépendante de la procédure de preuve utilisée et d'autre part, elle utilise des techniques de généralisation inductive et non déductives. Nous discutons également les avantages et les inconvénients liés à l'utilisation de notre méthode et donnons des éléments informels de comparaison avec les approches existantes. Nous nous intéressons ensuite aux aspects théoriques de l'utilisation des I-termes en démonstration automatique. Nous démontrons que l'extension aux I-termes du calcul de résolution ordonnée est réfutationnellement complète, que l'extension du calcul de superposition n'est pas réfutationnellement complète et nous proposons une nouvelle règle d'inférence pour restaurer la complétude réfutationnelle. Nous proposons ensuite un algorithme d'indexation (pour une sous-classe) des I-termes, utile pour le traitement des règles de simplification et d'élimination de la redondance. Finalement nous présentons DEI, un démonstrateur automatique de théorèmes capable de gérer directement des formules contenant des I-termes. Nous évaluons les performances de ce logiciel sur un ensemble de benchmarks.

Motivés par la facilitation du raisonnement sur des méta-théories logiques à l'intérieur de l'assistant de preuve Coq, nous étudions les versions constructives de certains théorèmes de complétude. Nous commençons par l'analyse des preuves de Krivine et Berardi-Valentini qui énoncent que la logique classique est constructivement complète au regard des modèles booléens relaxés, ainsi que l'analyse de l'algorithme de cette preuve. En essayant d'élaborer une preuve de complétude plus canonique pour la logique classique, inspirés par la méthode de la normalisation-par-évaluation (NPE) de Berger et Schwichtenberg, nous concevons une preuve de complétude pour la logique classique en introduisant une notion de modèle dans le style des modèles de Kripke, dont le contenu calculatoire est l'élimination des coupures, ou la normalisation. Nous nous tournons ensuite vers la NPE pour une logique de prédicats intuitionniste (en considérant tous les connecteurs logiques), c'est-à-dire, vers sa complétude par rapport aux modèles de Kripke. Inspirés par le programme informatique de Danvy pour la normalisation des termes du $\lambda$-calcul avec sommes, lequel utilise des opérateurs de contrôle délimité, nous développons une notion d'un modèle, encore une fois semblable aux modèles de Kripke, qui est correct et complet pour la logique de prédicats intuitionniste, et qui est, par coïncidence, très similaire à la notion de modèle de Kripke introduit pour la logique classique. Finalement, en se fondant sur des observations de Herbelin, nous montrons que l'on peut avoir une logique intuitionniste étendue avec des opérateurs de contrôle délimité qui est equiconsistante avec la logique intuitionniste, qui préserve les propriétés de disjonction et d'existence, et qui est capable de dériver le schéma « Double Negation Shift » et le principe de Markov.

Notre thèse a pour ambition de faire émerger un niveau linguistique supérieur à la phrase et dont la prise encompte est indispensable à toute caractérisation et compréhension de ce qu'est un texte. A ce titre, lapragmatique, comme science du dire, est sans doute la plus à même de fournir une caractérisationsatisfaisante de ce niveau. Dans sa conception gricéenne, elle a mis en avant un principe de coopération etl'existence de maximes conversationnelles, sans approfondir, ni même discuter, le niveau auquel ce principeet ces maximes seraient attachés, celui-là même de contribution, alors que c'est précisément cette notion-ciqui, a priori, et quand on considère la maxime de quantité, est de fait un ensemble de phrases (ou mêmed'énoncés), ensemble qui certes peut à l'occasion se réduire à un(e) seul(e) énoncé (phrase) mais qui, dansla plupart des cas, définit un niveau langagier intermédiaire entre l'énoncé et la totalité de ce qui est dit dansl'échange.La thèse montre alors principalement que ces contributions sont des ensembles de phrases satisfaisant descontraintes pragmatiques, avec, entre autres, une contrainte de complétude forte, issue de la maxime dequantité, que l'on pose comme heuristique. De fait, les textes sont des contributions (plus précisément desmacro-contributions constituées de micro-contributions) et doivent être décrits comme tels. L'étudeempirique, appliquée au roman de formation, de la pertinence textuelle, de l'intégration textuelle et de ladisposition textuelle met à jour un certain nombre de phénomènes qui caractérisent le texte en tant que tel.