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

Taken at face value, a programming language is defined by a formal grammar. But, clearly, there is more to it. By themselves, the naked strings of the language do not determine when a program is correct relative to some specification. For this, the constructs of the language must be given some semantic content. Moreover, to be employed to generate physical computations, a programming language must have a physical implementation. How are we to conceptualize this (...) complex package? Ontologically, what kind of thing is it? In this paper, we shall argue that an appropriate conceptualization is furnished by the notion of a technical artifact. (shrink)

Paul M. Pietroski, University of Maryland I had heard it said that Chomsky’s conception of language is at odds with the truth-conditional program in semantics. Some of my friends said it so often that the point—or at least a point—finally sunk in.

Paul M. Pietroski, University of Maryland I had heard it said that Chomsky’s conception of language is at odds with the truth-conditional program in semantics. Some of my friends said it so often that the point—or at least a point—finally sunk in.

Mathematical models are an important tool in the development ofsoftware technology, including programming languages and algorithms.During the last few years, a new class of such models has beendeveloped based on the notion of a mathematical game that isespecially well-suited to address the interactions between thecomponents of a system. This paper gives an introduction to thesegame-semantical models of programming languages, concentrating onmotivating the basic intuitions and putting them into context.

This paper describes a novel pedagogical software program that can be seen as an online companion to one of the standard textbooks of formal natural language semantics, Heim and Kratzer (1998). The Penn Lambda Calculator is a multifunctional application designed for use in standard graduate and undergraduate introductions to formal semantics: Teachers can use the application to demonstrate complex semantic derivations in the classroom and modify them interactively, and students can use it to work on problem sets (...) provided by the teacher. The program supports demonstrations and exercises in two main areas: (1) performing beta reduction in the simply typed lambda calculus; (2) application of the bottom-up algorithm for computing the compositional semantics of natural language syntax trees. The program is able to represent the full range of phenomena covered in the Heim and Kratzer textbook by function application, predicate modification, and lambda abstraction. This includes phenomena such as intersective adjectives, relative clauses and quantifier raising. In the student use case, emphasis has been placed on providing “live” feedback for incorrect answers. Heuristics are used to detect the most frequent student errors and to return specific, interactive suggestions. (shrink)

In the tradition of Denotational Semantics one usually lets program constructs take their denotations in reflexive domains, i.e. in domains where self-application is possible. For the bulk of programming constructs, however, working with reflexive domains is an unnecessary complication. In this paper we shall use the domains of ordinary classical type logic to provide the semantics of a simple programming language containing choice and recursion. We prove that the rule of {\em Scott Induction\/} holds in (...) this new setting, prove soundness of a Hoare calculus relative to our semantics, give a direct calculus ${\cal C}$ on programs, and prove that the denotation of any program $P$ in our semantics is equal to the union of the denotations of all those programs $L$ such that $P$ follows from $L$ in our calculus and $L$ does not contain recursion or choice. (shrink)

The paper studies a simply typed term system Mω providing a primitive recursive concept of parallelism in the sense of Plotkin. The system aims at defining and computing partial continuous functionals. Some connections between denotational and operational semantics → for Mω are investigated. It is shown that → is correct with respect to the denotational semantics. Conversely, → is complete in the sense that if a program denotes some number k, then it is reducible to the numeral nk. (...) Restricting to the primitive recursive kernel Rω of Mω, it is shown that → is strongly normalising with uniquely determined normal forms. The twist is the design of fixed point style conversion rules for constants accounting for parallelly bounded parallel search such that correctness and strong normalisation hold. Thereupon, minor alternations to → bring about that every reduction sequence for a program of Rω terminates either in a numeral nk if the program denotes k, or in the term 0 if the program denotes the “undefined” object. Thus, Rω can be considered a primitive recursive version of Plotkin's PA+·. (shrink)

Michael Devitt is a distinguished philosopher of language. In this book he takes up one of the most important difficulties that must be faced by philosophical semantics: namely, the threat posed by holism. Three important questions lie at the core of this book: what are the main objectives of semantics; why are they worthwhile; how should we accomplish them? Devitt answers these 'methodological' questions naturalistically and explores what semantic programme arises from the answers. The approach is anti-Cartesian, (...) rejecting the idea that linguistic or conceptual competence yields any privileged access to meanings. This new methodology is used first against holism. Devitt argues for a truth-referential localism, and in the process rejects direct-reference, two-factor, and verificationist theories. The book concludes by arguing against revisionism, eliminativism, and the idea that we should ascribe narrow meanings to explain behaviour. (shrink)

Almost forty years ago Richard Montague proposed to analyse natural language with the same tools as formal languages. In particular, he gave formal semantic analyses of several interesting fragments of English in terms of typed logic. This led to the development of Montague grammar as a particular style of formal analysis of natural language.

