11th International Workshop, CSL '97 Annual Conference of the EACSL Aarhus, Denmark, August 23–29, 1997 Selected Papers
A general construction of models of call-by-value from models of call-by-name computation is described. The construction makes essential use of the properties of sum types in common denotational models of call-by-name. When applied to categories of games, it yields fully abstract models of the call-by-value functional language PCFv, which can be extended to incorporate recursive types, and of a language...
We integrate two concepts from programming languages into a specification language based on WS2S, namely high-level data structures such as records and recursively-defined datatypes (WS2S is the weak second-order monadic logic of two successors). Our integration is based on a new logic whose variables range over record-like trees and an algorithm for translating datatypes into tree automata. We have...
Given a finite set K of lethal genes, a starting genome x and a desired target genome y, is there a sequence of base insertions, deletions, and substitutions, which from x produces the desired genome y, and such that no intermediate genome contains a lethal gene. The main result of this paper is that, appropriately formulated, this problem is undecidable, even when the underlying alphabet has only...
Two models of classical linear logic are set up. First our recent version of AJM games model which will be our source model. Then the target model, polarized pointed relations, a variant of the plain relational model which is constructed in two steps: first the model of pointed relations, then the additional polarization structure which yields a proper duality. Then the natural time-forgetting map...
Milner introduced action calculi as a framework for investigating models of interactive behaviour. We present a type-theoretic account of action calculi using the propositions-as-types paradigm; the type theory has a sound and complete interpretation in Power's categorical models. We go on to give a sound translation of our type theory in the (type theory of) intuitionistic linear logic, corresponding...
In this paper, we introduce a sequent calculus CIRC for propositional Circumscription. This work is part of a larger project, aiming at a uniform proof-theoretic reconstruction of the major families of non-monotonic logics. Among the novelties of the calculus, we mention that CIRC is analytic and comprises an axiomatic rejection method, which allows for a fully detailed formalization of the nonmonotonic...
We investigate the complexity of proofs in Frege (F), Substitution Frege (sF) and Renaming Frege (rF) systems. Starting from a recent work of Urquhart and using Kolmogorov Complexity we give a more general framework to obtain superlogarithmic lower bounds for the number of lines in both tree-like and dag-like sF. We show the previous known lower bound, extend it to the tree-like case and, for another...
In this paper we describe a solution to the problem of proving cut-elimination for FILL, a variant of exponential-free and multiplicative Linear Logic originally introduced by Hyland and de Paiva. In the work of Hyland and de Paiva, a term assignment system is used to describe the intuitionistic character of FILL and a proof of cut-elimination is barely sketched. In the present paper, as well as correcting...
We give new upper bounds for resolution proofs of the weak pigeonhole principle. We also give lower bounds for tree-like resolution proofs. We present a normal form for resolution proofs of pigeonhole principles based on a new monotone resolution rule.
We present a concrete example of how one can extract constructive content from a non-constructive proof. The proof investigated is a termination proof of the string-rewriting system 1100 → 000111. This rewriting system is self-embedding, so the standard termination techniques which rely on Kruskal's Tree Theorem cannot be applied directly. Dershowitz and Hoot [3] have given a classical termination...
The spectrum of a first-order sentence is the set of cardinalities of its finite models. This paper is concerned with spectra of sentences over languages that contain only unary function symbols. In particular, it is shown that a set S of natural numbers is the spectrum of a sentence over the language of one unary function symbol precisely if S is an eventually periodic set.
Cut-elimination, besides being an important tool in proof-theory, plays a central role in the proofs-as-programs paradigm. In recent years this approach has been extended to classical logic (cf. Girard 1991, Parigot 1991, and recently Danos Joinet Schellinx 1997). This paper introduces a new sequent calculus for (propositional) classical logic, indicated by ⊥C. Both, the calculus and the cut-elimination...
Let Lk be the k-variable fragment of first-order logic, for some k ≥ 3. We prove that equivalence of finite structures in Lk has no P-computable canonization function unless NP ⊑ P/poly. The latter assumption is considered as highly unlikely; in particular it implies a collapse of the polynomial hierarchy. The question for such a canonization function came up in the context of the problem of whether...
We study an applied typed call-by-value λ-calculus which in addition to the usual types for higher-order functions contains an extra type called proc, for processes; the constructors for terms of this type are similar to those found in standard process calculi such as CCS. We first give an operational semantics for this language in terms of a labelled transition system which is then used to give a...
A continuous predicate on a domain, or more generally a topological space, can be concretely described as an open or closed set, or less obviously, as the set of all predicates consistent with it. Generalizing this scenario to quantitative predicates, we obtain under certain well-understood hypotheses an isomorphism between continuous functions on points and supremum preserving functions on open sets,...
This paper introduces a simply-typed lambda calculus with both modal and linear function types. Through the use of subtyping extra term formers associated with modality and linearity are avoided. We study the basic metatheory of this system including existence and inference of principal types. The system serves as a platform for certain higher-order generalisations of Bellantoni-Cook's function...
We have axiomatized test algebra equations and achieved a finite equational axiomatization relative to Kleene algebra. The previous section showed that the Kleene algebra component cannot be replaced by a finite set of test algebra equations. There is thus a tradeoff: on the one hand we have a sound and complete axiomatization using an infinite number of equations (this paper), on the other...
We discuss in this paper how connections, discovered almost forty years ago, between logics and automata can be used in practice. For such logics expressing regular sets, we have developed tools that allow efficient symbolic reasoning not attainable by theorem proving or symbolic model checking. We explain how the logic-automaton connection is already exploited in a limited way for the case...
In the automata-theoretic approach to verification, we model programs and specifications by automata on infinite words. Correctness of a program with respect to a specification can then be reduced to the language-containment problem. In a concurrent setting, the program is typically a parallel composition of many coordinating processes, and the language-containment problem that corresponds to verification...