Learning Logic and Grammar

November 23, 2001, 9.00h --- 18.00h
P.C. Hoofthuis
Spuistraat 134, Amsterdam
Room 605
On Friday, November 2001, a workshop "Learning Logic and Grammar" is held in Amsterdam. The aim of the workshop is to find and establish cross-connections between the OTS (Utrecht) and ILLC (Amsterdam) research groups.

Preliminary Program



The EMILE Grammar Inducer

Pieter Adriaans and Marco Vervoort

(Marco's part:) This talk will be about the EMILE program, a program designed to infere the grammar of a language from a sample of sentences, using the concept of characteristic expressions and contexts. I will explain the concepts behind the program, and sketch some of the basic algorithms.

Back to Top

Intrinsic Complexity

Christophe Costa Florencio

Quite recently a new approach to the study of "intrinsic" complexity of learning has emerged in the work of Freivalds. Freivalds, Kinber and Smith applied this notion to function identification, Jain and Sharma applied it to language learning. Instead of considering the behavior of the learning algorithm, this approach uses the notion of reducibility to investigate the complexity of the concept classes being learned. I will discuss the weak and strong versions of this notion, hardness and completeness, results for pattern languages, self-referential languages and convex hulls, and structural properties of the induced hierarchy of classes.

Back to Top

Complexity of Type Logical Grammar

Richard Moot

Many different structural rules have been proposed for giving a description of linguistic phenomena using the multimodal Lambek calculus.
We will show that if we restrict the structural rules to those which are non-expanding, in the sense that no information is added in the consequent of a rule, the decision procedure for the multimodal Lambek calculus is PSPACE complete.

Back to Top

Implementation of Hybrid Logic

Carlos Areces and Juan Heguiabehere

Many examples show that "hybridization" (the addition of nominals and satisfiability operators to a base logic) has important effects. To start with, it usually enhances the expressive power of the logic, in many cases without modifying the complexity of its satisfiability problem. But perhaps more importantly, it improves the "behavior" of the logic, both proof- and model-theoretically.
In this talk, we will discuss how we can devise a simple resolution system for a very expressive hybrid logic: H(@,\downarrow). While the satisfiability problem for this logic is undecidable, the system can effectively decide satisfiability of the languages for basic modal and hybrid logics which live as subsystems inside H(@,\downarrow).
We have implemented this resolution system in Haskell. And the first prototype, which we call HyLoRes, is up and running. We will discuss how HyLoRes implements a version of the classical "given clause" algorithm for resolution, which is today the standard algorithm in first order theorem proving. The prototype is, by no means, competitive but it already shows some of the main characteristics of the system: on-the-fly transformation to clausal form, controlled firing of rules, paramodulation for handling nominal equality, etc.
We will present details on how HyLoRes has been evolving, and how the changes affected its performance. We will discuss our choices on architecture and data types. We will also comment on what has still *not* been done. Which are the theoretical issues (like ordered hybrid resolution, universal modalities, etc.) that we are investigating now? And how will HyLoRes be extended in the coming months?

Back to Top

Quantification and Reference in Dynamic Semantics

Jan van Eijck

The talk sketches a very simple framework for dynamic semantics in polymorphic type theory. This semantic framework fits any reasonable (categorial) approach to syntax. It is demonstrated how static and dynamic generalized quantification and references to individuals and groups are treated in this framework.
Note: this is joint work, in part, with Rick Nouwen (Uil-OTS).

Back to Top

Dynamic Interpretation in a Categorial Framework

Paul Dekker

In my talk I will discuss some (not fully satisfactory) attempts to generalize Jacobson's binding mechanisms in a variable free categorial grammar. I will first discuss some of the limitations of her own approach and next discuss some alternative treatments. Inspired by a certain parallel with systems of dynamic semantics I will next sketch some ways of formulating dynamic binding in a categorial style. This part of the talk serves as a leg up for Gert's propopsal.

Back to Top

Anaphora and Indefinites in Type Logical Grammar

Gerhard Jäger

We propose to extend the Lambek calculus with two additional implications, where the first one models anaphora and the second one indefiniteness. Both pronouns and indefinites are interpreted as identity functions, but they give rise to different types and are thus subject to different interpretation strategies. This leads to a straightforward surface compositional analysis of scopal behavior of indefinites and of Sluicing.

Back to Top

Polarity Items in Type Logical Grammar. Connection with DMG

Raffaella Bernardi and Oystein Nilsen

In the talk we will show how categorial type logic (CTL) can contribute to the study of linguistic typologies, and how this application sheds light on the different roles of binary vs. unary operators in the analysis of linguistic phenomena.
In particular, we will use the base logic studied in [Areces, Bernardi, Moortgat 01] to elucidate the typology of Greek polarity items (PIs) discussed in [Giannakidou 97] and compare it with Italian data and types.
The derivability patters which govern residuated and Galois connected operators are used to encode semantic features which determine polarity distribution. These derivations among types (i) encode subset relations among items of the same syntactic category which differ for some semantic features, and (ii) help clarify cross-linguistic differences.
Finally, the application of this logic to the analysis of PIs sheds light on a possible connection between dynamic Montague grammar (DMG) and CTL giving new intuitions about the interpretations of the unary operators.

Back to Top

Why Meaning is Essentially Nonmonotonic

Michiel van Lambalgen

Back to Top