Game semantics extends the Curry–Howard isomorphism to a three-way correspondence: proofs, programs, strategies. But the universe of strategies goes beyond intuitionistic logics and lambda calculus, to capture stateful programs. In this paper we describe a logical counterpart to this extension, in which proofs denote such strategies. The system is expressive: it contains all of the connectives of Intuitionistic Linear Logic, and first-order quantification. Use of Lairdʼs sequoid operator allows proofs with imperative behaviour to be expressed. Thus, we can embed (...) first-order Intuitionistic Linear Logic into this system, Polarized Linear Logic, and an imperative total programming language.The proof system has a tight connection with a simple game model, where games are forests of plays. Formulas are modelled as games, and proofs as history-sensitive winning strategies. We provide a strong full completeness result with respect to this model: each finitary strategy is the denotation of a unique analytic proof. Infinite strategies correspond to analytic proofs that are infinitely deep. Thus, we can normalise proofs, via the semantics. (shrink)

A volume of studies in natural language semantics which brings together work by philosophers, logicians and linguists. The main topics treated are: quantification and reference in natural language; the relations between formal logic, programming languages and natural language; pragmatics and discourse meaning; surface syntax and logical meaning. The volume derives from a colloquium organised in 1973 by the Kings College Research Centre, Cambridge and the papers have been edited for publication by Professor Keenan. It is (...) hoped that the collection will make available some of the best work in this fast-moving field and will stimulate further progress by juxtaposing the different approaches and interests represented here. (shrink)

For most of the 1980s, Jon Barwise focused much of his research in the area of natural language semantics. This article surveys his research publications in that area.Most, but not all, of those publications were in the area of situation semantics, a new approach to natural language semantics Barwise developed jointly with his colleague John Perry in the first half of the 1980s. That work was both blessed, and cursed, by becoming closely identified in academic (...) circles with the award of a $23 million gift to Stanford from the System Development Foundation for the establishment in 1983 of its Center for the Study of Language and Information. The development of situation semantics, and in due course its underlying mathematical foundation Situation Theory, carried out for the most part within the framework of CSLI's STASS research group, was actually a relatively small part of the overall research program at CSLI. But because Barwise and Perry were leading figures at CSLI, were centrally involved in securing the SDF gift, and were respectively the first and second directors of CSLI, a general impression sprung up that the two of them had been awarded millions of dollars to develop situation semantics.A major consequence of this false impression was that from the theory's early days, a great deal of interest was shown in the project. With so many accomplished scholars pouring over the work while the ink was still wet on the manuscript pages, Barwise and Perry were able to take advantage of a broad range of helpful criticism. This meant that they were able to develop the new theory much more rapidly than would otherwise have been the case. (shrink)

In a recent paper, Ferraris, Lee and Lifschitz conjectured that the concept of a stable model of a first-order formula can be used to treat some answer set programming expressions as abbreviations. We follow up on that suggestion and introduce an answer set programming language that defines the mean- ing of counting and choice by reducing these constructs to first-order formulas. For the new language, the concept of a safe program is defined, and its semantic role (...) is investigated. We compare the new language with the concept of a disjunc- tive program with aggregates introduced by Faber, Leone and Pfeifer, and discuss the possibility of implementing a frag- ment of the language by translating it into the input language of the answer set solver DLV. The language is also compared with cardinality constraint programs defined by Syrjänen. (shrink)

Just as war can be viewed as continuation of diplomacy using other means, computational semantics is continuation of logical analysis of natural language by other means. For a long time, the tool of choice for this used to be Prolog. In our recent textbook we argue (and try to demonstrate by example) that lazy functional programming is a more appropriate tool. In the talk we will lay out a program for computational semantics, by linking computational (...) class='Hi'>semantics to the general analysis of procedures for social interaction. The talk will give examples of how Haskell can be used to begin carrying out this program. (shrink)

An emerging standard for polymorphically typed, lazy, purely functional programming is Haskell, a language named after Haskell Curry. Haskell is based on (polymorphically typed) lambda calculus, which makes it an excellent tool for computational semantics.

Expressivism - the sophisticated contemporary incarnation of the noncognitivist research program of Ayer, Stevenson, and Hare - is no longer the province of metaethicists alone. Its comprehensive view about the nature of both normative language and normative thought has also recently been applied to many topics elsewhere in philosophy - including logic, probability, mental and linguistic content, knowledge, epistemic modals, belief, the a priori, and even quantifiers. Yet the semantic commitments of expressivism are still poorly understood and have not (...) been very far developed. As argued within, expressivists have not yet even managed to solve the "negation problem" - to explain why atomic normative sentences are inconsistent with their negations. As a result, it is far from clear that expressivism even could be true, let alone whether it is. Being For seeks to evaluate the semantic commitments of expressivism, by showing how an expressivist semantics would work, what it can do, and what kind of assumptions would be required, in order for it to do it. Building on a highly general understanding of the basic ideas of expressivism, it argues that expressivists can solve the negation problem - but only in one kind of way. It shows how this insight paves the way for an explanatorily powerful, constructive expressivist semantics, which solves many of what have been taken to be the deepest problems for expressivism. But it also argues that no account with these advantages can be generalized to deal with constructions like tense, modals, or binary quantifiers. Expressivism, the book argues, is coherent and interesting, but false. (shrink)

