Les travaux de cette thèse se situent dans le cadre de la linguistique computationnelle. La problématique est de définir une interface syntaxe / sémantique basée sur les théories de la grammaire générative.<br />Une première partie, concernant le problème de l'analyse syntaxique, présente tout d'abord, la syntaxe générative, puis un formalisme la réalisant: les grammaires minimalistes de Stabler. <br />À partir de ces grammaires, nous réalisons une étude sur les propriétés de l'opération de fusion pour laquelle nous définissons des notions d'équivalence, ainsi qu'une modélisation abstraite des lexiques.<br />Une seconde partie revient sur le problème de l'interface. Pour cela, nous proposons un formalisme de type logique, basé sur la logique mixte (possédant des connecteurs commutatifs et non-commutatifs), qui équivaut, sous certaines conditions, aux grammaires de Stabler. <br />Dans ce but, nous introduisons une normalisation des preuves de cette logique, normalisation permettant de vérifier la propriété de la sous-formule. Ces propriétés sont également étendues au calcul de Lambek avec produit.<br />À partir de l'isomorphisme de Curry-Howard, nous synchronisons un calcul sémantique avec les preuves réalisant l'analyse syntaxique. Les termes de notre calcul font appel aux propriétés du lambda mu-calcul, ainsi qu'à celles de la DRT (Discourse Representative Theory).<br />Une dernière partie applique ces formalismes à des cas concrets. Nous établissons des fragments d'une grammaire du français autour du problème des clitiques.

Reproduction de : Thèse de doctorat : Informatique : Lille 1 : 2004. / Titre provenant de la page de titre du document numérisé. Bibliogr. p. 183-194.

Les systèmes d'information actuels doivent, à la fois, protéger les informations qui leur sont confiées et se plier à des environnements opérationnels variables. Cesdeux objectifs, sécurité et flexibilité, peuvent être antinomiques. Ce conflit conduit généralement à l'utilisation de systèmes offrant un niveau de sécurité acceptable, mais non maximal. Définir un tel niveau présuppose l'existence de méthodes d'évaluation de la sécurité. Cette problématique fait l'objet de cette thèse. L'auteur y passe en revue les différents critères d'évaluation existant ainsi que les méthodes dites d'analyse de risques. Ceci introduit la nécessité de définir un cadre formel capable de modéliser tout système et d'évaluer dans quelle mesure il satisfait à des objectifs de protection précis.<br />Les modèles formels développés pour l'étude de la sécurité informatique, n'offrent pas le cadre mathématique désiré. L'auteur montre qu'ils adoptent une hypothèse de pire cas sur le comportement des utilisateurs, incompatible avec une modélisation réaliste. Après avoir montré, sur la base du modèle take-grant, comment s'affranchir de cette hypothèse, l'auteur définit un nouveau modèle, le graphe des privilèges, plus efficace pour gérer certains problèmes de protection. Il illustre son utilisation dans le cadre des systèmes Unix.<br />Enfin, l'auteur propose d'évaluer la sécurité en calculant le temps et l'effort nécessaires à un intrus pour violer les objectifs de protection. Il montre comment définir un cadre mathématique apte à représenter le système pour obtenir de telles mesures. Pour cela, le graphe des privilèges est transformé en un réseau de Petri stochastique et son graphe des marquages est dérivé. Les mesures sont calculées sur cette dernière structure et leurs propriétés mathématiques sont démontrées. L'auteur illustre l'utilité du modèle par quelques résultats issus d'un prototype développé afin d'étudier la sécurité opérationnelle d'un système Unix.

Cette thèse apporte plusieurs contributions dans le domaine des langages formels. Notre premier travail a été de montrer la pertinence des grammaires de graphes comme outil de démonstration de résultats fondamentaux sur les langages algébriques. Nous avons ainsi reformulé avec un point de vue géométrique les démonstrations du lemme des paires itérantes et du lemme de Parikh. Nous avons ensuite étendu aux graphes réguliers des algorithmes de base sur les graphes finis, notamment pour calculer des problèmes de plus court chemin. Ces extensions ont été faites par calcul de plus petits points fixes sur les grammaires de graphes. Enfin, nous avons caractérisé des familles générales de systèmes de récriture de mots dont la dérivation préserve la régularité ou l'algébricité. Ces familles ont été obtenues par décomposition de la dérivation en une substitution régulière suivie de la dérivation du système de Dyck

