A Calculus of Lambda Calculus Contexts

The calculus c serves as a general framework for representing contexts. Essential features are control over variable capturing and the freedom to manipulate contexts before or after hole filling, by a mechanism of delayed substitution. The context calculus c is given in the form of an extension of the lambda calculus. Many notions of context can be represented within the framework; a particular variation can be obtained by the choice of a pretyping, which we illustrate by three examples.     

CPS Translations and Applications: The Cube and Beyond

Continuation passing style (CPS) translations of typed -calculi have numerous applications. However, the range of these applications has been confined by the fact that CPS translations are known for non-dependent type systems only, thus excluding well-known systems like the calculus of constructions (CC) and the logical frameworks (LF). This paper presents techniques for CPS translating systems with dependent types, with an emphasis on pure type-theoretical applications.In the first part of the paper we review several lines of work in which the need for CPS translations of dependent type systems has arisen, and discuss the difficulties involved with CPS translating such systems. One way of overcoming these difficulties is to work with so-called domain-free type systems. Thus, instead of Barendregt's -cube we shall consider the domain-free -cube, and instead of traditional pure type systems, we shall consider domain-free pure type systems.We therefore begin the second part by reviewing the domain-free -cube, which includes domain-free versions of CC and LF, and then present CPS translations for all the systems of the domain-free -cube. We also introduce Direct Style (DS) (i.e., inverse CPS) translations for all the systems of the domain-free -cube; such DS translations, which have been used in a number of applications, were previously formulated for untyped and simply-typed languages only.In the third part we review domain-free pure type systems and generalize the CPS translations of the domain-free -cube to a large class of domain-free pure type systems which includes most of the systems that appear in the literature, including those of the domain-free -cube. Many translations that appear in the literature arise as special cases of ours.In the fourth part of the paper we present two approaches to CPS translations of traditional pure type systems. The first, indirect, technique lifts the CPS translation of domain-free pure type systems to the analogous class of traditional pure type systems by using results that relate derivations in domain-free and traditional pure type systems. The second, direct, approach translates derivations, requiring a certain order on derivations to be well-founded. Both techniques yield translations for most of the systems that appear in the literature, including those of Barendregt's -cube.     

Expressing combinatory reduction systems derivations in the rewriting calculus

The last few years have seen the development of the rewriting calculus (also called rho-calculus or ρ-calculus) that uniformly integrates first-order term rewriting and the λ-calculus. The combination of these two latter formalisms has been already handled either by enriching first-order rewriting with higher-order capabilities, like in the Combinatory Reduction Systems (CRS), or by adding to the λ-calculus algebraic features. The various higher-order rewriting systems and the rewriting calculus share similar concepts and have similar applications, and thus, it is important to compare these formalisms to better understand their respective strengths and differences. We show in this paper that we can express Combinatory Reduction Systems derivations in terms of rewriting calculus derivations. The approach we present is based on a translation of each possible CRS-reduction into a corresponding ρ-reduction. Since for this purpose we need to make precise the matching used when evaluating CRS, the second contribution of the paper is to present an original matching algorithm for CRS terms that uses a simple term translation and the classical matching of lambda terms.     

The <Emphasis Type="Italic">λ</Emphasis>-Calculus and the Unity of Structural Proof Theory

In the context of intuitionistic implicational logic, we achieve a perfect correspondence (technically an isomorphism) between sequent calculus and natural deduction, based on perfect correspondences between left-introduction and elimination, cut and substitution, and cut-elimination and normalisation. This requires an enlarged system of natural deduction that refines von Plato’s calculus. It is a calculus with modus ponens and primitive substitution; it is also a “coercion calculus”, in the sense of Cervesato and Pfenning. Both sequent calculus and natural deduction are presented as typing systems for appropriate extensions of the λ-calculus. The whole difference between the two calculi is reduced to the associativity of applicative terms (sequent calculus = right associative, natural deduction = left associative), and in fact the achieved isomorphism may be described as the mere inversion of that associativity. The novel natural deduction system is a “multiary” calculus, because “applicative terms” may exhibit a list of several arguments. But the combination of “multiarity” and left-associativity seems simply wrong, leading necessarily to non-local reduction rules (reason: normalisation, like cut-elimination, acts at the head of applicative terms, but natural deduction focuses at the tail of such terms). A solution is to extend natural deduction even further to a calculus that unifies sequent calculus and natural deduction, based on the unification of cut and substitution. In the unified calculus, a sequent term behaves like in the sequent calculus, whereas the reduction steps of a natural deduction term are interleaved with explicit steps for bringing heads to focus. A variant of the calculus has the symmetric role of improving sequent calculus in dealing with tail-active permutative conversions.     

A general framework for types in graph rewriting

