Richard Moot
email: richard.moot@labri.fr

Semi-automated Extraction of a Wide-Coverage Type-Logical Grammar for French *

Keywords: Extraction de grammaires, grammaires catégorielles, supertagging Categorial grammar, grammar extraction, supertagging, type-logical grammar

The paper describes the development of a wide-coverage type-logical grammar for French, which has been extracted from the Paris 7 treebank and received a significant amount of manual verification and cleanup. The resulting treebank is evaluated using a supertagger and performs at a level comparable to the best supertagging results for English.

Résumé. Cet article décrit le développement d'une grammaire catégorielle à large couverture du

Français, extraite à partir du corpus arboré de Paris 7 et vérifiée et corrigée manuellement. Le grammaire catégorielle résultant est évaluée en utilisant un supertagger et obtient des résultats comparables aux meilleurs supertaggers pour l'Anglais.

Introduction

Though the development of parsers for the French language is an active area of research -as witnessed, for example, by the participation in the EASy evaluation -currently available grammar and parsers for the French language produce structures (typically shared forests or dependency structures) which are not easily exploitable for semantic tasks. Recently, the first results for wide-coverage semantic analysis for English have begun to emerge (Bos et al., 2004); these developments have been made possible to a large extent by the availability of an automatically extracted grammar which permits an easy mapping of syntactic structures to semantic structures: the CCGbank [START_REF] Hockenmaier | CCGbank, a corpus of CCG derivations and dependency structures extracted from the Penn Treebank[END_REF], a treebank for English with annotations in combinatory categorial grammar (CCG). This paper describes the development of a type-logical treebank for French, which has been developed with is usefulness for such semantic tasks in mind. Using the Paris 7 treebank as a starting point, type-logical formulas are extracted automatically and then verified and corrected manually. The resulting grammar, which is still highly ambiguous because of the large number of lexical categories assigned to each word, is then evaluated using a supertagger, which disambiguates the lexical categories using local information only, and found to perform at a level comparable to the best results for English.

Type-logical Grammar

This introduction to modern type-logical grammars will be necessarily brief and gives only an informal sketch of many of the ideas without going into the formal details. However, this short introduction will be sufficient to help the reader understand the grammar extraction in the next section. The interested reader can find a more detailed introduction and motivations in [START_REF] Moortgat | Categorial type logics[END_REF].

Type-logical grammars are a grammatical formalism with its roots in formal logic and the theory of types. A type-logical grammar defines a finite set of atomic formulas (typically s for sentence, np for noun phrase, n for noun and pp for prepositional phrase) and complex formulas A / B (which looks to its right for an expression of type B in order to produce an expression of A) and B \ A (which looks to its left for an expression of type B in order to produce an expression of type A).

Therefore (np \ s) / np is a formula of the calculus. It would be the formula assigned to a transitive verb. It states that it combines first with a noun phrase to its right to produce an expression of type np \ s (the type assigned to an intransitive verb) after which it combines with a noun phrase to its left to form a sentence.

In order to give an account of long-distance dependencies, such as those introduced by relativizers like que in French, we assign a formula of the form (n \ n) / (s / 32np). Here, abstracting over the logical details, this formula indicates that que is looking to its right for a sentence s missing a noun phrase somewhere, as indicated by the subformula s / 32np, after which is will function as a noun modifier, selecting an n to its left to form an n.

In addition, the multimodal type-logical grammar used here [START_REF] Moortgat | Categorial type logics[END_REF]) permits a controlled access to "movement" operations, and allows the assignment of a formula s\ 1 s indicating that the adverb is a sentence modifier with mode information 1 allowing it to 'move' towards the head of the phrase.

In order to obtain the semantics for a syntactic analysis in a type-logical grammars we can directly apply the fact that the set of derivations in a type-logical grammar is a proper subset of the set of derivations in intuitionistic logic and thereby obtain the semantics of a derivation simply by means of the well-established Curry-Howard isomorphism between proofs and λ-terms. This means that from a categorial derivationand an approriated lexicon assigning λ-terms to word-formulas pairs -we can directly obtain a semantic representation in the style of Montague or in a more modern dynamic framework such as DRT (Bos et al., 2004).

Grammar Extraction

The Paris 7 treebank (Abeillé et al., 2003) is a corpus containing extracts of the 'Le Monde' newspaper from December 1989 to January 1994. Part of this corpus (12,440 sentences containing a total of 371,029 word tokens, with 25,280 word types) has been given a functional annotation as well. Given that this functional annotation helps the extraction process and reduces the number of manual corrections, the grammar extraction has been defined for this sub-corpus only.

Figure 1 shows a tree from the Paris 7 corpus, a segment of the longer phrase "La cour a, d'autre part, atténué le montant des amendes que la 11 chambre avait infligées aux autres prévenus". This sentence segment suffices to discuss the most interesting cases of the extraction algorithm. The grammar extraction algorithm used follows the general principles of grammar extraction for categorial grammars, as it has been used in other contexts [START_REF] Buszkowski | Categorial grammars determined from linguistic data by unification[END_REF][START_REF] Hockenmaier | CCGbank, a corpus of CCG derivations and dependency structures extracted from the Penn Treebank[END_REF][START_REF] Moot R | Automated extraction of type-logical supertags from the spoken dutch corpus[END_REF].

1. the tree is binarized, when necessary nodes are inserted for 'traces' (we will see this in more detail in the example below).

2. in the resulting tree, a distinction is made between heads (functors), arguments and modifiers; a simple table lookup is used to decide between the different cases based on the node labels and their functional annotation, so in a sentence (annotated by SENT) the verb cluster (annotated by VN) is assigned as its head, NP and PP daughters are assigned as arguments1 , whereas adverbs (annotated by ADV and ADVP) would be assigned a modifier role. Similarly, in an NP, adjectives and prepositions will be modifiers.

3. formulas are assigned in a top-down fashion starting with the root node and descending the tree by case analysis; again a table lookup is used to convert syntactic categories to atomic formulas

