We present a new method for characterizing the interpretive possibilities generated by elliptical constructions in natural language. Unlike previous analyses, which postulate ambiguity of interpretation or derivation in the full clause source of the ellipsis, our analysis requires no such hidden ambiguity. Further, the analysis follows relatively directly from an abstract statement of the ellipsis interpretation problem. It predicts correctly a wide range of interactions between ellipsis and other semantic phenomena such as quantifier scope and bound anaphora. Finally, although the (...) analysis itself is stated nonprocedurally, it admits of a direct computational method for generating interpretations. (shrink)

Using a version of situation semantics, this article argues that bare and complex demonstratives are interpreted as individual concepts.

We present a general theory of scope and binding in which both crossover and superiority violations are ruled out by one key assumption: that natural language expressions are normally evaluated (processed) from left to right. Our theory is an extension of Shan’s (2002) account of multiple-wh questions, combining continuations (Barker, 2002) and dynamic type-shifting. Like other continuation-based analyses, but unlike most other treatments of crossover or superiority, our analysis is directly compositional (in the sense of, e.g., Jacobson, 1999). In particular, (...) it does not postulate a level of Logical Form or any other representation distinct from surface syntax. One advantage of using continuations is that they are the standard tool for modeling order-of-evaluation in programming languages. This provides us with a natural and independently motivated characterization of what it means to evaluate expressions from left to right. We give a combinatory categorial grammar that models the syntax and the semantics of quantifier scope and wh-question formation. It allows quantificational binding but not crossover, in-situ wh but not superiority violations. In addition, the analysis automatically accounts for a variety of sentence types involving binding in the presence of pied piping, including reconstruction cases such as Whose criticism of hisi mother did each personi resent? (shrink)

Questions of definedness are ubiquitous in mathematics. Informally, these involve reasoning about expressions which may or may not have a value. This paper surveys work on logics in which such reasoning can be carried out directly, especially in computational contexts. It begins with a general logic of partial terms, continues with partial combinatory and lambda calculi, and concludes with an expressively rich theory of partial functions and polymorphic types, where termination of functional programs can be established in a natural way.

It is well known that the circumflex notation used by Russell and Whitehead to form complex function names in Principia Mathematica played a role in inspiring Alonzo Church's “lambda calculus” for functional logic developed in the 1920s and 1930s. Interestingly, earlier unpublished manuscripts written by Russell between 1903–1905—surely unknown to Church—contain a more extensive anticipation of the essential details of the lambda calculus. Russell also anticipated Schönfinkel's combinatory logic approach of treating multiargument functions as functions having other functions as value. (...) Russell’s work in this regard seems to have been largely inspired by Frege’s theory of functions and “value-ranges”. This system was discarded by Russell due to his abandonment of propositional functions as genuine entities as part of a new tack for solving Russell’s paradox. In this article, I explore the genesis and demise of Russell’s early anticipation of the lambda calculus. (shrink)

We document the influence on programming language semantics of the Platonism/formalism divide in the philosophy of mathematics.

Proofs from assumptions are amongst the most fundamental reasoning techniques. Yet the precise nature of assumptions is still an open topic. One of the most prominent conceptions is the placeholder view of assumptions generally associated with natural deduction for intuitionistic propositional logic. It views assumptions essentially as holes in proofs, either to be filled with closed proofs of the corresponding propositions via substitution or withdrawn as a side effect of some rule, thus in effect making them an auxiliary notion subservient (...) to proper propositions. The Curry–Howard correspondence is typically viewed as a formal counterpart of this conception. I will argue against this position and show that even though the Curry–Howard correspondence typically accommodates the placeholder view of assumptions, it is rather a matter of choice, not a necessity, and that another more assumption-friendly view can be adopted. (shrink)

