FG-2006

Maxime Amblard

We propose an extension of Stabler's version of clitics treatment for a wider coverage of the french language. For this, we will present the lexical entries needed in the lexicon. Then, we will show the recognition of complex syntactic phenomena as (left and right) dislocation, clitic climbing over modal and extraction from determiner phrase. The main goal of this presentation is the syntax-semantic interface for clitics analyses in which we will stress on clitic climbing over verb and control verb.

Logical Grammar with Emptiness

Houda Anoun and Alain Lecomte

The purpose of this paper is to show that we can work in the spirit of Minimalist Grammars by means of an undirected deductive system called LGE, enhanced with constraints on the use of assumptions. Lexical entries can be linked to sequences of controlled hypotheses which represent intermediary sites. These assumptions must be introduced in the derivation and then discharged in tandem by their proper entry which will therefore manage to find its final position: this allows to logically simulate move operation. Relevance of this formalism will be stressed by showing its ability to analyze difficult linguistic phenomena in a neat fashion.

P-TIME Decidability of NL! with Assumptions

Maria Bulinska

Buszkowski (2005) showed that all Nonassociative Lambek Calculus with finitely many nonlogical axioms are decidable in polynomial time and generate context-free languages. The same holds for systems with unary modalities, studied in Moortgat (1997), n-ary operations, and the rule of permutation, studied in Jager(2002). The polynomial time decidability for Classical Nonassociative Lambek Calculus was established by de Groote and Lamarche (2002).

We study Nonassociative Lambek Calculus with identity enriched with a finite set of assumptions. To prove that this system is decidable in polynomial time we adapt the method used by Buszkowski (2005). The modification is essential. The novelty is the lemma about the elimination of cut rules with premisses with empty antecedents for auxiliary system. The context-freeness of the language generated of this system is also established.

Transforming Parsing Algorithms and Other Weighted Logic Programs

Jason Eisner and John Blatz

Many algorithms in statistical natural language processing can be easily described as weighted dynamic programs. We give a notation and execution model for such programs. We then describe several source-to-source transformations that affect a program's efficiency by changing the search strategy, moving work from runtime to compile time, rearranging computations, or rearranging data structures.

On Theoretical and Practical Complexity of TAG Parsers

Carlos Gomez-Rodriguez, Miguel A. Alonso and Manuel Vilares

We present a system allowing the automatic transformation of parsing schemata to efficient executable implementations of their corresponding algorithms. This system can be used to easily prototype, test and compare different parsing algorithms. In this work, it has been used to generate several different parsers for Context Free Grammars (CFG) and Tree Adjoining Grammars (TAG). By comparing their performance on different sized, artificially generated grammars, we can measure their empirical computational complexity. This allows us to evaluate the overhead caused by using TAG to parse context-free languages, and the influence of string and grammar size on TAG parsing.

Properties of Binary Transitive Closure Logic over Trees

Stephan Kepser

Binary transitive closure logic (FOT, for short) is the extension of first-order predicate logic by a transitive closure operator of binary relations. It is known that this logic is more powerful than FO on arbitrary structures and on finite ordered trees. It is also known that it is at most as powerful as monadic second-order logic (MSO) on arbitrary structures and on finite trees. We will study the expressive power of FOT on trees to show that several MSO properties can be expressed in FOT.

The following results will be shown.

• A linear order can be defined on trees.
• The class EVEN of trees with an even number of nodes can be defined.
• On arbitrary structures with a tree signature, the classes of trees and finite trees can be defined.
• FOT is strictly more powerful than tree walking automata.

Pregroups with modalities

Aleksandra Kislak-Malinowska

In this paper we concentrate mainly on the notion of beta-pregroups, which are pregroups (first introduced by Lambek in 1999) enriched with modality operators. Beta pregroups were first proposed by Fadda in 2001. The motivation to introduce them was to limit (locally) the associativity in the calculus considered. In this paper we present this new calculus in the form of a rewriting system, prove the very important feature of this system - that in a given derivation the non-expanding rules must always proceed non-contracting ones in order the derivation to be minimal (normalization theorem). We also propose a sequent system for this calculus and prove the cut elimination theorem for it.

Simpler TAG Semantics through Synchronization

Rebecca Nesson and Stuart M. Shieber

In recent years Laura Kallmeyer, Maribel Romero, and their collaborators have led research on TAG semantics through a series of papers refining a system of TAG semantics computation using semantic feature structures and other tools. Kallmeyer et al. (2004) bring together the lessons of these attempts with a set of desirable properties that such a system should have. First, computation of the semantics of a sentence should rely only on the relationships expressed in the TAG derivation tree. Second, the generated semantics should compactly represent all valid interpretations of the input sentence, in particular with respect to quantifier scope. Third, the formalism should not, if possible, increase the expressivity of the TAG formalism.

We revive the proposal of using synchronous TAG (STAG) to simultaneously generate syntactic and semantic representations for an input sentence. Although STAG meets the three requirements above, no serious attempt had previously been made to determine whether it can model the semantic constructions that have proved difficult for other approaches. In this paper we begin exploration of this question by proposing STAG analyses of many of the hard cases that have spurred the research in this area. We reframe the TAG semantics problem in the context of the STAG formalism and in the process present a simple, intuitive base for further exploration of TAG semantics.

Encoding second order string ACGs with Deterministic Tree Walking Transducers.

Sylvain Salvati

This paper presents a study of the expressivity of a fragment of Abstract Categorial Grammars (ACGs), namely second order string ACGs. This fragment is already known to be able to encode Linear Context Free Rewriting systems (LCFRS). In this paper, we show that it is not more powerfull than LCFRS by encoding its grammars with Deterministic Tree Walking Transducers which are equivalent to LCFRS.

Sidewards without copying

Edward Stabler

A traditional movement step relates a single source position to a single c-commanding target position, and never moves an argument to another argument position. But head movement involves non-c-command relations, control relates two argument positions. Special mechanisms could be invoked for these things, but a different strategy slightly generalizes movement and enforces certain fundamental symmetries observed by all movements to block overgeneration. This paper defines a class of `sideward movement grammars' (SMGs) with such symmetries, with example applications to adjunct control and head movement. These grammars allow copying, but the question of whether to copy is completely independent of the question of whether to allow sideward movement. SMG definable languages are all PMCFG definable, and hence are efficiently recognizable.

English prepositional passives in HPSG

Jesse Tseng

This paper discusses the treatment of English prepositional passives (sometimes also called ``pseudopassives'') in HPSG. Two possible approaches to the syntactic aspects of the problem are outlined and compared; the constructional approach seems preferable to the lexical approach.

Linearization of Affine Abstract Categorial Grammars

Ryo Yoshinaka

The abstract categorial grammar (ACG) is a grammar formalism based on linear lambda calculus. It is a natural question asking how the expressive power of ACGs increases when we relax the linearity constraint on the formalism. This paper introduces the notion of affine ACGs by extending the definition of original ACGs, and presents a procedure for constructing a corresponding linear ACG for a given affine ACG such that the language of the constructed linear ACG is exactly the set of linear lambda-terms generated by the original affine ACG.