Regular Tree Grammars as a Formalism for Scope Underspecification

Proceedings of ACL-08: HLT, pages 218–226, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Regular tree grammars as a formalism for scope underspecification Alexander Koller∗ a.koller@ed.ac.uk ∗ University of Edinburgh Michaela Regneri† § regneri@coli.uni-sb.de † University of Groningen Stefan Thater§ stth@coli.uni-sb.de § Saarland University Abstract We propose the use of regular tree grammars (RTGs) as a formalism for the underspecified processing of scope ambiguities. By applying standard results on RTGs, we obtain a novel algorithm for eliminating equivalent readings and the first efficient algorithm for computing the best reading of a scope ambiguity. We also show how to derive RTGs from more tradi- tional underspecified descriptions. 1 Introduction Underspecification (Reyle, 1993; Copestake et al., 2005; Bos, 1996; Egg et al., 2001) has become the standard approach to dealing with scope ambiguity in large-scale hand-written grammars (see e.g. Cope- stake and Flickinger (2000)). The key idea behind underspecification is that the parser avoids comput- ing all scope readings. Instead, it computes a single compact underspecified description for each parse. One can then strengthen the underspecified descrip- tion to efficiently eliminate subsets of readings that were not intended in the given context (Koller and Niehren, 2000; Koller and Thater, 2006); so when the individual readings are eventually computed, the number of remaining readings is much smaller and much closer to the actual perceived ambiguity of the sentence. In the past few years, a “standard model” of scope underspecification has emerged: A range of for- malisms from Underspecified DRT (Reyle, 1993) to dominance graphs (Althaus et al., 2003) have offered mechanisms to specify the “semantic mate- rial” of which the semantic representations are built up, plus dominance or outscoping relations between these building blocks. This has been a very suc- cessful approach, but recent algorithms for elimi- nating subsets of readings have pushed the expres- sive power of these formalisms to their limits; for instance, Koller and Thater (2006) speculate that further improvements over their (incomplete) redun- dancy elimination algorithm require a more expres- sive formalism than dominance graphs. On the theo- retical side, Ebert (2005) has shown that none of the major underspecification formalisms are expres- sively complete, i.e. supports the description of an arbitrary subset of readings. Furthermore, the some- what implicit nature of dominance-based descrip- tions makes it difficult to systematically associate readings with probabilities or costs and then com- pute a best reading. In this paper, we address both of these shortcom- ings by proposing regular tree grammars (RTGs) as a novel underspecification formalism. Regular tree grammars (Comon et al., 2007) are a standard approach for specifying sets of trees in theoretical computer science, and are closely related to regu- lar tree transducers as used e.g. in recent work on statistical MT (Knight and Graehl, 2005) and gram- mar formalisms (Shieber, 2006). We show that the “dominance charts” proposed by Koller and Thater (2005b) can be naturally seen as regular tree gram- mars; using their algorithm, classical underspecified descriptions (dominance graphs) can be translated into RTGs that …

Content truncated to 500 words