Discontinuity refers to the character of many natural language constructions wherein signs differ markedly in their prosodic and semantic forms. As such it presents interesting demands on monostratal computational formalisms which aspire to descriptive adequacy. Pied piping, in particular, is argued by Pollard (1988) to motivate phrase structure-style feature percolation. In the context of categorial grammar, Bach (1981, 1984), Moortgat (1988, 1990, 1991) and others have sought to provide categorial operators suited to discontinuity. These attempts encounter certain difficulties with respect (...) to model theory and/or proof theory, difficulties which the current proposals are intended to resolve.Lambek calculus is complete for interpretation byresiduation with respect to the adjunction operation of groupoid algebras (Buszkowski 1986). In Moortgat and Morrill (1991) it is shown how to give calculi for families of categorial operators, each defined by residuation with respect to an operation of prosodic adjunction (associative, non-associative, or with interactive axioms). The present paper treats discontinuity in this way, by residuation with respect to three adjunctions: + (associative), (.,.) (split-point marking), andW (wrapping) related by the equations 1+s 2+s 3=(s 1,s 3)Ws 2. We show how the resulting methods apply to discontinuous functors, quantifier scope and quantifier scope ambiguity, pied piping, and subject and object antecedent reflexivisation. (shrink)

We define dual and symmetric combinatory calculi (inequational and equational ones), and prove their consistency. Then, we introduce algebraic and set theoretical relational and operational - semantics, and prove soundness and completeness. We analyze the relationship between these logics, and argue that inequational dual logics are the best suited to model computation.

The implicational fragment of the relevance logic "ticket entailment" is closely related to the so-called hereditary right maximal terms. I prove that the terms that need to be considered as inhabitants of the types which are theorems of $T_\rightarrow$ are in normal form and built in all but one casefrom B, B' and W only. As a tool in the proof ordered term rewriting systems are introduced. Based on the main theorem I define $FIT_\rightarrow$ - a Fitch-style calculus for the (...) implicational fragment of ticket entailment. (shrink)

A reduction rule is introduced as a transformation of proof figures in implicational classical logic. Proof figures are represented as typed terms in a -calculus with a new constant P (()). It is shown that all terms with the same type are equivalent with respect to -reduction augmented by this P-reduction rule. Hence all the proofs of the same implicational formula are equivalent. It is also shown that strong normalization fails for P-reduction. Weak normalization is shown for P-reduction with another (...) reduction rule which simplifies of (( ) ) into an atomic type. (shrink)

The structuralist conception of metaphysics holds that it aims to uncover the ultimate structure of reality and explain how the world's richness and variety are accounted for by that ultimate structure. On this conception, metaphysicians produce fundamental theories, the primitive, undefined expressions of which are supposed to 'carve reality at its joints', as it were. On this conception, ontological questions are understood as questions about what there is, where the existential quantifier 'there is' has a fundamental, joint-carving interpretation. Structuralist orthodoxy (...) holds that there is exactly one fundamental, joint-carving interpretation that an existential quantifier could have. This orthodox assumption could go wrong--either by there being too few fundamental-quantifier interpretations, or by there being too many. In this dissertation I examine the implications of these non-orthodox options. Someone who thinks there are too many fundamental-quantifier interpretations might think this means standard ontological debates are in some sense defective of 'merely verbal', or she might think instead that the different quantifiers show that there are different 'ways' or 'modes' of being. I argue that the first option runs into problems with a certain sort of realism about logic, but that there is no general problem with the second option, despite its longstanding bad philosophical reputation. I also argue that realism about logic gives us reason to think the dispute between someone who thinks there are many 'modes of being' in this sense and someone who thinks there is just one is not itself verbal. Finally, I turn to the case in which there are no fundamental quantifiers, arguing that it brings with it a host of theoretical problems we could avoid with quantifiers. (shrink)

We introduce new proof systems G[β] and G ext[β], which are equivalent to the standard equational calculi of λβ- and λβη- conversion, and which may be qualified as ‘analytic’ because it is possible to establish, by purely proof-theoretical methods, that in both of them the transitivity rule admits effective elimination. This key feature, besides its intrinsic conceptual significance, turns out to provide a common logical background to new and comparatively simple demonstrations—rooted in nice proof-theoretical properties of transitivity-free derivations—of a number (...) of well-known and central results concerning β- and βη-reduction. The latter include the Church–Rosser theorem for both reductions, the Standardization theorem for β- reduction, as well as the Normalization (Leftmost reduction) theorem and the Postponement of η-reduction theorem for βη-reduction. (shrink)