This book contains papers from a colloquium held in 1973 at Kings College, Cambridge. The contributions deal with the number of questions on which a great deal of current linguistic research and writing focus. These include the problem of quantification and reference in natural language; the application of formal logic to natural language semantics; the semantics of non-declarative sentences; the relation between natural language semantics and programming languages; the relation between sentences and their (...) contexts of use; discourse meaning; and the relation between surface syntax and logical meaning. An adequate treatment of these issues requires the interaction of a number of different linguistic approaches. As one of the contributors to the volume points out, there recently have developed three major new developments in areas of research into linguistic phenomena: transformational grammar, formal logic, and speech act theory. Although no one of these are represented singly in this volume, a number of the problems which are discussed involve issues which depend on the interfaces between these various approaches. (shrink)

This book provides a synthesis of four versions of program semantic—srelational semantics, predicate transformer semantics, information systems, and domain theory—showing, through an exhaustive case study analysis, that it is possible to do back-and-forth translation from any of these versions of program semantics into any of the others, and demonstrating that while there are many variations of each, in principle they may be thought of as intertranslatable.

This book describes computability theory and provides an extensive treatment of data structures and program correctness. It makes accessible some of the author's work on generalized recursion theory, particularly the material on the logic programming language PROLOG, which is currently of great interest. Fitting considers the relation of PROLOG logic programming to the LISP type of language.

Donald Davidson did it. He did it slowly, deliberately, in more than a half dozen widely noted essays. What he did was to elaborate a program for the study of empirical semantics. Nor did he stop there. He went on to apply his program to some of the problems that have long bedeviled semantics: action sentences, indirect discourse and propositional attitudes. My goal in this paper is to assess Davidson's achievement. The first step is to assemble the program (...) from the sketches and hints scattered among Davidson's papers. This is the project of my first section where my aim is sympathetic exposition. Since Davidson sometimes seems to be playing a game of hide and seek with his reader, my reconstruction of his program and arguments is of necessity occasionally speculative. In the second section my stance turns critical. There are anomalies in the program; the sort of theory Davidson advocates is not the sort delivered. When the problems are pushed, I think the program loses whatever initial plausibility it may have had. It is my contention that Davidson has provided no serious framework for the empirical study of natural language. (shrink)

In this short monograph, John Horty explores the difficulties presented for Gottlob Frege's semantic theory, as well as its modern descendents, by the treatment of defined expressions. The book begins by focusing on the psychological constraints governing Frege's notion of sense, or meaning, and argues that, given these constraints, even the treatment of simple stipulative definitions led Frege to important difficulties. Horty is able to suggest ways out of these difficulties that are both philosophically and logically plausible and Fregean in (...) spirit. This discussion is then connected to a number of more familiar topics, such as indexicality and the discussion of concepts in recent theories of mind and language. In the latter part of the book, after introducing a simple semantic model of senses as procedures, Horty considers the problems that definitions present for Frege's idea that the sense of an expression should mirror its grammatical structure. The requirement can be satisfied, he argues, only if defined expressions--and incomplete expressions as well--are assigned senses of their own, rather than treated contextually. He then explores one way in which these senses might be reified within the procedural model, drawing on ideas from work in the semantics of computer programming languages. With its combination of technical semantics and history of philosophy, Horty's book tackles some of the hardest questions in the philosophy of language. It should interest philosophers, logicians, and linguists. (shrink)

This essay considers what it means to understand natural language and whether a computer running an artificial-intelligence program designed to understand natural language does in fact do so. It is argued that a certain kind of semantics is needed to understand natural language, that this kind of semantics is mere symbol manipulation (i.e., syntax), and that, hence, it is available to AI systems. Recent arguments by Searle and Dretske to the effect that computers cannot understand (...) natural language are discussed, and a prototype natural-language-understanding system is presented as an illustration. (shrink)

