The Experts below are selected from a list of 11715 Experts worldwide ranked by ideXlab platform
Krzysztof R Apt - One of the best experts on this subject based on the ideXlab platform.
-
a Denotational Semantics for first order logic
Lecture Notes in Computer Science, 2000Co-Authors: Krzysztof R AptAbstract:In Apt and Bezem [AB99] we provided a computational interpretation of first-order formulas over arbitrary interpretations. Here we complement this work by introducing a Denotational Semantics for first-order logic. Additionally, by allowing an assignment of a nonground term to a variable we introduce in this framework logical variables. The Semantics combines a number of well-known ideas from the areas of Semantics of imperative programming languages and logic programming. In the resulting computational view conjunction corresponds to sequential composition, disjunction to "don't know" nondeterminism, existential quantification to declaration of a local variable, and negation to the "negation as finite failure" rule. The soundness result shows correctness of the Semantics with respect to the notion of truth. The proof resembles in some aspects the proof of the soundness of the SLDNF-resolution.
-
a Denotational Semantics for first order logic
arXiv: Programming Languages, 2000Co-Authors: Krzysztof R AptAbstract:In Apt and Bezem [AB99] (see cs.LO/9811017) we provided a computational interpretation of first-order formulas over arbitrary interpretations. Here we complement this work by introducing a Denotational Semantics for first-order logic. Additionally, by allowing an assignment of a non-ground term to a variable we introduce in this framework logical variables. The Semantics combines a number of well-known ideas from the areas of Semantics of imperative programming languages and logic programming. In the resulting computational view conjunction corresponds to sequential composition, disjunction to ``don't know'' nondeterminism, existential quantification to declaration of a local variable, and negation to the ``negation as finite failure'' rule. The soundness result shows correctness of the Semantics with respect to the notion of truth. The proof resembles in some aspects the proof of the soundness of the SLDNF-resolution.
Rasmus Ejlers Mogelberg - One of the best experts on this subject based on the ideXlab platform.
-
Denotational Semantics for guarded dependent type theory
Mathematical Structures in Computer Science, 2020Co-Authors: Ales Bizjak, Rasmus Ejlers MogelbergAbstract:We present a new model of guarded dependent type theory (GDTT), a type theory with guarded recursion and multiple clocks in which one can program with and reason about coinductive types. Productivity of recursively defined coinductive programs and proofs is encoded in types using guarded recursion and can therefore be checked modularly, unlike the syntactic checks implemented in modern proof assistants. The model is based on a category of covariant presheaves over a category of time objects, and quantification over clocks is modelled using a presheaf of clocks. To model the clock irrelevance axiom, crucial for programming with coinductive types, types must be interpreted as presheaves internally right orthogonal to the object of clocks. In the case of dependent types, this translates to a lifting condition similar to the one found in homotopy theoretic models of type theory, but here with an additional requirement of uniqueness of lifts. Since the universes defined by the standard Hofmann–Streicher construction in this model do not satisfy this property, the universes in GDTT must be indexed by contexts of clock variables. We show how to model these universes in such a way that inclusions of clock contexts give rise to inclusions of universes commuting with type operations on the nose.
-
ticking clocks as dependent right adjoints Denotational Semantics for clocked type theory
Logical Methods in Computer Science, 2020Co-Authors: Bassel Mannaa, Rasmus Ejlers Mogelberg, Niccolo VeltriAbstract:Clocked Type Theory (CloTT) is a type theory for guarded recursion useful for programming with coinductive types, allowing productivity to be encoded in types, and for reasoning about advanced programming language features using an abstract form of step-indexing. CloTT has previously been shown to enjoy a number of syntactic properties including strong normalisation, canonicity and decidability of the equational theory. In this paper we present a Denotational Semantics for CloTT useful, e.g., for studying future extensions of CloTT with constructions such as path types. The main challenge for constructing this model is to model the notion of ticks on a clock used in CloTT for coinductive reasoning about coinductive types. We build on a category previously used to model guarded recursion with multiple clocks. In this category there is an object of clocks but no object of ticks, and so tick-assumptions in a context can not be modelled using standard tools. Instead we model ticks using dependent right adjoint functors, a generalisation of the category theoretic notion of adjunction to the setting of categories with families. Dependent right adjoints are known to model Fitch-style modal types, but in the case of CloTT, the modal operators constitute a family indexed internally in the type theory by clocks. We model this family using a dependent right adjoint on the slice category over the object of clocks. Finally we show how to model the tick constant of CloTT using a semantic substitution. This work improves on a previous model by the first two named authors which not only had a flaw but was also considerably more complicated.
-
Denotational Semantics of recursive types in synthetic guarded domain theory
Mathematical Structures in Computer Science, 2019Co-Authors: Rasmus Ejlers Mogelberg, Marco PaviottiAbstract:Just like any other branch of mathematics, Denotational Semantics of programming languages should be formalised in type theory, but adapting traditional domain theoretic Semantics, as originally formulated in classical set theory to type theory has proven challenging. This paper is part of a project on formulating Denotational Semantics in type theories with guarded recursion. This should have the benefit of not only giving simpler Semantics and proofs of properties such as adequacy, but also hopefully in the future to scale to languages with advanced features, such as general references, outside the reach of traditional domain theoretic techniques.Working in Guarded Dependent Type Theory (GDTT), we develop Denotational Semantics for Fixed Point Calculus (FPC), the simply typed lambda calculus extended with recursive types, modelling the recursive types of FPC using the guarded recursive types of GDTT. We prove soundness and computational adequacy of the model in GDTT using a logical relation between syntax and Semantics constructed also using guarded recursive types. The Denotational Semantics is intensional in the sense that it counts the number of unfold-fold reductions needed to compute the value of a term, but we construct a relation relating the denotations of extensionally equal terms, i.e., pairs of terms that compute the same value in a different number of steps. Finally, we show how the Denotational Semantics of terms can be executed inside type theory and prove that executing the denotation of a boolean term computes the same value as the operational Semantics of FPC.
-
Denotational Semantics of recursive types in synthetic guarded domain theory
arXiv: Logic in Computer Science, 2018Co-Authors: Rasmus Ejlers Mogelberg, Marco PaviottiAbstract:Just like any other branch of mathematics, Denotational Semantics of programming languages should be formalised in type theory, but adapting traditional domain theoretic Semantics, as originally formulated in classical set theory to type theory has proven challenging. This paper is part of a project on formulating Denotational Semantics in type theories with guarded recursion. This should have the benefit of not only giving simpler Semantics and proofs of properties such as adequacy, but also hopefully in the future to scale to languages with advanced features, such as general references, outside the reach of traditional domain theoretic techniques. Working in Guarded Dependent Type Theory (GDTT), we develop Denotational Semantics for FPC, the simply typed lambda calculus extended with recursive types, modelling the recursive types of FPC using the guarded recursive types of GDTT. We prove soundness and computational adequacy of the model in GDTT using a logical relation between syntax and Semantics constructed also using guarded recursive types. The Denotational Semantics is intensional in the sense that it counts the number of unfold-fold reductions needed to compute the value of a term, but we construct a relation relating the denotations of extensionally equal terms, i.e., pairs of terms that compute the same value in a different number of steps. Finally we show how the Denotational Semantics of terms can be executed inside type theory and prove that executing the denotation of a boolean term computes the same value as the operational Semantics of FPC.
-
Denotational Semantics for guarded dependent type theory
arXiv: Logic in Computer Science, 2018Co-Authors: Ales Bizjak, Rasmus Ejlers MogelbergAbstract:We present a new model of Guarded Dependent Type Theory (GDTT), a type theory with guarded recursion and multiple clocks in which one can program with, and reason about coinductive types. Productivity of recursively defined coinductive programs and proofs is encoded in types using guarded recursion, and can therefore be checked modularly, unlike the syntactic checks implemented in modern proof assistants. The model is based on a category of covariant presheaves over a category of time objects, and quantification over clocks is modelled using a presheaf of clocks. To model the clock irrelevance axiom, crucial for programming with coinductive types, types must be interpreted as presheaves orthogonal to the object of clocks. In the case of dependent types, this translates to a lifting condition similar to the one found in homotopy theoretic models of type theory, but here with an additional requirement of uniqueness of lifts. Since the universes defined by the standard Hofmann-Streicher construction in this model do not satisfy this property, the universes in GDTT must be indexed by contexts of clock variables. We show how to model these universes in such a way that inclusions of clock contexts give rise to inclusions of universes commuting with type operations on the nose.
Peter D Mosses - One of the best experts on this subject based on the ideXlab platform.
-
VDM Semantics of programming languages: combinators and monads
Formal Aspects of Computing, 2010Co-Authors: Peter D MossesAbstract:The Vienna Development Method (VDM) was developed in the early 1970s as a variant of Denotational Semantics. VDM descriptions of programming languages differ from the original Scott–Strachey style by making extensive use of combinators which have a fixed operational interpretation. After recalling the main features of Denotational Semantics and the Scott–Strachey style, we examine the combinators of the VDM specification language, and relate them to monads, which were introduced more than 15 years later. We also suggest that use of further monadic combinators in VDM could be beneficial. Finally, we provide an overview of published VDM semantic descriptions of major programming languages.
-
vdm Semantics of programming languages combinators and monads
Formal Methods, 2007Co-Authors: Peter D MossesAbstract:Although VDM semantic descriptions of programming language are Denotational, they can be read quite operationally. After recalling the main features of Denotational Semantics, this paper examines the combinators of the VDM specification language, and relates them to the use of monads in the monadic style of Denotational Semantics. It also provides an overview of published VDM semantic descriptions of major programming languages. Familiarity is assumed with the basic concepts of formal specification.
Dirk Pattinson - One of the best experts on this subject based on the ideXlab platform.
-
Denotational Semantics of hybrid automata
The Journal of Logic and Algebraic Programming, 2007Co-Authors: Abbas Edalat, Dirk PattinsonAbstract:Abstract We introduce a Denotational Semantics for non-linear hybrid automata and relate it to the operational Semantics given in terms of hybrid trajectories. The Semantics is defined as least fixpoint of an operator on the continuous domain of functions of time that take values in the lattice of compact subsets of n -dimensional Euclidean space. The semantic function assigns to every point in time the set of states the automaton can visit at that time, starting from one of its initial states. Our main results are the correctness and computational adequacy of the Denotational Semantics with respect to the operational Semantics given in terms of hybrid trajectories. Moreover, we show that our Denotational Semantics can be effectively computed, which allows for the effective analysis of a large class of non-linear hybrid automata.
-
Denotational Semantics of hybrid automata
Foundations of Software Science and Computation Structure, 2006Co-Authors: Abbas Edalat, Dirk PattinsonAbstract:We introduce a Denotational Semantics for non-linear hybrid automata, and relate it to the operational Semantics given in terms of hybrid trajectories. The Semantics is defined as least fixpoint of an operator on the continuous domain of functions of time that take values in the lattice of compact subsets of n-dimensional Euclidean space. The semantic function assigns to every point in time the set of states the automaton can visit at that time, starting from one of its initial states. Our main results are the correctness and computational adequacy of the Denotational Semantics with respect to the operational Semantics and the fact that the Denotational Semantics is computable.
Steffen Lewitzka - One of the best experts on this subject based on the ideXlab platform.
-
Denotational Semantics for modal systems s3 s5 extended by axioms for propositional quantifiers and identity
Studia Logica, 2015Co-Authors: Steffen LewitzkaAbstract:There are logics where necessity is defined by means of a given identity connective: $${\square\varphi := \varphi\equiv\top}$$??:=??? ($${\top}$$? is a tautology). On the other hand, in many standard modal logics the concept of propositional identity (PI) $${\varphi\equiv\psi}$$??? can be defined by strict equivalence (SE) $${\square(\varphi\leftrightarrow\psi)}$$?(???) . All these approaches to modality involve a principle that we call the Collapse Axiom (CA): "There is only one necessary proposition." In this paper, we consider a notion of PI which relies on the identity axioms of Suszko's non-Fregean logic SCI. Then S3 proves to be the smallest Lewis modal system where PI can be defined as SE. We extend S3 to a non-Fregean logic with propositional quantifiers such that necessity and PI are integrated as non-interdefinable concepts. CA is not valid and PI refines SE. Models are expansions of SCI-models. We show that SCI-models are Boolean prealgebras, and vice-versa. This associates non-Fregean logic with research on Hyperintensional Semantics. PI equals SE iff models are Boolean algebras and CA holds. A representation result establishes a connection to Fine's approach to propositional quantifiers and shows that our theories are conservative extensions of S3---S5, respectively. If we exclude the Barcan formula and a related axiom, then the resulting systems are still complete w.r.t. a simpler Denotational Semantics.
-
a Denotational Semantics for a lewis style modal system close to s1
arXiv: Logic in Computer Science, 2013Co-Authors: Steffen LewitzkaAbstract:While possible worlds Semantics provides a natural framework for normal modal logics, there is no such intuitive Semantics for modal system S1 designed by C. I. Lewis as a logic of strict implication. In this paper, we interpret strict equivalence $\square(\varphi\rightarrow\psi)\wedge\square(\psi\rightarrow\varphi)$ as propositional identity $\varphi\equiv\psi$ (read: "$\varphi$ and $\psi$ denote the same proposition") and extend S1 by an inference rule which is a natural generalization of the rule of Substitutions of Proved Strict Equivalents. The resulting modal system is only slightly stronger than S1 and satisfies the principles of non-Fregean logic. This enables us to develop an intuitive, non-Fregean Denotational Semantics for which the system is sound and complete.
-
Denotational Semantics for modal systems s3 s5 extended by axioms for propositional quantifiers and identity
arXiv: Logic in Computer Science, 2012Co-Authors: Steffen LewitzkaAbstract:There are logics where necessity is defined by means of a given identity connective: $\square\varphi := \varphi\equiv\top$ ($\top$ is a tautology). On the other hand, in many standard modal logics the concept of propositional identity (PI) $\varphi\equiv\psi$ can be defined by strict equivalence (SE) $\square(\varphi\leftrightarrow\psi)$. All these approaches to modality involve a principle that we call the Collapse Axiom (CA): "There is only one necessary proposition." In this paper, we consider a notion of PI which relies on the identity axioms of Suszko's non-Fregean logic $\mathit{SCI}$. Then $S3$ proves to be the smallest Lewis modal system where PI can be defined as SE. We extend $S3$ to a non-Fregean logic with propositional quantifiers such that necessity and PI are integrated as non-interdefinable concepts. CA is not valid and PI refines SE. Models are expansions of $\mathit{SCI}$-models. We show that $\mathit{SCI}$-models are Boolean prealgebras, and vice-versa. This associates Non-Fregean Logic with research on Hyperintensional Semantics. PI equals SE iff models are Boolean algebras and CA holds. A representation result establishes a connection to Fine's approach to propositional quantifiers and shows that our theories are \textit{conservative} extensions of $S3$--$S5$, respectively. If we exclude the Barcan formula and a related axiom, then the resulting systems are still complete w.r.t. a simpler Denotational Semantics.
