AN EFFICIENT GRAPH ALGORITHM FOR DOMINANCE CONSTRAINTS

Description

AN EFFICIENT GRAPH ALGORITHM FOR DOMINANCE CONSTRAINTS? ERNST ALTHAUS† , DENYS DUCHIER‡ , ALEXANDER KOLLER , KURT MEHLHORN† , JOACHIM NIEHREN‡ , AND SVEN THIEL† Abstract. Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify normal dominance constraints and present an efficient graph algorithm for testing their satisfiablity in deterministic polynomial time. Previously, no polynomial time algorithm was known. 1. Introduction. The dominance relation of a tree is the ancestor relation be- tween its nodes. Dominance constraints are logical descriptions of trees talking about the dominance relation. Dominance based tree descriptions were first used in automata theory in the six- ties [TW67], rediscovered in computational linguistics in the early eighties [MHF83], and investigated from a logical point of view in the early nineties [BRVS95]. Since then, they have found numerous applications in computational linguistics: they have been used for grammar formalisms [VS92, RVSW95, DT99, Per00], in natural lan- guage semantics [Mus95, ENRX98], and for discourse analysis [GW98]. The two most important computational tasks for dominance constraints are sat- isfiability testing – does the constraint describe a tree? – and enumerating solu- tions, i.e. the described trees. But as shown recently [KNT01], testing satisfiability is an NP-complete problem.

• variable names


• dominance constraints


• annotate variable


• let ?


• problem


• labeled variables


• normal dominance


• identify normal


• algorithm back


• graph algorithm

Sujets

• Problem
• List of algorithms

Informations

• Publié par: pefav
• Nombre de lectures: 10
• Langue: English

Extrait