This is a thesis in formal semantics. It consists of two parts corresponding to the distinction, due to Richard Montague, between universal grammar and specific semantic theories. The first part concerns universal grammar and is intended to provide a precise and unified conceptual framework within which different theories of formal semantics can be represented and compared. ;The second part of the thesis is concerned with intensional logic, i.e., with the logical analysis of discourse involving so called oblique contexts. (...) These contexts are characterized by the apparent failure of certain classically valid principles of substitutivity. Two kinds of reactions among logicians to the appearance of oblique contexts in natural languages are distinguished: (1) the intensional point of view, according to which oblique contexts are seen as genuine counterexamples to classical logic and to the related semantical principle of extensionality: the principle that the denotation of an expression is a function of the denotations of its parts; and (2) the extensional point of view, according to which the conflict between oblique contexts and classical logic is only apparent. The extensional point of view therefore calls for analyses of oblique contexts that preserve the laws of classical logic and the principle of extensionality. In this thesis, we are concerned with the precise formulation of and comparison between different programs for the formal semantic representation of oblique contexts. In Chapter 5, we are concerned with Church's program of representing oblique contexts within a formal language whose semantics is fully extensional and based on Frege's distinction between sense and denotation. The ambiguity between the "direct" and "indirect" denotation of an expression A is avoided by letting A be replaced in oblique contexts by an expression which denotes A's ordinary sense. We provide a possible-worlds semantics for a version of Church's formal language with the following features: (i) Objectual quantification into oblique constructions is accounted for. The treatment of quantification requires for each entity x an essence of x, by which we mean a sense which determines x in those worlds in which x exists and is undefined in all other worlds. (ii) The variables range over actually existing entities only. It is allowed that entities of certain types are contingent, i.e., the same entity may exist in one world and fail to exist in other worlds. (iii) In order to combine a proper treatment of the cross-world identification of functions with varying domains, partial functions are allowed. (iv) Senses are allowed to be partially defined. For example, the sense of a proper name is undefined in a world in which the denotation of the name does not exist. (v) Senses of functions from objects of type a to objects of type b are identified with functions from senses of objects of type a to senses of objects of type b. In Chapters 6 and 7, we pursue the Russellian Alternative in intensional semantics, where a sense/denotation distinction is avoided. Apparent failures of substitutivity principles for singular terms are explained along the lines of Russell's theory of definite descriptions. Failures of substitutivity of coextensional sentences and predicates are explained by Russell's doctrine that sentences and predicate denote propositions and propositional functions , respectively. Russellian semantics is fully extensional in the sense that the Russellian denotation of a designator is a function of the Russellian denotations of its parts. In Chapter 6, a theory of Russellian propositions is developed within set theory. This theory is then applied in Chapter 7 to the task of providing a set-theoretic semantics for Russellian type theory. (shrink)

What makes our utterances mean what they do? In this work I formulate and justify a structural constraint on possible answers to this key question in the philosophy of language, and I show that accepting this constraint leads naturally to the adoption of an algebraic formalization of truth-theoretic semantics. I develop such a formalization, and show that applying algebraic methodology to the theory of meaning yields important insights into the nature of language. ;The constraint I propose is, (...) roughly, this: the meaning of an utterance of a natural language sentence is derived from the place of that sentence within a system that includes other sentences, and is structured in virtue of primitive semantic facts about complete sentences. This constraint calls for a formal semantics program where the meaning of natural language sentences is represented by an appropriate assignment of the elements of an algebraic structure to sentences, an assignment that represents facts concerning complete sentences. I call the above constraint 'The Algebraic Thesis', and the corresponding formal semantics program 'Algebraic Semantics.' ;I introduce AT by carving it out of the holistic views of language of Quine and Davidson, and I show that it is independent of other important features of these philosophers' views. I then argue for AT, taking into account recent work by Brandom, Dummett, Fodor and Lepore, Gaifman and Perry. In developing Algebraic Semantics I present structures of two basic types: Boolean algebras and cylindric algebras; these structures are construed in the context of AT in a novel way: they are treated as applying to classes of sentences as numbers apply to physical objects in measurement. Applying algebraic methodology to formal semantics and to the theory of meaning, I develop these results: ; An account of the semantics of necessity and possibility that avoids both Quine's dismissal of these notions and their reduction by David Lewis to quantification over possible worlds; ; The application of the model-theoretic notion of expansion to capture the process of our learning progressively more of the meaning of expressions in our first languages. (shrink)

Algorithms for NLG NLG is typically broken down into stages of discourse planning (to select information and organize it into coherent paragraphs), sentence planning (to choose words and structures to fit information into sentence-sized units), and realization (to determine surface form of output, including word order, morphology and final formatting or intonation). The SPUD system combines the generation steps of sentence planning and surface realization by using a lexicalized grammar to construct the syntax and semantics of a sentence simultaneously.

Bilattices, introduced by M. Ginsberg, constitute an elegant family of multiple-valued logics. Those meeting certain natural conditions have provided the basis for the semantics of a family of logic programming languages. Now we consider further restrictions on bilattices, to narrow things down to logic programming languages that can, at least in principle, be implemented. Appropriate bilattice background information is presented, so the paper is relatively self-contained.

We present a logic programming language, which we call Proflog, with an operational semantics based on tableaus, and a denotational semantics based on supervaluations. We show the two agree. Negation is well-behaved, and semantic non-computability issues do not arise. This is accomplished essentially by dropping a domain closure requirement. The cost is that intuitions developed through the use of classical logic may need modification, though the system is still classical at a level once removed. Implementation problems (...) are discussed very briefly — the thrust of the paper is primarily theoretical. (shrink)

We introduce a game model for an Algol-like programming language with primitives for parallel composition and synchronization on semaphores. The semantics is based on a simplified version of Hyland–Ong-style games and it emphasizes the intuitive connection between the concurrent nature of games and that of computation. The model is fully abstract for may-equivalence.

In this paper we systematically derive a predicate transformer semantics from a direct semantics for a simple probabilistic-nondeterministic programming language . This goal is achieved by exhibiting the direct semantics as isomorphic to a continuation semantics from which the predicate transformer semantics can be read off immediately. This isomorphism allows one to identify nonempty convex compact saturated sets of valuations on the set S of states with certain “good” functionals from to in a (...) way similar to the one how H. Minkowski in 1903 related nonempty convex compact subsets of to what is nowadays called Minkowski functionals. (shrink)

