Cette thèse s'intéresse à la modélisation de la syntaxe et de l'interface syntaxe-sémantique de la phrase, et explore la possibilité de contrôler au niveau des structures de dérivation la surgénération que produit le traitement des dépendances à distance par des types d'ordre supérieur. À cet effet, nous étudions la possibilité d'étendre le système de typage des Grammaires Catégorielles Abstraites avec les constructions de la somme disjointe, du produit cartésien et du produit dépendant, permettant d'étiqueter les catégories syntaxiques par des structures de traits. Nous prouvons dans un premier temps que le calcul résultant de cette extension bénéficie des propriétés de confluence et de normalisation, permettant d'identifier les termes beta-équivalents dans le formalisme grammatical. Nous réduisons de plus le même problème pour la beta-eta-équivalence à un ensemble d'hypothèse de départ. Dans un second temps, nous montrons comment cette introduction de structures de traits peut être appliquée au contrôle des dépendances à distances, à travers les exemples des contraintes de cas, des îlots d'extraction pour les mouvements explicites et implicites, et des extractions interrogatives multiples, et nous discutons de la pertinence de placer ces contrôles sur les structures de dérivation / This thesis focuses on the modelisation of syntax and syntax-semantics interface of sentences, and investigate how the control of the surgeneration caused by the treatment of linguistics movements with higher order types can take place at the level of derivation structures. For this purpose, we look at the possibility to extend the type system of Abstract Categorial Grammars with the constructions of disjoint sum, cartesian product and dependent product, which enable syntactic categories to be labeled by feature structures. At first, we demonstrate that the calculus associated with this extension enjoy the properties of confluence and normalization, by which beta-equivalence can be computed in the grammatical formalism. We also reduce the same problem for beta-eta-equivalence to a few hypothesis. Then, we show how this feature structures can be used to control linguistics movements, through the examples of case constraints, extraction islands for overt and covert movements and multiples interrogative extractions, and we discuss the relevancy of operating these controls on the derivation structures

Nowadays, mobile computing is more present in daily life. Mobile phones, notebooks, smart phones and wireless networks are part of everyday life. With this technology available, the research in pervasive computing is growing. The idea of pervasive computing was introduced by Mark Weiser in 1991, with a personal vision of how would be computing in the 21st century. Weiser s idea was that information processing would become part of everyday life, and would be available everywhere. Furthermore, it would be so natural as being invisible in the ambient. To make computing invisible, applications must be proactive, asking for a minimum of user intervention for its operation. An important concept that arises with pervasive computing is the context awareness . Context is any information that can be used to characterize an entity. Based on contextual information, applications can dynamically adapt to the environments in which they operate, becoming proactive and conveying the idea of invisibility. New programming languages or even new paradigms are being developed trying to make more intuitive the programming of pervasive applications. Most of these programming languages attempt to add new features into existing programming languages. However, some authors argue that there must be new formalisms that help to model the properties of pervasive systems, in particular the context awareness. The formal description of a system modeled by formal methods can be used to demonstrate that some properties of the system are correctly modeled. In this sense, this work studies a formal model that can be used as a basis for specifying a new programming language, called Calculus of Context-aware Ambients (CCA), proposed to describe mobile and pervasive applications. Another formal method used in the specification of programming languages are the type systems. Type systems helps to ensure that the system behaves according to the specification, that is, is a way to formally prove the absence of undesirable behavior in a system. Thus, the main contribution of this work is the definition of a type system for the CCA with the focus in the communication between processes. As a case study two real scenarios were modeled using the CCA, demonstrating the use of the type system developed. The preservation (or subject reduction) property of the type system was formally proved, demonstrating that the type system is correct, i.e., achieving the main purpose of the present work. / Atualmente, a computação móvel está mais presente na rotina das pessoas. Celulares, notebooks, smartphones e redes sem fio fazem parte do cotidiano. Com essa tecnologia disponível, as pesquisas na área de computação pervasiva crescem a cada dia. A ideia da computação pervasiva surgiu com um artigo escrito por Mark Weiser em 1991, com uma visão pessoal de como seria a computação no século 21. Weiser descreveu que a computação faria parte do cotidiano das pessoas, e estaria acessível em todos os ambientes. Além disso, seria tão natural que passaria a ideia de estar invisível no ambiente. Para tornar a computação invisível, as aplicações devem ser pró-ativas, solicitando o mínimo de intervenção do usuário para o seu funcionamento. Um conceito importante que surge na computação pervasiva é a sensibilidade ao contexto . Contexto é qualquer informação que possa ser utilizada para caracterizar uma entidade. Com base em informações contextuais, as aplicações podem se adaptar dinamicamente aos ambientes nos quais estão inseridas, tornando-se pró-ativas e transmitindo a ideia da invisibilidade. Novas linguagens de programação ou até mesmo novos paradigmas de programação estão sendo desenvolvidos, tentando tornar mais intuitiva a programação de aplicações pervasivas. A maioria dessas linguagens tenta adicionar novas funcionalidades em linguagens já existentes. Porém, alguns autores defendem que deveriam existir novos formalismos que ajudem a modelar as propriedades dos sistemas pervasivos, em especial a sensibilidade ao contexto. A descrição formal de um sistema modelado através de métodos formais pode ser utilizada para demonstrar que algumas propriedades de um sistema estão corretamente modeladas. Nesse sentido, este trabalho estuda um modelo formal que pode servir como base para a especificação de novas linguagens de programação, chamado Cálculo de Ambientes Sensível ao Contexto (CASC), proposto para descrever ambientes móveis e aplicações pervasivas. Outro método formal que é utilizado para especificar linguagens de programação são os sistemas de tipos. Sistemas de tipos ajudam a garantir que um sistema se comporta de acordo com a sua especificação, ou seja, são uma maneira de provar formalmente a ausência de comportamentos indesejados dentro de um sistema. Dessa forma, a principal contribuição deste trabalho é a definição de um sistema de tipos para o CASC com o foco no controle de comunicação entre processos. Como estudo de caso, dois cenários reais foram modelados utilizando o CASC, demonstrando o uso do sistema de tipos desenvolvido. A propriedade preservation (ou subject reduction) do sistema de tipos foi provada formalmente, demostrando que o sistema de tipos está correto, ou seja, atingindo o objetivo principal do trabalho. Palavras-chave: Sistema de Tipos. Cálculo de Ambientes. Computação Pervasiva. Sensibilidade ao Contexto.

