Infinite intersection types

A type theory with infinitary intersection and union types for an extension of the λ-calculus is introduced. Types are viewed as upper closed subsets of a Scott domain and intersection and union type constructors are interpreted as the set-theoretic intersection and union, respectively, even when they are not finite. The assignment of types to λ-terms extends naturally the basic type assignment system. We prove soundness and completeness using a generalization of Abramsky’s finitary logic of domains. Finally, we apply the framework to applicative transition systems, obtaining a sound a complete infinitary intersection type assignment system for the lazy λ-calculus.     

Perpetual Reductions inλ-Calculus

This paper surveys a part of the theory ofβ-reduction inλ-calculus which might aptly be calledperpetual reductions. The theory is concerned withperpetual reduction strategies, i.e., reduction strategies that compute infinite reduction paths fromλ-terms (when possible), and withperpetual redexes, i.e., redexes whose contraction inλ-terms preserves the possibility (when present) of infinite reduction paths. The survey not only recasts classical theorems in a unified setting, but also offers new results, proofs, and techniques, as well as a number of applications to problems inλ-calculus and type theory.     

Discrimination by Parallel Observers: The Algorithm

The main result of the paper is a constructive proof of the following equivalence: two pureλ-terms are observationally equivalent in the lazy concurrentλ-calculusiffthey have the same Lévy–Longo trees. An algorithm which allows to build a context discriminating any two pureλ-terms with different Lévy–Longo trees is described. It follows that contextual equivalence coincides with behavioural equivalence (bisimulation) as considered by Sangiorgi. Another consequence is that the discriminating power of concurrent lambda contexts is the same as that of Boudol–Laneve's contexts with multiplicities.     

On the Jacopini Technique

The general concern of the Jacopini technique is the question: “Is it consistent to extend a given lambda calculus with certain equations?” The technique was introduced by Jacopini in 1975 in his proof that in the untyped lambda calculusΩis easy, i.e.,Ωcan be assumed equal to any other (closed) term without violating the consistency of the lambda calculus. The presentations of the Jacopini technique that are known from the literature are difficult to understand and hard to generalise. In this paper we generalise the Jacopini technique for arbitrary lambda calculi. We introduce the concept ofproof-replaceabilityby which the structure of the technique is simplified considerably. We illustrate the simplicity and generality of our formulation of the technique with some examples. We apply the Jacopini technique to theλμ-calculus, and we prove a general theorem concerning the consistency of extensions of theλμ-calculus of a certain form. Many well known examples (e.g., the easiness ofΩ) are immediate consequences of this general theorem.     

Translating Combinatory Reduction Systems into the Rewriting Calculus

The last few years have seen the development of the rewriting calculus (or rho-calculus, ρCal) that extends first order term rewriting and λ-calculus. The integration 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, or by adding to λ-calculus algebraic features. The different higher-order rewriting systems and the rewriting calculus share similar concepts and have similar applications, and thus, it seems natural to compare these formalisms. We analyze in this paper the relationship between the Rewriting Calculus and the Combinatory Reduction Systems and we present a translation of CRS-terms and rewrite rules into rho-terms and we show that for any CRS-reduction we have a corresponding rho-reduction.     

Subtyping in Logical Form

By using intersection types and filter models we formulate a theory of types for a λ-calculus with record subtyping via a finitary programming logic. Types are interpreted as spaces of filters over a subset of the language of properties (the intersection types) which describes the underlying type free realizability structure. We show that such an interpretation is a PER semantics, proving that the quotient space arising from “logical” PERs taken with the intrinsic ordering is isomorphic to the filter semantics of types.     

Completeness of Continuation Models for λμ-Calculus

We show that a certain simple call-by-name continuation semantics of Parigot's λ_μ-calculus is complete. More precisely, for every λ_μ-theory we construct a cartesian closed category such that the ensuing continuation-style interpretation of λ_μ, which maps terms to functions sending abstract continuations to responses, is full and faithful. Thus, any λ_μ-category in the sense of L. Ong (1996, in “Proceedings of LICS '96,” IEEE Press, New York) is isomorphic to a continuation model (Y. Lafont, B. Reus, and T. Streicher, “Continuous Semantics or Expressing Implication by Negation,” Technical Report 93-21, University of Munich) derived from a cartesian-closed category of continuations. We also extend this result to a later call-by-value version of λ_μ developed by C.-H. L. Ong and C. A. Stewart (1997, in “Proceedings of ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Paris, January 1997,” Assoc. Comput. Mach. Press, New York).     

