Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFitch-Style Modal Lambda Calculi
79
0
0.0
(
0
)
Added by
Ranald Clouston
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Authors
Ranald Clouston
Ask ChatGPT about the research
No Arabic abstract
Fitch-style modal deduction, in which modalities are eliminated by opening a subordinate proof, and introduced by shutting one, were investigated in the 1990s as a basis for lambda calculi. We show that such calculi have good computational properties for a variety of intuitionistic modal logics. Semantics are given in cartesian closed categories equipped with an adjunction of endofunctors, with the necessity modality interpreted by the right adjoint. Where this functor is an idempotent comonad, a coherence result on the semantics allows us to present a calculus for intuitionistic S4 that is simpler than others in the literature. We show the calculi can be extended `{a} la tense logic with the left adjoint of necessity, and are then complete for the categorical semantics.
rate research
Read More
A notion of probabilistic lambda-calculus usually comes with a prescribed reduction strategy, typically call-by-name or call-by-value, as the calculus is non-confluent and these strategies yield different results. This is a break with one of the main advantages of lambda-calculus: confluence, which means results are independent from the choice of strategy. We present a probabilistic lambda-calculus where the probabilistic operator is decomposed into two syntactic constructs: a generator, which represents a probabilistic event; and a consumer, which acts on the term depending on a given event. The resulting calculus, the Probabilistic Event Lambda-Calculus, is confluent, and interprets the call-by-name and call-by-value strategies through different interpretations of the probabilistic operator into our generator and consumer constructs. We present two notions of reduction, one via fine-grained local rewrite steps, and one by generation and consumption of probabilistic events. Simple types for the calculus are essentially standard, and they convey strong normalization. We demonstrate how we can encode call-by-name and call-by-value probabilistic evaluation.
Formal reasoning about distributed algorithms (like Consensus) typically requires to analyze global states in a traditional state-based style. This is in contrast to the traditional action-based reasoning of process calculi. Nevertheless, we use domain-specific variants of the latter, as they are convenient modeling languages in which the local code of processes can be programmed explicitly, with the local state information usually managed via parameter lists of process constants. However, domain-specific process calculi are often equipped with (unlabeled) reduction semantics, building upon a rich and convenient notion of structural congruence. Unfortunately, the price for this convenience is that the analysis is cumbersome: the set of reachable states is modulo structural congruence, and the processes state information is very hard to identify. We extract from congruence classes of reachable states individual state-informative representatives that we supply with a proper formal semantics. As a result, we can now freely switch between the process calculus terms and their representatives, and we can use the stateful representatives to perform assertional reasoning on process calculus models.
Encodings or the proof of their absence are the main way to compare process calculi. To analyse the quality of encodings and to rule out trivial or meaningless encodings, they are augmented with encodability criteria. There exists a bunch of different criteria and different variants of criteria in order to reason in different settings. This leads to incomparable results. Moreover, it is not always clear whether the criteria used to obtain a result in a particular setting do indeed fit to this setting. This paper provides a short survey on often used encodability criteria, general frameworks that try to provide a unified notion of the quality of an encoding, and methods to analyse and compare encodability criteria.
A recent strand of research in structural proof theory aims at exploring the notion of analytic calculi (i.e. those calculi that support general and modular proof-strategies for cut elimination), and at identifying classes of logics that can be captured in terms of these calculi. In this context, Wansing introduced the notion of proper display calculi as one possible design framework for proof calculi in which the analiticity desiderata are realized in a particularly transparent way. Recently, the theory of properly displayable logics (i.e. those logics that can be equivalently presented with some proper display calculus) has been developed in connection with generalized Sahlqvist theory (aka unified correspondence). Specifically, properly displayable logics have been syntactically characterized as those axiomatized by analytic inductive axioms, which can be equivalently and algorithmically transformed into analytic structural rules so that the resulting proper display calculi enjoy a set of basic properties: soundness, completeness, conservativity, cut elimination and subformula property. In this context, the proof that the given calculus is complete w.r.t. the original logic is usually carried out syntactically, i.e. by showing that a (cut free) derivation exists of each given axiom of the logic in the basic system to which the analytic structural rules algorithmically generated from the given axiom have been added. However, so far this proof strategy for syntactic completeness has been implemented on a case-by-case base, and not in general. In this paper, we address this gap by proving syntactic completeness for properly displayable logics in any normal (distributive) lattice expansion signature. Specifically, we show that for every analytic inductive axiom a cut free derivation can be effectively generated which has a specific shape, referred to as pre-normal form.
Type theories with higher-order subtyping or singleton types are examples of systems where computation rules for variables are affected by type information in the context. A complication for these systems is that bounds declared in the context do not interact well with the logical relation proof of completeness or termination. This paper proposes a natural modification to the type syntax for F-Omega-Sub, adding variables bound to the variable type constructor, thereby separating the computational behavior of the variable from the context. The algorithm for subtyping in F-Omega-Sub can then be given on types without context or kind information. As a consequence, the metatheory follows the general approach for type systems without computational information in the context, including a simple logical relation definition without Kripke-style indexing by context. This new presentation of the system is shown to be equivalent to the traditional presentation without bounds on the variable type constructor.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
