New developments in parsing technology. Selected papers based on the contribution to the 6th international workshop on parsing technology, IWPT 2000, Trento, Italy, February 23--25, 2000, and the 7th international workshop on parsing technology, IWPT 2001, Beijing, China, October 17--19, 2001. (Q705706)

This book is based on selected contributions at two consecutive meetings of the ``International Workshop on Parsing Technology'' (IWPT), held in Trento, Italy (IWPT2000) and Beijing, China (IWPT2001). The volume contains 19 papers (chapters), grouped in five main topics (that we shall call parts). The starting, pilot Chapter 1: Developments in parsing technology: from theory to application, belongs to the editors: Harry Bunt, John Carroll, and Giorgio Satta. The next four chapters constitute Part I, devoted to statistical parsing. Chapter 2: Parameter estimation for statistical parsing models: theory and practice of distribution-free methods (Michael Collins), addresses the fundamental problem in statistical parsing: that of choosing criteria and algorithms to estimate the parameters of a model. Chapter 3: High precision extraction of grammatical relations (John Carroll and Ted Briscoe), describes a parsing system that uses a manually constructed wide-coverage grammar of English to produce syntactic analyses in the form of sets of grammatical relations. Chapter 4: Automated extraction of TAGs from the Penn treebank (John Chen and K. Vijay Shanker), presents new directions in both the extraction of a Lexicalized Tree Adjoining Grammar (LTAG) from a treebank, and in its application to statistical parsing models. Chapter 5: Computing the most probable parse for a discontinuous phrase-structure grammar (Oliver Plaehn), presents a probabilistic extension of Discontinuous Phrase-Structure Grammar (DPSG) and an agenda-based chart parser that is capable of computing the most probable parse for a given input sentence for probabilistic versions of both DPSG and Context-Free Grammar (CFG). Part II groups the next six chapters under the topic of new parsing techniques for various extensions of CFGs, including TAG (Tree Adjoining Grammar) and HPSG (Head-driven Phrase Structure Grammar) frameworks. E.g., in many domains, the neural networks became an effective alternative to statistical methods. Chapter 6: A neural network parser that handles sparse data (James Henderson), identifies suitable neural architecture for natural language (NL) parsing, called Simple Synchrony Networks (SSNs) whose computing performance results are favourably compared on the same dataset with standard parsing methods. Chapter 7: An efficient LR parser generator for TAG (Carlos A. Prolo), proposes a new version of the LR parsing algorithm that succeeds to reduce significantly the average number of conflicts per state and the size of the table. Chapter 8: Relating tabular parsing algorithms for LIG and TAG (Miguel Alonso, Éric de la Clergerie, Víctor Díaz and Manuel Vilares), defines several parsing algorithms for TAGs on the basis of their equivalent parsers for Linear Indexed Grammars (LIGs). Chapter 9: Improved left-corner chart parsing for large CFGs (Robert C. Moore), presents an improved left-corner chart parser for large CFGs (over 24,000 rules), compiled from a task-specific unification grammar that can be used as a speech recognition language model. Chapter 10: On two classes of feature paths in large-scale unification grammars (Liviu Ciortuz), studies two related techniques for speeding up parsing with large-scale typed unification grammars, using a compiled-based parsing system on an HPSG grammar of English (LinGO project), showing an improvement in parsing speed up to 56\%. Chapter 11: A context-free approximation of HPSG (Bernd Kiefer and Hans-Ulrich Krieger), presents a CF approximation of unification-based grammars (such as HPSG and PATR-II), generalizing from lexical entries and abstracting by a `lexicon restrictor'. Applied to the English Verbmobil grammar, the proposed approach reports promising results. Part III contains three chapters, strongly oriented on theoretical linguistics topics. Chapter 12: A recognizer for minimalist grammar (Hans Harkema), presents a recognizer for minimalist grammars [N. Chomsky; 1995], while Chapter 13: Range concatenation grammars (Pierre Boullier), introduces a new grammar formalism (Range Concatenation Grammars -- RCGs), with number of attractive features, with a (polynomial-time) parsing algorithm for RCGs and with its prototype implementation. Chapter 14: Grammar induction by MDL-based distributional classification (Yikun Guo, Fuliang Weng, and Lide Wu), devises a new learning algorithm, based on the Minimal Description Length (MDL) principle, which can automatically induce high-quality parsing-oriented grammar rules from a tagged corpus without any structural annotation. Part IV of this volume collects three chapters especially (while other ones are casually) devoted to parsing techniques for spoken language processing. Chapter 15: Optimal ambiguity packing in context-free parsers with interleaved unification (Alon Lavie and Carolyn Penstein Rosé), is concerned with the optimization of ambiguity packing for enhancing the efficiency of GLR* and LCFlex (left-corner chart) parsers. Chapter 16: Robust data oriented spoken language understanding (Khalil Sima'an), addresses the issue of the robustness of data-oriented parsing with a Dutch speech-based dialogue system. Chapter 17: SOUP: a parser for real-world spontaneous speech (Marsal Gavaldà), describes the SOUP parser, a stochastic, chart-based, top-down parser especially engineered for real-time analysis of spoken language with large, multi-domain semantic grammars. Finally, Part V encloses the last two chapters of the book, which are concerned with mathematical and engineering aspects of parsing technology. Chapter 18: Parsing and hypergraphs (Dan Klein and Christopher D. Manning), exposes a novel view on parsing, based on the observation that there is intuitively very little difference between (a) combining subtrees to form a tree; (b) combining hypotheses to form a tree; and (c) visiting all nodes of an arc in a directed hypergraph before traversing to a head node. In Chapter 19: Measure for measure: towards increased component comparability and exchange (Stephan Oepen and Ulrich Callmeier), discusses notable improvements that have been made in efficient processing of large HPSG-based grammars through representation and algorithmic techniques, analytical insights, and high-performance software. The cooperative work of several research groups evolved HPSG-based systems that can process medium-complexity sentences in English and German, in average parse times comparable to human reading time. This volume is of indispensable interest for researchers, graduate students and teachers working actively in the following areas: Computational (and Theoretical) Linguistics, Parsing Technology, Text and Speech Processing, Language Technology, Artificial Intelligence, Information and Cognitive Science.