there has been a steadily increasing interest in syntactic parsing based on dependency analysis in re cent years. one important reason seems to be thatdependency parsing offers a good compromise be tween the conflicting demands of analysis depth, on the one hand, and robustness and efficiency, on the other. thus, whereas a complete dependency structure provides a fully disambiguated analysisof a sentence, this analysis is typically less complex than in frameworks based on constituent analysis and can therefore often be computed determin istically with reasonable accuracy. deterministicmethods for dependency parsing have now been ap plied to a variety of languages, including japanese (kudo and matsumoto, 2000), english (yamada and matsumoto, 2003), turkish (oflazer, 2003), and swedish (nivre et al, 2004). for english, the interest in dependency parsing has been weaker than for other languages. to some extent, this can probably be explained by the strong tradition of constituent analysis in anglo-american linguistics, but this trend has been reinforced by the fact that the major treebank of american english,the penn treebank (marcus et al, 1993), is anno tated primarily with constituent analysis. on the other hand, the best available parsers trained on thepenn treebank, those of collins (1997) and charniak (2000), use statistical models for disambigua tion that make crucial use of dependency relations. moreover, the deterministic dependency parser of yamada and matsumoto (2003), when trained on the penn treebank, gives a dependency accuracy that is almost as good as that of collins (1997) and charniak (2000). the parser described in this paper is similar to that of yamada and matsumoto (2003) in that it uses a deterministic parsing algorithm in combination with a classifier induced from a treebank. however, there are also important differences between the twoapproaches. first of all, whereas yamada and matsumoto employs a strict bottom-up algorithm (es sentially shift-reduce parsing) with multiple passes over the input, the present parser uses the algorithmproposed in nivre (2003), which combines bottom up and top-down processing in a single pass in order to achieve incrementality. this also means that the time complexity of the algorithm used here is linearin the size of the input, while the algorithm of ya mada and matsumoto is quadratic in the worst case. another difference is that yamada and matsumoto use support vector machines (vapnik, 1995), whilewe instead rely on memory-based learning (daele mans, 1999). most importantly, however, the parser presented in this paper constructs labeled dependency graphs, i.e. dependency graphs where arcs are labeled with dependency types. as far as we know, this makesit different from all previous systems for dependency parsing applied to the penn treebank (eis ner, 1996; yamada and matsumoto, 2003), althoughthere are systems that extract labeled grammatical relations based on shallow parsing, e.g. buchholz (2002). the fact that we are working with labeled dependency graphs is also one of the motivations for choosing memory-based learning over sup port vector machines, since we require a multi-class classifier. even though it is possible to use svmfor multi-class classification, this can get cumber some when the number of classes is large. (for the the   ? dep finger-pointing   ? np-sbj has already   ? advp begun   ? vp . ?   dep figure 1: dependency graph for english sentenceunlabeled dependency parser of yamada and matsumoto (2003) the classification problem only in volves three classes.) the parsing methodology investigated here haspreviously been applied to swedish, where promis ing results were obtained with a relatively smalltreebank (approximately 5000 sentences for train ing), resulting in an attachment score of 84.7% and a labeled accuracy of 80.6% (nivre et al, 2004).1 however, since there are no comparable resultsavailable for swedish, it is difficult to assess the significance of these findings, which is one of the reasons why we want to apply the method to a bench mark corpus such as the the penn treebank, even though the annotation in this corpus is not ideal for labeled dependency parsing.the paper is structured as follows. section 2 describes the parsing algorithm, while section 3 ex plains how memory-based learning is used to guidethe parser. experimental results are reported in sec tion 4, and conclusions are stated in section 5.the conversion of the penn tree bank to dependency trees has been performed using head rules kindly provided by hiroyasu yamada and yuji matsumoto. there has been a steadily increasing interest in syntactic parsing based on dependency analysis in re cent years. experimental results are reported in sec tion 4, and conclusions are stated in section 5. sentences whose unlabeled dependency structure is completely correct (yamada and mat sumoto, 2003). one important reason seems to be thatdependency parsing offers a good compromise be tween the conflicting demands of analysis depth, on the one hand, and robustness and efficiency, on the other. the memory-based classifiers used in the experiments have been constructed using thetilburg memory-based learner (timbl) (daelemans et al, 2003). first of all, we see that model 1 gives better accuracy than model 2 with the smaller label set g, which confirms our expectations that the added part-of-speech featuresare helpful when the dependency labels are less informative. acknowledgements the work presented in this paper has been supportedby a grant from the swedish research council (621 2002-4207). all metrics except cm are calculated as meanscores per word, and punctuation tokens are con sistently excluded.table 1 shows the attachment score, both unla beled and labeled, for the two different state models with the two different label sets.