AN EFFICIENT GRAPH ALGORITHM
FOR DOMINANCE CONSTRAINTS
y z x yERNST ALTHAUS , DENYS DUCHIER , ALEXANDER KOLLER , KURT MEHLHORN ,
z yJOACHIM NIEHREN , AND SVEN THIEL
Abstract. Dominance constraints are logical descriptions of trees that are widely used in
computational linguistics. Their general satis abilit y problem is known to be NP-complete. Here
we identify normal dominance constraints and present an e cien t graph algorithm for testing their
satis ablit y in deterministic polynomial time. Previously, no polynomial time algorithm was known.
1. Introduction. The dominance relation of a tree is the ancestor relation be-
tween its nodes. Dominance constraints are logical descriptions of trees talking about
the dominance relation.
Dominance based tree descriptions were rst used in automata theory in the six-
ties [TW67], rediscovered in computational linguistics in the early eighties [MHF83],
and investigated from a logical point of view in the early nineties [BRVS95]. Since
then, they have found numerous applications in computational linguistics: they have
been used for grammar formalisms [VS92, RVSW95, DT99, Per00], in natural lan-
guage semantics [Mus95, ENRX98], and for discourse analysis [GW98].
The two most important computational tasks for dominance constraints are sat-
is ability testing { does the constraint describe a tree? { and enumerating solu-
tions, i.e. the described trees. But as shown recently [KNT01], testing satis abilit y
is an NP-complete problem. Earlier attempts at processing dominance constraints
[Cor94, VSWR95, DN00] all su er from this fact. This has shed doubt on their
practical usefulness.
In this article, we identify normal dominance constraints, a natural subclass of
dominance constraints whose restrictions should be unproblematic for many applica-
tions. We present an e cien t graph algorithm that decides satis abilit y of normal
dominance constraints in deterministic polynomial time. Previously, no polynomial
time algorithm was known.
We derive the graph algorithm for testing satis abilit y as follows. First, we in-
troduce dominance graphs and de ne their con guration problem (investigated in
+[ADK 01]). Second, we show that the con gurabilit y of dominance graphs is lin-
ear time equivalent to the satis abilit y of normal dominance constraints ( rst shown
in [KMN00]). Third, we characterize the y of dominance graphs as the
absence of certain cycles, which we nally test for by reduction to a matching problem.
We also discuss how to use the e cien t satis abilit y test to enumerate solutions.
We apply a choice rule exhaustively while checking for satis abilit y after each step.
Both procedures have been implemented in C++ using the LEDA library [MN99] and
applied to scope ambiguities in natural language semantics in the CLLS framework
[ENRX98, EKN01, EKN02].
+This article joins the results from two conference publications [ADK 01] and [KMN00]. The
authors are partially supported by the IST Programme of the EU under contract number IST-
1999-14186 (ALCOM-FT), and by the Collaborative Research Centre (SFB) 378 of the Deutsche
Forschungsgemeinschaft.
yMax-Planck-Institute for Computer Science, Saarbruc ken, Germany
zProgramming Systems Lab, Fachbereich Informatik, Universit at des Saarlandes, Saarbruc ken,
Germany
xDepartment of Computational Linguistics, Universit at des Saarlandes, Saarbruc ken, Germany
18x 9 y 2
! ^
linguist lang
x y
speak
x y
Fig. 2.1. A simple dominance constraint.
8x 9 y 2
! ^
linguist 9 y lang 8x 2
x ^ y !
lang speak linguist speak
x y x y
y x
Fig. 2.2. Readings represented by the constraint in Fig. 2.1.
To complement our results, we nally investigate a close variant of the con gura-
tion problem of dominance graphs where closed leaves are permitted in addition. This
variant is more general but also relevant for applications in computational linguistics
[Bos96, CFS97]. We show that con gurabilit y is already NP-complete for the more
general dominance graphs. Nevertheless, the presented algorithms can still help to
solve this alternative problem more e cien tly.
Plan of the paper. The rst part of the paper introduces dominance constraints:
We motivate using them in computational linguistics in Section 2; then we de ne
them in Section 3, discuss their satis abilit y problem, and introduce the concepts of
normal dominance constraints and of solved forms. In the second part of the pa-
per, we turn to a discussion of dominance graphs. We de ne them and relate them
to normal dominance constraints in Section 4. Section 5 presents a basic algorithm
for enumerating the solved forms of a dominance graph. Then we derive the above-
mentioned characterization of con gurabilit y in Section 6, show how to test for this
property e cien tly in Section 7, and plug this e cien t algorithm into the enumera-
tion algorithm in Section 8. In the nal part of the article, we apply this e cien t
enumeration algorithm back to normal dominance constraints and discuss an imple-
mentation (Section 9), and prove that the more general con gurabilit y with closed
leaves is NP-complete (Section 10). Section 11 concludes and discusses further work.
2. Motivation. As one of the many applications of dominance constraints in
computational linguistics, we will give a brief introduction to scope underspeci c ation
[EKN01, AC92, Rey93, Bos96].
This application is concerned with coping with ambiguous sentences such as the
following:
(2.1) Every linguist speaks two languages.
Sentence (2.1) is ambiguous because it has two di eren t possible meanings, indi-
cated by the continuations
(2.2) . . .namely, English and Chinese.
2say
john
9u 8w 9x 9y 8z
! ! ^ ^ !
comp ^ ^ ^ prod
dept repr spl
u z
w x y
in of see of
w u x w x y y z
Fig. 2.3. A dominance constraint describing the meaning of (2.6).
(2.3) . . .but not necessarily the same ones.
In the rst reading, each linguist must speak the same two languages. In the second, no
two linguists necessarily speak a common language, but each speaks at least two. We
can represent the two possible meanings logically as the following rst-order formulas,
which can be represented as trees as in Fig. 2.2.
(2.4) 8x:(linguist(x)!9 y:lang(y)^ speak(x; y))2
(2.5) 9 y:lang(y)^8x:(linguist(x)! speak(x; y))2
Ambiguity is a real problem to language processing because the number of read-
ings of a sentence grows quickly with the number of \quanti ers" such as \every
linguist" and \two languages", and interacts with other sources of ambiguity besides.
5The sentence (2.6) has already 56 readings, and larger examples are easy to construct.
(2.6) John says that some representative of every department in a company saw a
sample of each product.
The key observation to scope underspeci cation is that the di erences between
the readings are very systematic; all contain the same \semantic material" (e.g. repre-
sentations of the constituents \every linguist", \two languages", and \speak"), which
is only combined in di eren t ways. The constraints on these combinations can be
speci ed using dominance constraints.
An example is Fig. 2.1. This constraint graph is a description of the two readings
of (2.1), shown in Fig. 2.2; it can be seen as a graphical representation of a dominance
constraint. Similarly, the 56 readings of (2.6) can beted by the graph in
Fig. 2.3. In the paper, we will use constraint graphs to link the (logic) work on
dominance constraints to graph algorithms.
Pictures as in Fig. 2.3 are being drawn in most modern approaches to scope
underspeci cation. However, they are not always interpreted as dominance constraints
[Rey93, Bos96]. The subtle di erence in meaning has the surprising e ect of making
these other approaches NP-complete even when the graphs fall into the class where
dominance constraints have polynomial satis abilit y. We will show this in Section 10.
3. Satis abilit y of Dominance Constraints. In this section, we de ne the
the language of dominance constraints and recall known results on satis abilit y. The
variant of dominance constraints we employ describes constructor trees { ground
5The following sentence from [Hob83], which is interesting both in form and in content, has around
200 readings: \Many people feel that most sentences exhibit too few quanti er scope ambiguities for
much e ort to be devoted to this problem, but a casual inspection of several sentences from any text
should convince almost everyone otherwise."
3terms over a signature of function symbols { rather than feature trees as considered
in [Smo92, BRVS95, ST94, MNP00].
3.1. Trees and Constructor Trees. We assume a nite or in nite signature
with function symbols f; g; : : :, each of which is equipped with an arity ar(f) 0.
Constants are function symbols of arity 0 denoted by a; b. We assume that contains
at least one constant and one symbol of arity at least 2.
A constructor tree can be de ned either as a term or equivalently on the basis
of directed graphs. The ground term f(g(a; a)), for instance, corresponds to the
directed graph in Figure 3.1. Throughout this article, we will employ the graph based
de nition.
An (unlabeled) tree is a forest with