Approximation by Bézier type of Meyer–König and Zeller operators

In this paper, we give direct, inverse and equivalence approximation theorems for the Bézier type of Meyer–König and Zeller operator with unified Ditzian–Totik modulus ω_φ^λ(f,t) (0≤λ≤1).     

Congruence of Bisimulation in a Non-Deterministic Call-By-Need Lambda Calculus

We present a call-by-need λ-calculus λ_ND with an erratic non-deterministic operator pick and a non-recursive let. A definition of a bisimulation is given, which has to be based on a further calculus named λ_≈, since the naïve bisimulation definition is useless. The main result is that bisimulation in λ_≈ is a congruence and coincides with the contextual equivalence. The proof is a non-trivial extension of Howe's method. This might be a step towards defining useful bisimulation relations and proving them to be congruences in calculi that extend the λ_ND-calculus.     

A Proof of Strong Normalization for F2, Fω, and Beyond

We present an evaluation technique for proving strong normalization (SN). We use the technique to give SN proofs for F₂, F-bounded quantification, subtypes, and Fω. The evaluation technique derives SN as a corollary of the soundness of the typing rules under an appropriate evaluation semantics. The evaluation semantics yields simpler type sets than those used in the earlier SN proofs. The type sets discussed here form a complete lattice under classical union and intersection. The simplified type sets allow a simplified treatment of a variety of type constructors.     

Maximum flow and critical cutset as descriptors of multi-state systems with randomly capacitated components

Let G = (V, E, s, t) denote a directed network with node set V, arc set E = {1,…, n}, source node s and sink node t. Let Γ denote the set of all minimal s−t cutsets and b₁(τ), …, B_n(τ), the random arc capacities at time τ with known joint probability distribution function. Let Λ(τ) denote the maximum s−t flow at time τ and D(τ), the corresponding critical minimal s−t cutset. Let Ω denote a set of minimal s−t cutsets. This paper describes a comprehensive Monte Carlo sampling plan for efficiently estimating the probability that D(τ)εΩ-Γ and x<λ(τ)y at time τ and the probability that D(τ) Ω given that x < Λ(τ) y at time τ. The proposed method makes use of a readily obtainable upper bound on the probability that Λ(τ) > x to gain its computational advantage. Techniques are described for computing confidence intervals and credibility measures for assessing that specified accuracies have been achieved. The paper includes an algorithm for performing the Monte Carlo sampling experiment, an example to illustrate the technique and a listing of all steps needed for implementation.     

An Extension of System F with Subtyping

System F is a well-known typed λ-calculus with polymorphic types, which provides a basis for polymorphic programming languages. We study an extension of F, called F_<: (pronounced ef-sub), that combines parametric polymorphism with subtyping. The main focus of the paper is the equational theory of F_<:, which is related to PER models and the notion of parametricity. We study some categorical properties of the theory when restricted to closed terms, including interesting categorical isomorphisms. We also investigate proof-theoretical properties, such as the conservativity of typing judgments with respect to F. We demonstrate by a set of examples how a range of constructs may be encoded in F_<:. These include record operations and subtyping hierarchies that are related to features of object-oriented languages.     

Database Query Languages Embedded in the Typed Lambda Calculus

We investigate the expressive power of the typedλ-calculus when expressing computations over finite structures, i.e., databases. We show that the simply typedλ-calculus can express various database query languages such as the relational algebra, fixpoint logic, and the complex object algebra. In our embeddings, inputs and outputs areλ-terms encoding databases, and a program expressing a query is aλ-term which types when applied to an input and reduces to an output. Our embeddings have the additional property that PTIME computable queries are expressible by programs that, when applied to an input, reduce to an output in a PTIME sequence of reduction steps. Under our database input-output conventions, all elementary queries are expressible in the typedλ-calculus and the PTIME queries are expressible in the order-5 (order-4) fragment of the typedλ-calculus (with equality).     