• if the parent node has formula A assigned to it and the left (resp. right) daughter is a modifier then the left daughter will receive formula A/A and the right daughter formula A (resp. A and A\A in the case the right daughter was a modifier • if the left daughter is an argument and the right daughter is a functor, we look up the corresponding formula B in the table and assign B and B\A to the two daughters; similarly if the left daughter is a functor and the right daughter an argument with formula B then the corresponding formulas will be A/B and B respectively. • for a leaf with word w and computed formula A, the pair w -A is added to the lexicon.

Figure 2 shows the result of the extraction algorithm for the tree discussed above. I will just comment on some of the less evident aspects of the extracted lexicon.

Firstly, some restructuring has taken place. The prepositional phrase headed by aux was assigned in the corpus as an argument of the verb cluster VN, where in the extracted lexicon it is an argument of the past participle infligées. Again, these cases are very common and this reattachment gives us a more natural lexicon. Otherwise, the binarization is without surprises.

A second important element is the analysis of the relative pronoun que. As can be seen in Figure 1, the corpus indicates the que is has the role of object in the relative phrase, but in addition it functions as a modifier of the noun amendes (absent from the figure). The extraction algorithm adds an np 'trace', indicated by ǫ, to the rightmost verb of the first verbal group occurring after the relativizer, though manual verification is often necessary to verify this is the correct position. 2 The relation between the trace and the relativizer is indicated in the figure by a dotted line. Readers familiar with multimodal categorial grammars will recognize the dotted line corresponds to the introduction rule for the implication [/I]. All in all, this gives us the category for the relative pronoun que which we discussed in Section 2: a noun modifier selecting a sentence missing a noun phrase to its right.

Finally, it should be noted that some of the syntactic categories have subcategories: we distinguish between s when it occurs as a past participle (s ppart ) or infinitive group (s inf ) making it possible for a verb to admit only specific verb groups as its arguments. This allows us to assign (np\s)/(np\s ppart ) to the different forms of avoir and (np\s)/(np\s inf ) to the different forms of vouloir.

Improving the extracted grammar

A first run of the extraction algorithm gives a highly ambiguous grammar with 5.240 distinct formulas which have been assigned at least once to one of the words in the lexicon. Manual inspection of this first treebank TLG 0 reveals that the extracted lexicon contains many formulas which are the result either of inconsistencies in the treebank or of inconsistencies between the way a phenomenon is analyzed in the treebank and the way it would preferably be analyzed in a type-logical grammar.

A first improvement is the reduction of the different formulas assigned to adverbs. One of the prototypical positions for an adverb is directly to the right of the verb it modifies. This means that if we assign the formula A to this verb, the adverb will have formula A\A assigned to it. However, using the multimodal solution sketched in Section 2 permits us to reduce these instances to the formula s \ 1 s.

In addition, by inspecting the different lexical entries, both for the most frequent words and for the different part-of-speech tags, entries which have been deemed suspect have been manually verified and, where necessary, corrected. Inversely, the list of words assigned to each of the different formulas has been inspected and again formulas which looked inappropriate for the words to which they were assigned have been verified, corrected and made more consistent. To give an indication of the impact of these simplifications, the different formulas for conjunctions have been reduced from 606 in TLG 0 to 188 in TLG.

Taken together, these improvements reduce the number of lexical formulas to a more reasonable, but still quite large, number of 817 distinct formulas. This second treebank, TLG, while undoubtedly still containing a fair amount of errors, provides a good balance between lexicon size and descriptive adequacy. Some differences with the English treebank CCGbank should be noted. First of all, in the CCGbank, conjunctions (in our case et, ou and on some occasions the comma) are handled by the parser whereas in the TLG treebank this information is handled by the supertagger, hence the 188 different categories cited above. In addition, to reduce the number of lexical categories, the CCGbank uses a number of non-logical axioms which transform past participles to adjectives (useful in noun phrases like "le risque lié au négoce international", where lié is assigned (n\n)/pp a -instead of its usual (np\s ppart )/pp a -indicating that in this context, it selects a prepositional phrase to its right in order to become a noun modifier). Other nonlogical axiom include a rule allowing an n to function as an np, which is used for a noun phrases without a determiner. In order to give an indication of the effects of these simplifications in the current context, a second grammar by automatically simplifying the first grammar in accordance with these strategies. We will refer to this more compact grammar as TLG c .

Evaluation

β TLG #/w TLG c #/w 1.0 90.5 1.0 93.5 1.0 0.1 96.4 2.7 97.5 2.5 0.05 97.3 3.1 98.0 2.9 0.01 98.4 4.7 98.8

3.8

Table 1: Supertagger results for the TLG treebanks

In spite of all the reductions made to the treebanks, the resulting lexicon still has a very high number of formulas assigned to each word. In order for the extracted grammar to be more easily parsed, a 'classic' strategy is to use a supertagger which decides, based on the surrounding local contextthe words and part-of-speech tags occurring in a two-word window around the current word as well as the previous two formulas or 'supertags' -which is the most likely formula to assign to the current word.

The maximum entropy supertagger developed by [START_REF] Curran | Parsing the WSJ using CCG and log-linear models[END_REF] Results for the extracted grammars TLG and TLG c are shown in Table 1. 3 For the first row only the best supertag has been kept, whereas the other rows list the result for a multitagger which keeps all supertag with probability greater than β times the highest probability [START_REF]Supertagging for combinatory categorial grammar[END_REF], with a lower β value meaning a larger set of supertags assigned to each word. The left-hand column lists the percentage of the sets of supertags assigned to word-POS tag pairs containing the correct supertag for experiments TLG and TLG c , with the right-hand column listing the average number of supertags per word. Though we should be careful making direct comparisons between results from different languages and different formalisms, these results indicate a supertagger performance comparable with the supertaggers for English described in [START_REF]Supertagging for combinatory categorial grammar[END_REF], though our results have a slightly higher number of supertags assigned to each word for the lower β values.

Conclusion and Future Work

In this paper a wide-coverage type-logical gramar for French has been semi-automatically extracted from the Paris 7 treebank and the resulting corpus has been evaluated using a supertagger. The supertagger obtains state-of-the-art performance compared to English supertaggers.

Currently, different parsing strategies are being developped for further evaluation of the results of the supertagger, and early results look promising. Development of a wide-coverage semantic lexicon for this grammar -in the style of Bos et al. (2004) -is progressing rapidly and both this lexicon and the trained models for the POS and supertagger will be made available to the research community under the LGPL-LR license.

Figure 1 :Figure 2 :

 12 Figure 1: Example tree from the Paris 7 treebank with the extracted formulas indicated below the leaves n\n

  has been used to evaluate supertagger performance on the TLG treebank. The treebank has been split into two set: a of training data containing 11.196 sentences and 334.525 words and a set of test data, containing 1.244 sentences and 36.504 words. The maximum entropy model has been trained with the Clark & Curran (2004) supertagger using their adaptation of the L-BFGS algorithm to optimize parameter estimation.

  ABEILLÉ A.,CLÉMENT L. & TOUSSENEL F. (2003). Building a treebank for French. In A. ABEILLÉ, Ed., Treebanks: Building and Using Parsed Corpora, chapter 10, p. 165-187. Dordrecht: Kluwer. BOS J., CLARK S., STEEDMAN M., CURRAN J. R. & HOCKENMAIER J. (2004). Wide-coverage semantic representation from a CCG parser. In Proceedings of the 20th International Conference on Computational Linguistics(COLING-2004), p. 1240-1246, Geneva, Switzerland.

unless they have the NP mod functional annotation, as would expressions like "dimanche 5 janvier" or "cette fois" or the PP mod functional annotation, as would expressions like "en Espagne" or "sauf accident"

Some relatative pronouns like qui are easy, whereas others, like dont and laquelle require more effort.

Results for the treebank TLG 0 which incorporates none of the improvements described in Section

are not shown in the table. Supertagging predicision for this treebank is 79.4 %, which is in line with results reported for automatically extracted TAGs[START_REF] Vijay-Sjanker | Automated extraction of TAGs from the Penn treebank[END_REF] both in terms of the number of different supertags and precision.

* This research has been partially financed by the conseil régional d'Aquitaine in the context of the ITIPY project.


Richard Moot
email: richard.moot@labri.fr

Wide-Coverage French Syntax and Semantics using Grail *

Keywords: Discourse Representation Theory, grammaires catégorielles Categorial grammar, Discourse Representation Theory, type-logical grammar

The system demo introduces Grail, a general-purpose parser for multimodal categorial grammars, with special emphasis on recent research which makes Grail suitable for wide-coverage French syntax and semantics. These developments have been possible thanks to a categorial grammar which has been extracted semi-automatically from the Paris 7 treebank and a semantic lexicon which maps word, part-of-speech tags and formulas combinations to Discourse Representation Structures.

Résumé. Cette démonstration décrit Grail : un analyseur syntaxique pour grammaires catégorielles.

Elle met l'accent sur les recherches récentes qui ont permis à Grail de donner des analyses syntaxiques et sémantiques du Français. Ces développements sont possibles grâce à une grammaire extraite semiautomatiquement du corpus de Paris 7 ainsi qu'un lexique sémantique qui traduit des combinaisons de mots, des étiquettes syntaxiques et des formules en Discourse Representation Structures.

Introduction

Grail is platform for developing and parsing multimodal categorial grammars [START_REF] Moortgat | Categorial type logics[END_REF]. Up until now Grail has mainly been used for the development of fairly small grammars treating specific linguistic phenomena, often with an emphasis on the syntax-semantics interface 1 . The current system demonstration will showcase a prototype wide-coverage multimodal categorial grammar for French which outputs discourse representation structures in the style of [START_REF] Bos | Wide-coverage semantic representation from a CCG parser[END_REF] for unseen text (current newspaper articles or sentences proposed by the audience). Though this is work in progress and the semantic lexicon still needs to be significantly extended, early results are promising.

The French Grammar

The French grammar used by Grail has been semi-automatically extracted from the Paris 7 treebank [START_REF] Abeillé | Building a treebank for French[END_REF]. The lexical ambiguity in the resulting grammar, even after a significant amount 69), the comma "," (54) or "est" (57, the other forms of "être" are slightly easier).

Fortunately, we can reliably estimate the most likely formula assignments based on local information only (surrounding words and part-of-speech tags, preceding formula assignments). This approach is called supertagging (Bangalore & Joshi, 2010).

The part-of-speech tagger and supertagger of Clark & Curran ( 2004) have been trained on the extracted grammar and achieve a precision of 98.4% for the part-of-speech tagger and 90.5% for the supertagger.

Coverage for the supertagger can be significantly increased by using a multi-tagger, assigning all supertags with a probability of greater than a certain factor of the probability assigned to the best supertag to each word. This factor is a parameter which can be used to trade coverage of the corpus for speed of parsing.

When keeping all supertags with a probability of greater than 1% of the probability assigned to the best supertag, the supertagger assigns an average of 4.7 formulas to each word, which includes the correct formula in 98.4% of the cases.

To illustrate the supertagger and give an example indicative of what can be expected during the demo, the following sentence has been taken from one of today's French newspapers2 .

1. Le gouvernement refuse tout commentaire sur cette proposition et préfère avancer les chiffres positifs récoltés par la mesure.

Figure 1 shows part of the output of the part-of-speech tagger and the supertagger for this example sentence. The relative probability of the different supertags is indicated by the percentage of the block next to it which is displayed in a darker blue.

As can be seen, the number of assigned supertags for each word remains quite reasonable. For example, "et" is assigned only a single formula, that of a VP conjunction -taking a VP or np\s to its right as well as its left in order to produce a new np\s. Categories about which the supertagger is less sure -the adverbs ADV, prepositions PRP and the different verb forms VER:X -have multiple formula assignments.

So the preposition "sur" has four assigned categories: pp sur /np, the category for a preposition which selects a noun phrase to its right to become a pp verb argument, being the supertagger's first choice, with (n\n)/np, the category for a preposition modifying a noun as its second choice. The two other possibilities (adverbial sentence modifier and noun phrase modifier) being considered considerably less likely.

Categorial grammars come with a simple and transparent semantics: since categorial parses/derivations are a proper subset of derivations in intuitionistic logic, which by the Curry-Howard isomorphish are in a 1-1 correspondance with lambda terms in the simply typed lambda calculus, each parse corresponds to a different lambda term.

The use of the simply typed lambda calculus has been popularized by Richard Montague and many others, though it should be noted that the simply typed lambda calculus is compatible with more modern dynamic semantic theories like Discourse Representation Theory [START_REF] Kamp | From Discourse to Logic[END_REF]

Figure 2: Grail L A T E X output
The current prototype uses DRT as target for its semantic output, though a Montegovian Dynamics semantic lexicon is being developed as well. There are many reasons for having chosen DRT as the semantic language, the principal reasons being:

1. there is an impressive body of research into a large number of semantically interesting phenomena which have been formalized in DRT, 2. while providing a visually simple presentation of its semantics in the form of discourse representation structures (DRSs) there is an easy translation of the DRSs into firstorder logic. 3A semantic lexicon, in the style of the one used for English by [START_REF] Bos | Wide-coverage semantic representation from a CCG parser[END_REF], is currently under active development. The lexicon contains two main parts: the first assigns lambda terms to specific word-formula pairs, these are frequently occurring words which require some form of special treatment, eg. the conjunctions such as "et" and relativizers such as "que" and "dont". The second part contains default rules, which assign a semantics to words not in the first lexicon, based only on the part-of-speech tag, formula and lexical lemma. This lexicon contains the 'open' classes such as nouns and verbs. The current lexicon contains entries for over 300 words and has around 150 default rules.