A number of general points behind the story of this paper may be worth setting out separately, now that we have come to the end.There is perhaps one obvious omission to be addressed right away. Although the word “information” has occurred throughout this paper, it must have struck the reader that we have had nothing to say on what information is. In this respect, our theories may be like those in physics: which do not explain what “energy” is (a notion (...) which seems quite similar to “information” in several ways), but only give some basic laws about its behaviour and transmission.The eventual recommendation made here has been to use a broad type-theoretic framework for studying various more classical and more dynamic notions of proposition in their interaction. This is not quite the viewpoint advocated by many current authors in the area, who argue for a whole-sale switch from a ‘static’ to a ‘dynamic’ perspective on propositions. This is not the place, however, to survey the conceptual arguments for and against such a more radical move.This still leaves many questions about possible reductions from one perspective to another. For instance, it would seem that classical systems ought to serve as a ‘limiting case’, which should still be valid after procedural details of some cognitive process have been forgotten. There are various ways of implementing the desired correspondence: e.g. by considering extreme cases with ⫅ equal to identity, or, in the pure relational algebra framework by considering only pairs (x, x). What we shall want then are reductions of dynamic logics, in those special cases, to classical logic. But perhaps also, more sophisticated views are possible. How do we take a piece of ‘dynamic’ prose, remove control instructions and the like, and obtain a piece of ‘classical’ text, suitable for inference ‘in the light of eternity’?There is also a more technical side to the matter of ‘reduction’. By now, Logic has reached such a state of ‘inter-translatability’ that almost all known variant logics can be embedded into each other, via suitable translations. In particular, once an adequate semantic has been given for a new system, this usually induces an embedding into standard logic: as we know, e.g., for the case of Modal Logic. Like-wise, all systems of dynamic interpretation or inference proposed so far admit of direct embedding into an ordinary ‘static’ predicate logic having explicit transition predicates (cf. van Benthem 1988b). Thus, our moral is this. The issue is not whether the new systems of information structure or processing are essentially beyond the expressive resources of traditional logical systems: for, they are not. The issue is rather which interesting phenomena and questions will be put into the right focus by them.The next broad issue concerns the specific use of the perspective proposed here, vis-à-vis concrete proposals for information-oriented or dynamic semantics. The general strategy advocated here is to locate some suitable base calculus and then consider which ‘extras’ are peculiar to the proposal. For instance, this is the spirit in which modal S4 would be a base logic of information models, and intuitionistic logicthe special theory devoting itself to upward persistent propositions. Or, with the examples in Section 4.1, the underlying base logic is our relational algebra, whereas, say, ordinary updates then impose special properties, such as ‘idempotence’: $$xRy \Rightarrow yRy$$ Does this kind of application presuppose the existence of one distinguished base logic, of which all others are extensions? This would be attractive-and some form of relational algebra or linear logic might be a reasonable candidate. Nevertheless, the enterprise does not rest on this outcome. What matters is an increased sensitivity to the ‘landscape’ of dynamic logics, just as with the ‘Categorial Hierarchy’ in Categorial Grammar (cf. van Benthem 1989a, 1991) where the family of logics with their interconnections seems more important than any specific patriarch.Finally, perhaps the most important issue in the new framework is the possibility of new kinds of questions arising precisely because of its differences from standard logic. Notably, given the option of regarding propositions as programs, it will be of interest to consider systematically which major questions about programming languages now make sense inside logic too.EXAMPLE. Correctness. When do we have $$\left[\kern-0.15em\left[ \pi \right]\kern-0.15em\right](\left[\kern-0.15em\left[ A \right]\kern-0.15em\right]) \subseteq \left[\kern-0.15em\left[ B \right]\kern-0.15em\right]$$ for (s, t) propositions A, B and a dynamic (s, (s, t)) proposition π?Program Synthesis. Which dynamic proposition will take us from an information state satisfying A to one satisfying B? (This question needs refinement, lest there be trivial answers.)Determinism. Which propositions as programs are deterministic, in the sense of defining single-valued functions from states to states?Querying. What does it mean to ask for information in the present setting? (Again, individual types referring to e will be crucial here.)This is not merely an agenda for wishful thinking. Within Logic, there are various ways of introducing such concerns into semantics, especially, using tools from Automata Theory. (See van Benthem 1989c for further discussion of such computational perspectives in ‘cognitive programming’.)At least if one believes that ‘dynamics’ is of the essence in cognition (rather than a mere interfacing problem between the halls of eternal truth and the noisy streets of reality), the true test for the present enterprise is the development of a significant new research program not merely copying the questions of old. (shrink)

