Regular Tree Grammars as a Formalism for Scope Underspecification
Koller, Alexander and Regneri, Michaela and Thater, Stefan

Article Structure

Abstract

We propose the use of regular tree grammars (RTGs) as a formalism for the underspecified processing of scope ambiguities.

Introduction

Underspecification (Reyle, 1993; Copestake et al., 2005; B08, 1996; Egg et al., 2001) has become the standard approach to dealing with scope ambiguity in large-scale handwritten grammars (see e. g. Copestake and Flickinger (2000)).

Underspecification

The key idea behind scope underspecification is to describe all readings of an ambiguous expression with a single, compact underspecified representation (USR).

Regular tree grammars

We will now recall the definition of regular tree grammars and show how they can be used as an underspecification formalism.

Expressive completeness and redundancy elimination

Because every finite tree language is regular, RTGs constitute an expressively complete underspecification formalism in the sense of Ebert (2005): They can represent arbitrary subsets of the original set of readings.

Computing best configurations

A second advantage of using RTGs as an underspecification formalism is that we can apply existing algorithms for computing the best derivations of weighted regular tree grammars to compute best (that is, cheapest or most probable) configurations.

Conclusion

In this paper, we have shown how regular tree grammars can be used as a formalism for scope underspecification, and have exploited the power of this view in a novel, simpler, and more complete algorithm for redundancy elimination and the first efficient algorithm for computing the best reading of a scope ambiguity.

Topics

treebank

Appears in 7 sentences as: treebank (8)
In Regular Tree Grammars as a Formalism for Scope Underspecification
  1. 2 compares the average number of configurations and the average number of RTG production rules for USRs of increasing sizes in the Rondane treebank (see Sect.
    Page 4, “Regular tree grammars”
  2. Computing the charts for all 999 MRS-nets in the treebank takes about 45 seconds.
    Page 4, “Regular tree grammars”
  3. For instance, the following sentence from the Rondane treebank is analyzed as having six quantifiers and 480 readings by the ERG grammar; these readings fall into just two semantic equivalence classes, characterized by the relative scope of “the lee of” and “a small hillside”.
    Page 4, “Expressive completeness and redundancy elimination”
  4. To measure the extent to which the new algorithm improves upon KT06, we compare both algorithms on the USRs in the Rondane treebank (version of January 2006).
    Page 5, “Expressive completeness and redundancy elimination”
  5. The Rondane treebank is a “Redwoods style” treebank (Oepen et al., 2002) containing MRS-based underspecified representations for sentences from the tourism domain, and is distributed together with the English Resource Grammar (ERG) (Copestake and Flickinger, 2000).
    Page 5, “Expressive completeness and redundancy elimination”
  6. The treebank contains 999 MRS-nets, which we translate automatically into dominance graphs and further into RTGs; the median number of scope readings per sentence is 56.
    Page 5, “Expressive completeness and redundancy elimination”
  7. In practice, we can extract the best reading of the most ambiguous sentence in the Rondane treebank (4.5 x 1012 readings, 75 000 grammar rules) with random soft edges in about a second.
    Page 8, “Computing best configurations”

See all papers in Proc. ACL 2008 that mention treebank.

See all papers in Proc. ACL that mention treebank.

Back to top.

semantic representations

Appears in 4 sentences as: semantic representation (1) semantic representations (3)
In Regular Tree Grammars as a Formalism for Scope Underspecification
  1. In the past few years, a “standard model” of scope underspecification has emerged: A range of formalisms from Underspecified DRT (Reyle, 1993) to dominance graphs (Althaus et al., 2003) have offered mechanisms to specify the “semantic material” of which the semantic representations are built up, plus dominance or outscoping relations between these building blocks.
    Page 1, “Introduction”
  2. We can now use regular tree grammars in underspecification by representing the semantic representations as trees and taking an RTG G as an underspecified description of the trees in L(G).
    Page 3, “Regular tree grammars”
  3. Koller and Thater (2006) define semantic equivalence in terms of a rewrite system that specifies under what conditions two quantifiers may exchange their positions without changing the meaning of the semantic representation .
    Page 4, “Expressive completeness and redundancy elimination”
  4. Expressions of natural language itself are (extremely underspecified) descriptions of sets of semantic representations , and so Ebert’s argument applies to NL expressions as well.
    Page 6, “Expressive completeness and redundancy elimination”

See all papers in Proc. ACL 2008 that mention semantic representations.

See all papers in Proc. ACL that mention semantic representations.

Back to top.