We investigate a general framework which can be instantiated in order to obtain type systems for graph rewriting, allowing us to statically infer behavioural properties of a graph. We describe conditions such as the subject reduction property and compositionality that should be satisfied by such a framework. We present a methodology for proving these conditions, specifically we prove that it is sufficient to show properties that are local to graph transformation rules. In order to show the applicability of this framework, we describe in several case studies how to integrate existing type systems (for the π-calculus and the λ-calculus) and a system for typing acyclic graphs. This is a completely revised and extended version of a paper of which an earlier version has appeared in FSTTCS '00.     

Cut-free proof systems for logics of weak excluded middle

 In this work we perform a proof-theoretical investigation of some logical systems in the neighborhood of substructural, intermediate and many-valued logics. The common feature of the logics we consider is that they satisfy some weak forms of the excluded-middle principle. We first propose a cut-free hypersequent calculus for the intermediate logic LQ, obtained by adding the axiom *A∨**A to intuitionistic logic. We then propose cut-free calculi for systems W _n , obtained by adding the axioms *A∨(A ⊕ ⋯ ⊕ A) (n−1 times) to affine linear logic (without exponential connectives). For n=3, the system W _n coincides with 3-valued Łukasiewicz logic. For n>3, W _n is a proper subsystem of n-valued Łukasiewicz logic. Our calculi can be seen as a first step towards the development of uniform cut-free Gentzen calculi for finite-valued Łukasiewicz logics.     

The π-Calculus in Direct Style

We introduce a calculus which is a direct extension of both the and the calculi. We give a simple type system for it, that encompasses both Curry's type inference for the -calculus, and Milner's sorting for the -calculus as particular cases of typing. We observe that the various continuation passing style transformations for -terms, written in our calculus, actually correspond to encodings already given by Milner and others for evaluation strategies of -terms into the -calculus. Furthermore, the associated sortings correspond to well-known double negation translations on types. Finally we provide an adequate CPS transform from our calculus to the -calculus. This shows that the latter may be regarded as an assembly language, while our calculus seems to provide a better programming notation for higher-order concurrency. We conclude by discussing some alternative design decisions.     

Rate of convergence of nonlinear integral operators for functions of bounded variation

The aim of this paper is to study the behavior of the operators T _λ defined by

On Chebyshev quadrature for ultraspherical weight functions

It is well-known that for the ultraspherical weight function (1-x²)^λ-1/2 there exist no Chebyshev quadrature formulae in the strict sense having n nodes, where n is sufficiently large and λ>0, whereas on the other hand for λ=0 every Gaussian quadrature formulae is a Chebyshev formula in the strict sense. In this paper we study the open question of Chebyshev quadrature for λ <0. It is shown that there exists no Chebyshev quadrature formula in the strict sense having more than two nodes for λ≤λ₀=-.30056... (for definition of λ₀ see (1.8) below). Moreover, results are obtained for Chebyshev-type formulae and Chebyshev formulae of closed type. For the remaining values of λ (λ₀<λ<0) numerical results are given.     

Eliminating Proofs from Programs

This paper presents a step in the development of an operational approach to program extraction in type theory. In order to get a program from a lambda term, the logical parts need to be removed. This is done by a reduction relation →_ε. We study the combination of β-reduction and ε-reduction, both in the setting of simply typed lambda calculus and for pure type systems. In the general setting the properties confluence, subject reduction, and strong normalization are studied.     

Explaining the lazy Krivine machine using explicit substitution and addresses

In a previous paper, Benaissa, Lescanne, and Rose, have extended the weak lambda-calculus of explicit substitution λ σ _w with addresses, so that it gives an account of the sharing implemented by lazy functional language interpreters. We show in this paper that their calculus, called λ σ _w ^a , fits well to the lazy Krivine machine, which describes the core of a lazy (call-by-need) functional programming language implementation. The lazy Krivine machine implements term evaluation sharing, that is essential for efficiency of such languages. The originality of our proof is that it gives a very detailed account of the implemented strategy.     

Thermal waveguide and fine-scale periodic relief on the semiconductor’s surface induced by TEA CO<Subscript>2</Subscript> laser radiation

The results of experimental study of linear CO₂ laser radiation interaction with semiconductor monocrystals (silicon, germanium, gallium arsenide,) are presented. It was shown that produced surface relief of micro- and nano-structures with spatial periods d ~ λ/n, d ~ λ/2n and d ~ λ/8n (for germanium) are well explained in the framework of universal polariton model of laser-induced condensed-matter damage.     

Classification of Steiner quadruple systems of order 16 and rank at most 13<Superscript>1</Superscript>

A Steiner quadruple system SQS(v) of order v is a 3-design T (v, 4, 3, ) with = 1. In this paper we describe all nonisomorphic systems SQS(16) that can be obtained by the generalized concatenated construction (GC-construction). These Steiner systems have rank at most 13 over ₂. In particular, there is one system SQS(16) of rank 11 (points and planes of the a fine geometry AG(4, 2)), fifteen systems of rank 12, and 4131 systems of rank 13. All these Steiner systems are resolvable.Translated from Problemy Peredachi Informatsii, No. 4, 2004, pp. 48–67.Original Russian Text Copyright © 2004 by V. Zinoviev, D. Zinoviev.     

