Search

Two of the main motivations for logic and (model-theoretic) semantics overlap in the sense that both subjects are concerned with representing features of natural language meaning and inference. At the same time, the two subjects have other motivations and so are largely separate enterprises. This paper returns to the topic of language and logic, presenting to semanticists natural logic, the study of logics for reasoning with sentences close to their surface form. My goal is to show that the subject already has some results that natural language semanticists might find interesting. At the same time it leads to problems and perspectives that I hope will interest the community. One leading idea is that the target logics for translations should have a decidable validity problem, ruling out first-order logic. I also will present a fairly new result based on the transitivity of comparative adjective phrases that suggests that in addition to `meaning postulates΄ in semantics, we will also need to posit `proof principles΄. [ABSTRACT FROM AUTHOR]

Final coalgebras for a functor serve as semantic domains for state based systems of various types. For example, formal languages, streams, non-well-founded sets and behaviors of CCS processes form final coalgebras. We present a uniform account of the semantics of recursive definitions in final coalgebras by combining two ideas: (1) final coalgebras are also initial completely iterative algebras (cia); (2) additional algebraic operations on final coalgebras may be presented in terms of a distributive lawλ. We first show that a distributive law leads to new extended cia structures on the final coalgebra. Then we formalize recursive function definitions involving operations given by λ as recursive program schemes for λ, and we prove that unique solutions exist in the extended cias. We illustrate our results by the four concrete final coalgebras mentioned above, e. g., a finite stream circuit defines a unique stream function and we show how to define new process combinators from given ones by sos rules involving recursion. [ABSTRACT FROM AUTHOR]

This paper is a contribution to natural logic, the study of logical systems for linguistic reasoning. We construct a system with the following properties: its syntax is closer to that of a natural language than is first-order logic; it can faithfully represent simple sentences with standard quantifiers, subject relative clauses (a recursive construct), and negation on nouns and verbs. We also give a proof system which is complete and has the finite model property. We go further by adding comparative adjective phrases, assuming interpretations by transitive relations. This last system has all the previously-mentioned properties as well. The paper was written for theoretical computer scientists and logicians interested in areas such as decidability questions for fragments of first-order logic, modal logic, and natural deduction. [ABSTRACT FROM AUTHOR]

The goal of natural logic is to present and study logical systems for reasoning with sentences of (or which are reasonably close to) ordinary language. This paper explores simple systems of natural logic which make use of intersecting adjectives; these are adjectives whose interpretation does not vary with the noun they modify. Our project in this paper is to take one of the simplest syllogistic fragments, that of all and some, and to add intersecting adjectives. There are two ways to do this, depending on whether one allows iteration or prefers a ˵flat″ structure of at most one adjective. We present rules of inference for both types of syntax, and these differ. The main results are four completeness theorems: for each of the two types of syntax we have completeness for the all fragment and for the full language of this paper. [ABSTRACT FROM AUTHOR]

This paper studies uniformity conditions for endofunctors on sets following Aczel [1], Turi [21], and others. The "usual" functors on sets are uniform in our sense, and assuming the Anti-Foundation Axiom AFA, a uniform functor H has the property that its greatest fixed point H* is a final coalgebra whose structure is the identity map. We propose a notion of uniformity whose definition involves notions from recent work in coalgebraic recursion theory: completely iterative monads and completely iterative algebras (cias). Among our new results is one which states that for a uniform H, the entire set-theoretic universe V is a cia: the structure is the inclusion of HV into the universe V itself. [ABSTRACT FROM AUTHOR]

This paper provides a general account of the notion of recursive program schemes, their uninterpreted and interpreted solutions, and related concepts. It can be regarded as the category-theoretic version of the classical area of algebraic semantics. The overall assumptions needed are small indeed: working only in categories with "enough final coalgebras" we show how to formulate, solve, and study recursive program schemes. Our general theory is algebraic and so avoids using ordered, or metric structures. Our work generalizes the previous approaches which do use this extra structure by isolating the key concepts needed to study recursion, e. g., substitution in infinite trees, including second-order substitution. As special cases of our interpreted solutions we obtain the usual denotational semantics using complete partial orders, and the one using complete metric spaces. Our theory also encompasses implicitly defined objects which are not usually taken to be related to recursive program schemes at all. For example, the classical Cantor two-thirds set falls out as an interpreted solution (in our sense) of a recursive program scheme. In this short version of our paper we can only sketch some proofs. [ABSTRACT FROM AUTHOR]

We consider the semantics of algebraic specifications viewed as evolving rather than static entities. This leads to a relativization of final algebra semantics with respect to the space of evolutionary possibilities open to a given specification. The evolutionary space itself, which we call a language, has significant semantic content. The unit of application for our semantics is such a language of specifications. We formalize relevant notions of languages and language models and derive conditions to establish the existence of a final object in the category of models for a language. The results can be used to broaden the applicability of final algebra semantics and to fine tune the balance between the desired strength of semantically valid assertions and the range of evolutionary possibilities to be considered. [ABSTRACT FROM AUTHOR]

This talk describes work on one of the first applications of algebra to theoretical computer science, the study of recursive program schemes. I would like to put a lot of the past work in perspective and then to describe recent work by Stefan Milius and myself which reworks the classical theory of uninterpreted and interpreted recursive program schemes using tools from coalgebraic recursion theory. Finally, I hope to speculate on whether the new work could be of interest to those pursuing AMAST's goal of "setting of software technology on a firm, mathematical basis." [ABSTRACT FROM AUTHOR]