A free logic is one in which a singular term can fail to refer to an existent object, for example, `Vulcan' or `5/0'. This essay demonstrates the fruitfulness of a version of this non-classical logic of terms (negative free logic) by showing (1) how it can be used not only to repair a looming inconsistency in Quine's theory of predication, the most influential semantical theory in contemporary philosophical logic, but also (2) how Beeson, Farmer and Feferman, among others, use it (...) to provide a natural foundation for partial functions in programming languages. Vis à vis (2), the question is raised whether the Beeson-Farmer-Feferman approach is adequate to the treatment of partial functions in all programming languages. Gumb and the author say No, and suggest a way of handling the refractory cases by means of positive free logic. Finally, Antonelli's solution of a problem associated with the Gumb-Lambert proposal is mentioned. (shrink)

J. L. Austin, in "Ifs and Cans," proclaimed the common hope that we soon "may see the birth, through the joint labors of philosophers, grammarians, and numerous other students of language, of a true and comprehensive science of language." The problem has always been with the "joint labors" part. Philosophers have always been willing to issue linguists dictums and linguists have been happy to teach philosophers "plain facts." Austin’s general view of language, and his particular notion of (...) performative utterance, can be found in the writing of J. R. Firth, the most commanding British linguist of Austin’s generation, but Austin never refers to Firth. In the present volume, however, we find clear and exciting evidence of genuinely joint labors on the part of philosophers and linguists. They stem from a summer conference in 1969 rounded out with contributions from notables. To two thick issues of Synthese the editors have added a dazzling piece by Saul Kripke, two substantial pieces by James McCawley and J. R. Ross, a short paper by Paul Ziff, and a reprint of P. F. Strawson’s "Grammar and Philosophy." This is an invaluable book and the best book among the many now available concerning the interaction of linguistics and philosophy: worth the cost, which the contributors attempted to reduce through foregoing royalties. The philosophers in this volume hold, or hold intriguing, the view that the semantics of a natural language can and must, in effect, be a theory of truth for a language in much the manner that Tarski suggested, and provided, for artificial language: the recursive specification of biconditionals in which the left hand gives the structural description of an object language sentence and the right hand, the truth conditions in the metalanguage. In "homophonic" translation this requirement can be trivially satisfied simply by mentioning the sentence on the left that one uses on the right: one makes the requirement non-trivial by forcing enough into the recursive specification so that one captures the native speaker’s implicit semantic competence. In this volume, the "orthodox" Davidsonian program, which takes the syntax of the metalanguage to be standard predicate logic, is ably argued by John Wallace ; Richard Montague, David Lewis, and Jaakko Hintikka would want an intensional logic covering modality and propositional attitudes. The linguists who find this philosophical climate most appealing are called "generative semanticists": McCawley, Ross, George Lakoff and others argue that any proposed semantic rule will eventually prove necessary to syntax too and that, hence, the deepest level of syntactical form will be equivalent to semantic form. Whatever the ultimate fate of this joint program, it leads here to much exciting interaction between linguists and philosophers: linguists who welcome the machinery and conceptual standards of modern logic, and philosophers who try to grasp the specifics of crucial issues in recent linguistic theory. Even if Quine’s doubts, here sketched, and Chomsky’s currently unpublished more technical objections should be well-founded, nonetheless the joint labor will have been very much worthwhile. Aside from this general debate about semantics, there are several papers covering more specific issues. The papers of J. A. Fodor, Terence Parsons, and Ross concern adverbs and the logical form of action sentences; several papers, particularly B. H. Partee’s, examine "Opacity, Coreference, and Pronouns." In all these papers one notes the fulfillment of Austin’s hope that philosophic and linguistic arguments should become intermixed, if not at times properly indistinguishable. Perhaps the most enjoyable and exciting paper stands aside from linguistics: Saul Kripke’s "Naming and Necessity." Kripke here argues quite informally for the separation of analytic, a priori, and necessary that is required for a Kripke style, S5, modal logic with de re modalities. "Gold is a yellow metal," for example, turns out to be contingent, while "Heat is the motion of particles" is necessary but a posteriori ; and that philosopher’s stone of stones, "The morning star is the evening star," is discovered to be necessary but a posteriori.—J. L. (shrink)

From a leading authority in artificial intelligence, this book delivers a synthesis of the major modern techniques and the most current research in natural language processing. The approach is unique in its coverage of semantic interpretation and discourse alongside the foundational material in syntactic processing.

This text/courseware package presents a new approach to teaching first-order logic. Taking advantage of Tarski's World 4.0, the text skilfully balances the semantic conception of logic with methods of proof. The book contains eleven chapters, in four parts. Part I is about propositional logic, Part II about quantifier logic. Part III contains chapters on set theory and inductive definitions. Part IV contains advanced topics in logic, including topics of importance in applications of logic in computer science. The Language of (...) First-order Logic contains hundreds of problems and exercises for the user to work through. (shrink)