Ce travail se situe dans le cadre de la recherche de systèmes de notation permettant de transcrire de façon symbolique l’aspect concret et sensoriel, et non seulement abstrait et structurel, des artefacts de la musique par ordinateur. Dans ce but, nous exposons tout d’abord un modèle formel complet et minimal des objets et structures audionumériques, en référence aux critères de la perception ; ce modèle est implémenté sous la forme d’un langage fonctionnel Turing-potent qui permet d’effectuer l’équivalence entre l’expression mathématique d’un signal et sa réalisation informatique. Puis, nous employons ce formalisme afin d’exprimer un ensemble de critères de synthèse sonore, ce qui donne lieu à un logiciel de synthèse dont l’expressivité est considérable. Ces outils sont organisés suivant le schéma des théories Schaefferiennes, par une décomposition catégorielle dans laquelle les paramètres correspondent à des notions morphologiques. Finalement, nous rendons compte d’une série d’expériences visant à évaluer la pertinence de ces critères dans l’audition humaine, avec le concours d’un musicologue, puis sur un ensemble de sujets, et enfin vis-à-vis d’un public aussi large que possible. Ceci nous conduit à remettre en question la méthodologie la plus adéquate pour traiter ce type de problème, qui nous rapproche des sciences humaines et sociales, et suggère une démarche de science participative. / This piece of work is situated in the context of research on notation systems enabled to transcribe symbolically the concrete and sensorial aspect, and not only the abstract and structural aspect, of computer music artefacts. In this perspective, we first expose a complete and minimal formal model for digital audio objects and structures, relatively to the criteria of perception ; this model is implemented as a Turing-potent functional language, that draws the correspondance between the mathematical expression of a signal and its computational realisation. Then, we apply this formal construction to the expression of a number of schemes for sound synthesis, producing a software synthetiser whose expressivity is consequent. These tools are organised following the lines of Schaefferian theories, through a decomposition into categories whose parameters correspond with morphological notions. Finally, we draw the conclusions of a series of experiments aiming to evaluate the relevance of those schemes in human hearing, with the assistance of a musicologist, then with a number of subjects, and eventually by associating a public that is as wide as possible. This leads us to question the methodology most appropriate to tackle this kind of problem, which brings us closer to social science, and suggests a participative science approach.

