To see the other types of publications on this topic, follow the link: Denotational semantic.
Dissertations / Theses on the topic 'Denotational semantic'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 45 dissertations / theses for your research on the topic 'Denotational semantic.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Bryans, Jeremy William. "Denotational semantic models for real-time LOTOS." Thesis, University of Reading, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.360755.
Full text
2
Azevedo, Terceiro Antonio Soares de. "Semantics for an algebraic specification language." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2006. http://hdl.handle.net/10183/8126.
Full textAbstract:
Prosoft é um grupo de pesquisa do Instituto de Informática da UFRGS, desenvolvido pelo grupo de pesquisa homônimo e coordenado pelo Professor Daltro José Nunes. O objetivo do projeto é desenvolver um ambiente de desenvolvimento de software completo, o Ambiente Prosoft, que é baseado nos conceitos de Modelos, Cálculo Lambda, Tipos Abstratos de Dados e Orientação a Objetos. Um dos componentes do Ambiente Prosoft é sua linguagem de especificação algébrica: o Prosoft Algébrico. Apesar de ser base e tema de diversos trabalhos no grupo de pesquisa Prosoft, o Prosoft Algébrico não tem sua semântica devidamente definida. Os trabalhos desenvolvidos até agora foram baseados em noções operacionais, e apresentam diferentes interpretações do Prosoft Algébrico. Esta dissertação apresenta uma especificação de semântica denotacional para o Prosoft Algébrico, compreendendo, entre outras características, sua primitiva de comunicação entre tipos de dados, chamada ICS, e sua notação gráfica para representação de instanciação de tipos abstratos de dados. Essa dissertação apresenta também um estudo sobre prototipação semântica usando a linguagem de programação Haskell. O conceito de Literate Programming e a proximidade entre Cálculo Lambda e Haskell foram cruciais no rápido desenvolvimento de uma implementação protótipo do Prosoft Algébrico, baseada na sua semântica especificada. As principais contribuições dessa dissertação incluem: uma interpretação precisa e sem ambiguidades do Prosoft Algébrico, através da especificação da sua semântica; a definição de semântica para a ICS, um conceito único (até o limite do nosso conhecimento) que fornece um mecanismo de passagem de mensagens entre tipos de dados algébricos; uma implementação protótipo do Prosoft Algébrico, que pode realmente ser utilizada para experimentar e testar a definição da linguagem e a especificação da semântica do Prosoft Algébrico; resultados sobre prototipação semântica de especificações tanto de semântica denotacional quanto de semântica operacional usando a linguagem de programação Haskell para desenvolvimento rápido de protótipos de linguagens baseados na sua semântica. Como grande parte do desenvolvimento do Ambiente Prosoft é realizado através de projetos de cooperação internacional e essa dissertação irá influenciar fortemente o seu desenvolvimento futuro, o texto foi escrito em inglês para facilitar a troca de informação entre o grupo Prosoft e seus parceiros estrangeiros.Prosoft is a research project at Instituto de Informática da UFRGS, developed by the research group with the same name and coordinated by Professor Daltro José Nunes. The project’s goal is to develop a full software development environment, the Prosoft Environment, based on the concepts of Models, Lambda Calculus, Abstract Data Types and Object orientation. One of the components of the Prosoft Environment is its algebraic specification language: Algebraic Prosoft. Although being the basis and theme of several works in the Prosoft research group, Algebraic Prosoft doesn’t have its semantics properly defined. Works done up to now were based on operational notions and presented different interpretations of Algebraic Prosoft. This thesis presents a denotational semantics specification for Algebraic Prosoft, comprising, among other features, its “inter-data type” communication primitive, called ICS, and its graphical notation for representing instantiations of abstract data types. This thesis also presents a study of semantic prototyping using the Haskell programming language. The concept of Literate Programing and the proximity between lambda calculus and Haskell were crucial to the rapid development of a prototype implementation of Algebraic Prosoft, based on its specified semantics. This thesis’ main contributions include: a precise and unambiguous interpretation of Algebraic Prosoft, through a semantics specification; the definition of semantics to the ICS, a unique (to the best of our knowledge) concept that provides a messagepassing mechanism between algebraic data types; a prototype implementation of Algebraic Prosoft, which can actually be used to experiment and test the Algebraic Prosoft language definition and semantics specification; results regarding semantics prototyping of both denotational and operational semantics specifications using the Haskell programming language for rapid development of semantics-based prototypes of languages. Since a large portion of Prosoft Environment’s development is done through international cooperation projects and this thesis will strongly influence its future development, the text was written in English in order to facilitate the information exchange between the Prosoft research group and its foreign partners.
3
Gouy, Xavier. "Etude des théories équationelles et des propriétés algébriques des modèles stables du Lambda-calcul." Paris 7, 1995. http://www.theses.fr/1995PA077203.
Full textAbstract:
Ce travail est principalement consacre a l'etude des modeles stables du lambda-calcul pur. Il vise a situer cette classe de modeles par rapport a celle des modeles continus, de facon a mettre en evidence les ameliorations que la stabilite apporte a la modelisation du lambda-calcul pur. Pour ce faire, nous avons etudie les modeles du double point de vue de leur theorie equationnelle et de leurs proprietes algebriques. Nous presentons d'abord une classe abstraite de semantiques (les categories cartesiennes closes regulieres), qui contient les semantiques continue, stable et fortement stable, et nous montrons que dans ce cadre, tout modele analogue au modele de scott a la meme theorie equationnelle que ce dernier. Nous montrons qu'en revanche le modele de park et son analogue stable ont des theories differentes. Nous montrons ensuite que la classe des modeles stables est incomplete. Enfin, nous montrons que tout di-domaine reflexif contient un di-domaine de retractions universelles
4
Ruoppolo, Domenico. "Relational graph models and Morris's observability : resource-sensitive semantic investigations on the untyped λ-calculus." Thesis, Sorbonne Paris Cité, 2016. http://www.theses.fr/2016USPCD069/document.
Full textAbstract:
La thèse contribue à l’étude du λ-calcul non-typé de Church, un système de réécriture dont la règle principale est la β-réduction (formalisant l’exécution d’un programme). Nous nous concentrons sur la sémantique dénotationnelle, l’étude de modèles du λ-calcul interprétant de la même façon les λ-termes β-convertibles. On examine la sémantique relationnelle, une sémantique sensible aux ressources qui interprète les λ-termes comme des relations avec les entrées regroupées en multi-ensembles. Nous définissons une classe de modèles relationnels, les modèles de graphe relationnels (rgm’s), que nous étudions avec une approche issue de la théorie des types et de la démonstration, par le biais de certains systèmes de types avec intersection non-idémpotente. D’abord, nous découvrons la plus petite et la plus grande λ–théorie (théorie équationnelle étendant la β-conversion) représentées dans la classe. Ensuite, nous utilisons les rgm’s afin de résoudre le problème de l’adéquation complète pour la λ–théorie observationnelle de Morris, à savoir l’équivalence contextuelle de programmes que l’on obtient lorsqu’on prend les β-formes normales comme sorties observables. On résoudre le problème de différentes façons. En caractérisant la β-normalisabilité avec les types, nous découvrons une infinité de rgm’s complètement adéquats, que nous appelons uniformément sans fond. Puis, nous résolvons le problème de façon exhaustive, en prouvant qu’un rgm est complètement adéquat pour l’observabilité de Morris si et seulement si il est extensionnel (il modèle l’ŋ-conversion) et λ-König. Moralement un rgm est λ-König si tout arbre récursif infini a une branche infinie témoignée par un type non-bien-fondéThis thesis is a contribution to the study of Church’s untyped λ-calculus, a term rewritingsystem having the β-reduction (the formal counterpart of the idea of execution of programs) asmain rule. The focus is on denotational semantics, namely the investigation of mathematical models of the λ-calculus giving the same denotation to β-convertible λ-terms. We investigate relational semantics, a resource-sensitive semantics interpreting λ-terms as relations,with their inputs grouped together in multisets. We define a large class of relational models,called relational graph models (rgm’s), and we study them in a type/proof-theoretical way, using some non-idempotent intersection type systems. Firstly, we find the minimal and maximal λ-theories (equational theories extending -conversion) represented by the class.Then we use rgm’s to solve the full abstraction problem for Morris’s observational λ-theory,the contextual equivalence of programs that one gets by taking the β-normal forms asobservable outputs. We solve the problem in different ways. Through a type-theoretical characterization of β-normalizability, we find infinitely many fully abstract rgm’s, that wecall uniformly bottomless.We then give an exhaustive answer to the problem, by showing thatan rgm is fully abstract for Morris’s observability if and only if it is extensional (a model of ŋ-conversion) and λ-König. Intuitively an rgm is λ-König when every infinite computable tree has an infinite branch witnessed by some type of the model, where the witnessing is a property of non-well-foundedness on the type
5
MARANHÃO, Heitor Paceli. "Program synthesis from denotational semantics." Universidade Federal de Pernambuco, 2016. https://repositorio.ufpe.br/handle/123456789/20828.
Full textAbstract:
Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2017-08-23T12:57:53Z
No. of bitstreams: 2
license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5)
Dissertacao_Heitor_Maranhao.pdf: 1117044 bytes, checksum: ceea86d5a4dad585b8f79f5f79278656 (MD5)Made available in DSpace on 2017-08-23T12:57:53Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) Dissertacao_Heitor_Maranhao.pdf: 1117044 bytes, checksum: ceea86d5a4dad585b8f79f5f79278656 (MD5) Previous issue date: 2016-09-13
Program synthesis aims to automate the task of programming. Through program synthesis it is possible to let the programmer free to care about the description (specification) of the problem to be solved by the program under development, reducing human interaction with coding tasks. Automating new algorithms creation and transferring responsibility for writing code are some of the benefits propitiated by program synthesis. In this work, program synthesis is presented as an Alloy* specification for an imperative language. We synthesize programs described by pre and post-conditions (contracts) written using a Domain Specific Language proposed in this work. We embed the syntax and the denotational semantics of Winskel’s imperative language in Alloy*. Alloy* has proven to be an easy and productive way of building program synthesizers. Our experiments show that synthesis based on Alloy* is competitive once contracts, scopes and, if needed, sketches, are correctly chosen. As a consequence, our Alloy* program synthesizer can provide, in a single high-level framework, different features in comparison to other synthesizers: (i) synthesis based on scope; (ii) synthesis based on sketches; and (iii) verification. We introduce our Domain Specific Language for contracts and present a detailed description on the synthesis of the swap problem, the product of two numbers, the maximum of 2 and of 3 numbers, and the greatest common divisor. Another contribution of this work is a source code generator, using the programming language C#, of the algorithms created by our synthesizer.
Síntese de programas permite automatizar as atividades de programação. Através desta automação é possível deixar o programador livre para criar a descrição (especificação) do problema que o programa a ser desenvolvido busca resolver, reduzindo a interação humana com a etapa de escrita de código. Automatizar criação de novos algoritmos e transferir para máquinas a responsabilidade de escrever o código de programas são alguns dos benefícios que a síntese de programas possibilita. Neste trabalho, síntese de programas é apresentada através de uma especificação em Alloy* usando uma linguagem imperativa. A síntese é realizada a partir de um par de predicados, pré e pós-condição (contrato), escritos usando uma linguagem de domínio específico proposta neste trabalho. A semântica denotacional da linguagem imperativa usada por Winskel foi embutida em Alloy*. O uso de Alloy* se mostrou uma maneira fácil e produtiva de construir sintetizadores de programas. Os experimentos mostram que síntese baseada em Alloy* é competitiva, uma vez que contratos, escopos e, se necessário, esboços, sejam corretamente escolhidos. Como consequência, o sintetizador de programas em Alloy* pode fornecer, em um único framework de alto nível, características diferentes em comparação com outros sintetizadores: (i) síntese baseada em escopo; (ii) síntese baseada em esboços; e (iii) verificação. Para demonstrar a aplicabilidade prática de nosso trabalho, usamos nossa ferramenta na síntese de problemas clássicos da Computação, tais como troca do valor entre duas variáveis, o produto de dois números, o máximo de 2 e 3 números, e o maior divisor comum entre dois números. Outra contribuição deste trabalho consiste em um gerador de código na linguagem de programação C#, dos algoritmos criados pelo nosso sintetizador.
6
Bialkiewicz, Joël-Alexis. "Towards a denotational semantics for mobility." Paris 6, 2011. http://www.theses.fr/2011PA066007.
Full textAbstract:
La sémantique des systèmes concurrents a été largement étudiée. Même si plusieurs pistes ont été explorées, il y a deux écoles de pensée en la matière. La première promeut le pi-calcul, une algèbre de processus définie en étendant son ancêtre CCS. Son point de vue sémantique est opérationnel, étant donné que les processus sont représentés comme des systèmes de transitions étiquetées. Son avantage principale est qu'il permet de représenter la mobilité, c'est-à-dire la capacité des processus à changer de voisins, de façon intuitive. Ceci est possible en permettant à la portée des canaux de varier. La seconde approche repose sur CSP, une algèbre de processus qui est construite du point de vue dénotationnel, en tant qu'un langage concurrent à passage de valeurs dont les processus sont représentés dans un système de traces ensemblistes qui a été étendu année après année. Même si CSP ne gère pas nativement la mobilité, il a été récemment montré qu'il est suffisamment expressif pour encoder le pi-calcul. Le but principal de cette thèse était et est toujours de construire un pont entre les deux mondes, en apportant une algèbre de processus qui soit à la fois intégralement mobile comme le pi-calcul, avec toute l'expressivité de la portée dynamique des canaux, mais aussi intégralement dénotationnelle comme CSP, avec une dénotation ensembliste définie pour chaque processus en lieu et place d'une caractérisation opérationnelle. Afin de conserver l'expressivité complète du pi-calcul, une partie de sa syntaxe et de ses constructions ont dû être conservées, spécifiquement son concept de restriction de portée qui, avec la possibilité d'envoyer des canaux à portée réduite à travers des canaux publics, permet de rendre la portée des canaux intégralement dynamique. Ces constructions, qui sont nécessaires pour la véritable mobilité, ne sont toutefois pas compatibles avec le concept d'échecs et de divergences hérité de CSP, dans la mesure où il impose qu'un nom de canal ait le même sens d'un bout à l'autre d'une trace d'exécution. Ceci a imposé de repenser le concept de traces étendues et d'introduire des localisations afin de lier chaque observation au potentiel du processus de permettre de nouvelles interactions à ce niveau, non pas à travers des ensembles de refus mais plutôt en utilisant une identification spatiale unique du nœud correspondant dans la structure de branchement du processus. Les contributions de la thèse sont les suivantes. D'abord, une algèbre de processus qui est d'une certaine façon un hybride entre le pi-calcul et CSP, et est à la fois dénotationnelle, compositionnelle et mobile est introduite. Elle est dénotationnelle parce que toute expression de processus peut être traduite en un modèle ensembliste sans perte d'information. Elle est compositionnelle parce que ces modèles peuvent être combinés sans tenir compte du contexte, et une relation d'équivalence indépendante du contexte a pu être conçue. Elle est mobile parce qu'elle partage la totalité des propriétés mobiles du pi-calcul, non seulement le passage de canaux mais aussi l'extrusion de portée. Ensuite, une sémantique axiomatique est également fournie, et il est prouvé qu'elle est correcte et complète pour la partie finie du langage. En raison de ses propriétés, l'algèbre de processus se comporte avec élégance vis-à-vis de l'opérateur de mismatch, ce qui n'est pas une évidence pour de nombreuses versions du pi-calcul. De plus, une théorie du raffinement est proposée pour le langage. Même si elle reste perfectible, c'est inédit dans le monde de la mobilité. Enfin, une logique dénotationnelle a été conçue en suivant en cela l'exemple de CSP.
7
Cunha, Joao Bernardo de Sena Esteves Falcao e. "Denotational semantics in the definition of natural language uses." Thesis, Imperial College London, 1990. http://hdl.handle.net/10044/1/47834.
Full text
8
Ekembe, Ngondi Gerard. "Denotational semantics of mobility in Unifying Theories of Programming (UTP)." Thesis, University of York, 2016. http://etheses.whiterose.ac.uk/16525/.
Full textAbstract:
UTP promotes the unification of programming theories and has been used successfully for giving denotational semantics to Imperative Programming, CSP process algebra, and the Circus family of programming languages, amongst others. In this thesis, we present an extension of UTP-CSP (the UTP semantics for CSP) with the concept of mobility. Mobility is concerned with the movement of an entity from one location (the source) to another (the target). We deal with two forms of mobility: • Channel mobility, concerned with the movement of links between processes, models networks with a dynamic topology; and • Strong process mobility, which requires to suspend a running process first, and then move both its code and its state upon suspension, and finally resume the process on the target upon reception. Concerning channel mobility: • We model channels as concrete entities in CSP, and show that it does not affect the underlying CSP semantics. • A requirement is that a process may not own a channel prior to receiving it. In CSP, the set of channels owned by a process (called its interface) is static by definition. We argue that making the interface variable introduces a paradox. We resolve this by introducing a new concept: the capability of a process, and show how it relates to the interface. We then define channel mobility as the operation that changes the interface of a process, but not its capability. We also provide a functional link between static CSP and its mobile version. Concerning strong mobility, we provide: • The first extension of CSP with jump features, using the concept of continuations. • A novel semantics for the generic interrupt (a parallel-based interrupt operator), using the concept of Bulk Synchronous Parallelism. We then define strong mobility as a specific interrupt operator in which the interrupt routine migrates the suspended program.
9
Brown, Simon Ambrose. "The semantics of database query languages." Thesis, University of Sheffield, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.310781.
Full text
10
Buth, Karl-Heinz [Verfasser]. "Techniques for Modelling Structured Operational and Denotational Semantics Definitions with Term Rewriting Systems / Karl Heinz Buth." Kiel : Universitätsbibliothek Kiel, 1994. http://d-nb.info/1080332669/34.
Full text
11
Sioson, Allan A. "Multimodal Networks in Biology." Diss., Virginia Tech, 2005. http://hdl.handle.net/10919/29995.
Full textAbstract:
A multimodal network (MMN) is a novel mathematical construct that captures the structure of biological networks, computational network models, and relationships from biological databases. An MMN subsumes the structure of graphs and hypergraphs, either undirected or directed. Formally, an MMN is a triple (V,E,M) where V is a set of vertices, E is a set of modal hyperedges, and M is a set of modes. A modal hyperedge e=(T,H,A,m) in E is an ordered 4-tuple, in which T,H,A are subsets of V and m is an element of M. The sets T, H, and A are the tail, head, and associate of e, while m is its mode. In the context of biology, each vertex is a biological entity, each hyperedge is a relationship, and each mode is a type of relationship (e.g., 'forms complex' and 'is a'). Within the space of multimodal networks, structural operations such as union, intersection, hyperedge contraction, subnetwork selection, and graph or hypergraph projections can be performed. A denotational semantics approach is used to specify the semantics of each hyperedge in MMN in terms of interaction among its vertices. This is done by mapping each hyperedge e to a hyperedge code algo:V(e), an algorithm that details how the vertices in V(e) get used and updated. A semantic MMN-based model is a function of a given schedule of evaluation of hyperedge codes and the current state of the model, a set of vertex-value pairs.
An MMN-based computational system is implemented as a proof of concept to determine empirically the benefits of having it. This system consists of an MMN database populated by data from various biological databases, MMN operators implemented as database functions, graph operations implemented in C++ using LEDA, and mmnsh, a shell scripting language that provides a consistent interface to both data and operators. It is demonstrated that computational network models may enrich the MMN database and MMN data may be used as input to other computational tools and environments. A simulator is developed to compute from an initial state and a schedule of hyperedge codes the resulting state of a semantic MMN model.Ph. D.
12
Battenfeld, Ingo. "Topological domain theory." Thesis, University of Edinburgh, 2008. http://hdl.handle.net/1842/2214.
Full textAbstract:
This thesis presents Topological Domain Theory as a powerful and flexible framework for denotational semantics. Topological Domain Theory models a wide range of type constructions and can interpret many computational features. Furthermore, it has close connections to established frameworks for denotational semantics, as well as to well-studied mathematical theories, such as topology and computable analysis. We begin by describing the categories of Topological Domain Theory, and their categorical structure. In particular, we recover the basic constructions of domain theory, such as products, function spaces, fixed points and recursive types, in the context of Topological Domain Theory. As a central contribution, we give a detailed account of how computational effects can be modelled in Topological Domain Theory. Following recent work of Plotkin and Power, who proposed to construct effect monads via free algebra functors, this is done by showing that free algebras for a large class of parametrised equational theories exist in Topological Domain Theory. These parametrised equational theories are expressive enough to generate most of the standard examples of effect monads. Moreover, the free algebras in Topological Domain Theory are obtained by an explicit inductive construction, using only basic topological and set-theoretical principles. We also give a comparison of Topological and Classical Domain Theory. The category of omega-continuous dcpos embeds into Topological Domain Theory, and we prove that this embedding preserves the basic domain-theoretic constructions in most cases. We show that the classical powerdomain constructions on omega-continuous dcpos, including the probabilistic powerdomain, can be recovered in Topological Domain Theory. Finally, we give a synthetic account of Topological Domain Theory. We show that Topological Domain Theory is a specific model of Synthetic Domain Theory in the realizability topos over Scott's graph model. We give internal characterisations of the categories of Topological Domain Theory in this realizability topos, and prove the corresponding categories to be internally complete and weakly small. This enables us to show that Topological Domain Theory can model the polymorphic lambda-calculus, and to obtain a richer collection of free algebras than those constructed earlier. In summary, this thesis shows that Topological Domain Theory supports a wide range of semantic constructions, including the standard domain-theoretic constructions, computational effects and polymorphism, all within a single setting.
13
Eberhart, Clovis. "Catégories et diagrammes de cordes pour les jeux concurrents." Thesis, Université Grenoble Alpes (ComUE), 2018. http://www.theses.fr/2018GREAM091/document.
Full textAbstract:
La sémantique des jeux est une approche pour modéliser les langages de programmation dans laquelle les types sont interprétés par des jeux et les programmes par des stratégies. Ces modèles de jeux ont couvert des constructions fonctionnelles et impératives, des opérateurs de contrôle, etc. L'approche a récemment été étendue aux langages non-déterministes et concurrents, provoquant au passage un changement de perspective profond~: les parties sont maintenant organisées en une catégorie, sur laquelle les stratégies sont des préfaisceaux. La notion fondamentale d'innocence a aussi été caractérisée comme une condition de faisceau. Cette thèse s'attache à l'étude de quelques constructions apparaissant dans ces nouveaux modèles de jeux.D'abord, constatant que, dans plusieurs de ces modèles, l'étape cruciale consiste à définir une catégorie double de jeux et de parties, nous proposons une construction abstraite d'une telle catégorie double à partir de données de base, puis nous démontrons que, sous des hypothèses adéquates, le résultat obtenu permet en effet la construction des stratégies.Dans un second temps, nous établissons un lien entre deux techniques existantes pour définir les parties~: la technique standard, fondée sur les séquences justifiées, et une autre plus récente utilisant les diagrammes de cordes. Nous définissons un plongement (plein) de la première dans la seconde et prouvons qu'elles induisent essentiellement le même modèle.Enfin, nous proposons une axiomatisation des notions de jeu et de partie, de laquelle nous tirons une catégorie de jeux et stratégies. Nous raffinons ensuite les axiomes pour traiter l'innocence et nous démontrons que, sous des hypothèses adéquates, les stratégies innocentes sont stables par compositionGame semantics is a class of models of programming languages in which types are interpreted as games and programs as strategies. Such game models have successfully covered diverse features, such as functional and imperative programming, or control operators. They have recently been extended to non-deterministic and concurrent languages, which generated an in-depth recasting of the standard approach: plays are now organised into a category, on which strategies are presheaves. The fundamental notion of innocence has also been recast as a sheaf condition. This thesis is a study of various constructions appearing in this new approach to game semantics.We first consider a pattern common to several game models of concurrent languages, in which games and plays are first organised into a double category, from which strategies are then derived. We provide an abstract construction of such a double category from more basic data, and prove that, under suitable hypotheses, the result allows the construction of strategies.Our second contribution is to relate two established techniques for defining plays: the standard one, based on justified sequences, and a more recent one, based on string diagrams. We (fully) embed the former into the latter and prove that they induce essentially the same model.Finally, we propose an axiomatisation of the notions of game and play, from which we formally derive a category of games and strategies. We also refine the axioms to deal with innocence, and prove that, under suitable hypotheses, innocent strategies are stable under composition
14
Glimming, Johan. "Primitive Direcursion and Difunctorial Semantics of Typed Object Calculus." Doctoral thesis, Stockholm : Numerisk analys och datalogi (KTH CSC), Stockholms universitet, 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-7208.
Full text
15
Kammar, Ohad. "Algebraic theory of type-and-effect systems." Thesis, University of Edinburgh, 2014. http://hdl.handle.net/1842/8910.
Full textAbstract:
We present a general semantic account of Gifford-style type-and-effect systems. These type systems provide lightweight static analyses annotating program phrases with the sets of possible computational effects they may cause, such as memory access and modification, exception raising, and non-deterministic choice. The analyses are used, for example, to justify the program transformations typically used in optimising compilers, such as code reordering and inlining. Despite their existence for over two decades, there is no prior comprehensive theory of type-and-effect systems accounting for their syntax and semantics, and justifying their use in effect-dependent program transformation. We achieve this generality by recourse to the theory of algebraic effects, a development of Moggi’s monadic theory of computational effects that emphasises the operations causing the effects at hand and their equational theory. The key observation is that annotation effects can be identified with the effect operations. Our first main contribution is the uniform construction of semantic models for typeand- effect analysis by a process we call conservative restriction. Our construction requires an algebraic model of the unannotated programming language and a relevant notion of predicate. It then generates a model for Gifford-style type-and-effect analysis. This uniform construction subsumes existing ad-hoc models for type-and-effect systems, and is applicable in all cases in which the semantics can be given via enriched Lawvere theories. Our second main contribution is a demonstration that our theory accounts for the various aspects of Gifford-style effect systems. We begin with a version of Levy’s Callby- push-value that includes algebraic effects. We add effect annotations, and design a general type-and-effect system for such call-by-push-value variants. The annotated language can be thought of as an intermediate representation used for program optimisation. We relate the unannotated semantics to the conservative restriction semantics, and establish the soundness of program transformations based on this effect analysis. We develop and classify a range of validated transformations, generalising many existing ones and adding some new ones. We also give modularly-checkable sufficient conditions for the validity of these optimisations. In the final part of this thesis, we demonstrate our theory by analysing a simple example language involving global state with multiple regions, exceptions, and nondeterminism. We give decision procedures for the applicability of the various effect-dependent transformations, and establish their soundness and completeness.
16
Huffman, Brian Charles. "HOLCF '11: A Definitional Domain Theory for Verifying Functional Programs." PDXScholar, 2011. https://pdxscholar.library.pdx.edu/open_access_etds/113.
Full textAbstract:
HOLCF is an interactive theorem proving system that uses the mathematics of domain theory to reason about programs written in functional programming languages. This thesis introduces HOLCF '11, a thoroughly revised and extended version of HOLCF that advances the state of the art in program verification: HOLCF '11 can reason about many program definitions that are beyond the scope of other formal proof tools, while providing a high degree of proof automation. The soundness of the system is ensured by adhering to a definitional approach: New constants and types are defined in terms of previous concepts, without introducing new axioms. Major features of HOLCF '11 include two high-level definition packages: the Fixrec package for defining recursive functions, and the Domain package for defining recursive datatypes. Each of these uses the domain-theoretic concept of least fixed points to translate user-supplied recursive specifications into safe low-level definitions. Together, these tools make it easy for users to translate a wide variety of functional programs into the formalism of HOLCF. Theorems generated by the tools also make it easy for users to reason about their programs, with a very high level of confidence in the soundness of the results. As a case study, we present a fully mechanized verification of a model of concurrency based on powerdomains. The formalization depends on many features unique to HOLCF '11, and is the first verification of such a model in a formal proof tool.
17
Tsouanas, Athanasios. "On the semantics of disjunctive logic programs." Thesis, Lyon, École normale supérieure, 2014. http://www.theses.fr/2014ENSL0919.
Full textAbstract:
Cette thèse s’intéresse à la sémantique dénotationnelle (en théorie desmodèles et en théorie des jeux) de quatre langages de programmation logique: - LP, le plus restrictif de tous, - DLP, une extension de LP aux disjonctions, - LPN, une extension de LP aux négations, et - DLPN, qui inclut les deux.Ce manuscrit apporte trois contributions principales:(1) Un cadre abstrait pour la sémantique de la programmation logique yest défini, et toutes les approches sémantiques que nous étudions par lasuite prennent place dans ce cadre.Nous définissons la notion générale d'espace de valeurs de vérité commeune structure algébrique spécifique, satisfaisant un certain ensembled'axiomes. Les booléens forment l'exemple canonique d'un tel espace,mais nous devons étudier des cas plus généraux si nous voulonsconsidérer la "négation par l'échec". Pour cela, nous définissons etétudions une famille infinie d'espaces, paramétrée par un ordinal.(2) Une sémantique des jeux pour LP a été définie en 1986, et son étudea été approfondie en 1998. Elle a ensuite été étendue au cas desprogrammes LPN en 2005.Ici nous développons en détails une sémantique pour les programmes DLP.Nous prouvons qu'elle est correcte et complète par rapport aux modèlesminimaux de Minker.(3) Nous définissons un opérateur sémantique qui, étant donnée une sémantique abstraite d'un langage non disjonctif, la transforme en une sémantique disjonctive associée.La correction de cette transformation découle du fait qu'elle conserveles équivalences de sémantiques.Nous en présentons ensuite quelques applications qui permettent, entre autres, d'obtenir la première sémantique des jeux pour DLPNIn this thesis, we study denotational semantics (model-theoretic andgame-theoretic) of four logic programming languages:- LP which is the most restrictive one;- DLP which extends LP by allowing disjunctions;- LPN which extends LP by allowing negations; and- DLPN which allows both.The three main contributions of this dissertation can be summarized as follows:(1) An abstract framework for logic programming semantics is definedand all semantic approaches that we study are placed within this framework.We define the general notion of a truth value space as an appropriate algebraicstructure that satisfies a set of axioms.The booleans form the canonical example of such a space, but we need toconsider much more general ones when dealing with negation-as-failure. Forthis we define and study an infinite family of spaces, parametrized over anordinal number.(2) A game semantics for LP was defined in 1986 and further studied in 1998.Then in 2005 it was extended for the case of LPN programs.Here a game semantics for DLP programs is developed in full detail; we provethat it is sound and complete with respect to the standard, minimal modelssemantics of Minker.(3) We define a semantic operator which transforms any given abstractsemantics of a non-disjunctive language to a semantics of the"corresponding" disjunctive one. We exhibit the correctness of thistransformation by proving that it preserves equivalences of semantics,and we present some applications of it, obtaining new game semantics forDLPN, among others
18
Oliveira, Anna Maria Russo Patricio de. "Aspectos semânticos, conceituais e morfo-sintáticos das categorias nominais." Universidade de São Paulo, 2009. http://www.teses.usp.br/teses/disponiveis/8/8139/tde-05022010-155317/.
Full textAbstract:
Esta dissertação discute o estatuto morfossintático, semântico e conceitual das categorias nominais, a partir das denominações encontradas em textos didáticos e em trabalhos acadêmicos. O objetivo principal é esclarecer alguns aspectos que ainda permanecem obscuros na literatura, principalmente no que diz respeito às extensões de determinadas categorias nominais. As categorias discutidas neste trabalho são os nomes próprios, os nomes concretos e abstratos, os nomes de eventos e os nomes coletivos. Investigam-se especialmente as particularidades ligadas à interpretação das diferentes categorias nominais enquanto possíveis desencadeadoras de diferentes modos de denotação. Tendo como ponto de partida a semântica formal, este trabalho recebe contribuições também de outras sub-áreas da lingüística, assim como da filosofia da linguagem. Devido à escassez de embasamento teórico recente, foram buscados argumentos tanto em autores oriundos do campo filosófico tais como Russell, Wittgenstein e Varzi como lingüistas relativamente pouco freqüentados em nossos dias, como Jespersen e Pichon. O desenvolvimento desta pesquisa, que priorizou como objeto de análise, a língua portuguesa do Brasil, parece apontar alguns aspectos relevantes na diferenciação e na delimitação das classes nominais supra citadas. No caso dos nomes próprios, foi possível observar que as duas principais teorias que tratam deles, a descritivista e a referencialista, não são necessariamente excludentes. Do estudo dos vários autores que, de uma forma ou de outra, aderiram a essas teorias, evidenciou-se que cada uma delas, isoladamente tomada, apresenta deficiências que poderiam ser preenchidas pela outra e que ambas poderiam ser beneficiadas pelo acréscimo do fator contextual. Embora haja consenso quanto ao fato de que, do ponto de vista sintático, os nomes próprios ocupam o lugar do sujeito em sentenças afirmativas e que, do ponto de vista lógico, nomes próprios são todas as expressões nominais definidas, não é suficientemente salientado que, nesse aspecto, os nomes próprios são uma subclasse dos nomes concretos, assim como, de acordo com Ockham, coincidem com os nomes concretos os adjetivos empregados na predicação. Quanto à classe dos nomes abstratos, esta mostrou-se muito mais ampla do que se possa imaginar, abarcando além dos nomes abstratos de qualidades, derivados de adjetivos, também os nomes de ação e de estados, de derivação verbal, e os nomes quantificados (pela aposição de sufixos como edo, al, ama) ou massificados (pela aposição de sufixos como ada), de derivação substantival. No que diz respeito aos nomes coletivos, a pesquisa mostrou que, por exemplo, quando são examinados em sua forma desenvolvida (grupo de flores, no lugar de buquê), estes formam uma classe conspícua e de vasta aplicação. Além disso, o estudo dessa categoria abriu um interessante questionamento no que diz respeito à denotação dos nomes de espécies, pois os nomes coletivos teriam, apesar do atributo, uma extensão menor daquela dos nomes comuns. Os nomes de eventos constituíram também um assunto que não pode ser examinado apenas do ponto de vista semântico. No decorrer da pesquisa, este assunto levantou importantes aspectos morfológicos e sintáticos, pois, contrariamente ao que é consenso na literatura, os nomes de evento não parecem ser necessariamente de derivação verbal. No português, por exemplo, foram detectados vários nomes não deverbais que denotam eventos (festa, desastre, neblina, etc.), que são selecionados pelos mesmos verbos que selecionam os nomes de eventos derivados.This work discusses the morphosyntatic, semantic and conceptual statute of nominal categories from the denominations found in textbooks and academic writings. The main purpose is to clarify some aspects which remain obscure in the literature, mainly in regard to extensions of particular nominal categories. The categories discussed are the proper names, the concrete and abstract names, the event nouns and collective nouns. Particularities related to interpretations of different nominal categories are investigated as possible triggers of different denotation modes. Formal Semantics is the starting point of this work, which also has contributions from other subareas of Linguistics and from Philosophy of Language as well. Due to the lack of recent theoretical framework, arguments have been searched either in authors deriving from the philosophical area such as Russell, Wittgenstein and Varzi, or in not frequently studied nowadays linguists, like Jespersen and Pichon. The development of this research, which prioritized as its main analysis object Brazilian Portuguese, seems to point out some relevant aspects in the differentiation and delimitation of the nominal classes supra cited. Regarding proper names, it was possible to observe that the two main theories that deal with them, the descriptivist and referentialist ones, are not necessarily excludent. Considering the authors who somehow adhered to these theories, it became evident that each of them presents deficiencies that could be filled by the other and that both would benefit from the addition of the contextual factor. Despite of the consensus about the fact that, according to the syntactic point of view, proper names occupy the subject position in affirmative sentences and that, according to the logical point of view, proper names are all the definite nominal expressions, it is not enough highlighted that, in respect to that, proper names are a subclass of concrete names, likewise, to Ockham, III coincide with concrete nouns the adjectives used in predication. Concerning the abstract names class, it turned out to be much larger than could be expected, including not only the abstract names of qualities, but also nouns of actions and states, of verbal derivation, and the nouns quantified (by the adposition of suffixes like -edo, -al, -ama) or massified (by the adposition of suffixes like -ada), of nominal derivation. With respect to collective nouns, the research revealed that, for instance, when examined in their developed form grupo de flores (group of flowers) instead of buquê (bouquet), they represent a conspicuous class of large application. Additionally, the study of this category led to an interesting questioning of the species names denotation because the collective nouns seem to have, besides the attribute, a smaller extension than that of common names. Similarly, event nouns cant be analyzed only on a semantic basis. As the research advanced, this issue raised important morphological and syntactic aspects, because in spite of the consensus found in the literature, event nouns dont seem to be necessarily derived from verbs. In Portuguese, for example, there are non-deverbal event nouns like festa (party), desastre (disaster), neblina (fog), etc., which are selected by the same verbs that select the derived event nouns.
19
Kerjean, Marie. "Reflexive spaces of smooth functions : a logical account of linear partial differential equations." Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCC144/document.
Full textAbstract:
La théorie de la preuve se développe depuis la correspondance de Curry-Howard suivant deux sources d’inspirations : les langages de programmation, pour lesquels elle agit comme une théorie des types de données, et l’étude sémantique des preuves. Cette dernière consiste à donner des modèles mathématiques pour les comportements des preuves/programmes. En particulier, la sémantique dénotationnelle s’attache à interpréter les deux-ci comme des fonctions entre des types, et permet en retour d’affiner notre compréhension des preuves/programmes. La logique linéaire (LL), introduite par Girard, donne une interprétation logique des notions d’algèbre linéaire, quand la logique linéaire différentielle (DiLL), introduite par Ehrhard et Regnier, permet une compréhension logique de la notion de différentielle.Cette thèse s’attache à renforcer la correspondance sémantique entre théorie de la preuve et analyse fonctionnelle, en insistant sur le caractère involutif de la négation dans DiLL.La première partie consiste en un rappel des notions de linéarité, polarisation et différentiation en théorie de la preuve, ainsi qu’un exposé rapide de théorie des espaces vectoriels topologiques. La deuxième partie donne deux modèles duaux de la logique linéaire différentielle, interprétant la négation d’une formule respectivement par le dual faible et le dual de Mackey. Quand la topologie faible ne permet qu’une interprétation discrète des preuves sous forme de série formelle, la topologie de Mackey nous permet de donner un modèle polarisé et lisse de DiLL, et de raffiner des résultats précédemment obtenus par Blute, Dabrowski, Ehrhard et Tasson. Enfin, la troisième partie de cette thèse s’attache à interpréter les preuves de DiLL par des distributions à support compact. Nous donnons un modèle polarisé de DiLL où les formules négatives sont interprétés par des espaces Fréchet Nucléaires. Nous montrons que enfin la résolution des équations aux dérivées partielles linéaires à coefficients constants obéit à une syntaxe qui généralise celle de DiLL, que nous détaillonsAround the curry-coward correspondence, proof-theory has grown along two distinct fields : the theory of programming languages, for which formulas acts as data types, and the semantic study of proofs. The latter consists in giving mathematical models of proofs and programs. In particular, denotational semantics distinguishes data types which serves as input or output of programs, and allows in return for a finer understanding of proofs and programs. Linear Logic (LL) gives a logical interpretation of the basic notions from/of linear algebra, while Differential Linear Logic allows for a logical understanding of differentiation. This manuscript strengthens the link between proof-theory and functional analysis, and highlights the role of linear involutive negation in DiLL. The first part of this thesis consists in a quick overview of prerequisites on the notions of linearity, polarisation and differentiation in proof-theory, and gives the necessary background in the theory of locally convex topological vector spaces. The second part uses two classic topologies on the dual of a topological vector space and gives two models of DiLL: the weak topology allows only for a discrete interpretation of proofs through formal power series, while the Mackey topology on the dual allows for a smooth and polarised model of DiLL. Finally, the third part interprets proofs of DiLL by distributions. We detail a polarized model of DiLL in which negatives are Fréchet Nuclear spaces, and proofs are distributions with compact support. We also show that solving linear partial differential equations with constant coefficients can be typed by a syntax similar to the one of DiLL, which we detail
20
Warren, Jared. "Using Haskell to Implement Syntactic Control of Interference." Thesis, Kingston, Ont. : [s.n.], 2008. http://hdl.handle.net/1974/1237.
Full text
21
Castellan, Simon. "Structures concurrentes en sémantique des jeux." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSEN034/document.
Full textAbstract:
La sémantique des jeux permet l'étude et la modélisation abstraite des langages de programmation d'un point de vue mathématique, en gardant assez d'informations concrètes sur la structure des programmes, mais en laissant de côté les détails superflus. Durant mon doctorat, j'ai travaillé sur l'association de la sémantique des jeux avec les structures d'événements pour proposer des modèles dénotationnels vraiment concurrents de langages concurrents d'ordresupérieur. Dans un premier temps, je construis un modèle réalisant cette association, qui retient suffisamment d'informations sur le comportement des programmes pour interpréter adéquatement une grande variété de langages concurrents et non déterministes pour des notions fines de convergences. La construction de ce modèle se base surl'introduction de symétrie afin d'établir que le modèle forme une catégorie cartésienne fermée. Dans un second temps, je propose une généralisation dans ce cadre des notions d'innocence et de bon parenthésage, essentielles en sémantiquedes jeux pour comprendre les effets calculatoires, et résolvant ainsi des problèmes ouverts de la sémantique des jeux concernant l'innocence concurrente et non-déterministe. Dans un dernier temps je propose une interprétation dans ce modèle, de langages concurrents avec mémoire faible, un des premiers travaux de sémantique dénotationnelle pour ce type de langages. Bien que théoriques, ces modèles sont compositionnels et basés sur des ordres partiels, et donc pourraient permettre de faire passer la vérification de programmes concurrents à l'échelle (une problématique importante du domaine)Game semantics is an effective tool to study and model abstractly programming languages from a mathematical point of view, by keeping enough concrete information on the structure of programs but yet leaving aside superfluous details. During my PhD thesis, I worked on merging game semantics with event structures to propose truly concurrent denotational models of higher-order concurrent languages. In the first part, I build a model based on this merge, retaining enough information about the behaviour of programs to interpret adequately a large variety of concurrent programming languages for various notions of convergence. The construction of this model is based on the introduction of symmetry to prove that the model is indeed in a cartesian-closed category. In the second part, I propose a generalization, in this setting, of innocence and well-bracketing, key notions in game semantics to understand the computational effects, and thusly closing openproblems of game semantics about concurrent and nondeterministic innocence.In the last part, I propose an interpretation in this model of concurrent languages with weak shared memory, one of the first works of denotational semantics for these kinds of languages. Althoughtheoretical, these models are compositional and based on partial orders, and thus could permit scaling verification of concurrent programs (an important problem of the domain)
22
Krishnaswami, Neelakantan R. "Verifying Higher-Order Imperative Programs with Higher-Order Separation Logic." Research Showcase @ CMU, 2012. http://repository.cmu.edu/dissertations/164.
Full textAbstract:
In this thesis I show is that it is possible to give modular correctness proofs of interesting higher-order imperative programs using higher-order separation logic.
To do this, I develop a model higher-order imperative programming language, and develop a program logic for it. I demonstrate the power of my program logic by verifying a series of examples. This includes both realistic patterns of higher-order imperative programming such as the subject-observer pattern, as well as examples demonstrating the use of higher-order logic to reason modularly about highly aliased data structures such as the union-find disjoint set algorithm.
23
Gaboardi, Marco. "Linéarité : un outil analytique pour l'étude de la complexité et de la sémantique des langages de programmation." Thesis, Vandoeuvre-les-Nancy, INPL, 2007. http://www.theses.fr/2007INPL099N/document.
Full textAbstract:
Dans la première partie, on propose un système de type pour le lambda-calcul, dans le style du calcul des séquents, nomme « Soft Type Assignment » (STA) qui est inspiré par la logique linéaire « soft ». STA a la propriété de réduction du sujet et est correct et complète pour les calculs en temps polynomial. Par la suite on propose un déduction naturelle, STA_N. Ce système est simple mais il a le désavantage que les variables dans le sujet peuvent être explicitement renommées. Pour résoudre ce problème, on propose le système STA_M, où les contextes sont des multi-ensembles, donc les règles pour renommer les variables peuvent être interdit. L’inférence de type pour STA_M ne semble pas décidable. On propose un algorithme qui pour chaque lambda-terme rend l’ensemble de contraintes que doivent être satisfait pour que le terme soit type. Pi est correct et complet. Ensuite on étend le lambda-calcul par des constantes booléennes et on propose le système STA_B. La particularité de STA_B est que la règle du conditionnel utilise les contextes de façon additive. Chaque programme de STA_B peut être exécuté, par une machine abstraite, en espace polynomial. De plus le système est aussi complet pour PSPACE. Dans la deuxième partie, on propose une restriction de PCF, nommée SlPCF. Ce langage est équipé avec une sémantique opérationnelle qui mélange l’appelle par nom et l’appelle par valeur et peut être interprèté en mode standard dans les espaces cohérents linéaires. SlPCF est complet pour les fonctions récursives, mais il n’est pas complet et donc il n’est pas fully abstract pour les espaces cohérents linéairesIn the first part, we propose, inspired by Soft Linear Logic, a type assignment system for lambda-calculus in sequent calculus style, named Soft Type Assignment (STA). STA enjoys the subject reduction property. and is correct and complete for polynomial time computations. Then, we propose a natural deduction named STA_N. While simple, STA_N has the disadvantage of allowing the explicit renaming of variables in the subject. To overcome to this problem, we propose another natural deduction system, named STA_M, where contexts are multisets, hence rules renaming variables can be avoided. The type inference for STA_M seems in general undecidable. We propose an algorithm Pi returning, for every lambda-term, a set of constraints that need to be satisfied in order to type the term. Pi is correct and complete. We extend the lambda-calculus by basic boolean constants and we propose the system STA_B. The peculiarity of STA_B is that the conditional rule treats the contexts in an additive way. Every STA_B program can be executed, through an abstract machine, in polynomial space. Moreover, STA_B is also complete for PSPACE. In the second part we propose a restriction of PCF, named SlPCF. The language is naturally equipped with an operational semantics mixing call-by-name and call-by-value parameter passing and it can be interpreted in linear coherence space in a standard way. SlPCF is recursive complete, but it is not complete, and thus not fully abstract, with respect to linear coherence spaces
24
Diar, Fares Sonja. "All is well : An analysis of positivity through adjectives in two contemporary New Age self-help books." Thesis, Mälardalens högskola, Akademin för utbildning, kultur och kommunikation, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-40144.
Full textAbstract:
Self-help counselling is an important industry that not only influences its immediate users’ behavior but also society and social behaviors more generally. Since New Ageis a main branch of self-help, and since positivity is a dominant concept in (New Age) self-help discourse, it is worth analyzing how positivity might be achieved in terms of language use. The present study investigates whether the adjectives in a couple of New Age publications contribute to communicating positivity and, if yes, how. What adjectives are used and how can they be categorized in terms of positive, negative, neutral or undetermined connotations as well as semantic prosody? The findings support the hypothesis that the use of “positive adjectives” (Rozin, Berman & Royzman, 2010, p. 536) is what helps to make New Age self-help books convey a positive spirit.
25
Anglade, Sophie. "Semantique denotationnelle de s3l un langage de flux, d'ensembles et de suites et son implantation en caml." Orléans, 1988. http://www.theses.fr/1988ORLE2041.
Full textAbstract:
L'originalite du langage presente est due a une nouvelle notion intermediaire: le flux (ou n-uplet d'elements) qui rend compte de la notion de "pluriel" par opposition a l'ensemble ou les objets sont "enserres" dans une structure fixe. Une definition formelle du langage a ete ecrite a l'aide de l'approche semantique denotationnelle. Enfin, a partir des equations semantiques obtenues une implantation a ete effectuee avec le langage ml disponible dans le systeme caml
26
Royer, Véronique. "Compilation dirigee par la semantique : une methode constructive." Toulouse 3, 1986. http://www.theses.fr/1986TOU30170.
Full textAbstract:
Dans le cadre de la generation de compilateurs dirigee par la semantique, se pose le probleme de transformer une semantique source d'un langage de programmation en une semantique objet equivalente, plus proche d'une implementation. La plupart des travaux dans ce domaine resolvent ce probleme de facon non constructive: une semantique objet est d'abord exhibee, ensuite prouvee correcte vis-a-vis de la semantique source. Le but de cette these est de montrer qu'on peut deriver une semantique objet a partir d'une semantique source d'un langage, de maniere constructive, tout en preservant certains criteres de correction fixes au depart
27
Geoffroy, Guillaume. "Réalisabilité classique : nouveaux outils et applications." Thesis, Aix-Marseille, 2019. http://www.theses.fr/2019AIXM0099/document.
Full textAbstract:
La réalisabilité classique de Jean-Louis Krivine associe à chaque modèle de calcul et chaque modèle de la théorie des ensembles un nouveau modèle de la théorie des ensembles, appelé modèle de réalisabilité, d'une façon similaire au forcing. Chaque modèle de réalisabilité est muni d’une algèbre de Boole caractéristique $\gimel 2$ (gimel 2), dont la structure donne des informations sur les propriétés du modèle de réalisabilité. En particulier, les modèles de forcing correspondent au cas où $\gimel 2$ est l'algèbre de Boole à deux éléments.Ce travail présente de nouveaux outils pour manipuler les modèles de réalisabilité et donne de nouveaux résultats obtenus en les exploitant. L'un d'entre eux est qu'au premier ordre, la théorie des algèbres de Boole à au moins deux éléments est complète pour $\gimel 2$, au sens où $\gimel 2$ eut être rendue élémentairement équivalente à n'importe quelle algèbre de Boole. Deux autres résultats montrent que $\gimel 2$ peut être utilisée pour étudier les modèles dénotationnels de langage de programmation (chacun part d'un modèle dénotationnel et classifie ses degrés de parallélisme à l'aide de $\gimel 2$). Un autre résultat montre que la technique de Jean-Louis Krivine pour réaliser l'axiome des choix dépendants à partir de l'instruction quote peut se généraliser à des formes plus fortes de choix. Enfin, un dernier résultat, obtenu en collaboration avec Laura Fontanella, accompagne le précédent en adaptant la condition d'antichaîne dénombrable du forcing au cadre de la réalisabilité, ce qui semble semble ouvrir une piste prometteuse pour réaliser l'axiome du choixJean-Louis Krivine's classical realizability defines, from any given model of computation and any given model of set theory, a new model of set theory called the realizability model, in a similar way to forcing. Each realizability model is equipped with a characteristic Boolean algebra $\gimel 2$ (gimel 2), whose structure encodes important information about the properties of the realizability model. For instance, forcing models are precisely the realizability models in which $\gimel 2$ is the Boolean algebra with to elements.This document defines new tools for studying realizability models and exploits them to derive new results. One such result is that, as far as first-order logic is concerned, the theory of Boolean algebras with at least two elements is complete for $\gimel 2$, meaning that for each Boolean algebra B (with at least two elements), there exists a realizability model in which $\gimel 2$ is elementarily equivalent to B. Next, two results show that $\gimel 2$ can be used as a tool to study denotational models of programming languages (each one of them takes a particular denotational model and classifies its degrees of parallelism using $\gimel 2$). Moving to set theory, another results generalizes Jean-Louis Krivine's technique of realizing the axiom of dependant choices using the instruction quote to higher forms of choice. Finally, a last result, which is joint work with Laura Fontanella, complements the previous one by adapting the countable antichain condition from forcing to classical realizability, which seems to open a new, promising approach to the problem of realizing the full axiom of choice
28
De, Visme Marc. "Sémantique des Jeux Quantique." Thesis, Lyon, 2020. http://www.theses.fr/2020LYSEN056.
Full textAbstract:
Cette thèse porte sur la sémantique des langages de programmation quantiques, et en particulier sur celle du lambda-calcul quantique, un langage paradigmatique dû à Selinger et Valiron qui marrie flot de contrôle classique riche (fonctions d’ordre supérieur, récursion, etc) avec des données quantiques (création de qubits, mesure, application d’opérateurs unitaires). Pour donner un modèle du lambda-calcul quantique, il convient de trouver une alliance harmonieuse entre les modèles traditionnels de sémantique dénotationnelle (qui donnent du sens aux programmes en les interprétant dans des univers mathématiques adéquats) et les mathématiques du quantique (espaces de Hilbert, matrices de densité, etc). Cette thèse comporte trois contributions principales : Premièrement, nous étendons la sémantique des jeux, une approche dynamique à la sémantique dénotationnelle, au cas quantique. Nous obtenons le premier modèle dénotationnel du lambda-calcul quantique complet qui soit à la fois compositionnel et interactif, c’est à dire qu’il représente la dynamique de l’exécution. Notre modèle est une généralisation naturelle de développements récents pour le cas probabiliste.Deuxièmement, nous relions formellement notre modèle au seul modèle dénotationnel pré-existant du lambda-calcul quantique complet, le modèle relationnel quantique dû à Pagani, Selinger et Valiron. Finalement, nous montrons que notre modèle de jeux est pleinement adéquat, la correspondance idéale entre un langage de programmation et sa sémantique dénotationnelle. Nous en déduisons que le modèle relationnel quantique était lui-aussi pleinement adéquat, un problème que ses auteurs avaient laissé ouvert. Cette thèse se décompose en trois parties. La première partie présente des préliminaires de théorie des catégories, qui permettent de définir un cadre formel englobant à la fois notre modèle de jeux quantique et le modèle relationnel quantique, puis des préliminaires sur les mathématiques du quantique, et enfin des préliminaires sur la programmation quantique et ses modèles. La deuxième partie commence par des préliminaires de sémantique des jeux, et définit notre modèle de jeux quantique dans un cadre simplifié : le lambda-calcul linéaire quantique. Enfin, la troisième partie s'appuie sur la deuxième pour présenter le modèle de jeux quantique complet, prouver que ce modèle est pleinement adéquat, et en déduire que le modèle relationnel quantique est lui aussi pleinement adéquatIn this thesis, we study quantum programming languages, and focus on the quantum lambda-calculus, a paradigmatic language defined by Selinger and Valiron, which mixes a rich classical control flow (higher order functions, etc.) and quantum data (qubit creation, measure, and unitary operations). In this thesis, we search for a denotational semantics of this language, in other words, we extract the meaning and behaviour of programs by interpreting them in an adequately chosen mathematical universe. In order to model the quantum lambda-calculus, one must adapt the traditional denotational models to the mathematics of quantum computation (Hilbert spaces, density matrices, etc.). We have three main contributions:Firstly, we extend game semantics to the quantum case. Game semantics is a dynamic approach to denotational semantics, which focuses on the sequence of interactions between a program and its environment. We obtain the first denotational model of the full quantum lambda-calculus which is both compositional and interactive, meaning that it represents the dynamic of the execution. Our model generalise the recently developed model for the probabilistic case.Secondly, we formally link our model to the only pre-existing denotational model of the full lambda-calculus, the quantum relational model of Pagani, Selinger and Valiron.Lastly, we prove that our game model is fully abstract, the gold standard of denotational semantics, which ensures a total correspondence between the programming language and the model. We deduce that the quantum relational model was also fully abstract, which was an open problem.This thesis is constituted of three parts. The first part details some preliminaries on category theory, used for defining a formal framework including both the quantum game model and the quantum relational model, some preliminaries on the mathematics of quantum computation, and then some preliminaries on quantum programming and its models. The second part starts with some preliminaries on game semantics and defines our quantum game model in the simplified case of the linear quantum lambda-calculus. The third part builds on the second part to define the full quantum game model, prove its full abstraction, and deduce that the quantum relational model is fully abstract too
29
Alcolei, Aurore. "Jeux concurrents enrichis : témoins pour les preuves et les ressources." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSEN054/document.
Full textAbstract:
La sémantique des jeux est une sémantique dénotationnelle centrée sur l’interaction : preuves et programmes y sont représentés par des stratégies modélisant, par le flot d’exécution, leur manière de réagir à leur environnement. Malgré cette présentation intensionnelle, les sémantiques de jeux ne suffisent pas à capturer certaines informations calculatoires annexes au flot d’exécution telles que, par exemple, la production de témoins en logique du premier ordre ou la consommation de ressources dans les langages de programmation. Dans cette thèse nous proposons un enrichissement du modèle des jeux concurrent à base de structures d’événements permettant de garder trace de ces informations.Nous construisons d’abord un modèle de jeux concurrent dans lequel les coups joueurs d’une stratégie sont annotés par les termes d’une théorie (in)équationnelle. Cette théorie est un paramètre de notre modèle et les annotations permettent de refléter de manière compacte des informations d’exécution n’ayant pas d’influence sur le flot d’exécution. Nous montrons que le modèle ainsi construit préserve la structure catégorique compacte fermée du modèle sans annotation.Nous explorons ensuite l’expressivité de notre modèle et présentons deux interprétations nouvelles en sémantique des preuves et des programmes : l’une interprétant les preuves de la logique classique du premier ordre par des stratégies concurrentes avec échange de témoins, donnant une version compositionnelle au théorème de Herbrand ; l’autre permettant de refléter les aspects quantitatifs liés à la consommation de ressources telles que le temps, dans l’exécution de programmes concurrents d’ordre supérieur avec mémoire partagéeThis thesis presents a general framework for enriching causal concurrent games model with annotations. These annotations can be viewed as meta-data on strategies: they are modified throughout interactions but do not affect their general flow of control. These data can be of various nature, in particular our enrichment is parametrised over any multi-sorted equational theory and can also reflect structure upon these data such as a partial order. From a semantics point of view, this construction is motivated by problems from both logic and programming languages: On the logic side, the annotated games model specialised to first-order terms enables us to give a novel interpretation of first-order classical proofs as concurrent strategies carrying first-order witnesses. In particular this answer the question of giving a compositional version to Herbrand’s theorem while avoiding the usual proof sequentialization of other denotational approaches. On the programming language side, annotations on games offer intrinsic quantitative models. We show that those can be used to provide denotational semantics for resource consumption analysis of concurrent higher order programming language with shared memory.These enrichments, strongly connected to the causal structure of concurrent games, give an argument in favor of a causal meaning of computations
30
Plaice, John. "Sémantique et compilation de LUSTRE, un langage déclaratif synchrone." Grenoble INPG, 1988. http://www.theses.fr/1988INPG0032.
Full textAbstract:
Le langage étudie est un langage de programmation des systèmes temps réel fonde sur une interprétation synchrone des réseaux a flux de données. Son compilateur a été conçu entièrement à partir de descriptions formelles de la sémantique du langage. L'originalité principale du compilateur est qu'il tient d'une part aux vérifications statiques de cohérence temporelle et d'autre part à la génération de code séquentiel, par synthèse du contrôle sous forme d'automate fini
31
Seiller, Thomas. "Logique dans le facteur hyperfini : Géométrie de l' interaction et complexité." Thesis, Aix-Marseille, 2012. http://www.theses.fr/2012AIXM4064.
Full textAbstract:
Cette thèse est une étude de la géométrie de l'interaction dans le facteur hyperfini (GdI5), introduite par Jean-Yves Girard, et de ses liens avec les constructions plus anciennes. Nous commençons par montrer comment obtenir des adjonctions purement géométriques comme une identité entre des ensembles de cycles apparaissant entre des graphes. Il est alors possible, en choisissant une fonction qui mesure les cycles, d'obtenir une adjonction numérique. Nous montrons ensuite comment construire, sur la base d'une adjonction numérique, une géométrie de l'interaction pour la logique linéaire multiplicative additive où les preuves sont interprétées par des graphes. Nous expliquons également comment cette construction permet de définir une sémantique dénotationnelle de MALL, et une notion de vérité. Nous étudions finalement une généralisation de ce cadre afin d'interpréter les exponentielles et le second ordre. Les constructions sur les graphes étant paramétrées par une fonction de mesure des cycles, nous entreprenons ensuite l'étude de deux cas particuliers. Le premier s'avère être une version combinatoire de la GdI5, et nous obtenons donc une interprétation géométrique de l'orthogonalité basée sur le déterminant de Fuglede-Kadison. Le second cas particulier est une version combinatoire des constructions plus anciennes de la géométrie de l'interaction, où l'orthogonalité est basée sur la nilpotence. Ceci permet donc de comprendre le lien entre les différentes versions de la géométrie de l'interaction, et d'en déduire que les deux adjonctions — qui semblent à première vue si différentes — sont des conséquences d'une même identité géométriqueThis work is a study of the geometry of interaction in the hyperfinite factor introduced by Jean-Yves Girard, and of its relations with ancient constructions. We start by showing how to obtain purely geometrical adjunctions as an identity between sets of cycles appearing between graphs. It is then possible, by chosing a function that measures those cycles, to obtain a numerical adjunction. We then show how to construct, on the basis of such a numerical adjunction, a geometry of interaction for multiplicative additive linear logic where proofs are interpreted as graphs. We also explain how to define from this construction a denotational semantics for MALL, and a notion of truth. We extend this setting in order to deal with exponential connectives and show a full soundness result for a variant of elementary linear logic (ELL). Since the constructions on graphs we define are parametrized by a function that measures cycles, we then focus our study to two particular cases. The first case turns out to be a combinatorial version of GoI5, and we thus obtain a geometrical caracterisation of its orthogonality which is based on Fuglede-Kadison determinant. The second particular case we study will giveus a refined version of older constructions of geometry of interaction, where orthogonality is based on nilpotency. This allows us to show how these two versions of GoI, which seem quite different, are related and understand that the respective adjunctions are both consequences of a unique geometrical property. In the last part, we study the notion of subjective truth
32
Coupaye, Thierry. "Un modèle d'exécution paramétrique pour systèmes de bases de données actifs." Phd thesis, Université Joseph Fourier (Grenoble), 1996. http://tel.archives-ouvertes.fr/tel-00004983.
Full textAbstract:
Un systeme de bases de données actif est capable d'executer automatiquement des actions predefinies en reponse a des evenements specifiques lorsque certaines conditions sont satisfaites. Les regles actives, de la forme evenement-Condition-Action, sont au coeur de cette approche. Dans cette these, nous nous interessons aux modeles d'execution des systemes actifs. Le modele d'execution d'un systeme actif decrit quand et comment (ordonnancement, synchronisation) sont executées, au cours d'une application, les regles declenchées lors de l'execution d'une transaction. Nous proposons tout d'abord une taxonomie et une representation graphique des modeles d'execution des systemes actifs. Nous exposons ensuite un modele d'execution parametrique nomme Flare (Flexible active rule execution). Une caracteristique essentielle de ce modele est de considerer des modules de regles - chaque module etant destine a une utilisation particuliere des regles. On peut specifier, d'une part, le comportement de chaque regle d'un module, et d'autre part, la strategie d'execution de chaque module. Il suffit, pour cela, de choisir une valeur pour chacun des parametres proposes parmi un ensemble de valeurs predefinies. Nous donnons egalement une semantique denotationnelle (ou fonctionnelle) du modele. Nous montrons que ce formalisme fournit une specification implantable que nous utilisons dans le cadre de l'experimentation que nous menons autours de NAOS - un mecanisme de regles actives pour le SGBD a objets O2 - afin de remplacer son moteur d'execution par Flare.
33
Ringmar, Ingrid Maria. "Entre vocablos y volcanes : Dificultades terminológicas y formas de dirigirse al lector en un texto especializado para turistas." Thesis, Linnéuniversitetet, Institutionen för språk (SPR), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-46203.
Full textAbstract:
This has paper has two main purposes: to analyze the translation of specialized terminology and ways of addressing the reader in a specialized tourist text in Spanish and its Swedish target text. The terminological difficulties on volcanism in the translation concerns the fact that the semantic field on this topic is diversified in the Canary Islands, contrary to the semantic field on volcanoes in Swedish. The theoretical background in this paper gives keys to describing the meaning of words in terms of connotation and denotation and describes how to use semantic components to solve the difficulties of terminology. The theory applied to the difficulties concerning ways of addressing the reader in the source text, explains the relation between the sender and the reader in terms of distance and closenes. The paper shows that the source text is inconsistent in this matter. To solve this task the translator has adopted a homogeneous way of addressing the reader, to achieve a target text loyal to the Swedish speaking reader and to consistency. The translation of tourist texts has been thought of as being an easy task, not demanding too much of its translators. This paper aims at showing that this is not the case.
34
Fan, Yang, Hidehiko Masuhara, Tomoyuki Aotani, Flemming Nielson, and Hanne Riis Nielson. "AspectKE*: Security aspects with program analysis for distributed systems." Universität Potsdam, 2010. http://opus.kobv.de/ubp/volltexte/2010/4136/.
Full textAbstract:
Enforcing security policies to distributed systems is difficult, in particular, when a system contains untrusted components. We designed AspectKE*, a distributed AOP language based on a tuple space, to tackle this issue. In AspectKE*, aspects can enforce access control policies that depend on future behavior of running processes. One of the key language features is the predicates and functions that extract results of static program analysis, which are useful for defining security aspects that have to know about future behavior of a program. AspectKE* also provides a novel variable binding mechanism for pointcuts, so that pointcuts can uniformly specify join points based on both static and dynamic information about the program. Our implementation strategy performs fundamental static analysis at load-time, so as to retain runtime overheads minimal. We implemented a compiler for AspectKE*, and demonstrate usefulness of AspectKE* through a security aspect for a distributed chat system.
35
Favre, Jean-Marie. "Une approche pour la maintenance et la ré-ingénierie globale des logiciels." Phd thesis, Université Joseph Fourier (Grenoble), 1995. http://tel.archives-ouvertes.fr/tel-00724676.
Full textAbstract:
Alors que l'informatique est résolument tournée vers l'avenir, cette thèse se concentre sur le passé ; non pas par nostalgie mais plutôt parce que le futur des logiciels âgés est une question d'actualité. Plus particulièrement trois thèmes sont abordés : la maintenance, la ré-ingénierie et la programmation globale. L'objectif de cette étude est d'explorer l'intersection entre la ré-ingénierie et la programmation globale, domaine que nous avons baptisé ré-ingénierie globale. L'idée principale est de réutiliser des concepts et des techniques de programmation détaillée. En fait nous proposons de définir la programmation globale en distinguant 4 aspects du logiciel : l'architecture, la manufacture, la variation et l'évolution. Un modèle abstrait basé sur des concepts ensemblistes est proposé pour modéliser les différentes entités de programmation globale. La technologie relative à ce domaine est ensuite décrite en considérant aussi bien l'état de l'art que l'état de la pratique. La différence entre ces deux aspects souligne l'intérêt de la ré-ingénierie globale. A titre d'illustration, nous étudions le cas des préprocesseurs en tant qu'outils de programmation globale. Ces outils de bas niveau provenant des années 70 sont traditionnellement utilisés pour décrire des familles de programmes. Pour faciliter la compréhension de tels artefacts nous proposons d'utiliser des techniques comme l'évaluation partielle, l'analyse inter-procédurale de flot de données ou encore le découpage. Ces techniques, définies de manière rigoureuse, s'appuient sur la sémantique dénotationnelle du préprocesseur utilisé. Un prototype montrant leur utilité a été réalisé. Il prouve qu'une approche basée sur des fondements théoriques issus de la programmation détaillée est applicable pour résoudre des problèmes pratiques de programmation globale.
36
Sánchez, Álvarez Daniel. "Elementos de Semántica Denotacional de Lenguajes de Programación con Datos Borrosos." Doctoral thesis, Universidad de Murcia, 1999. http://hdl.handle.net/10803/10932.
Full textAbstract:
A fin de diseñar e implementar lenguajes de programación que tengan en cuenta el paradigma borroso modificaremos el lambda cálculo clásico, adjuntando a cada término un grado, y redefiniendo la beta-reducción, obteniendo que para que el nuevo cálculo verifique la propiedad de Church-Rosser la transmisión de los grados debe hacerse por medio de una función que sea una t-norma o s-conorma. Utilizando esta nueva herramienta diseñamos un lenguaje no determinista que satisface los requerimientos de la programación con datos borrosos.With the aim of designing and implementing programming languages that take into account the fuzzy paradigm we will modify the classical lambda calculus by adding a degree to each term and by redefining the b-reduction. Thus, for the new calculus to verify the Church-Rosser property, the degree computed with can be made through a function that is a t-norm or an s-conorm. With this new tool we design a nondeterminist language that satisfies fuzzy dataprogramming requirements, and an example of its behaviour is shown.
37
Sun, Juemin. "On the algebraic denotational specifications of programming language semantics." 1988. http://hdl.handle.net/2097/22461.
Full text
38
"Efficient verification of VLSI circuits based on syntax and denotational semantics." Research Laboratory of Electronics, Massachusetts Institute of Technology, 1989. http://hdl.handle.net/1721.1/4206.
Full textAbstract:
Filip Van Aelten.Also issued as: Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1988.
Includes bibliographical references (p. 139-141).
Support provided by Analog Devices.
39
"The functional logic programming language, PowerFuL: An analysis and a denotational semantics for efficient, logical implementation." Tulane University, 1996.
Find full textAbstract:
The PowerFuL programming language combines the expressive power of functional and logic programming languages, via the prescriptive use of denotational semantics. PowerFuL's implementation is based upon execution of it's denotational definition but also incorporates 'optimizations,' which are informal notations that represent and manipulate logical variables in a way similar to SLD-resolution We formalize PowerFuL's operational semantics by considering the terms that are produced within the interpreter to be a language, which we call Opts, and providing a denotational semantics for it. The semantics we provide maps Opts into PowerFuL's semantic algebra, so we may consider both PowerFuL code and terms used by PowerFuL's interpreter to represent expressions over the same algebra, denoting elements of the same domain This formalization of the operational semantics (as embodied by the interpreter) gives us a formal understanding of PowerFuL's interpretation and provides a logical characterization of PowerFuL's logical capability. We also provide PowerFuL with an analog to logic programming's computed answer substitution We show that PowerFuL's operational behavior is similar to that of constraint logic programming languages by giving a purely operational characterization of constraint logic programming and comparing it to PowerFuL's operational model. This suggests that PowerFuL can be extended to handle new domains in the same way logic programming languages are extended to form constraint logic programming languages This work is an example of 'reasoning about programs' and programming languages, an avowed goal of a great deal of work, but rarely performed. Our success in analyzing PowerFuL can be attributed to PowerFuL's elegant denotational semantics and wise design considerations. We discuss which aspects of PowerFuL's design were useful to us in formally reasoning about PowerFuL, and argue that this helps determine which design considerations are practical in generalacase@tulane.edu
40
Freire, Elisabete Raposo. "Contributos para o estudo da semântica de linguagens com concorrência e mobilidade." Doctoral thesis, 2004. http://hdl.handle.net/10400.3/119.
Full textAbstract:
Tese de Doutoramento em Informática, especialidade de Teoria da Computação.Neste trabalho mostra-se como abordagens matematicamente mais simples que as tradicionais podem ser usadas na definição da semântica de linguagens com concorrência e também de linguagens com mobilidade. Completam-se também alguns aspectos da semântica da mobilidade para os quais as propostas actualmente existentes apresentam limitações. Faz-se a exploração de dois tipos de técnicas para definir as semânticas operacionais e denotacionais de linguagens com concorrência e mobilidade. Por um lado usam-se os conjuntos com famílias de equivalência, um conceito mais simples e manejável, que parece substituir com vantagens ao nível da simplicidade os espaços métricos, usados nas abordagens tradicionais. Por outro lado, completa-se o trabalho com uma abordagem mais recente, baseada na utilização de coálgebras para definir sistemas e tirando partido das facilidades proporcionadas pelos conjuntos nominais na manipulação de nomes. A avaliação destas técnicas é feita sobre uma linguagem com sincronização restrita (Lsyn) e sobre uma linguagem com mobilidade (cálculo-π).
Fundação para a Ciência e a Tecnologia (FCT).
41
Gadea, Alejandro Emilio. "Biortogonalidad para corrección de compiladores y adecuación computacional." Doctoral thesis, 2019. http://hdl.handle.net/11086/14324.
Full textAbstract:
Tesis (Doctor en Ciencias de la Computación)--Universidad Nacional de Córdoba, Facultad de Matemática, Astronomía, Física y Computación, 2019.En esta tesis hemos estudiado en profundidad los métodos de biortogonalidad y step-indexing para probar tanto adecuación computacional como corrección de compiladores. Un primer aporte es la prueba de corrección de una semántica denotacional con respecto a una operacional para un lenguaje funcional lazy definido por John Launchbury corriegiendo ciertos ciertas irregularidades en algunas definiciones. Otra contribución es la prueba de adecuación computacional de una semántica operacional con respecto a una denotacional para un lenguaje funcional call-by-value con subtipado. Para este mismo lenguaje probamos la coincidencia entre una semántica denotacional extrínseca y una intrínseca, obteniendo como corolario la coherencia de la semántica intrínseca. Este aporte incluye la mecanización completa en Coq de todos los resultados; siendo, tanto como sabemos, la primera mecanización del teorema de bracketing propuesto por John Reynolds. Finalmente damos una prueba de corrección de un compilador para un lenguaje lazy con recursión generando código para una máquina abstracta, este aporte extiende significativamente un trabajo previo desarrollado por Leonardo Rodríguez. Incluimos también la mecanización completa en Coq.
In this work we studied the techniques of biorthogonality and step-indexing for proving computational adequacy and compiler correctness. The first contribution is the proof of correction of a denotational semantics with respect to a operational semantics for a lazy language originally defined by John Launchbury fixing some definition irregularities. Another contribution is the proof of computational adequacy of the operational semantics with respect to a denotational semantics for a call-by-value functional language with subtyping. Also for this same language we prove the coincidence between an extrinsic and intrinsic denotational semantics. This contribution includes the complete mechanization in Coq of all the results; being, as far as we know, the first mechanization of Reynolds’ bracketing theorem. Finally we give a proof of the correction of a compiler for an abstract machine, this contribution significantly extends previous work developed by Leonardo Rodríguez. We also include the complete mechanization in Coq.
Gadea, Alejandro Emilio. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía, Física y Computación; Argentina.
42
Little, Richard. "Intensional Context-Free Grammar." Thesis, 2013. http://hdl.handle.net/1828/5120.
Full textAbstract:
The purpose of this dissertation is to develop a new generative grammar, based on the principles of intensional logic. More specifically, the goal is to create a psychologically real grammar model for use in natural language processing. The new grammar consists of a set of context-free rewrite rules tagged with intensional versions.
Most generative grammars, such as transformational grammar, lexical functional-grammar and head-driven phrase structure grammar, extend traditional context-free grammars with a mechanism for dealing with contextual information, such as subcategorization of words and agreement between different phrasal elements. In these grammars there is not enough separation between the utterances of a language and the context in which they are uttered. Their models of language seem to assume that context is in some way encapsulated in the words of the language instead of the other way around.
In intensional logic, the truth of a statement is considered in the context in which it is uttered, unlike traditional predicate logic in which truth is assigned in a vacuum, regardless of when or where it may have been stated. To date, the application of the principles of intensionality to natural languages has been confined to semantic theory. We remedy this by applying the ideas of intensional logic to syntactic context, resulting in intensional context-free grammar.
Our grammar takes full advantage of the simplicity and elegance of context-free grammars while accounting for information that is beyond the sentence itself, in a realistic way. Sentence derivation is entirely encapsulated in the context of its utterance. In fact, for any particular context, the entire language of the grammar is encapsulated in that context. This is evidenced by our proof that the language of an intensional grammar is a set of context-free languages, indexed by context.
To further support our claims we design and implement a small fragment of English using the grammar. The English grammar is capable of generating both passive and active sentences that include a subject, verb and up to two optional objects. Furthermore, we have implemented a partial French to English translation system that uses a single language dimension to initiate a translation. This allows us to include multiple languages in one grammar, unlike other systems which must separate the grammars of each language. This result has led this author to believe that we have created a grammar that is a viable candidate for a true Universal Grammar, far exceeding our initial goals.Graduate
0984
0800
0290
rlittle@uvic.ca
43
Diemert, Simon. "A mathematical basis for medication prescriptions and adherence." Thesis, 2017. https://dspace.library.uvic.ca//handle/1828/8458.
Full textAbstract:
Medication prescriptions constitute an important type of clinical intervention. Medication adherence is the degree to which a patient consumes their medication as agreed upon with a prescriber. Despite many years of research, medication non-adherence continues to be a problem of note, partially due to its multi-faceted in nature. Numerous interventions have attempted to improve adherence but none have emerged as definitive. A significant sub-problem is the lack of consensus regarding definitions and measurement of adherence. Several recent reviews indicate that discrepancies in definitions, measurement techniques, and study methodologies make it impossible to draw strong conclusions via meta-analyses of the literature.
Technological interventions aimed at improving adherence have been the subject of ongoing research. Due to the increasing prevalence of the Internet of Things, technology can be used to provide a continuous stream of data regarding a patient's behaviour. To date, several researchers have proposed interventions that leverage data from the Internet of Things, however none have established an acceptable means of analyzing and acting upon this wealth of data.
This thesis introduces a computational definition for adherence that can be used to support continued development of technological adherence interventions. A central part of the proposed definition is a formal language for specifying prescriptions that uses fuzzy set theory to accommodate imprecise concepts commonly found in natural language medication prescriptions. A prescription specified in this language can be transformed into an evaluation function which can be used to score the adherence of a given medication taking behaviour. Additionally, the evaluator function is applied to the problem of scheduling medication administrations. A compiler for the proposed language was implemented and had its breadth of expression and clinical accuracy evaluated. The results indicate that the proposed computational definition of adherence is acceptable as a proof of concept and merits further works.Graduate
44
Rodríguez, Leonardo Matías. "Generación de código intermedio usando semántica funtorial." Bachelor's thesis, 2010. http://hdl.handle.net/11086/41.
Full textAbstract:
Tesis (Lic. en Ciencias de la Computación)--Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física, 2010.Este trabajo consiste en la implementación de un front-end para un lenguaje de programación Algol-like. El front-end es la primera etapa del proceso de compilación; cuyo objetivo es generar código en un lenguaje intermedio a partir del programa fuente.La generación de código intermedio se realiza a partir de la semántica denotacional del lenguaje, es decir, se elige un modelo que permite pensar las ecuaciones semánticas como traducciones al lenguaje intermedio. El modelo semántico que se elige es una categoría funtorial que permite explicitar en las ecuaciones algunas propiedades deseadas del lenguaje. La implementación se realiza en Agda, un lenguaje funcional con tipos dependientes.
45
Masia, Hlupheka Enock. "Nxopaxopo wa dinothexini na khonothexini eka Xitsonga." Diss., 2012. http://hdl.handle.net/11602/1042.
Full text