ABSTRACT Inspired by legal reasoning, this paper presents a semantics and proof theory of a system for defeasible argumentation. Arguments are expressed in a logic-programming language with both weak and strong negation, conflicts between arguments are decided with the help of priorities on the rules. An important feature of the system is that these priorities are not fixed, but are themselves defeasibly derived as conclusions within the system. Thus debates on the choice between conflicting arguments can also (...) be modelled. The semantics of the system is given with a fixpoint definition, while its proof theory is stated in dialectical style, where a proof takes the form of a dialogue between a proponent and an opponent of an argument: an argument is shown to be justified if the proponent can make the opponent run out of moves in whatever way the opponent attacks. (shrink)

In this paper we propoee a logic programming language which supports hypothetical updates together with integrity constraints. The language makes use of a revision mechanism, which is needed to restore consistency when an update violates some integrity constraint. The revision policy adopted is based on the simple idea that more recent information is preferred to earlier one. We show how this language can be used to represent and perform several types of defeasible reasoning. We develop a (...) logical characterization of the language in a three-valued conditional logic, by introducing a completion construction. We show that the operational semantics is sound and complete with respect to the completion construction. (shrink)

Chomsky’s (1995, 2000a) Minimalist Program (MP) invites a perspective on semantics that is distinctive and attractive. In section one, I discuss a general idea that many theorists should find congenial: the spoken or signed languages that human children naturally acquire and use— henceforth, human languages—are biologically implemented procedures that generate expressions, whose meanings are recursively combinable instructions to build concepts that reflect a minimal interface between the Human Faculty of Language (HFL) and other cognitive systems. In sections two (...) and three, I develop this picture in the spirit of MP, in part by asking how much of the standard Frege-Tarski apparatus is needed in order to provide adequate and illuminating descriptions of the “concept assembly instructions” that human languages can generate. I’ll suggest that we can make do with relatively little, by treating all phrasal meanings as instructions to assemble number-neutral concepts that are monadic and conjunctive. But the goal is not to legislate what counts as minimal in semantics. Rather, by pursuing one line of Minimalist thought, I hope to show how such thinking can be fruitful. (shrink)

We construct logical languages which allow one to represent a variety of possible types of changes affecting the information states of agents in a multi-agent setting. We formalize these changes by defining a notion of epistemic program. The languages are two-sorted sets that contain not only sentences but also actions or programs. This is as in dynamic logic, and indeed our languages are not significantly more complicated than dynamic logics. But the semantics is more complicated. In general, the (...) class='Hi'>semantics of an epistemic program is what we call aprogram model. This is a Kripke model of ‘actions’,representing the agents' uncertainty about the current action in a similar way that Kripke models of ‘states’ are commonly used in epistemic logic to represent the agents' uncertainty about the current state of the system. Program models induce changes affecting agents' information, which we represent as changes of the state model, called epistemic updates. Formally, an update consists of two operations: the first is called the update map, and it takes every state model to another state model, called the updated model; the second gives, for each input state model, a transition relation between the states of that model and the states of the updated model. Each variety of epistemic actions, such as public announcements or completely private announcements to groups, gives what we call an action signature, and then each family of action signatures gives a logical language. The construction of these languages is the main topic of this paper. We also mention the systems that capture the valid sentences of our logics. But we defer to a separate paper the completeness proof. (shrink)

A wide-ranging history of the intellectual developments that produced the modern idea of the algorithm. Bringing together the histories of mathematics, computer science, and linguistic thought, Language and the Rise of the Algorithm reveals how recent developments in artificial intelligence are reopening an issue that troubled mathematicians long before the computer age. How do you draw the line between computational rules and the complexities of making systems comprehensible to people? Here Jeffrey M. Binder offers a compelling tour of four (...) visions of universal computation that addressed this issue in very different ways: G. W. Leibniz's calculus ratiocinator; a universal algebra scheme Nicolas de Condorcet designed during the French Revolution; George Boole's nineteenth-century logic system; and the early programming language ALGOL, whose name is short for algorithmic language. These episodes show that symbolic computation has repeatedly become entangled in debates about the nature of communication. To what extent can meaning be controlled by individuals, like the values of a and b in algebra, and to what extent is meaning inevitably social? By attending to this long-neglected question, we come to see that the modern idea of the algorithm is implicated in a long history of attempts to maintain a disciplinary boundary separating technical knowledge from the languages people speak day to day. Machine learning, in its increasing dependence on words, now places this boundary in jeopardy, making its stakes all the more urgent to understand. The idea of the algorithm is a levee holding back the social complexity of language, and it is about to break. This book is about the flood that inspired its construction. (shrink)

Computer software is written in languages like C, Java or Haskell. In many cases social software is expressed in natural language. The paper explores connections between the areas of natural language analysis and analysis of social protocols, and proposes an extended program for natural language semantics, where the goals of natural language communication are derived from the demands of specific social protocols.

The foundations of AI design discourse are worth analyzing. Here, attention is paid to the nature of theory languages used in designing new AI technologies because the limits of these languages can clarify some fundamental questions in the development of AI. We discuss three types of theory language used in designing AI products: formal, computational, and natural. Formal languages, such as mathematics, logic, and programming languages, have fixed meanings and no actual-world semantics. They are context- and practically (...) content-free. Computational languages use terms referring to the actual world, i.e., to entities, events, and thoughts. Thus, computational languages have actual-world references and semantics. They are thus no longer context- or content-free. However, computational languages always have fixed meanings and, for this reason, limited domains of reference. Finally, unlike formal and computational languages, natural languages are creative, dynamic, and productive. Consequently, they can refer to an unlimited number of objects and their attributes in an unlimited number of domains. The differences between the three theory languages enable us to reflect on the traditional problems of strong and weak AI. (shrink)