Exprimer le parallélisme dans la programmation de manière simple et performante est un défi auquel l'informatique fait face, en raison de l'évolution actuelle des architectures matérielles. BSML est un langage permettant une programmation parallèle de haut niveau, structurée, qui participe à cette recherche. En s'appuyant sur le coeur du langage existant, cette thèse propose d'une part des extensions qui en font un langage plus général et plus simple (traits impératifs tels que références et exceptions, syntaxe spécifique...) tout en conservant et étendant sa sûreté (sémantiques formelles, système de types...) et d'autre part une méthodologie de développement d'applications parallèles certifiées / Finding a good paradigm to represent parallel programming in a simple and efficient way is a challenge currently faced by computer science research, mainly due to the evolution of machine architectures towards multi-core processors. BSML is a high level, structured parallel programming language that takes part in the research in an original way. By building upon existing work, this thesis extends the language and makes it more general, simple and usable with added imperative features such as references and exceptions, a specific syntax, etc. The existing formal and safety characteristics of the language (semantics, type system...) are preserved and extended. A major application is given in the form of a methodology for the development of fully proved parallel programs

Cette thèse traite de la conception et implémentationd’un langage de programmation pour les systèmes detraitement de flux en temps réel, comme l’encodagevidéo. Le modèle des réseaux de Kahn est bien adaptéà ce domaine et y est couramment utilisé. Dans cemodèle, un programme consiste en un ensemble deprocessus parallèles communicant à travers des filesmono-producteur, mono-consommateur. La force dumodèle réside en son déterminisme.Les langages synchrones fonctionnels comme Lustresont dédiés aux systèmes embarqués critiques. Un programmeLustre définit un réseau de Kahn synchronequi peut être exécuté avec des files bornées et sans blocage.Cette propriété est garantie par un système detypes dédié, le calcul d’horloge, qui établit une échellede temps globale à un programme. Cette échelle detemps globale est utilisée pour définir les horloges, sé-quences booléennes indiquant pour chaque file, et àchaque pas de temps, si un processus produit ou consommeune donnée. Cette information sert non seulementà assurer la synchronie mais également à générerdu logiciel ou matériel à état fini.Nous proposons et étudions les horloges entières, unegénéralisation des horloges booléennes autorisant desentiers naturels arbitrairement grands. Les horlogesentières décrivent la production ou consommation deplusieurs valeurs depuis une même file au cours d’uninstant. Nous les utilisons pour définir la constructiond’échelle de temps locale, qui peut masquer despas de temps cachés par un sous-programme au contexteenglobant.Ces principes sont intégrés à un calcul d’horloge pourun langage fonctionnel d’ordre supérieur. Nous étudionsses propriétés et prouvons en particulier que lesprogrammes bien typés ne bloquent pas. Nous compilonsles programmes typés vers des circuits numériquessynchrones en adaptant le schéma de générationde code dirigé par les horloges de Lustre. L’informationde typage contrôle certains compromis entre temps etespace dans les circuits générés. / This thesis addresses the design and implementationof a programming language for real-time streaming applications,such as video decoding. The model of Kahnprocess networks is a natural fit for this area and hasbeen used extensively. In this model, a program consistsin a set of parallel processes communicating via singlereader, single writer queues. The strength of the modellies in its determinism.Synchronous functional languages such as Lustre arededicated to critical embedded systems. A Lustre programdefines a synchronous Kahn process network, thatis, which can be executed using finite queues and withoutdeadlocks. This is enforced by a dedicated type system,the clock calculus, which establishes a global timescale throughout a program. The global time scale isused to define clocks: per-queue boolean sequences indicating,for each time step, whether a process producesor consumes a token in the queue. This information isused both for enforcing synchrony and for generatingfinite-state software or hardware.We propose and study integer clocks, a generalizationof boolean clocks featuring arbitrarily big natural numbers.Integer clocks model the production or consumptionof several values from the same queue in the courseof a time step. We then rely on integer clocks to definethe local time scale construction, which may hide timesteps performed by a sub-program from the surroundingcontext.These principles are integrated into a clock calculus fora higher-order functional language. We study its properties,proving among other results that well-typed programsdo not deadlock. We adjust the clock-directedcode generation scheme of Lustre to generate finite-statedigital synchronous circuits from typed programs. Thetyping information controls certain trade-offs betweentime and space in the generated circuits.