A type theory which is complete for Kreisel's modified realizability

We define a type theory with a strong elimination rule for existential quantification. As in Martin-Löf's type theory, the “axiom of choice” is thus derivable. Proofs are also annotated by realizers which are simply typed λ-terms. A new rule called “type extraction” which extracts the type of a realizer allows us to derive the so-called “independance of premisses” schema. Consequently, any formula which is realizable in HA^ω, according to Kreisel's modified realizability, is derivable in this type theory.     

An estimate on the convergence of MKZ–Bézier operators

The pointwise approximation properties of the MKZ–Bézier operators M_n,α(f,x) for α≥1 have been studied in [X.M. Zeng, Rates of approximation of bounded variation functions by two generalized Meyer–König–Zeller type operators, Comput. Math. Appl. 39 (2000) 1–13]. The aim of this paper is to study the pointwise approximation of the operators M_n,α(f,x) for the other case 0<α<1. By means of some new estimate techniques and a result of Guo and Qi [S. Guo, Q. Qi, The moments for the Meyer–König and Zeller operators, Appl. Math. Lett. 20 (2007) 719–722], we establish an estimate formula on the rate of convergence of the operators M_n,α(f,x) for the case 0<α<1.     

A numerical method for deadbeat control of generalized state-space systems

In this paper we give a new numerical method for constructing a rank m correction BF to an n × n matrix A, such that the generalized eigenvalues of λE−(A+BF) are all at λ = 0. In the control literature, this problem is known as ‘deadbeat control’ of a generalized state-space system Ex_i+1 = Ax_i + Bu_i, whereby the matrix F is the ‘feedback matrix’ to be constructed.     

A logic for reasoning about probabilities

We consider a language for reasoning about probability which allows us to make statements such as “the probability of E₁ is less than ” and “the probability of E₁ is at least twice the probability of E₂,” where E₁ and E₂ are arbitrary events. We consider the case where all events are measurable (i.e., represent measurable sets) and the more general case, which is also of interest in practice, where they may not be measurable. The measurable case is essentially a formalization of (the propositional fragment of) Nilsson's probabilistic logic. As we show elsewhere, the general (nonmeasurable) case corresponds precisely to replacing probability measures by Dempster-Shafer belief functions. In both cases, we provide a complete axiomatization and show that the problem of deciding satisfiability is NP-complete, no worse than that of propositional logic. As a tool for proving our complete axiomatizations, we give a complete axiomatization for reasoning about Boolean combinations of linear inequalities, which is of independent interest. This proof and others make crucial use of results from the theory of linear programming. We then extend the language to allow reasoning about conditional probability and show that the resulting logic is decidable and completely axiomatizable, by making use of the theory of real closed fields.     

Descendants and Origins in Term Rewriting

In this paper we treat various aspects of a notion that is central in term rewriting, namely that of descendants or residuals. We address both first-order term rewriting and λ-calculus, their finitary as well as their infinitary variants. A recurrent theme is the parallel moves lemma. Next to the classical notion of descendant, we introduce an extended version, known as origin tracking. Origin tracking has many applications. Here it is employed to give new proofs of three classical theorems: the genericity lemma in λ-calculus, the theorem of Huet and Lévy on needed reductions in first-order term rewriting, and Berry's sequentiality theorem in (infinitary) λ-calculus.     

Developing (Meta)Theory of λ-calculus in the Theory of Contexts

We present a case study on the formal development of a non trivial (meta)theory in the Theory of Contexts using the Coq proof assistant. The methodology underlying the Theory of Contexts for reasoning on systems presented in HOAS is based on an axiomatic syntactic standpoint. We feel that one of the main advantages of this approach, is that it requires a very low logical overhead.The object system we focus on is the lazy, call-by-name λ-calculus (λ_cbn), both untyped and simply typed. We will see that the formal, fully detailed development of the theory of (λ_cbn) in the Theory of Contexts introduces a small, sustainable overhead with respect to the proofs “on the paper”. Moreover, this will allow for comparison with similar case studies developed in other approaches to the metatheoretical reasoning in higher-order abstract syntax.