Search

We show how to compute readings of ambiguous natural language sentences that are minimal in some way. Formally, we consider the problem of computing, out of a set C of trees and a rewrite system R, those trees in C that cannot be rewritten into a tree in C. We solve the problem for sets of trees that are described by semantic representations typically used in computational linguistics, and a certain class of rewrite systems that we use to approximate entailment, and show how to compute the irreducible trees efficiently by intersecting tree automata. Our algorithm solves the problem of computing weakest readings that has been open for 25 years in computational linguistics.

The GIVE Challenge is a new Internet based evaluation effort for natural language generation systems. In this paper, we motivate and describe the software infrastructure that we developed to support this challenge.

We establish for the first time a formal relationship between dominance graphs, used for modeling semantics, and grammar formalisms with underspecified dominance links, used for modeling syntax. We present a translation of normal dominance graphs into Unordered Vector Grammars with Dominance Links (UVG-DL) and prove that the configurations of the dominance graph correspond to the derivation trees of the grammar. Moreover, the standard algorithms for both formalisms compute isomorphic charts.

In this paper, we translate sentence generation from TAG grammars with semantic and pragmatic information into a planning problem by encoding the contribution of each word declaratively and explicitly. This allows us to tap into the recent performance improvements in off-the-shelf planners. It also opens up new perspectives on referring expression generation and the relationship between language and action.

We present the first ever algorithm for solving unrestricted dominance graphs. The algorithm extends existing polynomial solvers for restricted classes of dominance graphs, which are not sufficient to model newer theories of scope ambiguity. Using the new solver, these theories now have access to an efficient solver for the first time. The solver runs in cubic time; for those graph classes that could be solved in the past, the runtime is reduced to the same quadratic time that the most efficient previous solvers achieved.

Would it be helpful or detrimental for the field of NLG to have a generally accepted competition? Competitions have definitely advanced the state of the art in some fields of NLP, but the benefits sometimes come at the price of over-competitiveness, and there is a danger of overfitting systems to the concrete evaluation metrics. Moreover, it has been argued that there are intrinsic difficulties in NLG that make it harder to evaluate than other NLP tasks (Scott and Moore, 2006).

Extensible Dependency Grammar (XDG; Duchier and Debusmann (2001)) is a recently developed dependency grammar formalism that allows the characterization of linguistic structures along multiple dimensions of description. It can be implemented efficiently using constraint programming (CP; Koller and Niehren 2002).In the CP context, parsing is cast as a search problem: The states of the search are partial parse trees, successful end states are complete and valid parses. In this paper, we propose a probability model for XDG dependency trees and an A-Star search control regime for the XDG parsing algorithm that guarantees the best parse to be found first. Extending XDG with a statistical component has the benefit of bringing the formalism further into the grammatical mainstream; it also enables XDG to efficiently deal with large, corpus-induced grammars that come with a high degree of ambiguity.

The constraint language for lambda structures (CLLS) is an expressive language of tree descriptions which combines dominance constraints with powerful parallelism and binding constraints. CLLS was introduced as a uniform framework for defining underspecified semantics representations of natural language sentences, covering scope, ellipsis, and anaphora. This article presents saturation-based algorithms for processing the complete language of CLLS. It also gives an overview of previous results on questions of processing and complexity. Liegt nicht vor.

Constraint programming is a programming paradigm that was originally invented in computer science to deal with hard combinatorial problems. Recently, constraint programming has evolved into a technology which permits to solve hard industrial scheduling and optimization problems. We argue that existing constraint programming technology can be useful for applications in natural language processing. Some problems whose treatment with traditional methods requires great care to avoid combinatorial explosion of (potential) readings seem to be solvable in an efficient and elegant manner using constraint programming. We illustrate our claim by two recent examples, one from the area of underspecified semantics and one from parsing.

Type and sort conflicts in semantics are usually resolved by a process of reinterpretation. Recently, Egg (1999) has proposed an alternative account in which conflicts are avoided by underspecification. The main idea is to derive sufficiently relaxed underspecified semantic representations; addition of reinterpretation operators then simply is further specialization. But in principle, relaxing underspecified representations bears the danger of overgeneration. In this paper, we investigate this problem in the framework of CLLS, where underspecified representations are expressed by tree descriptions subsuming dominance constraints. We introduce some novel properties of dominance constraints and present a safety criterion that ensures that an underspecified description can be relaxed without adding unwanted readings. We then apply this criterion systematically to Egg's analysis and show why its relaxation operation does not lead to overgeneration.