<p>Static program analyzers are vital tools to produce useful insights about programs without executing these programs. These insights can be used to improve the quality of programs, e.g., detecting defects in programs, or optimizing programs to use fewer resources. However, building static program analyzers that are simultaneously sound, performant, and flexible is notoriously challenging.</p> <p>This dissertation aims to address this challenge by exploring the potential of applying correct-by-construction metaprogramming techniques to build static program analyzers. Metaprogramming techniques manipulate and transform programs as data objects.  In this thesis, we consider static program analyzers as the objects to be manipulated or transformed. We show that metaprogramming techniques can improve our understanding, the construction, flexibility, and performance of program analyzers.</p> <p>We first study the inter-derivation of abstract interpreters. Using off-the-shelf program transformation techniques such as refunctionalization, we demonstrate that big-step abstract interpreters can be mechanically derived from their small-step counterparts, thus building a functional correspondence between two different styles of abstract interpretation.</p> <p>To build high-performance program analyzers, we exploit the first Futamura projection to build compilers for abstract interpretation and symbolic execution. The first Futamura projection states that specializing an interpreter with respect to an input program is a process equivalent to compilation, thus providing a practical way to repurpose interpreters for compilation and code generation. We systematically apply this idea to build program-analysis compilers by writing analyzers as staged interpreters using higher-level abstractions. The staged interpreter can be used for generating sound and performant analysis code given a specific input program. Moreover, the approach enables using abstractions without regret: by using higher-level program abstractions, the analyzer can be written in a way that is close to its high-level specification (e.g. big-step operational semantics), and by compilation, the analyzer is performant since it does not need to pay the runtime overhead of using these abstraction mechanisms.</p> <p>We also develop novel type systems that track sharing and separation in higher-order imperative languages. Such type systems are useful both for general-purpose programming languages and for optimization of domain-specific metaprograms such as those program-analysis compilers.</p> <p><br></p>

