FG provides a forum for the presentation of new and original
research on formal grammar, with particular regard to the application
of formal methods to natural language analysis.
Themes of interest include, but are not limited to,
Saturday, July 29th  
12:00  12:20  Welcome + registration  
12:20  14:20  Lunch  
14:20  14:30  Opening  
14:30  15:30  Invited talk: Josef van Genabith Dublin City University 
Parsing and Generation with TreebankBased Probabilistic LFG Resources 
15:30  16:00  Jason Eisner and John Blatz  Transforming Parsing Algorithms and Other Weighted Logic Programs 
16:00  16:30  Coffee break  
16:30  17:00  Stephan Kepser  Properties of Binary Transitive Closure Logic over Trees 
17:00  17:30  Houda Anoun and Alain Lecomte  Logical Grammar with Emptiness 
17:30  18:00  Aleksandra KislakMalinowska  Pregroups with modalities 
20:00  Conference dinner TBA 

Sunday, July 30th  
9:30  10:00  Sylvain Salvati  Encoding second order string ACGs with Deterministic Tree Walking Transducers 
10:00  10:30  Ryo Yoshinaka  Linearization of Affine Abstract Categorial Grammars 
10:30  11:00  Maria Bulinska  PTIME Decidability of NL! with Assumptions 
11:00  11:30  Coffee break  
11:30  12:00  Edward Stabler  Sidewards without copying 
12:00  12:30  Maxime Amblard  Treating clitics with Minimalist Grammars 
12:30  13:00  Jesse Tseng  English prepositional passives in HPSG 
13:00  15:00  Lunch break  
15:00  15:30  Carlos GomezRodriguez, Miguel A. Alonso and Manuel Vilares  On Theoretical and Practical Complexity of TAG Parsers 
15:30  16:00  Rebecca Nesson and Stuart M. Shieber  Simpler TAG Semantics through Synchronization 
16:00  17:00  Invited talk: Laura Kallmeyer Universität Tübingen 
Constraintbased Compositional Semantics in Lexicalized Tree Adjoining Grammars 
The full Proceedings are available here.
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 syntaxsemantic interface for clitics analyses in which we will stress on clitic climbing over verb and control verb.
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.
Buszkowski (2005) showed that all Nonassociative Lambek Calculus with finitely many nonlogical axioms are decidable in polynomial time and generate contextfree languages. The same holds for systems with unary modalities, studied in Moortgat (1997), nary 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 contextfreeness of the language generated of this system is also established.
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 sourcetosource 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.
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 contextfree languages, and the influence of string and grammar size on TAG parsing.
Binary transitive closure logic (FOT, for short) is the extension of firstorder 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 secondorder 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.
In this paper we concentrate mainly on the notion of betapregroups, 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 nonexpanding rules must always proceed noncontracting 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.
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.
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.
A traditional movement step relates a single source position to a single ccommanding target position, and never moves an argument to another argument position. But head movement involves nonccommand 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.
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.
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 lambdaterms generated by the original affine ACG.
http://cs.haifa.ac.il/~shuly/fg/
shuly@cs.haifa.ac.il
.
Last modified: Fri Jul 7 20:08:08 IDT 2006