Figure 2 shows the Grail output for the example sentence of Section 2. The variables d, e and f are event variables and variables x, y and z are entity variables. So d 2 in Figure 2 corresponds to an event of "préférer", with agent (subjet) z 18 , which is a variable denoting an entity with the property of being "gouvernement". The theme of the event d 2 , ie. the situation being preferred, is the embedded DRS with label x 4 . Note that z 18 is agent of this embedded DRS x 4 as well (since "préférer" is a subjet control verb) as well as agent of the top-right embedded DRS at the right-hand side of the implication since, as discussed in the previous section, our example phrase conjoins two verb phrases with "le gouvernement" being the subjet of both.

  and Montegovian Dynamics (de Groote, 2006) as well.

	d 2 z 18
	gouvernement(z 18 )
	z 14 x 17	→ e 0
	commentaire(z 14 )	event(e 0 )
	proposition(x 17 )	refuser(e 0 )
	sur(z 14 , x 17 )	agent(e 0 , z 18 )
		patient(e 0 , z 14 )
	préférer(d 2 )
	event(d 2 )
	agent(z 18 )
	theme(x 4 )
	x 4 : e 4 y 7
	event(e 4 )
	avancer(e 4 )
	agent(e 4 , z 18 )
	patient(e 4 , y 7 )
	positifs(y 7 )
	chiffres(y 7 )
	d 9 y 10
	mesure(y 10 )
	background(d 9 )
	récoltér(d 9 )
	patient(d 9 , y 7 )
	agent(d 9 , y 10 )

http://www.lepoint.fr/actualites-societe/2010-05-24/ solidarite-le-lundi-de-pentecote-ne-fait-pas-recette/920/0/458325, visited 24 May 2010

Of course, there are some drawbacks as well, which include the absence of the higher-order constructions allowed by the simply typed lambda calculus and the complications arising from what essentially amounts to the use of free variables in DRT semantics to handle anaphora resolution.

http://www.swi-prolog.org, note that Grail requires a full install which includes the optional libraries

http://svn.ask.it.usyd.edu.au/trac/candc/wiki

http://www.tcl.tk

http://www.latex-project.org

http://www.graphviz.org

can be downloaded under LGPL -together with a number of example grammars -at http://www.labri.fr


Richard Moot
email: richard.moot@labri.fr

Extraction of Type-Logical Supertags from the Spoken Dutch Corpus *

Introduction

The Spoken Dutch Corpus assigns 1 million of its 9 million total words a syntactic annotation in the form of dependency graphs. We will look at strategies for automatically extracting a lexicon of type-logical supertags from these dependency graphs and investigate how different levels of lexical detail affect the size of the resulting lexicon as well as the performance with respect to supertag disambiguation.

Type-Logical Grammars

Combinatory categorial grammars and type-logical grammars extend the simple but very limited AB grammars [START_REF] Ajdukiewicz | Die syntaktische Konnexität[END_REF][START_REF] Bar-Hillel | Language and Information. Selected Essays on their Theory and Application[END_REF] in different ways. Whereas CCGs [START_REF] Steedman | The Syntactic Process[END_REF] choose to add combinators allowing types to combine in more flexible ways, type-logical grammars, as pioneered by [START_REF] Lambek | The mathematics of sentence structure[END_REF] and further developed by -among many others - [START_REF] Morrill | Type Logical Grammar[END_REF], [START_REF] Moortgat | Adjacency, dependency and order[END_REF] choose to extend the system to a full logic. That is, they add to the AB calculus, which contains only rules telling us how to use complex formulas, the symmetric rules of proof which allow us to show we can derive a complex formula from an expression.

My introduction to type-logical grammars in this section will be necessarily brief, but I hope it will be enough for the reader to understand the applications in the following sections.

't ⊢ np/n the eten ⊢ n food is ⊢ (np\s)/(n/n) is koud ⊢ n/n cold Table 1: Example lexicon

The non-associative Lambek calculus

We will start by looking at the non-associative Lambek calculus, NL [START_REF] Lambek | Structure of Language and its Mathematical Aspects[END_REF]. Formulas in this calculus are either atomic formulas, from a fixed set determined by the grammar -for example, we typically find np for noun phrase, n for common noun and s for sentence -or complex formulas. If A and B are formulas, then

• B\A (B under A) is a formula looking to its left for a B formula to give an A as a result; an example would be np\s for an intransitive verb, which looks for a subject np to its left to form a sentence,

• A/B (A over B) is a formula looking to its right for a B formula to give an A as a result; an example would be np/n for a determiner, which looks for a common noun to its right to form a noun phrase or (np\s)/np for a transitive verb, which looks to the right for an object np to form an intransitive verb.

• finally, we have A • B (A and B) which is simply an expression of type A next to an expression of type B.

Note that we follow Lambek's notation where the result category is always above the slash and the argument below it.

A statement is a pair of the form X ⊢ A, where X is a non-empty, binary branching tree with words as its leaves and where A is a formula. It states that we have shown X to be an expression of type A.

To save space, we will usually write the tree X in flat notation, using an infix operator '•'. In this notation, the tree

• • 't eten
• is koud will be written as