Dans ce travail, nous adaptons la méthode des symétries conditionnelles afin de construire des solutions exprimées en termes des invariants de Riemann. Dans ce contexte, nous considérons des systèmes non elliptiques quasilinéaires homogènes (de type hydrodynamique) du premier ordre d'équations aux dérivées partielles multidimensionnelles. Nous décrivons en détail les conditions nécessaires et suffisantes pour garantir l'existence locale de ce type de solution. Nous étudions les relations entre la structure des éléments intégraux et la possibilité de construire certaines classes de solutions de rang k. Ces classes de solutions incluent les superpositions non linéaires d'ondes de Riemann ainsi que les solutions multisolitoniques. Nous généralisons cette méthode aux systèmes non homogènes quasilinéaires et non elliptiques du premier ordre. Ces méthodes sont appliquées aux équations de la dynamique des fluides en (3+1) dimensions modélisant le flot d'un fluide isentropique. De nouvelles classes de solutions de rang 2 et 3 sont construites et elles incluent des solutions double- et triple-solitoniques. De nouveaux phénomènes non linéaires et linéaires sont établis pour la superposition des ondes de Riemann. Finalement, nous discutons de certains aspects concernant la construction de solutions de rang 2 pour l'équation de Kadomtsev-Petviashvili sans dispersion. / In this work, the conditional symmetry method is adapted in order to construct solutions expressed in terms of Riemann invariants. Nonelliptic quasilinear homogeneous systems of multidimensional partial differential equations of hydrodynamic type are considered. A detailed description of the necessary and sufficient conditions for the local existence of these types of solutions is given. The relationship between the structure of integral elements and the possibility of constructing certain classes of rank-k solutions is discussed. These classes of solutions include nonlinear superpositions of Riemann waves and multisolitonic solutions. This approach is generalized to first-order inhomogeneous hyperbolic quasilinear systems. These methods are applied to the equations describing an isentropic fluid flow in (3+1) dimensions. Several new classes of rank-2 and rank-3 solutions are obtained which contain double and triple solitonic solutions. New nonlinear and linear superpositions of Riemann waves are described. Finally, certain aspects of the construction of rank-2 solutions through an application to the dispersionless Kadomtsev-Petviashvili equation are discussed.

Dans ce travail, nous adaptons la méthode des symétries conditionnelles afin de construire des solutions exprimées en termes des invariants de Riemann. Dans ce contexte, nous considérons des systèmes non elliptiques quasilinéaires homogènes (de type hydrodynamique) du premier ordre d'équations aux dérivées partielles multidimensionnelles. Nous décrivons en détail les conditions nécessaires et suffisantes pour garantir l'existence locale de ce type de solution. Nous étudions les relations entre la structure des éléments intégraux et la possibilité de construire certaines classes de solutions de rang k. Ces classes de solutions incluent les superpositions non linéaires d'ondes de Riemann ainsi que les solutions multisolitoniques. Nous généralisons cette méthode aux systèmes non homogènes quasilinéaires et non elliptiques du premier ordre. Ces méthodes sont appliquées aux équations de la dynamique des fluides en (3+1) dimensions modélisant le flot d'un fluide isentropique. De nouvelles classes de solutions de rang 2 et 3 sont construites et elles incluent des solutions double- et triple-solitoniques. De nouveaux phénomènes non linéaires et linéaires sont établis pour la superposition des ondes de Riemann. Finalement, nous discutons de certains aspects concernant la construction de solutions de rang 2 pour l'équation de Kadomtsev-Petviashvili sans dispersion. / In this work, the conditional symmetry method is adapted in order to construct solutions expressed in terms of Riemann invariants. Nonelliptic quasilinear homogeneous systems of multidimensional partial differential equations of hydrodynamic type are considered. A detailed description of the necessary and sufficient conditions for the local existence of these types of solutions is given. The relationship between the structure of integral elements and the possibility of constructing certain classes of rank-k solutions is discussed. These classes of solutions include nonlinear superpositions of Riemann waves and multisolitonic solutions. This approach is generalized to first-order inhomogeneous hyperbolic quasilinear systems. These methods are applied to the equations describing an isentropic fluid flow in (3+1) dimensions. Several new classes of rank-2 and rank-3 solutions are obtained which contain double and triple solitonic solutions. New nonlinear and linear superpositions of Riemann waves are described. Finally, certain aspects of the construction of rank-2 solutions through an application to the dispersionless Kadomtsev-Petviashvili equation are discussed.

GaugThe first half of the thesis concerns Abelian vortices and Yang-Mills theory. It is proved that the 5 types of vortices recently proposed by Manton are actually symmetry reductions of (anti-)self-dual Yang-Mills equations with suitable gauge groups and symmetry groups acting as isometries in a 4-manifold. As a consequence, the twistor integrability results of such vortices can be derived. It is presented a natural definition of their kinetic energy and thus the metric of the moduli space was calculated by the Samols' localisation method. Then, a modified version of the Abelian–Higgs model is proposed in such a way that spontaneous symmetry breaking and the Bogomolny argument still hold. The Painlevé test, when applied to its soliton equations, reveals a complete list of its integrable cases. The corresponding solutions are given in terms of third Painlevé transcendents and can be interpreted as original vortices on surfaces with conical singularity. The last two chapters present the following results in projective differential geometry and Hamiltonians of hydrodynamic-type systems. It is shown that the projective structures defined by the Painlevé equations are not metrisable unless either the corresponding equations admit first integrals quadratic in first derivatives or they define projectively flat structures. The corresponding first integrals can be derived from Killing vectors associated to the metrics that solve the metrisability problem. Secondly, it is given a complete set of necessary and sufficient conditions for an arbitrary affine connection in 2D to admit, locally, 0, 1, 2 or 3 Killing forms. These conditions are tensorial and simpler than the ones in previous literature. By defining suitable affine connections, it is shown that the problem of existence of Killing forms is equivalent to the conditions of the existence of Hamiltonian structures for hydrodynamic-type systems of two components.