The Postal Network: A Recursive Network for Parameterized Communication Model

The postal network is an interconnection network that possesses many desirable properties in networking applications. It includes hypercubes and Fibonacci cubes as its special cases. Basically, the postal network forms a series (with series number ) that is based on the sequence N (n)=N (n–1)+N (n–), where n is the dimension and N (n) represents the number of nodes in an n-dimensional postal network in series . In this paper, we study topological properties of postal networks and relationships between different postal networks. One application of postal networks is also shown in implementing barrier synchronization using a special spanning tree called a postal tree. The postal network can also be considered as a flexible version of the hypercube by relaxing the restriction on the number of nodes, and hence, makes it possible to construct multicomputers with arbitrary sizes.     

Weak Updates and Separation Logic

Separation logic provides a simple but powerful technique for reasoning about low-level imperative programs that use shared data structures. Unfortunately, separation logic supports only “strong updates,” in which mutation to a heap location is safe only if a unique reference is owned. This limits the applicability of separation logic when reasoning about the interaction between many high-level languages (e.g., ML, Java, C#) and low-level ones since the high-level languages do not support strong updates. Instead, they adopt the discipline of “weak updates,” in which there is a global “heap type” to enforce the invariant of type-preserving heap updates. We present SL ^w , a logic that extends separation logic with reference types and elegantly reasons about the interaction between strong and weak updates. We describe a semantic framework for reference types, which is used to prove the soundness of SL ^w . Finally, we show how to extend SL ^w with concurrency.     

Lifting Infinite Normal Form Definitions From Term Rewriting to Term Graph Rewriting

nfinite normal forms are a way of giving semantics to non-terminating rewrite systems. The notion is a generalization of the Böhm tree in the lambda calculus. It was first introduced in [Ariola, Z. M. and S. Blom, Cyclic lambda calculi, in: Abadi and Ito [Abadi, M. and T. Ito, editors, “Theoretical Aspects of Computer Software,” Lecture Notes in Computer Science 1281, Springer Verlag, 1997], pp. 77–106] to provide semantics for a lambda calculus on terms with letrec. In that paper infinite normal forms were defined directly on the graph rewrite system. In [Blom, S., “Term Graph Rewriting - syntax and semantics,” Ph.D. thesis, Vrije Universiteit Amsterdam (2001)] the framework was improved by defining the infinite normal form of a term graph using the infinite normal form on terms. This approach of lifting the definition makes the non-confluence problems introduced into term graph rewriting by substitution rules much easier to deal with. In this paper, we give a simplified presentation of the latter approach.     

Coquand's calculus of constructions: A mathematical foundation for a proof development system

The calculus of constructions of Coquand, which is a version of higher order typed-calculus based on the dependent function type, is considered from the perspective of its use as the mathematical foundation for a proof development system. The paper considers formulations of the calculus, the underlying consistency of the formalism (i.e., the strong normalisation theorem), and the proof theory of adding assumptions for notions from logic and set theory. Proofs are not given, but references to them are.A preliminary version of this paper was presented at the Third Banff Higher Order Workshop, 23–28 September 1989.     

On a Retrial Single-Server Queueing System with Finite Buffer and Multivariate Poisson Flow

We consider a single-server queueing system with a finite buffer, K input Poisson flows of intensities _i , and distribution functions B _i (x) of service times for calls of the ith type, . If the buffer is overflowed, an arriving call is sent to the orbit and becomes a repeat call. In a random time, which has exponential distribution, the call makes an attempt to reenter the buffer or server, if the latter is free. The maximum number of calls in the orbit is limited; if the orbit is overflowed, an arriving call is lost. We find the relation between steady-state distributions of this system and a system with one Poisson flow of intensity where type i of a call is chosen with probability _i / at the beginning of its service. A numerical example is given.     

An analytic approach to the problem of separability of quantum states based upon the theory of cones

Exploiting the cone structure of the set of unnormalized mixed quantum states, we offer an approach to detect separability independently of the dimensions of the subsystems. We show that any mixed quantum state can be decomposed as ρ = (1−λ)C _ρ  + λE _ρ , where C _ρ is a separable matrix whose rank equals that of ρ and the rank of E _ρ is strictly lower than that of ρ. With the simple choice C_r=M₁?M₂{C_{\rho}=M_{1}\otimes M_{2}} we have a necessary condition of separability in terms of λ, which is also sufficient if the rank of E _ρ equals 1. We give a first extension of this result to detect genuine entanglement in multipartite states and show a natural connection between the multipartite separability problem and the classification of pure states under stochastic local operations and classical communication. We argue that this approach is not exhausted with the first simple choices included herein.