Le langage mathématique courant et les langages mathématiques formelssont très éloignés. Par <<langage mathématique courant>> nousentendons la prose que le mathématicien utilise tous les jours dansses articles et ses livres. C'est une langue naturelle avec desexpressions symboliques et des notations spécifiques. Cette langue està la fois flexible et structurée mais reste sémantiquementintelligible par tous les mathématiciens.Cependant, il est très difficile de formaliser automatiquement cettelangue. Les raisons principales sont: la complexité et l'ambiguïté deslangues naturelles en général, le mélange inhabituel entre languenaturelle et notations symboliques tout aussi ambiguë et les sautsdans le raisonnement qui sont pour l'instant bien au-delà descapacités des prouveurs de théorèmes automatiques ou interactifs.Pour contourner ce problème, les assistants de preuves actuelsutilisent des langages formels précis dans un système logique biendéterminé, imposant ainsi de fortes restrictions par rapport auxlangues naturelles. En général ces langages ressemblent à des langagesde programmation avec un nombre limité de constructions possibles etune absence d'ambiguïté.Ainsi, le monde des mathématiques est séparé en deux, la vastemajorité qui utilise la langue naturelle et un petit nombre utilisantaussi des méthodes formelles. Cette seconde communauté est elle-mêmesubdivisée en autant de groupes qu'il y a d'assistants de preuves. Onperd alors l'intelligibilité des preuves pour tous les mathématiciens.Pour résoudre ce problème, on peut se demander:est-il possible d'écrire un programme qui comprend la langue naturellemathématique et qui la traduit vers un langage formel afin depermettre sa validation?Ce problème se subdivise naturellement en deux sous-problèmes tous lesdeux très difficiles:1. l'analyse grammaticale des textes mathématiques et leur traductiondans un langage formel,2. la validation des preuves écrites dans ce langage formel.Le but du projet MathNat (Mathematics in controlled Natural languages)est de faire un premier pas pour répondre à cette question trèsdifficile, en se concentrant essentiellement sur la première question.Pour cela, nous développons CLM (Controlled Language for Mathematics)qui est un sous-ensemble de l'anglais avec une grammaire et un lexiquerestreint, mais qui inclut tout de même quelques ingrédientsimportants des langues naturelles comme les pronoms anaphoriques, lesréférences, la possibilité d'écrire la même chose de plusieursmanières, des adjectifs distributifs ou non, ...Le second composant de MathNath est MathAbs (Mathematical Abstractlanguage). C'est un langage formel, indépendant du choix d'un systèmelogique permettant de représenter la sémantique des textes enpréservant leur structure et le fil du raisonnement. MathAbs est conçucomme un langage intermédiaire entre CLM et un système logique formelpermettant la vérification des preuves.Nous proposons un système qui permet de traduire CLM vers MathAbsdonnant ainsi une sémantique précise à CLM. Nous considèrons que cetravail est déjà un progrès notable, même si pour l'instant on estloin de pouvoir vérifier formellement toutes les preuves en MathAbsainsi générées.Pour le second problème, nous avons réalisé une petite expérience entraduisant MathAbs vers une liste de formules en logique du premierordre dont la validité garantit la correction de la preuve. Nous avonsensuite essayé de vérifier ces formules avec des prouveurs dethéorèmes automatiques validant ainsi quelques exemples. / There is a wide gap between the language of mathematics and itsformalized versions. The term "language of mathematics" or"mathematical language" refers to prose that the mathematician uses inauthoring textbooks and publications. It mainly consists of naturallanguage, symbolic expressions and notations. It is flexible,structured and semantically well-understood by mathematicians.However, it is very difficult to formalize it automatically. Some ofthe main reasons are: complex and rich linguistic features of naturallanguage and its inherent ambiguity; intermixing of natural languagewith symbolic mathematics causing problems which are unique of itskind, and therefore, posing more ambiguity; and the possibility ofcontaining reasoning gaps, which are hard to fill using the currentstate of art theorem provers (both automated and interactive).One way to work around this problem is to abandon the use of thelanguage of mathematics. Therefore in current state of art of theoremproving, mathematics is formalized manually in very precise, specificand well-defined logical systems. The languages supported by thesesystems impose strong restrictions. For instance, these languages havenon-ambiguous syntax with a limited number of possible syntacticconstructions.This enterprise divides the world of mathematics in two groups. Thefirst group consists of a vast majority of mathematicians whose relyon the language of mathematics only. In contrast, the second groupconsists of a minority of mathematicians. They use formal systems suchas theorem provers (interactive ones mostly) in addition to thelanguage of mathematics.To bridge the gap between the language of mathematics and itsformalized versions, we may ask the following gigantic question:Can we build a program that understands the language of mathematicsused by mathematicians and can we mechanically verify its correctness?This problem can naturally be divided in two sub-problems, both very hard:1. Parsing mathematical texts (mainly proofs) and translating thoseparse trees to a formal language after resolving linguistic issues.2. Verification of this formal version of mathematics.The project MathNat (Mathematics in controlled Natural language) aimsat being the first step towards solving this problem, focusing mainlyon the first question.First, we develop a Controlled Language for Mathematics (CLM) which isa precisely defined subset of English with restricted grammar anddictionary. To make CLM natural and expressive, we support some richlinguistic features such as anaphoric pronouns and references,rephrasing of a sentence in multiple ways and the proper handling ofdistributive and collective readings.Second, we automatically translate CLM to a system independent formaldescription language (MathAbs), with a hope to make MathNat accessibleto any proof checking system. Currently, we translate MathAbs intoequivalent first order formulas for verification.

The present work proposes visibly pushdown transducers (VPTs) for defining transformations of documents with a nesting structure. We show that this subclass of pushdown transducers enjoy good properties. Notably, we show that functionality is decidable in PTime and k-valuedness in co-NPTime. While this class is not closed under composition and its type checking problem against visibly pushdown automata is undecidable, we identify a subclass, the well-nested VPTs, closed under composition and with a decidable type checking problem. Furthermore, we show that the class of VPTs is closed under look-ahead, and that the deterministic VPTs with look-ahead characterize the functional VPTs transductions. Finally, we investigate the resources necessary to perform transformations defined by VPTs. We devise a memory efficient algorithm. Then we show that it is decidable whether a VPT transduction can be performed with a memory that depends on the level of nesting of the input document but not on its length. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Cette thèse propose une nouvelle approche de découverte de signatures de familles (et superfamilles) d'enzymes. Dans un premier temps, étant donné un échantillon aligné de séquences appartenant à une même famille, cette approche infère des grammaires algébriques caractérisant cette famille. Pour ce faire, de nouveaux principes de généralisation et de nouvelles classes de langages ont été introduites sur la base de la substituabilité locale. Un algorithme a également été développé à cet effet qui produit une grammaire réduite, conservant la structuration des exemples, d'un langage substituable. Dans un second temps, ce manuscrit présente une méthode de classification des séquences d'une superfamille en familles à l'aide d'une analyse de concepts formels basée sur l'alignement des séquences qui permet la détection de nouvelles familles et la découverte des motifs fonctionnels pour améliorer les signatures précédentes. / This thesis proposes a new approach to discover signatures of families (and superfamilies) enzymes. At first, given a sample of aligned sequences belonging to the same family, this approach infers context-free grammars characteristic of this family. To do this, new principles of generalization and new classes have been introduced based on substitutability. An algorithm has also been developed for this purpose, which produces a reduced grammar able to retain the structure of examples. In a second step, this manuscript presents a method for classification of a superfamily sequences into families with a formal concept analysis based on alignement sequences allowing detection of new families and the discovery of patterns to improve functional previous signatures.