<p>Three issues will be elaborated and disussed in the proposed thesis. The first is<br />administration and control of data access rights in networks with XML data, with<br />emphasis on data security. The second is the administration and control of<br />access rights to data in computer networks with RDF data, with emphasis on<br />data privacy. The third is prevention of errors and memory leaks, as well as<br />communication errors, generated by programs written in Sing # language in the<br />presence of exceptions. For all three issues, there will be presented formal<br />models with corresponding type systems and showed the absence of undesired<br />behavior i.e. errors in networks or programs.</p> / <p>У тези су разматрана три проблема. Први је администрација и контрола<br />права приступа података у рачунарској мрежи са XML подацима, са<br />нагласком на безбедости посматраних података. Други је администрација и<br />котрола права приступа подацима у рачунарској мрежи са RDF подацима,<br />са нагласком на приватности посматраних података. Трећи је превенција<br />грешака и цурења меморије, као и грешака у комуникацији генерисаним<br />програмима написаних на језику Sing# у којима су присутни изузеци. За сва<br />три проблема биће предложени формални модели и одговарајући типски<br />системи помоћу којих се показује одсуство неповољних понашања тј.<br />грешака у мрежама односно програмима.</p> / <p>U tezi su razmatrana tri problema. Prvi je administracija i kontrola<br />prava pristupa podataka u računarskoj mreži sa XML podacima, sa<br />naglaskom na bezbedosti posmatranih podataka. Drugi je administracija i<br />kotrola prava pristupa podacima u računarskoj mreži sa RDF podacima,<br />sa naglaskom na privatnosti posmatranih podataka. Treći je prevencija<br />grešaka i curenja memorije, kao i grešaka u komunikaciji generisanim<br />programima napisanih na jeziku Sing# u kojima su prisutni izuzeci. Za sva<br />tri problema biće predloženi formalni modeli i odgovarajući tipski<br />sistemi pomoću kojih se pokazuje odsustvo nepovoljnih ponašanja tj.<br />grešaka u mrežama odnosno programima.</p>

Cette thèse porte sur l’adaptation de la réalisabilité et la paramétricité au cas des types dépendants dans le cadre des Systèmes de Types Purs. Nous décrivons une méthode systématique pour construire une logique à partir d’un langage de programmation, tous deux décrits comme des systèmes de types purs. Cette logique fournit des formules pour exprimer des propriétés des programmes et elle offre un cadre formel adéquat pour développer une théorie de la réalisabilité au sein de laquelle les réalisateurs des formules sont exactement les programmes du langage de départ. Notre cadre permet alors de considérer les théorèmes de représentation pour le système T de Gödel et le système F de Girard comme deux instances d'un théorème plus général.Puis, nous expliquons comment les relations logiques de la théorie de la paramétricité peuvent s'exprimer en terme de réalisabilité, ce qui montre que la logique engendrée fournit un cadre adéquat pour développer une théorie de la paramétricité du langage de départ. Pour finir, nous montrons comment cette théorie de la paramétricité peut-être adaptée au système sous-jacent à l'assistant de preuve Coq et nous donnons un exemple d'application original de la paramétricité à la formalisation des mathématiques. / This thesis focuses on the adaptation of realizability and parametricity to dependent types in the framework of Pure Type Systems. We describe a systematic method to build a logic from a programming language, both described as pure type systems. This logic provides formulas to express properties of programs and offers a formal framework that allows us to develop a theory of realizability in which realizers of formulas are exactly programs of the starting programming language. In our framework, the standard representation theorems of Gödel's system T and Girard's system F may be seen as two instances of a more general theorem. Then, we explain how the so-called « logical relations » of parametricity theory may be expressed in terms of realizability, which shows that the generated logic provides an adequate framework for developping a general theory of parametricity. Finally, we show how this parametricity theory can be adapted to the underlying type system of the proof assistant Coq and we give an original example of application of parametricity theory to the formalization of mathematics.