('t • eten) • (is • koud).
A lexicon is a set of statements which assign formulas to single words. A Dutch example, with English translations for the words, is given is Table 1.

X ⊢ A • B x ⊢ A y ⊢ B . . . . Z[x • y] ⊢ C Z[X] ⊢ C [•E] X ⊢ A Y ⊢ B X • Y ⊢ A • B [•I] X ⊢ A/B Y ⊢ B X • Y ⊢ A [/E] x ⊢ B . . . . X • x ⊢ A X ⊢ A/B [/I] Y ⊢ B X ⊢ B\A Y • X ⊢ A [\E] x ⊢ B . . . . x • X ⊢ A X ⊢ B\A [\I]
Table 2: Natural deduction rules for the non-associative Lambek calculus NL

X ⊢ B x ⊢ B\A X • x ⊢ A [\E] X ⊢ A/(B\A) [/I] Figure 1: General derivability of lifting
The rules of NL, which allow us to combine these lexical statements into derivations, are given in Table 2.

A simple consequence of these rules is that type-lifting is now derivable: if X is an expression of type B it is necessarily also an expression of type A/(B\A). Figure 1 shows a proof of this.

Multimodal extensions

Because NL generates only context free languages, it is inadequate as a formalism for linguistic analysis. In this section we will look at some refinements of the calculus which allow it to expand its expressiveness without losing its essential logical nature. [START_REF] Moortgat | Categorial type logics[END_REF] gives a modern and more detailed description of these extensions.

Unary modalities

As a first extension, we no longer require the trees on the left-hand side of a statement to be binary branching. If we add the possibility of unary branching

X ⊢ 3 i A x ⊢ A . . . . Z[ x i ] ⊢ C Z[X] ⊢ C [3E] X ⊢ A X i ⊢ 3 i A [3I] X ⊢ 2 ↓ i A X i ⊢ A [2 ↓ E] X i ⊢ A X ⊢ 2 ↓ i A [2 ↓ I]
Table 3: Natural deduction rules for the unary modalities as well is different modes i of unary branching, indicated on the flat term as X i , we are led -by analogy to the binary rules -to the rules shown in Table 3. [START_REF] Kurtonina | Structural control[END_REF] provide a good introduction to these unary modalities and give several interesting applications. One of the typical applications of the unary modalities is to use them to implement linguistic features. For example X n could mean 'I'm an X constituent but I carry nominative case', whereas X a could mean 'I'm an X constituent, but I carry accusative case'. Note that a and n are simply used as mnemonics and we might just as well have use more abstract modes like 1 and 2 two distinguish between the two cases.

Let's look at the rules in Table 3 with the intended implementation of features in mind. The [2 ↓ E] rule states that if structure X is of type 2 ↓ i A then X i is of type A. The [2 ↓ E] rule adds feature information to a structure. Inversely, the [2 ↓ I] rule verifies if the antecedent structure has the proper form X i and then removes this feature information.

The [3I] rule states that if X is of type A then X i is of type 3 i A. Like the [2 ↓ E] rule, we add feature information to the previous structure. The final rule is perhaps the most difficult to explain; the [3I] rule tell us what to do when we have derived a structure X to be of type 3 i A. In order to remove this diamond formula, we start a subderivation using a structure x of type A demanding at the end of this subderivation that the variable x has the unary brackets i around it. Finally, we continue the derivation replacing the structure x i by X, ie. the structure we had computed for 3 i A before. In other words, we verify that an A constituent has the correct feature information, then remove this feature information and continue with a 3 i A constituent. This 'check then remove' behavior is similar to the [2 ↓ I] rule.

Two useful derivability patterns are shown in Figure 2. On the left we show that for every mode i and structure X of type A, this same structure is also of type 3 i 2 ↓ i A. Conversely, as shown on the right of the figure, if X is of type

3 i 2 ↓ i A then it is also of type A. X ⊢ A X i ⊢ 3 i A [3I] X ⊢ 2 ↓ i 3 i A [2 ↓ I] X ⊢ 3 i 2 ↓ i A x ⊢ 2 ↓ i A x i ⊢ A [2 ↓ E] X ⊢ A [3E]
Figure 2: Derivability patterns for the unary modalities

hij ⊢ 2 ↓ n 3 n np he hem ⊢ 2 ↓ a 3 a np him Vincent ⊢ np Vincent Peru ⊢ np Peru slaapt ⊢ 2 ↓ n 3 n np\s sleeps bezoekt ⊢ (2 ↓ n 3 n np\s)/2 ↓ a 3 a np visits
Table 4: Lexicon with basic case information

Table 4 shows how we can exploit these patterns when adding basic case information to the lexicon. [START_REF] Heylen | Types and Sorts: Resource Logic for Feature Checking[END_REF] gives a much more detailed treatment of feature information for categorial grammars. The personal pronouns, like 'hij' (he) and 'hem' (him) are specified in the lexicon for nominative and accusative case respectively.

Since Dutch proper nouns don't change their form to indicate their case, we would prefer to assign them only a single form which is underspecified for case. But this is exactly what the standard np type allows us to do, given that we have just see that any structure of type np is also a structure of type 2 ↓ n 3 n np and a structure of type 2 ↓ a 3 a np. The resulting grammar correctly predicts that 'hij bezoekt hem' is a grammatical sentence but that ' * hem bezoekt Peru' is not.

Structural Rules

By themselves, the unary modalities don't extend the generative capacity of type-logical grammars. A second extension, in the form of structural rules, allows us to do this. Adding structural rules to NL is not a new idea. For example, adding the structural rule of associativity to NL gives us an alternative formulation of the associative Lambek calculus L.

The advantage of a multimodal calculus is that rather than having structural rules apply globally we can 'anchor' them to specific modes, which in turn are obtained from the lexical types.

Consider for example a permutation mode p, which allows us to move constituents which have been lexically specified as being of type 3 p 2 ↓ p A. As we have seen in Figure 2 on the right, such a constituent can play the role of an A when needed. However, the structural rules shown in Figure 3 show us how we can move a constituent marked as X p from one right branch in a

Z[X 1 • (X 2 • X 3 p ) ⊢ C Z[(X 1 • X 2 ) • X 3 p ] ⊢ C [MA] Z[(X 1 • X 3 p ) • X 2 ] ⊢ C Z[(X 1 • X 2 ) • X 3 p ] ⊢ C [MC] • x 1 • x 2 3 p x 3 → MA • • x 1 x 2 3 p x 3 • • x 1 3 p x 3 x 2 → MC • • x 1 x 2 3 p x 3
Figure 3: The structural rules of mixed associativity and mixed commutativity in flat representation and as tree rewrites tree to another. The rule M A, for 'mixed associativity', takes an embedded x 3 , which is a sister of the x 2 node and moves it upwards to be a sister of the node one level up, regrouping x 1 and x 2 together. It is an associativity rule since it only changes the grouping of the nodes but not their order. The rule M C, for 'mixed commutativity' does change the order. Before application of the rule, the x 3 node is between the x 1 and x 2 nodes. After the rule, x 1 and x 2 are adjacent.

Observe that as long as the top of the binary tree hasn't been reached, ex-

wie ⊢ wh/(s/3 p 2 ↓ p np) who leest ⊢ (s/np)/np reads (interrogative) Proust ⊢ np Proust Tsjechov ⊢ np Chekov
Table 5: Lexicon for the treatment of wh questions in Dutch actly one of these two rules will apply, depending on whether the parent node of x 3 p is on a left or a right branch. We can use these structural rules to given an account of extraction in typelogical grammar. Let's look at the following examples.

wie ⊢ wh/(s/3 p 2 ↓ p np) leest ⊢ (s/np)/np Proust ⊢ np leest • Proust ⊢ s/np [/E] x ⊢ 3 p 2 ↓ p np y ⊢ 2 ↓ p np y p ⊢ np [2 ↓ E] x ⊢ np [3E] (leest • Proust) • x ⊢ s [/E] leest • Proust ⊢ s/3 p 2 ↓ p np [/I] wie • (leest • Proust) ⊢ wh [/E] wie ⊢ wh/(s/3 p 2 ↓ p np) x ⊢ 3 p 2 ↓ p np leest ⊢ (s/np)/np y ⊢ 2 ↓ p np y p ⊢ np [2 ↓ E] leest • y p ⊢ s/np [/E] Proust ⊢ np (leest • y p ) • Proust ⊢ s [/E] (leest • Proust) • y p ⊢ s [MC] (leest • Proust) • x ⊢ s [3E] leest • Proust ⊢ s/3 p 2 ↓ p np [/I] wie • (leest • Proust) ⊢ wh [/E]
(1) leest reads

Proust Proust

Tsjechov Tsjechov ? ? 'does Proust read Chekov?'

(2) wie who leest reads

Proust Proust ? ? ambiguous between 'who reads Proust?' and 'who does Proust read?' If we were to assign 'wie' the formula wh/(s/np) in our lexicon, only the second reading would be available to us. However, if we would assign it the formula wh/(s/32 ↓ np) it would say: I'm looking to my right for a sentence which is missing an np anywhere on a right branch to give a wh question. Figure 4 shows how this allows us to find both readings for this sentence.

The first reading simply uses the fact that a structure of type 3 p 2 ↓ p np can be used as an np, after which we simply have an NL derivation. The second reading is more interesting, as it requires us to use the structural rule of mixed commutativity. The [3E] and [2 ↓ E] rules introduce a constituent y p , our moving np. Combining this np with leest and Proust gives a configuration to which the mixed commutativity rule can be applied. We have the bottom left Adding unary modalities and structural rules gives us a flexible logic, able to handle the harsh reality of linguistic phenomena, to which we will now turn.

Treebank Extraction

In this section, I will show how to generate a type-logical treebank from the syntactic annotation files of the Spoken Dutch Corpus and some methods for reducing the size of the generated lexicon.

Syntactic Annotation for the Spoken Dutch Corpus

The Spoken Dutch Corpus ('Corpus Gesproken Nederlands' or CGN) contains 9 million words of contemporary spoken Dutch with various forms of linguistic annotation. Orthographic transcription and part-of-speech tagging have been provided for all 9 million words. A core corpus of 1 million word has, in addition, been provided with a syntactic annotation in the form of dependency graphs.

For the CGN syntactic annotation, the annotation tools developed for the German NEGRA Corpus [START_REF] Brants | Tagging and Parsing with Cascaded Markov Models -Automation of Corpus Annotation[END_REF] have been used to semi-automatically produce syntactic annotation graphs of the form shown in Figure 5 on the preceding page.

I will briefly discuss some properties of these annotation graphs. More details on the annotation format and philosophy can be found in [START_REF] Hoekstra | Syntactic analysis in the Spoken Dutch Corpus (CGN)[END_REF].

The annotation graphs are directed, acyclic graphs, where every leaf is labeled with a part-of-speech tag (like WW1 for a singular, inflected verb) and all other vertices are labeled with a grammatical constituent (like SV1 for a verbinitial sentence). Edges are labeled with a dependency relations (like hd for head and obj1 for a direct object).

The POS tags used for the syntactic annotation are a simplification of the morphologically richer tags which have been used for POS tagging the Spoken Dutch Corpus. The WW1 tag for the verb, for example is a simplification of the T301 tag, which also indicates the verb is in present tense and does not end with the 't' suffix for verb inflection.

Some other properties are:

• Annotation structures are flat. A new node is only introduced when necessitated by a lexical head. This means, for example, that we have no separate vp nodes.

• We can have multiple dependencies, sometimes called 'secondary edges'. These are used both for the treatment of ellipsis and for long-distance dependencies. In the example, we have a long-distance dependency, where VNW14 (wat) is both the head of the wh phrase and the subject of the verb-initial sentence. The annotation

• Constituents can be discontinuous. For example 'er aan' is a PP in the example sentence, even though the ADJ9 (zielig) is positioned between these two words.

• Annotation graphs are allowed to be disconnected. In our example the LET constituent is an isolated vertex.

Preprocessing

Given that we are using a spoken corpus, we have to deal with a number of artifacts which would not normally be present in written language. Words indicating speaker hesitation like 'uh', for example, occur frequently and are almost never assigned a grammatical function. They appear as isolated vertices in the annotation graph. Some annotators choose to give them a role in incomplete phrases, but this is relatively rare (192 out of 23,289 occurrences). The same can be said for interpunction marks, which, as shown in Figure 5 on the previous page, are generally annotated as an isolated LET vertex. Only 6 shows an example.

To prevent these 'easy' word categories from giving a too flattering impression of the performance of the supertagger, I cleaned up the data, filtering out all isolated vertices, including hesitation marks and interpunction symbols but also partial repeats (see 3, where 'het/'t is' occurs twice) and self-corrections, as in 4 where the speaker corrects the gender of the article he is using.

(3) ja yes In cases like these, the first occurrences of the repeated or corrected words are usually not assigned a grammatical role.

het it is is 't it
Removing all these isolated vertices gives a filtered corpus contains 87,404 sentences (out of 114,801, most of the removed sentences being single-word utterances like 'yes') and 794,872 words (out of 1,002,098).

We will look a way of filtering the corpus without looking at the syntactic annotation in Section 4.4.

Extraction Algorithm

The algorithm used for extracting a treebank is essentially the one proposed in [START_REF] Moortgat | Using the Spoken Dutch Corpus for typelogical grammar induction[END_REF], which is parametric for three functions:

1. a function from vertex labels (or vertex label, edge label pairs) to formulas, 2. a function identifying the head of every grammatical constituent, 3. a function identifying the modifiers of every grammatical constituent.

We will discuss different functions assigning formulas to vertex labels, since this has a great influence on the number of different lexical entries we extract. The other two functions have been kept constant.

The current implementation identifies the functor from a set of daughters by their edge labels using a list in order of preference. For most vertex labels this will just be hd, but, because the algorithm requires finding a head for every syntactic category, there are typically some strange items further down the list to make sure we can find a head even for incomplete utterances.

The function identifying modifiers marks only constituents with edge label mod as modifier for most syntactic categories. Siblings of the head which are not modifiers will be its arguments.

The algorithm operates by performing a basic depth-first search from the different root nodes of a corpus graph assigning a primary formula f to every node in the graph as well as a list g 1 , . . . , g n of secondary formulas. The list of secondary formulas is necessary for nodes with multiple parents and will contain a formula for each additional parent of the node, ie. every node will have one formula for every role if fulfills in the syntactic structure. The corresponding formula is (. . .

(f • 3 p 2 ↓ p g 1 ) . . . • 3 p 2 ↓ p g n ).
For most nodes, however, this list will be empty, and the primary formula f will directly correspond to the assigned type.

To divide an annotation graph into lexical formulas for all words in it, we begin by finding all root nodes in the annotation graph and looking up the corresponding formula f in the table. We determine for each of the children if they are the unique head, a modifier or an argument. We descend the modifiers assigning their vertex f /f or f \f , depending on their position with respect to the head. For the arguments, we look up the corresponding formulas a 1 , . . . , a n in the table and assign it to their vertex. Finally, the head child will be assigned the complex formula

(a i \ . . . (a 1 \((f /a n ) . . . /a i+1 )))
which first selects the arguments a i+1 , . . . , a n to the right of it then the arguments a 1 , . . . , a i , to its left. When we arrive at a node via a secondary edge we append the formula to the list of secondary formulas.

In every case, after assigning a type to a vertex we will descend recursively until we reach the leaves, in which case the formula will be added to the lexicon for that word. The operation of the algorithm is perhaps most clearly demonstrated by an example. If our vertex label to formula mapping assigns wh to WHQ and s to SV1 and we make, like the CGN annotation, the choice of whd as head of a wh question then, returning to Figure 5 on page 8, we are compelled to assign the formula s to the SV1 and wh/s to the VNW14 node, as shown in Figure 7. Now it's the turn of the SV1 node to be split. It has four children, the WW1, reached by the hd label, being the head and the PP, reached by the mod label, a modifier. Because it is to the right of the head, it will be assigned the modifier category s\s. The other two children are arguments and we look up the formulas which correspond to them: np for VNW14 and ap for ADJ9. Therefore, the formula assigned to the verb will be (s/ap)/np.

Because we now arrive at the relative pronoun via a secondary edge, we add an np formula to the list of secondary formulas. As shown in the figure, this corresponds to assigning it the formula (wh/s) • 32 ↓ np.

There is only one nonterminal left to be split, which is the PP node. We have the preposition VZ2 as its head and the pronoun VNW20 as its argument. Again, the type for the argument is np, so the type for the head will be np\(s\s).

The final extracted lexicon is shown in Figure 9 on the next page. We note that if we specialize the product type for 'wat', we will produce the type wh/(s/32 ↓ np) which is identical to the one proposed for the manually generated lexicon of Table 5 on page 6.

The algorithm for corpus extraction only exploits the fact that we have a dependency-based annotation. Given the three functions we discussed at the beginning of this section, we could directly use the current algorithm to extract

Refinement

Some of the vertex labels of the Spoken Dutch Corpus, like DU (discourse unit), CONJ (conjunction), LIST and MWU (merged word unit, a category assigned to multi-word names and fixed expressions) are not really grammatical categories.

An example of a discourse unit is shown in Figure 10 on the next page. Often it is just an ordinary sentence introduced by a tag like 'yes' or (as in the example) 'no' or an element linking it to the previous sentence like 'and'. Examples of the other categories are shown below.

( Rather than using a type conj or list in the lexicon, we give a conjunction the type of it first conjoint and a list the type of its first list item. A discourse unit is assigned the type of its nucleus, if there is one, and the type of its first discourse element otherwise. We simply assign np to merged-word units.

Supertagging

Now that we have a generic method of extracting supertags from the Spoken Dutch Corpus, it is time to extract different grammars and evaluate the size of the lexicon as well as the performance of supertag disambiguation for these lexicons.

The Extracted Grammars

The most basic way of applying the algorithm of the previous section is simply to keep syntactic categories of the CGN annotation (22 in total when we exclude DU, CONJ, LIST and MWU) and map the part-of-speech tags of the leaves to these categories (adjectives to AP, pronouns to NP, etcetera). This leaves us with a rather large lexicon, the basic treebank, containing 6,817 different formulas.

To reduce the size of the lexicon, we have merged a number of these formulas: no longer distinguishing between the different sentence types SMAIN (declarative sentence, which is verb second), SV1 (interrogative sentence, with the verb first) and SSUB (subordinate clause, with the verb last) and mapping them all simply to s. Though we can still determine the sentence type from the directionality of the implications, this will make a big difference for the sentence modifiers, which now no longer need to distinguish between the different sentence types. Other changes include mapping AP to noun modifier. This reduces the size of the lexicon to 3,539, giving us the compact treebank.

Another simplification is obtained by removing external discourse unit nodes. This removes the need to analyze a discourse unit containing several different parts, which are often elliptical or only loosely related like 8, 9 or 10 below, where any decision as to what would be modifiers, arguments or head would be rather artificial. The resulting split treebank contains 2,201 lexical entries. For comparison, I added three other strategies to reduce the size of this treebank. While these grammars will provide much coarser linguistic descriptions, it is perhaps useful to look at the effect of the reduced lexicon size on the performance of the supertagger.

• The first collapses even more lexical categories than before, by for example replacing the pp category by s\s, which causes a preposition which modifies a verb to have the same type as a preposition which is the argument of the verb, with only the verb type differing in the two cases. This is the very compact treebank, containing 1,962 entries.

• The second removes all multiple dependencies from the grammar. This makes the grammar a simple AB grammar, needing only elimination rules to find a derivation. This is useful if we are interested in parsing the supertagged sentence afterwards, given that we can use chart parsing techniques for these grammars. The AB treebank contains 1,761 lexical formulas.

• The third removes all directionality from the implications, making it a grammar for the Lambek-van Benthem calculus LP. For example, it no longer distinguishes between verbs in initial, second or final position. If we are only interested in the semantic type, however, this information would suffice. The LP treebank is the smallest we will consider, containing 1,137 formulas.

Other strategies for extracting type-logical grammars from structured data and reducing the size of the lexicon exist. [START_REF] Buszkowski | Categorial grammars determined from linguistic data by unification[END_REF] propose a strategy for learning AB grammars from structures and using unification of type variables to reduce the lexical ambiguity. An advantage of this method is that it can be used to find the optimal way of mapping vertex labels to formulas. Unfortunately, the algorithm for finding this mapping is exponential and therefore the current choice of requiring the extraction algorithm to know the formulas corresponding to the different labels seems more practical, giving us an algorithm for extracting our grammars in time linear to the size of the corpus. [START_REF] Moortgat | Structural equations in language learning[END_REF] proposes a strategy for reducing the lexical ambiguity for automatically extracted grammars by introducing modal operators and structural reasoning to replace different lexical type assignments by a single one which is at least as general the types it replaces. If we can avoid overgeneralisation, this would allow us to reduce our treebank to a corpus of a size which would ideally be comparable to the LP treebank without collapsing to full commutativity. This seems challenging to achieve, however.

Experiments and Results

All experiments have used the 72 part-of-speech tags instead of the 324 morphology tags, which contain too detailed morphology information, actually hindering performance because of the resulting data sparseness. The single exception is the SPEC (special) tag, which we split into the seven different versions used by the morphology tagger, giving us a total of 78 part-of-speech tags for our experiments. The choice to split up the special tags was made because it comprises words in different groups like: inaudible, broken off, foreign, partof-whole (as in multi-word proper names) and background noise.

We have trained our models using a supertagger based on the Edinburgh maximum entropy tools, making a decision for the lexical formula of the words based on:

• the current word and POS tags, as well the two previous/following words and POS tags

• the previous two supertags.

Only features which were seen 5 times or more in the training data have been selected for training. All models were trained using 100 iterations on 69,923 sentences of the filtered corpus (635,764 words), whereas the other 17,480 sentences (159,086 words, every fifth sentence of the corpus) were kept for testing the performance.

Experiment

Table 6 summarizes the results for the different corpora.

The Split corpus assigns lexical formulas which are closest to those provided by a manually generated lexicon and offers a good compromise between performance and descriptive adequacy. Compared to the Compact corpus, which differs only in that it does not split up root discourse unit nodes, there is a big improvement both in lexicon size and performance.

The AB corpus, in spite of its reduced lexicon size, actually performs worse than the Very Compact corpus, presumably because not treating the secondary edges forces us to assign unusual types to verbs.

The LP corpus has the best performance, both in lexicon size and in correct supertag assignments, though at the price of a significant loss in the information the supertags provide.

Analysis of the Extracted Lexicon

To give a better idea of the form of the extracted lexicon, I will now discuss some of the frequently occurring verb forms as well as the most frequent product types which are extracted in the case of multiple dependencies. All discussion in this section will be about the Split treebank.

Table 7 list the supertags which have been extracted over 1,000 times for finite, singular verbs, together with the percentage of the total extracted verb forms these formulas account for. So, the nine formulas shown in the table, when taken together, account for 72.09% of the total verbs forms.

The type assigned to auxiliaries (np\s)/(np\s) is the most frequent, closely followed by the type for transitive verb with the verb occurring in second position, as it will in a non-topicalized declarative sentence. In total there are 724 different supertags assigned to these verbs, though only 396 are assigned more than once. As can be seen from the formulas in the table, the types assigned are quite construction-specific, as they would be in an extracted LTAG grammar. For example, several frequently occurring type differ only in the order of the arguments. For intransitive verbs, we see both s/np and np\s, and for transitive verbs we see all three possibilities: verb-initial (s/np)/np, verb-second (np\s)/np and verb-final np\(np\s). Even the type (s/(np\s))/np is just the sentence-initial version of the standard auxiliary verb type. While it seems we can gain something using a unique type in these cases and derive the other possibilities using structural rules, the improvement in supertag performance is relatively small, with less than one percent improvement in the number of supertags which is correctly assigned to verbs. Apparently, the trigrams give us enough context to decide on the proper direction of the arguments of verbs and, given that this information is useful for parsing, I have decided not to collapse types which differ only in the direction of the arguments.

Table 8 lists all singular, declarative verb forms which occur more than 1,000 times, together with the number of supertags with which they have been found as well as indicating the most common one. Unsurprisingly, forms of 'be', 'have' and other auxiliaries dominate here, both in number of occurrences and in the number of assigned supertags. Some remarks on the most frequently assigned supertags: 'vind', as indicated by the type ((np\s)/(np/np))/np is most often seen in constructions of the type 'find movies interesting', whereas the s type for 'zeg' is due to the frequently occurring interjection 'zeg maar', which corresponds roughly to 'so to say'.

Product types for long-distance dependencies are a frequent occurrence as well. Table 9 shows the three most frequent ones, with their number of occurrences, formula and (where possible) the corresponding product-less formula. Unsurprisingly, the two most frequently occurring formulas are the type of the relativizer, as extracted for words like 'die' (that) and the question type for Word Transl. the word 'krant' will be assigned the type np • 3 p 2 ↓ p np since it is considered to be the head noun of both conjuncts. From a type-logical point of view, this is not an entirely satisfactory solution, we would like to keep a simple np type in these cases and analyze the construction differently, for example along the lines proposed by [START_REF] Hendriks | Ellipsis and multimodal categorial type logic[END_REF]. However, it is unclear if we can keep the lexicon extraction fully automatic when reanalyzing these constructions in the treebank.

Freq. # st

Detecting Isolated Vertices Automatically

While we have cleaned up the training data using information from the syntactic annotation itself, it is useful to see how well we do if we perform this step using only the information we would have for the 8 million which have only part-of-speech tag information.

To verify if training with the filtered dataset has actually gained us something we performed the following final experiment. We repeated the Split extraction procedure, this time using the non-filtered corpus and divided this into a set of training data and test data. As before, every fifth sentence has been reserved for test data.

We trained three models using these data: one assigning supertags directly, one indicating only if a word is isolated or not and a final model using the filtered version of the training data. Our goal is to compare the performance of the first model against the two others applied in series. That is to say: a word correctly tagged as isolated is considered to have the correct tag, a word incorrectly tagged as isolated is considered to have an incorrect tag and a word tagged as non-isolated is considered to have the correct tag if the model trained on the filtered corpus produces the correct result for it.

For deciding whether a word is an isolated vertex in the graph or not, a simple experiment was performed, using only word and part-of-speech tag information of the current word and the two words preceding and following it. Additionally, we used information about words which are labeled as being broken off or a repeat of the current word or part-of-speech tag in the previous five words. This simply strategy received a 98.35% success rate on the test data.

Table 10 shows a comparison between the two strategies. We note that the performance on both tasks is better than the supertagging performance on the filtered corpus, even when we don't count interpunction symbols. This is because, as already noted in Section 3.2, word categories like hesitation marks 'uh' are almost always correctly tagged as isolated (in the combined experiment) or assigned the correct category based on their unigram information (in the non-filtered experiment).

We also note that the combined experiment performs slightly better than the direct method: filtering out words which do not contribute to the syntactic structure of the phrase means we get somewhat cleaner trigrams to train our models.

Finally, these experiments show it is possible to remove the isolated nodes from the corpus automatically, without negatively affecting the performance.

Comparison

Chen & Vijay-Sjanker (2000) propose a method of automatically extracting LT-AGs from the Penn treebank and investigate the effect of different extraction strategies. Their results appear to be a bit better than the results presented here, between 77.79% and 78.90% depending on the extraction strategy, even though we obtain a more compact lexicon. It stands to reason, however, that these differences are due to spoken corpora being inherently more noisy.

Semiautomatically extracted supertag sets, as used by [START_REF] Clark | Supertagging for combinatory categorial grammar[END_REF], and manually crafted supertag sets, as used by [START_REF] Srinivas | Performance evaluation of supertagging for partial parsing[END_REF], appear to fare significantly better, producing both a more compact lexicon and better performance for supertag disambiguation, which suggests there is a trade-off to be made between manual effort and performance.

Figure 4 :

 4 Figure 4: Two derivations for the ambiguous sentence 'wie leest Proust'

Figure 5 :

 5 Figure 5: What is pitiful about it?

Figure 7 :

 7 Figure 7: Lexicon extraction: removing the WHQ node

Figure 9 :

 9 Figure 9: Final lexicon

  of positive opinion, unless ...'

Table 6 :

 6 Combined results of the different extraction procedures

		Formulas Result
	1 Basic	6,817	70.61%
	2 Compact	3,539	72.06%
	3 Split	2,201	77.13%
	4 Very compact	1,962	77.83%
	5 AB	1,761	77.52%
	6 LP	1,137	80.50%

Table 7 :

 7 All supertags which have been extracted over 1,000 times for finite verbs

	Formula	Occurrences Total Coverage
	1 (np\s)/(np\s)	9,487	14.66%
	2 (np\s)/np	9,401	29.18%
	3 np\s	7,187	40.28%
	4 (s/(np\s))/np	6,019	49.58%
	5 s/np	4,698	56.84%
	6 (np\s)/(np/np)	3,893	62.85%
	7 (s/np)/np	3,050	67.57%
	8 np\(np\s)	1,660	70.07%
	9 (s/(np/np))/np	1,268	72.09%

Table 8 :

 8 All verb forms occurring more than 1,000 times

	Most Frequent

Table 10 :

 10 Comparison between the combined and the non-filtered supertaggers

	Experiment	Result
	Non-filtered, with interpunction	81.26%
	Non-filtered, without interpunction	78.85%
	Combined supertagger, with interpunction	81.50%
	Combined supertagger, without interpunction 79.11%

Conclusions

We have seen how we can automatically extract a type-logical treebank from the CGN syntactic annotation. Depending on the level of detail we choose to maintain in our lexicon, the number of different formulas varies between 6.817 and 1.137, whereas the correctness of supertag disambiguation varies between 72.06 and 80.50%.


EDITORIAL

Picturing the brain from different perspectives: the neuroimaging of early AD

The last 150 years have witnessed dramatic improvements in the field of what we now call Neuropsychology. The description of the clinical and cognitive signs of specific brain diseases, as well as our understanding of normal brain function have been considerably improved, thanks to research ranging from anatomoclinical studies to experimental psychology paradigms applied both to patients with brain lesions and to healthy subjects. In the field of dementia, since Dr Alois Alzheimer presented his first case of the eponymous disorder [START_REF] Alzheimer | Uber eine eigenartige Erkrankung der Hirinde[END_REF][START_REF] Jucker | Alzheimer: 100 Years and Beyond[END_REF]) roughly a century ago, studies of Alzheimer's disease (AD) have allowed us to characterize the cognitive deficits associated with this neurodegenerative disease far more accurately, thereby improving its diagnosis. These studies have also informed the modelling of memory [START_REF] Eustache | MNESIS: Towards the Integration of Current Multisystem Models of Memory[END_REF] and other cognitive functions, such as language, executive functions, control of behaviour and social cognition [START_REF] Hodges | Alzheimer's centennial legacy: origins, landmarks and the current status of knowledge concerning cognitive aspects[END_REF]. Research in this area has had a chequered history, with a sixty-year period of relative indifference giving way to a sudden wave of enthusiasm in the early 1980s, bringing together scientists from many disciplines and generating a huge amount of knowledge with a considerable societal impact.

Cognitive neuropsychology has been the driving force behind this reawakening of interest, allowing for a better understanding of the preserved and impaired cognitive processes/systems in the very early stages of different neurodegenerative diseases, through highly informative and comparative approaches. We now know, for instance, that AD is typically characterized by early and marked deficits in episodic memory, whereas other memory systems (such as procedural memory) remain relatively preserved until a far later stage in the disease [START_REF] Heindel | Neuropsychological evidence for multiple implicit memory systems: a comparison of Inserm -EPHE -Université de Caen Basse Normandie Unité de Recherche U923 Centre Cyceron Bd H. Becquerel[END_REF]. Regarding episodic memory, detailed neuropsychological assessments have revealed that deficits not only concern the retrieval of information, but also its encoding [START_REF] Gainotti | Some aspects of memory disorders clearly distinguish dementia of the Alzheimer's type from depressive pseudo-dementia[END_REF]. By contrast, memory decline related to normal ageing would appear to stem mainly from retrieval difficulties. These contrasting profiles of memory deficits are particularly important, as they may make it easier to distinguish between normal and pathological ageing. A better understanding of the very early cerebral and cognitive impairments and their mechanisms would contribute to earlier diagnosis of AD and lead to fresh developments in therapeutic intervention strategies. As such, it would constitute a decisive breakthrough from a social, financial and scientific standpoint.

Over the last thirty years, the field of neuropsychology has witnessed considerable developments in cognitive assessments, with the introduction of computerized techniques and virtual reality, together with the emergence of anatomical and functional neuroimaging methods. This decisive shift in methodologies has been parallelled by an impressive growth in our knowledge about cerebral impairments related to brain diseases, including AD. As the disease progresses, the brain changes: it becomes atrophied, its metabolism declines, its resting-state and task-induced activity drops, amyloid deposits accumulate, brain alpha rhythm amplitude decreases, cholinergic neurotransmission is impaired, etc.

Interestingly, AD-associated changes are not solely characterized by declines, as there are also signs that the brain puts up varied forms of resistance to this attack. There is evidence of increased brain activity in some areas, upregulation of certain neurotransmission systems and additional recruitment of relatively preserved brain regions that may reflect compensatory attempts. Over and above the fact that this brings a positive message amidst all the doom and gloom of the pathological events, these enhancements are particularly interesting, as they represent the brain's natural and ecological defence mechanisms in response to injury, which could inspire future pharmacological or nonpharmacological interventions. Moreover, they provide useful information about the physiological mechanisms of brain function and plasticity. Thus, despite the shift in methodologies, neuropsychology continues to pursue the same target as ever, studying brain pathology in order to gain a better understanding not only of the diseased brain but also of normal brain function.

This special issue focuses on early AD, with the specific objective of highlighting the way in which different yet complementary neuroimaging approaches each offer invaluable insight into AD-related brain changes. Although it does not claim to be exhaustive, it does seek to provide a comprehensive overview of the disease, presenting a wide range of points of view via different neuroimaging techniques, from the earliest and most widely-used methods employed to study cognitive deficits, such as EEG, structural and functional MRI and resting-state FDG-PET, to more recent techniques such as diffusion tensor imaging, novel ways of using tried and tested techniques and new data analysis methods, allowing us to explore neuronal integrity and connectivity, specific neurotransmitter systems, and amyloid plaque and tau tangle deposition.

Thus, the profile of early brain atrophy and its progression over the course of AD are detailed in the review by Apostolova et al., as This attempt to provide an overview of the various manifestations of the disease is just the start of efforts to fit together the different pieces of the jigsaw puzzle in order to gain a more complete picture of the disease that may help us to understand its underlying mechanisms. Following the era in which the emphasis was very much on describing the clinical, cognitive and behavioural signs of the disease, the last two decades have been marked by the incredibly rapid development of neuroimaging techniques and the gradual establishment of relationships between neuroimaging and cognitive manifestations. The time has now come to combine complementary neuroimaging findings. While there have already been some tentative attempts at an integrative model (e.g. [START_REF] Buckner | Molecular, structural, and functional characterization of Alzheimer's disease: evidence for a relationship between default activity, amyloid, and memory[END_REF], longitudinal multimodal studies are now needed if we are to enhance our understanding of these AD-related changes still further and effectively gauge the impact of new and promising treatments.

  well as in the original papers by Chételat et al., detailing hippocampal changes, and Schott et al., assessing the correlations with neuropsychological decline. Resting-state FDG-PET changes and their relationship with cognitive deterioration are described in the review by Salmon et al. and the study by Giffard et al., while Herholz et al. present an overview of the impairment of cholinergic neurotransmission in the very early stages of AD. The review by Dickerson and Sperling focuses on fMRI findings for the hippocampus in early AD, tackling the notion of compensation, while the original contribution from Trivedi et al. investigates the effect of AD risk factors on brain activity, analyzing fMRI data from a large sample of cognitively healthy individuals. Liu et al.'s review and Persson et al.'s study focus on the effect of AD on the default-mode network, adopting several different approaches, including deactivations, resting-state fMRI, functional connectivity and synchrony, illustrating the wealth of this recently developed and extremely promising topic. Structural connectivity impairments due to AD are studied using diffusion tensor imaging in the paper by Fellgiebel et al., while the original contribution from Babiloni et al. introduces the area of EEG research and illustrates the potential of multimodal neuroimaging approaches. Last but not least, the exciting developments in PET amyloidimaging tracers are explored in the review by Nordberg et al. and in the original research by Villemagne et al., which highlights the relationship between amyloid deposition and cognitive change.


Danyao Wang
email: wangda@eecg.toronto.edu

Natalie Enright Jerger

J Gregory Steffan
email: steffan@eecg.toronto.edu

DART: Fast and Flexible NoC Simulation using FPGAs

Introduction

A packet-switched network-on-chip (NoC) is becoming a more compelling choice for the communication backbone in next-generation multicores and systems-on-chip [START_REF] Dally | Route packets, not wires: onchip interconnection networks[END_REF]. NoC designs are sensitive to many parameters such as topology, buffer sizes, routing algorithms, and flow control mechanisms. Hence, system architects and researchers must include detailed NoC simulation as part of any complete system simulation. However, detailed NoC simulation adds to the already burdensome computation required to accurately perform full-system evaluation.

NoCs are normally simulated in software, as standalone NoC simulators [START_REF] Dally | Principles and Practices of Interconnection Networks[END_REF], [START_REF] Puente | SICOSYS: an integrated framework for studying interconnection network performance in multiprocessor systems[END_REF] and also as the interconnect component of large full-system simulators [START_REF] Agarwal | GAR-NET: A detailed on-chip network model inside a fullsystem simulator[END_REF], [START_REF] Hardavellas | Simflex: a fast, accurate, flexible fullsystem simulation framework for performance evaluation of server architecture[END_REF]. Software NoC simulators have the advantages of being very flexible, easy to program, fast to compile, and deterministic (making them suitable for debugging). However, software simulators are very slow for large NoCs, and can require the user to reduce simulation detail to maintain reasonable simulation times.

Several FPGA-based NoC emulators have been proposed [START_REF] Genko | A complete network-onchip emulation framework[END_REF], [START_REF] Krasteva | A Fast Emulation-Based NoC Prototyping Framework[END_REF], [START_REF] Schelle | Onchip interconnect exploration for multicore processors utilizing FPGAs[END_REF], [START_REF] Wolkotte | Fast, Accurate and Detailed NoC Simulations[END_REF] that reduce simulation time by several orders of magnitude. These dramatic speedups are possible because the emulator is typically implemented by laying out the entire NoC on the FPGA, allowing the FPGA to exploit all available fine and coarse grain parallelism between events in the NoC. However, mapping the simulated NoC directly onto the FPGA has three key drawbacks: (i) any change in the simulated NoC requires manual redesign of the emulator HDL, (ii) redesign in turn requires complete compilation/synthesis of the FPGA design (which can take hours, or up to a day for a large design), and (iii) the maximum simulatable NoC size is determined by the available FPGA capacity.

A Flexible NoC Simulation Engine:

To address these challenges we propose DART, an FPGA-based NoC simulation engine where the simulated NoC and the architecture of DART are decoupled and independent. In this paper, we present an implementation of DART on a Virtex 2 Pro FPGA, demonstrating: (i) an overlay engine that provides software-like accessibility to the FPGA, allowing different NoC architectures to be simulated without recompiling/resynthesizing the DART engine; and (ii) over 300× speedup over the cycle-based software simulator Booksim [START_REF] Dally | Principles and Practices of Interconnection Networks[END_REF], while maintaining the same level of simulation accuracy.

Related Work

Genko et al. [START_REF] Genko | A complete network-onchip emulation framework[END_REF] describe an emulation platform that consists of programmable traffic generators and receptors that drive a 6-switch NoC and is 2600× faster than a SystemC simulation of the same network. While this platform supports programmable traffic patterns and statistics counters, changing the configuration of the network requires re-generating the emulator. DRNoC [START_REF] Krasteva | A Fast Emulation-Based NoC Prototyping Framework[END_REF] circumvents this requirement by leveraging the partial reconfigurability of Xilinx FPGAs. The DRNoC host FPGA is divided into grids; each grid slot can be dynamically reconfigured to implement a new component to model different networks. However, partial reconfiguration requires a special design flow and incurs area overheads; it's also only available for select devices. In contrast, DART's configuration interface is based on a generic shift register and can be implemented on any FPGA.

NoCem [START_REF] Schelle | Onchip interconnect exploration for multicore processors utilizing FPGAs[END_REF] improves emulation density over Genko et al.'s design [START_REF] Genko | A complete network-onchip emulation framework[END_REF] and implements a 9-node mesh network on a single FPGA by eliding the router pipeline details and virtual channels. Instead of sacrificing these important details, we employ a simple design for each DART Router: each has multiple input ports but only one output port, and models the all-to-all switching in a simulated router by routing one input port per DART cycle.

Wolkotte et al. [START_REF] Wolkotte | Fast, Accurate and Detailed NoC Simulations[END_REF] virtualize a single router on an FPGA, allowing the simulation of a NoC with multiple routers. An off-chip ARM processor stores N contexts for the router model and orchestrates the emulation of the N-node network. This approach allows the router model to be much more detailed. However, the off-chip ARM/FPGA communication link is a performance bottleneck. DART is implemented entirely on-chip and does not suffer from this bottleneck.

DART Architecture

A basic NoC simulation requires that flits be forwarded around the network while modeling the timing of flit transfers. In DART we abstract the components of a NoC into three primitive types: Flit Queues (FQs), Traffic Generators (TGs), and Routers. In the DART architecture (Figure 1), each node contains FQs, a TG, and a Router, although the TG may or may not be used. Nodes are grouped into partitions that are interconnected by a crossbar, allowing all-to-all communication between any node pairs. DART simulates a NoC by mapping the simulated NoC to DART nodes, and restricts the communication pattern through the interconnect to model the connectivity of the simulated topology. Each DART node has parameters that can be configured to match the properties of the component they simulate, without modifying the DART HDL.

To capture the timing of flit transfers, we define a time step as a flit cycle in the simulated NoC. A global counter keeps track of current simulation time, and is only incremented when all flit transfers for this time step are performed. A time step may take multiple DART cycles to simulate. This virtualization of time allows DART to trade speed for area efficiency.

We use flit and credit descriptors to model the traffic within the simulator. The 32-bit flit descriptor contains (i) the metadata for routing and flow control, (ii) a timestamp that indicates when the flit should be forwarded to the next node, and (iii) the injection time to compute latency at the destination. The 11-bit credit descriptor only contains a timestamp and a VC identifier. A flit's lifetime starts when it is injected at a TG. It is then alternately forwarded between FQs and Routers until it is received at the destination.

Flit Queue

The Flit Queue (FQ) component models the bandwidth and latency constraints of a wire link. Each FQ encapsulates multiple virtual channels (VCs). The VC buffers are implemented using a block-RAM that is statically partitioned among the VCs. A Verilog parameter controls the number of VCs to incorporate (set to two for this paper). Each incoming flit is queued according to its VC and the new dequeue timestamp is computed using the following algorithm: Here N through counts the number of flits through the FQ during a time step. T lastf lit is the dequeue timestamp of the previous flit less the link latency. The latency and bandwidth parameters are configurable on a per-FQ basis.

Traffic Generator

When enabled, the Traffic Generator (TG) component injects packets using a Bernoulli process. Packet size (minimum 2 flits), destination node address, and the average injection interval are configurable per-TG. TGs also serve as traffic sinks. They record the number of packets received and the cumulative packet latency. Each TG contains two FQs; the input buffer models the last-hop delay to the TG, and the output buffer models the source queue. We use the same technique from Dally et al. [START_REF] Dally | Principles and Practices of Interconnection Networks[END_REF] and allow a TG to lag behind the current simulation time when its output buffer is full, to model an infinite source queue.

Router

The Router component models a canonical five-stage wormhole VC router with credit-based flow control [START_REF] Dally | Principles and Practices of Interconnection Networks[END_REF]. The number of ports is controlled by a Verilog parameter, set to five for this paper. Each Router connects to four FQs that model per-port input buffers and one TG. Table-based routing is used, and the table content is configurable for each Router without reprogramming the FPGA. In contrast to a real 5-ported wormhole router, the Router component forwards one flit per DART cycle. A time step is simulated by iterating over all ready input FQs and processing them sequentially over multiple DART cycles. Meanwhile, the global time counter is stalled so all flits appear to be routed in the same time step. By doing so, we can use simple arbiters to simulate the switch allocator and the crossbar, which constitute a significant portion of the area in a real router. Head-of-line blocking can arise if the selected input VC cannot be routed due to failed VC allocation or lack of credits. We solve this by setting an inspected flag for the offending VC so it is not selected again until the next time step. This creates a bubble in the Router pipeline and wastes a DART cycle.

Pipeline latency of the simulated router is modeled by incrementing the flit timestamp when it leaves the Router; this value is configurable per Router. Contention in VC and switch allocation are also modeled by adjusting the timestamp appropriately.

Credit-based flow control is implemented using a credit counter for each output VC, for which initial credit values are configurable. When a flit is routed, the output VC's counter is decremented, and a credit is sent to the corresponding input FQ of the upstream Router through the global interconnect. The corresponding is updated when the credit is received.

3.4.

The global interconnect provides all-to-all communication between DART nodes. By restricting the actual communicating pairs in the routing tables, DART can simulate any regular or irregular topology, provided the maximum node radix is less than the number of input ports in the Router component. Although a crossbar is a first intuition, its area increases quadratically with network size which can be expensive as DART's size increases. Instead, DART nodes are grouped into partitions and interconnected by a concentrated crossbar (Figure 2). Both intra-and inter-partition arbitrations use the three LSBs of the flit timestamp as priority to guarantee chronological simulation of flit transfers. The partitions are the main throughput bottleneck of the interconnect since each partition can only send and receive one flit per DART cycle. Varying the degree of concentration trades crossbar area for performance. We currently use an 8 × 8 crossbar as it strikes a good area/performance balance. Section 4 discusses these trade-offs in more detail. Credit traffic uses a separate interconnect that is similar but narrower.

Configuration and Data Collection

As mentioned earlier, each DART node has configurable parameters (packet size, latency, bandwidth, etc.). With the exception of the routing tables, these parameters are chained in a 16-bit shift register. A software tool on the host PC sends the configuration bits over an RS232 serial interface. The block-RAMbased routing tables are connected to the input end of the shift register. An finite state machine captures a chunk of the configuration bits to populate the block-RAM. When configuration completes, an enable signal is asserted to start the simulation.

Similar to the configuration registers, a 16-bit shift register is used to read simulator output performance counters. We currently have three counters per TG to measure the number of injected and received packets and the cumulative packet latency. More counters can be easily added to this shift register chain. Since configuration and stats collection are only performed once before and after the simulation, the host PC-FPGA communication latency is not performance critical.

Using DART

We have automated the process of mapping a user's simulated NoC to DART. In the current implementation, the configuration management tool runs on a host PC and communicates with DART over an RS232 serial link. This interface is not performance critical, since it is only used for configuration, commands, and gathering results. We use a round-robin scheme to evenly distribute the simulated NoC nodes across the DART partitions-because the global interconnect is symmetric, balancing the load this way is sufficient to achieve good performance.

Evaluation

In this section, we quantify the trade-offs made in the design of DART and evaluate its performance by comparing with Booksim 2.0 [START_REF] Dally | Principles and Practices of Interconnection Networks[END_REF], which is widely used in NoC studies. The results presented are obtained using a cycle-accurate simulator of the DART architecture, which has been verified to be identical to our actual HDL implementation.

DART's simplified Router component allows a 9node DART engine to fit on a Virtex II Pro (XC2VP30) FPGA while modeling detailed VCs, wormhole routing, credit-based flow-control, and providing runtime configurability. However, there is a performance penalty because DART serializes the switching that is normally performed concurrently in a real router. Using the number of time steps simulated per DART cycle (SPC) as a performance metric, Figure 3 shows the Router component's impact on performance for two simple benchmarks. Both cases use 2 VCs, 5-flit VC buffers, and permutation traffic with 2-flit packets and flit injection rates between 0.1 and 0.8. While the ideal SPC is 1.0, we expect DART's achievable SPC to be inversely proportional to the average number of busy input ports per time step. This agrees with the figure, since DART's performance degrades gracefully with increased network load.

A second trade-off in DART is the use of the concentrated crossbar interconnect to allow the simulation of arbitrary topologies without modification to the DART HDL. The contention at the crossbar input and output ports is the main performance bottleneck. For a DART simulator with a fixed number of nodes, increasing the crossbar size alleviates this contention by reducing the size of the partitions. However, crossbar area grows quadratically with the number of ports. Figure 4 shows the scalability of various crossbar configurations for different DART sizes. Each data point is evaluated using a torus with permutation traffic. The results for the 4 × 8 and 8 × 16 configurations are not shown here because their performance is similar to that of the 8 × 4 and 16 × 8 configurations respectively. Relative to a square crossbar, doubling the number of either the input ports or output ports only improves performance slightly as the asymmetric configurations do not fully remove the contention due to concentration. Hence, the largest square crossbar that meets the area constraint should always be used, which is 8 × 8 for the FPGA hardware in use.

Our current implementation of the 9-node DART uses 13,050 slices (95% available) on the XC2VP30 FPGA and runs at 50 MHz. The critical path includes the logic that selects the earliest flits to cross the global interconnect. Using the same benchmarks as in Figure 3, we compare the number of milliseconds it takes DART and Booksim to simulate a time step. We measured Booksim's runtime on a 2.66 GHz Intel Core 2 Quad linux workstation and averaged the measurements over 20 runs. Both simulators simulated approximately 30K cycles and the reported average packet latencies agree within 5%. Figure 5a shows DART's speedup. The upward trend is because the 9-node benchmarks do not saturate the global interconnect even at high injection rates. As a result, DART's performance degrades more slowly than Booksim. Under similar network load, Booksim exhibits worse scaling than DART when network size increases (Figure 5b); however, the interconnect can become the bottleneck in larger DART systems, in which case additional network load results in declining speedup.

Conclusions and Future Work

In this paper, we introduced a flexible NoC simulation engine that provides software-like accessibility to the FPGA and achieves significant speedup over software simulators while maintaining the same level of accuracy. The DART simulator architecture is decoupled and independent from the simulated NoC and allows us to trade speed for programmability and area efficiency. Moving forward, we plan to add multiple contexts to each DART node to allow the user to further trade speed for simulated network capacity if necessary. It is also possible to integrate DART with a full system simulator by replacing the synthetic Traffic Generators with application or trace driven ones to enable comprehensive evaluation of the entire system.

Figure 1 .

 1 Figure 1. DART architecture. Each node models a 5-ported router, and nodes in the same partition share a crossbar port. The host PC communicates with the FPGA over a serial link.

Figure 2 .

 2 Figure 2. DART's 8 × 8 concentrated crossbar interconnect

  DART cycle (SPC) Avg. # of busy ports / sim cycle Injection rate (flits / node / sim cycle) DART cycle (SPC) Avg. # of busy ports / sim cycle Injection rate (flits / node / sim cycle) (b) 3x3 Mesh

Figure 3 .

 3 Figure 3. Performance impact due to the serialization in the Router component

Figure 4 .

 4 Figure 4. Performance impact of crossbar sizes

Figure 5 .

 5 Figure 5. Speedup of DART vs. Booksim