Miller, D., G. Nadathur, F. Pfenning and A. Scedrov, Uniform proofs as a foundation for logic programming, Annals of Pure and Applied Logic 51 125–157. A proof-theoretic characterization of logical languages that form suitable bases for Prolog-like programming languages is provided. This characterization is based on the principle that the declarative meaning of a logic program, provided by provability in a logical system, should coincide with its operational meaning, provided by interpreting logical connectives as simple and fixed search (...) instructions. The operational semantics is formalized by the identification of a class of cut-free sequent proofs called uniform proofs. A uniform proof is one that can be found by a goal-directed search that respects the interpretation of the logical connectives as search instructions. The concept of a uniform proof is used to define the notion of an abstract logic programming language, and it is shown that first-order and higher-order Horn clauses with classical provability are examples of such a language. Horn clauses are then generalized to hereditary Harrop formulas and it is shown that first-order and higher-order versions of this new class of formulas are also abstract logic programming languages if the inference rules are those of either intuitionistic or minimal logic. The programming language significance of the various generalizations to first-order Horn clauses is briefly discussed. (shrink)

We introduce _Interleave-Disjunction-Lock parallel multiple context-free grammars_ (IDL-PMCFG), a novel grammar formalism designed to describe the syntax of free word order languages that allow for extensive interleaving of grammatical constituents. Though interleaved constituents, and especially the so-called hyperbaton, are common in several ancient (Classical Latin and Greek, Sanskrit...) and modern (Hungarian, Finnish...) languages, these syntactic structures are often difficult to express in existing formalisms. The IDL-PMCFG formalism combines Seki et al.’s parallel multiple context-free grammars (PMCFG) with Nederhof and Satta’s IDL (...) expressions. We define the semantics of IDL-PMCFGs and study their expressivity, proving that IDL-PMCFG extends both PMCFG and IDL-CFG (context-free grammars equipped with IDL expressions) and that IDL-PMCFG parsing is \(\mathrm {NP}\) -hard. We then introduce COMPĀ, a programming language extending Ranta’s Grammatical Framework (GF) and built as a high-level front-end formalism to IDL-PMCFG for practical grammar development. We present a parsing algorithm for IDL-PMCFG inspired by earlier Earley-style PMCFG parsing algorithms and Nederhof and Satta’s IDL graphs and give a worst-case estimate of its complexity as a function of several metrics on IDL expressions, the size of the input and a new notion of the _G_-density of a language. (shrink)

Language in Action demonstrates the viability of mathematical research into the foundations of categorial grammar, a topic at the border between logic and linguistics. Since its initial publication it has become the classic work in the foundations of categorial grammar. A new introduction to this paperback edition updates the open research problems and records relevant results through pointers to the literature. Van Benthem presents the categorial processing of syntax and semantics as a central component in a more general (...) dynamic logic of information flow, in tune with computational developments in artificial intelligence and cognitive science. Using the paradigm of categorial grammar, he describes the substructural logics driving the dynamics of natural language syntax and semantics. This is a general type-theoretic approach that lends itself easily to proof-theoretic and semantic studies in tandem with standard logic. The emphasis is on a broad landscape of substructural categorial logics and their proof-theoretical and semantic peculiarities. This provides a systematic theory for natural language understanding, admitting of significant mathematical results. Moreover, the theory makes possible dynamic interpretations that view natural languages as programming formalisms for various cognitive activities. (shrink)

The article discusses the reasons why modern formal semantics of natural language is an integral part of a larger philosophical research program for the study of the nature of intentionality. The purpose of this article is to show how research in the field of formal semantics of natural language became the implementation of a large philosophical research program that is focused on the nature of intentional objects, which since the time of F. Brentano have been considered (...) an integral part of mental phenomena. Mental phenomena are opposed to physical phenomena due to their inherent intentionality. In modern philosophy, it is commonly considered that the comprehension of the nature of intentionality is the key to understanding the nature of consciousness, and, consequently, the nature of man. The article shows that formal semantics represents the structure of the meaning of linguistic expressions, with the help of which human thought is formed, which is one of the main objects of intentional consciousness. In formal semantics, this representation is carried out in a rigorous, systematic, and empirically verifiable way on the basis of natural languages, that is, on those symbolic systems that real people use in real practice to shape their thoughts. The research is based on the works of G. Frege, who laid the foundation for the formal-semantic methodology. Thus, the answer is given to the question of why modern formal linguistics, which originates in the analytical philosophy of the 20th century, is a philosophically significant discipline. This response is a reaction to the objections of skeptics who believe that modern analytic philosophy cannot be considered a direction that has any serious philosophical significance. (shrink)