Les réseaux logiciels (connus sous l'éppellation: Software Defined Networking, SDN), qui s'appuient sur le paradigme de séparation du plan de contrôle et du plan d'acheminement, ont fortement progressé ces dernières années pour permettre la programmabilité des réseaux et faciliter leur gestion. Reconnu aujourd'hui comme des architectures logicielles pilotées par des applications, offrant plus de programmabilité, de flexibilité et de simplification des infrastructures, les réseaux logiciels sont de plus en plus largement adoptés et graduellement déployés par l'ensemble des fournisseurs. Néanmoins, l'émergence de ce type d'architectures pose un ensemble de questions fondamentales sur la manière de garantir leur correct fonctionnement. L'architecture logicielle SDN est elle-même un système complexe à plusieurs composants vulnérable aux erreurs. Il est essentiel d'en assurer le bon fonctionnement avant déploiement et intégration dans les infrastructures.Dans la littérature, la manière de réaliser cette tâche n'a été étudiée de manière approfondie qu'à l'aide de vérification formelle. Les méthodes de tests s'appuyant sur des modèles n'ont guère retenu l'attention de la communauté scientifique bien que leur pertinence et l'efficacité des tests associés ont été largement demontrés dans le domaine du développement logiciel. La création d'approches de test efficaces et réutilisables basées sur des modèles nous semble une approche appropriée avant tout déploiement de réseaux virtuels et de leurs composants. Le problème abordé dans cette thèse concerne l'utilisation de modèles formels pour garantir un comportement fonctionnel correct des architectures SDN ainsi que de leurs composants. Des approches formelles, structurées et efficaces de génération de tests sont les principale contributions de la thèse. En outre, l'automatisation du processus de test est mis en relief car elle peut en réduire considérablement les efforts et le coût.La première contribution consiste en une méthode reposant sur l'énumération de graphes et qui vise le test fonctionnel des architectures SDN. En second lieu, une méthode basée sur un circuit logique est développée pour tester la fonctionnalité de transmission d'un commutateur SDN. Plus loin, cette dernière méthode est étendue pour tester une application d'un contrôleur SDN. De plus, une technique basée sur une machine à états finis étendus est introduite pour tester la communication commutateur-contrôleur.Comme la qualité d'une suite de tests est généralement mesurée par sa couverture de fautes, les méthodes de test proposées introduisent différents modèles de fautes et génèrent des suites de tests avec une couverture de fautes guarantie. / Having gained momentum from its concept of decoupling the traffic control from the underlying traffic transmission, Software Defined Networking (SDN) is a new networking paradigm that is progressing rapidly addressing some of the long-standing challenges in computer networks. Since they are valuable and crucial for networking, SDN architectures are subject to be widely deployed and are expected to have the greatest impact in the near future. The emergence of SDN architectures raises a set of fundamental questions about how to guarantee their correctness. Although their goal is to simplify the management of networks, the challenge is that the SDN software architecture itself is a complex and multi-component system which is failure-prone. Therefore, assuring the correct functional behaviour of such architectures and related SDN components is a task of paramount importance, yet, decidedly challenging.How to achieve this task, however, has only been intensively investigated using formal verification, with little attention paid to model based testing methods. Furthermore, the relevance of models and the efficiency of model based testing have been demonstrated for software engineering and particularly for network protocols. Thus, the creation of efficient and reusable model based testing approaches becomes an important stage before the deployment of virtual networks and related components. The problem addressed in this thesis relates to the use of formal models for guaranteeing the correct functional behaviour of SDN architectures and their corresponding components. Formal, and effective test generation approaches are in the primary focus of the thesis. In addition, automation of the test process is targeted as it can considerably cut the efforts and cost of testing.The main contributions of the thesis relate to model based techniques for deriving high quality test suites. Firstly, a method relying on graph enumeration is proposed for the functional testing of SDN architectures. Secondly, a method based on logic circuit is developed for testing the forwarding functionality of an SDN switch. Further on, the latter method is extended to test an application of an SDN controller. Additionally, a technique based on an extended finite state machine is introduced for testing the switch-to-controller communication. As the quality of a test suite is usually measured by its fault coverage, the proposed testing methods introduce different fault models and seek for test suites with guaranteed fault coverage that can be stated as sufficient conditions for a test suite completeness / exhaustiveness.

Dans le but de faciliter la tâche d'évaluation du niveau de sécurité incendie aux ingénieurs et permettre aux spécialistes impliqués dans le domaine d'utiliser leurs langages et outils préférés, nous proposons de créer un langage dédié au domaine de la sécurité incendie générant automatiquement une simulation en prenant en considération les langages métiers utilisés par les spécialistes intervenants dans le domaine. Ce DSL nécessite la définition, la formalisation, la composition et l'intégration de plusieurs modèles, par rapport aux langages spécifiques utilisés par les spécialistes impliqués dans le domaine. Le langage spécifique dédié au domaine de la sécurité incendie est conçu par composition et intégration de plusieurs autres DSLs décrits par des langages techniques et naturels (ainsi que des langages naturels faisant référence à des langages techniques). Ces derniers sont modélisés de manière à ce que leurs composants soient précis et fondés sur des bases mathématiques permettant de vérifier la cohérence du système (personnes et matériaux sont en sécurité) avant sa mise en œuvre. Dans ce contexte, nous proposons d'adopter une approche formelle, basée sur des spécifications algébriques, pour formaliser les langages utilisés par les spécialistes impliqués dans le système de génération, en se concentrant à la fois sur les syntaxes et les sémantiques des langages dédiés. Dans l'approche algébrique, les concepts du domaine sont abstraits par des types de données et les relations entre eux. La sémantique des langages spécifiques est décrite par les relations, le mapping (correspondances) entre les types de données définis et leurs propriétés. Le langage de simulation est basé sur un langage conçu par la composition de plusieurs DSL spécifiques précédemment décrits et formalisés. Les différents DSLs sont implémentés en se basant sur les concepts de la programmation fonctionnelle et le langage fonctionnel Haskell bien adapté à cette approche. Le résultat de ce travail est un outil informatique dédié à la génération automatique de simulation, dans le but de faciliter la tâche d'évaluation du niveau de sécurité incendie aux ingénieurs. Cet outil est la propriété du Centre Scientifique et Technique du bâtiment (CSTB), une organisation dont la mission est de garantir la qualité et la sécurité des bâtiments, en réunissant des compétences multidisciplinaires pour développer et partager des connaissances scientifiques et techniques, afin de fournir aux différents acteurs les réponses attendues dans leur pratique professionnelle. / In order to facilitate the engineers task of evaluating the fire safety level, and to allow the specialists involved in the field to use their preferred languages and tools, we propose to create a language dedicated to the field of fire safety, which automatically generates a simulation, taking into account the specific languages used by the specialists involved in the field. This DSL requires the definition, the formalization, the composition and the integration of several models, regardig to the specific languages used by the specialists involved in the field. The specific language dedicated to the field of fire safety is designed by composing and integrating several other DSLs described by technical and natural languages (as well as natural languages referring to technical ones). These latter are modeled in a way that their components must be precise and based on mathematical foundations, in order to verify the consistency of the system (people and materials are safe) before it implementation. In this context, we propose to adopt a formal approach, based on algebraic specifications, to formalize the languages used by the specialists involved in the generation system, focusing on both syntaxes and semantics of the dedicated languages. In the algebraic approach, the concepts of the domain are abstracted by data types and the relationships between them. The semantics of specific languages is described by the relationships, the mappings between the defined data types and their properties. The simulation language is based on a composition of several specific DSLs previously described and formalized. The DSLs are implemented based on the concepts of functional programming and the Haskell functional language, well adapted to this approach. The result of this work is a software dedicated to the automatic generation of a simulation, in order to facilitate the evaluation of the fire safety level to the engineers. This tool is the property of the Scientific and Technical Center for Building (CSTB), an organization whose mission is to guarantee the quality and safety of buildings by combining multidisciplinary skills to develop and share scientific and technical knowledge, in order to provide to the different actors the expected answers in their professional practice.