The Constraint Language for Lambda Structures.
This paper presents the Constraint Language for Lambda Structures (CLLS), a first-order language for semantic underspecification that conservatively extends dominance constraints. It is interpreted over lambda structures, tree-like structures that encode -terms. Based on CLLS, we present an underspecified, uniform analysis of scope, ellipsis, anaphora, and their interactions. CLLS solves a variable capturing problem that is omnipresent in scope underspecification and can be processed efficiently.
Introduction
Underspecication is a recent approach to the issue of combinatorial
explosion caused by ambiguity. Its key idea is to derive a single, compact
description of all readings instead of the (exponential number
of) readings themselves. For as long as possible, later processing steps
operate on these descriptions; readings are only enumerated by need.
One type of ambiguity for which underspecication has been investigated
particularly well is scope ambiguity. Common to many recent
scope underspecication formalisms (Reyle, 1993; Muskens, 1995; Bos,
1996; Niehren et al., 1997b; Egg et al., 1998) is that they provide the
'semantic material' of which the description of the readings is built, plus
structural relations that constrain possible combinations of this mate-
rial. Dominance constraints, a tree logic which can express dominance
of nodes in a tree, are a very natural way for doing this. Muskens (1995)
was the rst to do this explicitly, but Reyle (1993) and Bos (1996) can
be subsumed under this kind of approach as well.
In this article, we show how to integrate a treatment of other linguistic
phenomena { in particular, anaphora and VP ellipsis { with
a scope underspecication formalism based on dominance constraints.
The interaction of these three phenomena has been considered before in
Crouch (1995) and Shieber et al. (1996). In our approach, it is modelled
by a conservative extension of the language of dominance constraints
c
2000 Kluwer Academic Publishers. Printed in the Netherlands.
Markus Egg, Alexander Koller, Joachim Niehren
by additional atomic formulas, viz., anaphoric binding constraints and
parallelism constraints. While the former are based on an idea by
Kehler (1993), the latter are formally equivalent to context unica-
tion as used in Niehren et al. (1997b), which was shown in Niehren
and Koller (1998). In addition, -binding constraints are introduced in
order to solve a capturing problem that appears in all dominance-based
underspecication formalisms.
The combination of all of these constraints, called CLLS (Constraint
Language for Lambda Structures), correctly describes many challenging
cases from the literature that exhibit interaction of scope, anaphora,
and ellipsis. In addition, its being an extension of dominance constraints
makes for some appealing dierences to existing formalisms
with comparable coverage: Unlike Shieber et al. (1996), the CLLS
analysis is completely order-independent; and in contrast to the QLF-
based analysis in Crouch (1995), it achieves a clean separation between
underspecied descriptions and the described readings.
The paper is structured as follows. In Section 2, we introduce the
phenomena under consideration and present the intuitions behind our
linguistic analysis without going into detail. Section 3 presents the formal
denitions of lambda structures and CLLS and lls in the formal
details that were omitted in Section 2. In Section 4, we extend the
analysis to more involved cases from the literature. Section 5 denes
a syntax/semantics interface that derives CLLS constraints on the basis
of a simple phrase structure syntax. In Section 6, we give a brief
overview over results on formal and computational aspects of CLLS.
Finally, Section 7 concludes and outlines directions for future work.
2. Elements of CLLS
This section introduces the three main phenomena considered in the
paper { scope, ellipsis, and anaphora { and the major concepts used
in their CLLS analyses. After discussing -structures and their correspondence
to -terms, we go through the phenomena and present the
intuitions underlying our analysis. The section does not even attempt
to be formally precise; the formal details are put section 3.
2.1. Lambda structures and lambda terms
The idea behind -structures is to represent a -term by a tree-like
graph; a node in a -structure corresponds to an occurrence of a sub-term
in the -term it represents. Consider e.g. the -term in (1), which
happens to represent one of the readings of (3) below:
The Constraint Language for Lambda Structures 3
(1)
(a workshop)(x
(every linguist)(y
(attend
We draw the corresponding -structure as the graph in (2). An
occurrence of a -abstraction corresponds to a node labelled by lam, an
occurrence of an application, to a node labelled by @, and an occurrence
of a bound variable, to a node labelled by var. Variable binding is
represented in a lambda structure by dashed arrows from the variables
to their binders. For instance, if we identify each node by its address,
i.e. the word of natural numbers that indicates the path from the root
to the node, the unique occurrence of x in (1) corresponds to the node
with the address 212 in (2); it binds the variable represented by the
node with the address 21212.
@
a  workshop
lam
@
@
every  linguist
lam  212
@
@
visit  var
var  21212
Note that variable names in a -term (such as x and y in (1)) are
not re
ected by the node labels of the corresponding -structure. Con-
sequently, a -structure represents a closed -term uniquely modulo
consistent renaming of bound variables (-equality).
Via the detour through -structures, we can use tree descriptions in
semantic underspecication: We simply talk about -structures in the
same way one usually talks about trees. The explicit binding relation is
important in that context because variable names may not be sucient
to ensure proper binding in a radically underspecied framework; we
will come back to this in a minute.
2.2. Scope
The rst class of phenomena we are concerned with is scope ambiguity,
as in the following sentence.
(3) Every linguist attends a workshop.
This sentence has two readings, which dier in a permutation of
quantiers only: Either the sentence means that there is one specic
workshop which every linguist attends, or it means that every linguist
attends a workshop, but not necessarily the same as the others. The
rst reading is represented by the -term in (1), and the second by (4):
4 Markus Egg, Alexander Koller, Joachim Niehren
(every linguist)(y
(a workshop)(x
(attend
Closer inspection reveals that (1) and (4), and hence their corresponding
lambda structures, are closely related. The lambda structures
are composed from the same tree-like subgraphs, corresponding to
the term fragments (every linguist)(x(:)), (a workshop)(y(:)), and
((attend x) y). But these fragments are composed in dierent order.
We can describe both lambda structures at once by specifying the
fragments and their relationships. Such a description is given in (5).
a  workshop
lam  X 3
@
attend  var
every  linguist
lam  X 7
Intuitively, description (5) is satised by all -structures into which
the graph in (5) can be embedded in such a way that no labelled nodes
of the graph overlap. Dotted edges in (5) signify dominance: Of the
two nodes they connect, the upper one must be above the lower one in
the lambda structure. The dashed arrows, for -binding, act like elastic
bands, which can be stretched indenitely without breaking.
The description leaves the relative ordering between the two quan-
tier fragments unspecied. But since both fragments dominate the
nuclear scope and, just like trees, -structures cannot branch in the
bottom-up direction, one of the two quantier fragments must dominate
the other. This situation is very common in scope underspecication.
Note that variable binders must always dominate their bound variables;
so the -binding relations, logically
entail the dominance relations, X 4   X 9 and X 8   X 9 . Inserting these
dominance edges in (5) only enhances readability.
In Section 3 we will give pictures like (5) a formal meaning as constraints
over -structures, i.e. logical formulas that are interpreted over
the class of -structures. Then nodes of the graph correspond to variables
denoting nodes of a -structure, whereas labels, edges, and arrows
correspond to various types of atomic constraints. In addition, such a
graphical description imposes implicit inequality constraints between
labelled nodes, which excludes proper overlap of fragments.
We have said that a description like (5) is satised by all lambda
structures into which they can be embedded. In particular, the lambda
The Constraint Language for Lambda Structures 5
structure may contain additional fragments that are not mentioned in
the description. This is a desired feature because we want to compute
with limited information that can in principle be augmented at any
later point; the fact that the information is complete must be expressed
independently. As long as one is only concerned with scope, one can
impose a general constructiveness restriction: each node in a lambda
structure that we describe must be denoted by a variable in the de-
scription. But constructiveness would be too strict for our treatment of
ellipses below and also for an underspecied account of reinterpretation
(Koller et al., 1999; Egg, 1999).
2.3. Ellipsis
The second phenomenon we treat is VP ellipsis. VP ellipsis interacts
with scope ambiguities, thus the treatment of both phenomena must be
integrated. In the framework presented in this article, this integration
simply amounts to adding further constraints on lambda structures.
For ellipses, we introduce parallelism constraints, which permit to
express structural equality between fragments of -structures. As an
example, consider the elliptical sentence (6):
Every man sleeps, and so does Mary.
The meaning of the target sentence so does Mary is exactly like
the meaning of the source sentence every man sleeps, except that the
source parallel element every man is replaced by the target parallel
element Mary. This can be modelled in two steps. First, we describe
the -structure for the source sentence, as in (7), and the -structure
for the target parallel element, as in (8).
every  man
lam
sleep  var
Mary  Y 2 lam
var
In any lambda structure described by these constraints, the semantics
for the source sentence will be below X 1 , and the semantics for the
target sentence will be below Y 1 . The -structure for the entire sentence
will be the conjunction of source and target sentence, like this:
The second step is to impose the parallelism constraint (10), which
says that the lambda structures for the source and target sentence (i.e.
6 Markus Egg, Alexander Koller, Joachim Niehren
below X 0 and Y 0 ) are equal, with the exception of the sub-lambda
structures representing the parallel elements (below X 2 and Y 2
Indeed, the intended semantic representation of (6), shown in (11),
simultaneously solves all constraints in (7), (8), (9), and (10).
@
@
every  man
lam
@
sleep  var
@
Mary  lam
@
sleep  var
This shows that ellipsis resolution can be reduced to solving constraints
over -structures.
Since proper names and quantier NPs can be parallel elements in an
ellipsis (as in (6)), our analysis requires type-raising of proper names;
the constant Mary in (8) corresponds to a -term of type hhe; ti; ti.
Where there is no ellipsis, proper names are freely analyzed as constants
of type e, as this simplies the presentation. To distinguish the two
analyses of proper names, we will capitalize the rst letter of label used
in the former; that is, the label for the type-raised analysis of proper
nouns is Mary and the one for the non-type-raised analysis, mary.
2.4. Anaphora
Anaphora are the nal class of phenomena we consider. In order to
represent anaphora, we extend our notion of -structures. Anaphora
are represented as nodes labelled by ana which are linked to their
antecedents by anaphoric links. We draw anaphoric links as dashed
arrows using straight lines. For instance, a representation of (12) is
shown in (13). For simplicity, we use a constant mother of here; we will
analyze the possessive dierently later.
liked his j mother.
@
say  @
@
like  @
mother of  ana  X 3
In the example, the two anaphoric links form a link chain. Link
chains go back to Kehler (1993, 1995); they have been worked out in
The Constraint Language for Lambda Structures 7
this setting by Xu (1998). This representation of anaphoric reference
can cope with a series of problematic cases from the literature, such as
strict/sloppy ambiguities, the many-pronouns puzzle (of which (12) is
the source clause), and cascaded ellipses.
2.5. The Capturing Problem
A major dierence between CLLS and other underspecication formalisms
is that variable binding is modelled by explicit -binding
arrows and not by variable names. This looks like an unnecessary
deviation from standard procedure, but it turns out that variable
names are inconvenient in the context of underspecication and become
completely unusable once we add parallelism.
Let us assume that variable binding is modelled by using variable
names; for instance, that we use new labels lam x and var x for each
object-level variable x. Now imagine that a binder lam x appears twice
in a description, and that there is a scope ambiguity between the two
occurrences. In this case, it would be unclear which the intended binder
of a node with label var x is; in each solution, the lower binder wins.
The obvious way to avoid this problem is to name all variables
apart when generating a description. But this restriction cannot be
maintained once parallelism comes into play. This is best illustrated by
corrections, as in the following example.
Hans knows every student. No, Manfred knows every student.
(15) is an underspecied description of the meaning of (14):
correct
@
@
every  student
lam x  X 1
@
@
know  var x  X 3
hans  X 2
@
@
every  student
lam x  Y 1
@
@
know  var x  Y 3
manfred  Y 2
In the analysis, we used the same variable name x in both binders.
This is necessary since in solving the parallelism constraint, we must
make X 1 correspond to Y 1 . If these two nodes carried dierent variable
names, we would have to soften the meaning of parallelism constraints
in that the labels of corresponding nodes need not be identical, but
only uniable in some sense; but this raises very dicult problems of
8 Markus Egg, Alexander Koller, Joachim Niehren
bookkeeping which variables have been identied with which. The only
feasible option is using the same variable name twice.
There are other problems, too. We have seen in Section 2.3 that
we cannot even maintain the constructiveness restriction on satisfying
lambda structures; parallelism may force us to copy material. But if we
do not require constructiveness, we can get (16) as a solution for
correct
@
every  student
lam x  X 1
@
@
every  student
lam x  Y 0@
@
know  var x  X 3
hans  X 2
@
every  student
lam x  X 0@
@
every  student
lam x  Y 1
@
@
know  var x  Y 3
manfred  Y 2
More precisely, the problem is that parallelism (not only for correc-
tions) may force us to copy binders, and if we cannot always rename
variables apart, we must enforce that copying variables does not break
the intended binding relations (as the one between X 1 and X 3 in (16)).
The problems with variable binding are real problems in the presence
of parallelism only; they can be avoided otherwise by naming variables
apart and requiring constructiveness, both of which is still slightly un-
pleasant. Modelling variable binding with an explicit binding relation
between nodes oers a clean solution to all of these capturing problems:
how much and what kind of material is added between a
variable and its binder, the binding relation can never be broken.
3. Syntax and Semantics of CLLS
Section 2 presented the general intuitions behind lambda structures.
We showed how to describe -structures and how to apply their descriptions
in an underspecied analysis of scope, ellipsis, and anaphora.
Now we give a rigorous denition of the constraint language for lambda
structure (CLLS), which we will use throughout the paper. We will start
with the semantic level by rst presenting tree structures, then move
over to lambda structures as an extension of tree structures. Once the
semantics is xed, a denition of a syntax to talk about it is simple.
The Constraint Language for Lambda Structures 9
3.1. Tree Structures
A tree corresponds to a unique tree structure in the same way that
a lambda structure relates to a unique -term modulo -equivalence.
Lambda structures are extended tree structures because -terms are
extended trees (trees plus variable binding).
Let  be a set of function symbols, f; g; a; b. Each function f symbol
comes with a xed arity. We write f k for a function symbol with arity
k  0. A (nite constructor) tree is simply a ground term (without
variables) built from a set of function symbols. For instance, f(g(a; a))
is a tree built from function symbols f Taking IN to be the
set of natural numbers starting at 1, we can dene a path as a word
over IN . We identify each node of a tree with the path from the root
to this node; the empty word, , identies the root. Paths are named
with lowercase Greek letters, such as Concatenation of
words  and  is written as , and a word  is a prex of  i there
is a word  1 such that
A tree structure is a rst-order model structure which characterizes
a tree. The domain of a tree structure contains all nodes of the corresponding
tree, and its relations specify labelling and childhood. E.g.,
the domain of the tree structure for f(g(a; a)) is f; 12g. The fact
that the root  is labelled with f and has a single child 1 is expressed by
a relation we write as :f(1); the children and labels of the remaining
nodes are specied by the relationships 1:g(11; 12), 11:a, and 12:a.
More generally, a tree domain  is a nite nonempty set of nodes
which is prexed-closed (that is,  2  implies  2 ) and closed
under left siblings (i.e. if i 2  then j 2  for all 1  j < i), and a
tree structure is dened as follows:
DEFINITION 3.1. A tree structure over  consists of a tree domain
IN  and a relation :f   n+1 for each n-ary function symbol
, such that for all nodes  2  and the maximal n 2 IN with
there is a unique symbol f n 2  such that
Given nodes
This relation expresses that  0 is a node of
the tree structure with the label f and the children  , in this
order. Note that two nodes may be labelled by the same constant
without being equal. The condition in the denition means that the
number of children of a node is specied by the arity of its label.
Markus Egg, Alexander Koller, Joachim Niehren
3.2. Lambda Structures
A -structure extends a tree structure with two additional relations for
-binding and anaphoric links. For -structures, we assume:
DEFINITION 3.2. A -structure over  consists of a tree structure
over  with tree domain  and two additional binary relations  and
ante on  which satisfy the following properties.
1.    is a partial function that maps every node  2  with
label var to a prex of  which is labelled with lam.
2. ante   is a partial function that maps every node with label
ana to another node.
The lambda structures we are interested in here have additional
properties, which we have not included in the denition because they
are not essential for what follows. For instance, there are no cyclic
anaphoric link chains, and if a link chain ends at a node with label var,
then each node in the chain (all of which are labelled by ana) must be
below the binder of that var-labelled node.
We draw lambda structures as tree-like graphs. E.g., the binding and
anaphoric linking functions of the lambda structure (17) are specied
by 1. Note that we annotate only those
nodes with addresses in the picture that we want to refer to.
@
@
like  ana  2112
var  212
Lambda structures and -terms can almost be mapped to each other
one-to-one. The two exceptions are that lambda structures do not mention
variable names and that lambda structures contain anaphoric links.
We do not elaborate on the further interpretation of anaphoric links
roughly, they express that the interpretation of the last element
of the link chain determines the interpretation of all other elements of
the chain.
The Constraint Language for Lambda Structures 11
3.3. Dominance and Parallelism
Finally, we conservatively extend lambda structures by two additional
relations between nodes: dominance and parallelism. These relations
were not included in the original denition as they can be dened from
the relations specied there; but they are essential for the application.
Let  be a -structure and ;  two of its nodes. We say that
dominates  (  ) if it lies above it, i.e. if  is a prex of . The
dominance relation is a partial order on the domain of , i.e. re
exive,
transitive, and antisymmetric.
For the denition of parallelism, we rst dene for any two nodes
in  the context of  below  in  as the set of nodes of  which
are dominated by , but not by . Intuitively, the context of  below
is the set of nodes 'between'  and . Taking the labelling relations
of  into account, a context looks almost like a tree domain starting
at , except that one node (the mother of ) has one too few children.
Based on this intuition, we call  the root of the context and  its hole.
Intuitively, the parallelism  holds for a -structure
if  imposes parallel structures on the contexts between  1 and  1 and
between  2 and  2 . As it must also specify what it means for binding
and anaphoric linking to be parallel, however, the following denition
of the relation is rather involved.
DEFINITION 3.3. Let  be a -structure over  and  1
nodes of its domain . Parallelism  holds in  i there
are subsets  1 ;  2   and a bijective correspondence function c :
such that P1{P6 are satised.
P1 For 2g, the set  i is the context  i below  i in :
and not  i   g
P2  imposes parallel tree relations on  1 and
In particular, this enforces that c( 1 (that is, the holes correspond
to each other) and that for all  2 IN  ,  1  2  1 [f 1 g )
(that is, corresponding nodes can be reached over the
same path from the roots of their respective contexts).
P3 Binding within  1 and  2 is parallel:
Markus Egg, Alexander Koller, Joachim Niehren
P4 For i 2 f1; 2g, no node below  i is bound by a node inside
P5 If  binds a variable node within  1 properly above  1 or the corresponding
variable node in  2 properly above  2 , then the two binder
nodes are binding equivalent ('/ proper dominance).
For the time being, we assume that binding equivalence  is simply
the node identity. We will modify this denition in Section 4.5.
P6 If  is an anaphoric node in  1 , then the corresponding anaphoric
node in  2 must be linked either to  (strict) or, if it exists, to the
correspondence of ante() (sloppy).
P1 species the parallel contexts and the correspondence function
between them. P2 requires parallelism of tree structure. Conditions
P3{P5 are concerned with the interaction of parallelism and variable
binding. Condition P6 deals with the interaction of parallelism and
anaphora, i.e. with strict/sloppy ambiguities.
The parallelism relation is almost symmetric; the only exception is
that the strict variant of the rule P6 only allows to link the anaphoric
node in  2 to the corresponding node in  1 , but not vice versa.
3.4. The Constraint Language CLLS
Now that -structures and their relations are dened, it is straight-forward
to x a constraint language to go with them. We assume an
innite set of node variables, ranged over by X;X pick
relation symbols for all relations dened so far. To keep the presentation
simple, we use the same symbols as for the relations themselves. The
constraint language over lambda structures (CLLS) is given by the
following abstract syntax:
The Constraint Language for Lambda Structures 13
The semantics of CLLS is dened by interpretation of constraints
over the class of lambda structures in the usual Tarski style. A constraint
' of CLLS can be evaluated to a truth value if a -structure
and a variable assignment  into the domain of  are given. A solution
of ' is a pair (; ) which satises '.
3.5. Constraint Graphs
CLLS constraints as just dened can become unreadable rather quickly.
Throughout the paper, we will use constraint graphs instead. Constraint
graphs are an alternative, graphical syntax for CLLS; a constraint
graph corresponding to a constraint ' contains one node for
each variable in ' and labels and edges for the atomic constraints that
appear in '. A simple example is given in (18).
lam  X
var  Z
represents
For every dominance constraint X  Y , we draw a dotted line from
X to Y . For every labelling constraint X:f(X
the graph node for X with f and draw solid lines to the nodes for
. For every -binding constraint (X)=Y , we draw a curved
dashed arrow from X to Y ; and for every anaphoric binding constraint
ante(X)=Y , we draw a dashed arrow from X to Y that only uses
straight lines. Parallelism constraints cannot be represented easily in
constraint graphs; we will simply write them next to the graph.
Finally, a constraint graph represents inequality constraints X 1 6=X 2
for each two labelled nodes in the graph. This assumption nicely
prevents 'overlaps' between the `fragments' of the constraint graph.
Now we can interpret the intuitive diagrams from Section 2 as CLLS
constraint graphs. This gives them a formal meaning as CLLS con-
straints, which can be satised by lambda structures. These lambda
structures, in turn, represent -terms which stand for the actual
meaning(s) of the sentence.
4. Interaction of Quantiers, Anaphora, and Ellipsis
Now that we know how to deal with simple examples, we turn to
some well-known, more complex challenges in the area of quantiers,
anaphora, and ellipses, in particular to involving their interactions.
We look into quantier parallelism, strict/sloppy ambiguities, nested
14 Markus Egg, Alexander Koller, Joachim Niehren
ellipses, a sentence involving interaction of all three, and antecedent-
contained deletion (ACD). There are other interesting things that the
analysis can do; e.g., to deal with gapping, parallelism could be extended
to allow two exception positions rather than one: Niehren et al.
(1997a) showed that this can be done in a dierent setting.
Throughout, we assume a xed signature:
We follow the convention that proper nouns are always analyzed as
constants of type e, except as contrasting elements in ellipses where the
other contrasting element is a quantier. We indicate the rst analysis
by labelling the corresponding nodes in lowercase letters (john), the
second one, by using labels with a capitalized rst letter (John). Fur-
thermore, we draw dominance edges wherever dominance is entailed
by -binding constraints. This is logically redundant, but may improve
readability.
4.1. Quantifier Parallelism
The rst phenomenon we consider is quantier parallelism, an interaction
of scope and ellipsis. By way of example, we continue the sentence
(3), repeated here as (19), with the elliptical sentence (20).
Every linguist attends a workshop.
Every computer scientist does, too.
This pair of sentences, modelled after an example from Hirschbuhler
(1982), has three readings: Either there is a single workshop which
both all linguists and all computer scientist attend; or there is one
workshop for all linguists and one for all computer scientists (but not
necessarily the same one); or every linguist and computer scientist can
attend a dierent workshop. This is surprising; if the target sentence
means 'Every computer scientist attends a workshop', each sentence is
two-way ambiguous, for a total of at least four readings.
In CLLS, parallelism enforces that the quantier scopes in both
sentences must be analogous; the ambiguities cannot be resolved inde-
pendently. This is re
ected by the following constraint (abbreviating
workshop to ws, linguist to ling, and computer scientist to cs):
The Constraint Language for Lambda Structures 15
@
a  ws
lam
s
every  ling
lam
every  cs
@
@
attend  var
var
s
X s is the root of the semantics of the source sentence; X t is the root
of the target sentence. The contrasting elements, every linguist and
every computer scientist, are below the variables X 0
s
tively. There is a dominance constraint between X s and X 2 , but not
between X s and X 1 , since, like most quantiers, universal quantiers
must obey a 'scope island constraint' that prevents them from escaping
from a sentence. This restriction does not hold for indenites, such as
a workshop.
There are three places where the fragment below X 1 can go in a
lambda structure satisfying the constraint: below the fragment starting
at above the conjunction. In each case,
the parallelism constraint enforces that whatever is below X s is also
below replacing what is below X 0
s
with what is below X 0
. This
produces exactly the three readings of the sentence. Note that in the
third reading, the indenite takes scope over the entire conjunction; it
is not part of the parallel contexts.
A particular consequence of the parallelism constraint enforcing
structural parallelism of the sub-lambda structures below X s and X t is
that the relative scopes of the quantiers must be identical in both the
source and the target sentence (if the indenite is below X s , of course).
4.2. Strict/sloppy Ambiguities
Strict/sloppy ambiguities are ambiguities of anaphoric reference that
occur in the context of VP ellipses. They are an important benchmark
for analyses of ellipsis. The prototypical example looks as follows:
likes his mother, and Bill does too.
This sentence has two readings: Either Bill likes John's mother (this
is the strict reading), or Bill likes his own mother (the sloppy reading).
We describe the meaning of (22) as in (23), using parallelism and
anaphoric linking constraints. We have hidden the sub-lambda struc-
Markus Egg, Alexander Koller, Joachim Niehren
ture for his mother and only drawn an empty triangle, as the only node
we are interested in is the anaphor.
ana  X a
lam
@
@
like  var
s
bill  X 0
Except for the fact that the source clause contains an anaphor, this
constraint is totally analogous to the simple ellipses we considered
above. The parallelism constraint rst enforces that the tree part of
the lambda structure below X t is the same as the tree part of the one
below X s , except for the contrasting elements, as follows:
a
lam
@
@
like  var
bill  X 0
(24) is not a complete lambda structure because the anaphor at X 0
a
does not have an antecedent. According to P6 of Denition 3.3, there
are two legal antecedents that this anaphor can be linked to. It can
either be linked to the anaphor in the source context, i.e. to the node
denoted by X a . In this case, the link chain starting at X 0
a
ends at X s ,
which is labelled with john; so this is the strict reading. Or it can be
linked to the node corresponding to the antecedent of X a . As X a is
linked to the hole of the source context, X 0
a
must be linked to the hole
of the target context; this is X 0
, which produces the sloppy reading.
4.3. Nested Ellipses
This analysis of strict/sloppy ambiguity carries over to more sophisticated
cases like the Gawron and Peters (1990) example
revised his paper before the teacher did, and so did Bill.
This sentence comprises nested ellipsis: the source clause John revised
his paper before the teacher did of the ellipsis is elliptical itself;
ellipsis resolution is made even more interesting by the presence of
an anaphor. We follow Dalrymple et al. (1991) in assuming ve readings
(listed in (27)) for (25). These ve readings are described by the
constraint in (26).
The Constraint Language for Lambda Structures 17
@
ana  X a
lam
@
s
s
lam
before
the   teacher
Bill  X 0
@
@
revise  var
var
s
s
For readability, we again compressed the subconstraint describing
his paper into an empty triangle; the only visible (and interesting) node
is X a , the anaphor. The constraint contains two parallelism constraints,
one for each ellipsis. Note that the source sentence seems to contain a
scope ambiguity between the three fragments corresponding to his pa-
per, John, and before. However, the constraint entails that before takes
scope over John because Y s =Y 0
s
. The remaining
scope ambiguity between his paper and the other two fragments is
spurious; we chose to leave it in the constraint to be closer to what the
syntax/semantics interface (Section 5) would produce.
To understand how the ve (constructive) solutions come about,
let us try to 'solve' the constraint by mimicking rst resolution of the
inner and then of the outer ellipsis. An actual solution algorithm might
behave dierently; in particular, it could interleave resolution steps for
the inner and outer parallelism constraint and other constraints such
as the dominance constraints for a scope ambiguity, as the formalism is
totally declarative. We call the correspondence function on the parallel
contexts that is induced by the inner parallelism constraint c i , and that
of the outer one, c
Resolution of the parallelism constraint for the inner ellipsis will
make the description of the sentence the teacher revised his paper more
explicit. Let us say that the node denoted by the variable for the original
anaphor is  a ; then its copy via this parallelism constraint is c i ( a ).
There are two options where c i ( a ) can be linked: either to  a (strict {
this produces the rst three readings in (27)) or to  0
, the denotation
of Y 0
(sloppy { this produces the other two readings).
If we now resolve the parallelism constraint for the outer ellipsis,
we produce copies of  a and of c i ( a )). The node
a ) can be linked either to  a (strict) or to  0
, the denotation of X 0
Markus Egg, Alexander Koller, Joachim Niehren
(sloppy). Likewise, c can be linked either to c i ( a ) (strict), or
it can be linked to the respective value of c
So there are ve possible combinations of linking relations:
(27) 1. ante(c i (a))=a , ante(co(a))=a , ante(co(c i (a)))=c i (a) and
John revised John's paper before the teacher revised John's paper,
Bill revised John's paper before the teacher revised John's paper
2. ante(c i (a))=a , ante(co(a))= 0
John revised John's paper before the teacher revised John's paper,
Bill revised Bill's paper before the teacher revised John's paper
3. ante(c i (a))=a , ante(co(a))= 0
John revised John's paper before the teacher revised John's paper,
Bill revised Bill's paper before the teacher revised Bill's paper
4. ante(c i (a))= 0
John revised John's paper before the teacher revised the teacher's paper,
Bill revised John's paper before the teacher revised the teacher's paper
5. ante(c i (a))= 0
John revised John's paper before the teacher revised the teacher's paper,
Bill revised Bill's paper before the teacher revised the teacher's paper
A reading where  a , c i ( a ), and c are all linked to John and
is linked to Bill, which is particularly dicult to exclude in
other approaches, is impossible here, as c must be linked either
to c i ( a ) or to c
4.4. A Complex Interaction
Now we consider an example involving quantication, anaphora, and
ellipsis where all three phenomena interact.
Mary read a book she liked before Sue did.
This sentence, modelled after a Gawron and Peters (1990) example,
has three readings. In the rst, the indenite NP a book she liked takes
wide scope over both clauses (a particular book liked by Mary is read by
both Mary and Sue). The second and third arise from the strict/sloppy
ambiguity that occurs if the operator before outscopes the indenite:
either both read a book that Mary liked, or each read a book she liked
herself. A constraint describing these three readings is shown in (29).
The Constraint Language for Lambda Structures 19
lam
before  X 2
@
@
read  var
mary  X 0
s
sue  X 0
For the sake of readability, we once again simplify the semantics of
a book she liked to a mere empty triangle with the anaphoric node X 3 .
The rst reading, with the NP taking wide scope, results when the
relative scope of X 1 and X 2 is resolved such that X 1 dominates X 2 . In
this case, the anaphoric node is not part of the parallel subdomain,
which means that there is no strict/sloppy ambiguity. A schematic
representation of this solution (in which we have compressed even more
sub-lambda structures into empty triangles) is shown in (30).
before  X 2
mary  X 0
s
sue  X 0
The other possible scoping is for X 2 to dominate X 1 . The two
solutions this gives rise to are displayed in (31) and (32). Now the
interpretation of the indenite, below X 1 , is dominated by X s and
is copied by resolving the parallelism constraint. In particular, the
anaphoric node, denoted by X 3 , is copied; the strict/sloppy ambiguity
of its copy is dealt with in the now familiar way.
mary  X 0
s
ana
sue  X 0
mary  X 0
s
ana
sue  X 0
Markus Egg, Alexander Koller, Joachim Niehren
4.5. Antecedent-Contained Ellipsis
We conclude this section with a notoriously dicult case of ellipsis,
antecedent-contained deletion (ACD), as in (33).
John greeted every person that Max did.
The problem here is is that the ellipsis is contained in the VP that
it refers to (its 'antecedent'). A naive approach to ellipsis that simply
copies phonetic material from the source to the target sentence runs
into an innite loop as there is always an elliptic sub-sentence left.
Generative syntax solves this problem by raising the universal quan-
tier out of the sentence in LF (Sag, 1980; Fiengo and May, 1994); this
has the eect that the ellipsis is no longer contained in the copied
material. Dalrymple et al. (1991) and Crouch (1995) avoid a similar
kind of recursion by an 'occurs check' of higher-order unication.
In CLLS, the meaning of (33) can be described as follows.
@
every  lam  X 4
@
person  var
@
lam  X 2
@
var
lam  X 1
@
@
greet  var  X 9
Like in the other analyses, the universal quantier is not contained in
the source context of the parallelism constraint. 1 As already discussed
in Section 4.3, the constraint also entails that the universal quantier
must take scope over John.
There is one subtle problem, however. Condition P5 in Denition
3.3 requires that if  is labelled with var, the binders of  and c()
must be binding equivalent, which we have taken to mean 'equal' so
far. However, ACD forces one to soften this restriction: The var-node
3 is bound by X 2 , but X 2 cannot bind the copy of X 3 because it does
not dominate it. Intuitively, it should be permitted for the copy (X 9 )
to be bound by X 1 because if it is, a sequence of -reductions will map
1 If the universal quantier was contained in the context, the only solutions of
the constraint would be innite lambda structures. This means that it would be
unsatisable according to Section 3, as we are interpreting CLLS over nite lambda
structures. This is reminiscent of the occurs check, as the function of an occurs check
is to avoid innite solutions to unication problems.
The Constraint Language for Lambda Structures 21
its copy to the same variable. The separation of the two binders
is merely an artifact of the type-raised analysis of every.
However, checking for -equivalence while processing the constraint
is unfeasible: It is computationally expensive, and it is unclear if it can
be done at all before all readings have been enumerated. Instead, we use
the following revised denition of binding equivalence, which is easier
to check and works for the examples:
DEFINITION 4.1. Let  be a lambda structure. Binding equivalence
in  is the smallest equivalence relation  on nodes in the domain of
such that for all
1. if  1 :lam( 6
where Q is a quantier label, i.e. a member of
2. if  3
The rst branch models -equivalence; the precondition is shown
in (35a). The second branch models -equivalence; its precondition is
shown in (35b). If we modify our denition of the parallelism relation
in this way, the constraint in (34) has exactly the correct solution.
@   4
lam   2
(b) lam   1
@   3
lam   2
var   4
Note, by way of conclusion, that our analysis can also account for
the dierence between (36) and (37) (Sag, 1980), the rst of which lacks
one of the two readings of the second one (where the matrix verb want
outscopes the universal quantier).
wants Bill to read everything that Max does.
wants Bill to read everything Max wants him to read.
This blocking is achieved in the CLLS analysis because, as discussed
above, John must be in the scope of the universal quantier (it is
the contrasting element). As every NP argument outscopes the verb
of which it is a syntactic argument, John must outscope want ; so
the relative scope of the universal quantier and want is xed. If the
elliptic material of (36) is spelt out like in (37), there is no parallelism
constraint to enforce wide scope of the universal quantier over John.
22 Markus Egg, Alexander Koller, Joachim Niehren
5. The Syntax-Semantics Interface
This section denes a grammar with a syntax/semantics interface which
allows the derivation of the CLLS constraints for the example sentences
discussed in this paper. As we have used a mixture of type-raised and
rst-order representations of proper names in the examples to improve
readability, we will dene an interface for each version.
We will rst dene the grammar and then the rules for semantic
construction, starting with the type-raised version and then showing
what needs to be changed to get the rst-order representations. Finally,
we will go through an example to show how the interface works.
5.1. Grammar
The grammar is dened by the phrase structure rules in Fig. 1.

Figure

1. The grammar
Most labels for syntactic categories are self-explanatory, perhaps
except for the following: PN is a category that comprises proper nouns
and anaphora, Conj refers to the category of conjunctions like before,
Coord, to the one of sentence coordinators like and, and RP and RCl,
to the categories of relative pronoun and relative clause, respectively.
Beyond transitive and intransitive verbs, we also allow 'AcI verbs' AV
(such as expect) and sentence complement verbs SV (such as say). Conj
and Coord are distinguished because they percolate scope domains in
a dierent fashion.
The lexicon is dened by a relation Lex, which relates words W and
lexical categories  2 fDet; N; IV; TV; SV; productions
expand lexical categories to words of this category.
We make two types of simplifying assumptions about the grammar.
First, we disregard all aspects of syntactic analysis that are inconvenient
for a pure phrase structure grammar, such as agreement. Any
The Constraint Language for Lambda Structures 23
serious NLP system would employ some type of unication grammar,
in which these aspects could be taken care of easily. As a matter of fact,
we have implemented an HPSG grammar that does this and produces
essentially the same constraints as the one presented here.
Second, we assume that the syntax provides coindexation that relates
anaphoric pronouns to their antecedents and relative pronouns
to their corresponding traces, and that the parallelism constraints that
model VP ellipsis are generated by an independent source. Determining
elliptic elements is, to our knowledge, an open problem and therefore
beyond the scope of this paper.
5.2. Semantic construction
The overall strategy of our syntax-semantics interface is to factor out as
much of the constraint construction as possible into the interface rules.
This allows us to keep the entries in the semantic lexicon extremely
simple: most of them introduce just one labelling constraint. We generate
a constraint for each node in the syntax tree; the constraint for the
entire tree will then be simply the conjunction of these subconstraints.
Each node  2 N  in the syntax tree is associated with two variables,
(the local scope domain of ) and X r
(the root of the subconstraint
for
denotes the root of the 'semantic contribution'
of the syntactic constituent below . X s
is referred to in scope island
constraints; for each quantier NP , except for indenites, a constraint
keeps the quantier within its scope domain. The values of
are set in the construction rules for embedded sentences; otherwise,
daughters inherit the scope domains of their mothers.
Furthermore, we associate with each NP index i that is used for
coindexation in the syntax tree a variable X i . We will use these variables
to model anaphoric binding and relative clauses.
The (semantic) variables associated with syntactic nodes are related
by the rules in Fig. 2, one for each syntactic rule from Fig. 1. Each
construction rule is applied to syntactic nodes that have been expanded
by a certain syntax rule. These rules are specied on the left hand sides
of the arrows; [ :P Q R] means that node  in the syntax tree is labelled
with P , and its two daughter nodes  0 and  00 are labelled with Q and
R, respectively.
The complete constraint which the interface generates is the conjunction
of all of these local constraints, plus the dominances X s
for scope islands, plus constraints for the lexical entries. Most of the
latter constraints are simple labelling constraints; for instance, the
constraint we add for the intransitive verb sleep would be X r
:sleep.
Markus Egg, Alexander Koller, Joachim Niehren
@
000
000
@
lam
@
@
lam
lam  X r
@
var
@
var
lam  X r
000

Figure

2. The syntax/semantics interface
The Constraint Language for Lambda Structures 25
There are some exceptions to this general rule. First, the elliptic
does (too) does not add a labelling constraint; its semantics is
determined via a parallelism constraint. Furthermore, whenever coindexation
signies a relation between an anaphor  0 and its antecedent
, we add the constraint X r
when we process  and the constraint
when we process  0 . Similarly, the constraint
for a relative pronoun with index i at  is X r
and the
constraint for the corresponding trace (say, at  0 ) is X r
together with rule (b11), enforces correct binding of the trace.
Finally, the constraints for possessive pronouns, such as his, are
as in (38). Intuitively, we want to analyze the NP his i book just like
the NP the book of him i ; the diagram in (38) hides most details of
this construction for readability, but notice that there is an anaphoric
linking constraint from the anaphoric node to the antecedent X i , as
specied by the syntactic coindexation.
ana
The interface as presented so far will always produce type-raised
representations of all NPs. A version of the interface which produces
rst-order representations of proper names (i.e. as constants of type
e) can be obtained by making exactly two changes to the interface.
For one, the rule (b7) must be replaced by a rule that looks like
(b9); second, the lexicon must be changed to label the nodes with
the constants of type e (i.e., mary instead of Mary).
5.3. An Example
To see how semantic construction works, consider example (39).
person that Bill greeted
The grammar assigns to (39) the parse tree in Fig. 3. From this parse
tree, application of the synsem interface rules returns the constraint in
Fig. 4. First, rule b7 builds the fragment below X 15 plus the node
(with its -link to X 17 ). Next, rules b3 and b1 build up the
subtree below X 9 from the semantics of the verb greet and its two NP
arguments (without the label of X 12 ; recall that the corresponding trace
contributes only an unlabelled node). Then rule b11 constructs the
subtree below X 7 and introduces the -link for X 12 ; the label of X 12
comes from the semantics of the relative pronoun. The root node of the
26 Markus Egg, Alexander Koller, Joachim Niehren
person
RCl
that i
PN
Bill
greeted

Figure

3. person that Bill greeted
lam  X 1
@
person  X 4 var
@
lam  X 7
@
greet  var  X 12
var
Bill  lam  X 17

Figure

4. Semantic representation of example (39).
constraint for the relative clause is X 7 . Finally, the subtree below X 1
(the root node of the semantics of (39)) is built according to b10. The
semantic contribution of the noun person is node X 4 .
6. Ecient Disambiguation
A good underspecication formalism should not only allow to write
down appropriate underspecied descriptions, but also to enumerate
their readings eciently. The most optimistic case is that they can be
enumerated in time polynomial in the total number of readings.
In a framework that allows the analysis of ellipsis and anaphora in
addition to scope, it is unlikely that such a low runtime can be obtained.
A prime example is the Dalrymple et al. (1991) analysis of ellipsis: It
uses higher-order unication, which is known to be undecidable.
Similarly, the problem of disambiguating arbitrary CLLS descriptions
(that is, of enumerating all most general solved forms of a
constraint) is very complex. It was shown in Niehren and Koller (1998)
that CLLS is equivalent to context unication (Schmidt-Schau and
Schulz, 1998; Niehren et al., 1997a). There are semi-decision procedures
The Constraint Language for Lambda Structures 27
for context unication, but its decidability is a prominent open problem
in theoretical computer science (RTA, 1998).
For the sublanguage of dominance constraints (which are sucient
for scope underspecication alone), the situation is better: It was shown
in Koller et al. (1998) that the satisability problem of dominance
constraints is decidable, but NP-complete. This means that the most efcient
solution procedure may take (deterministic) exponential time for
enumerating all readings, even if the number of readings is polynomial.
Nevertheless, there are solvers for dominance constraints that perform
very eciently for all constraints from scope underspecication.
These solvers are based on constraint programming with nite sets
(Koller and Niehren, 1999); the general strategy is iterating deterministic
propagation steps and non-deterministic choices. It turns out that
despite the general NP-completeness, all choices made in the disambiguation
of a constraint from scope underspecication are necessary
to distinguish dierent readings; the search never fails. Recent research
in this area focuses on obtaining formal complexity results that model
this experience and on integrating a semi-decision procedure for the
rest of CLLS with a dominance constraint solver. A demo system that
derives dominance constraints describing a scope ambiguity and solves
them eciently is available on the WWW (CHORUS Project, 1999).
7. Conclusion and Outlook
In this paper, we have presented the Constraint Language for Lambda
Structures (CLLS), a rst-order language for semantic underspecica-
tion. CLLS allows the representation of scope ambiguities, anaphora,
and ellipses in simple underspecied structures that are transparent
and suitable for processing. It is a language of tree descriptions that
conservatively extends the language of dominance constraints.
We have shown that CLLS correctly represents many notorious problems
from the literature involving scope, anaphora, ellipses, and their
interactions. An advantage over earlier approaches to this area is that
CLLS analyses are completely order-independent, and the formal foundations
are very transparent. It also provides a clean solution to a problem
with variable binding in the context of scope underspecication
that becomes most obvious in the presence of ellipses.
Although the linguistic coverage of CLLS includes various challenging
problems, it still needs to be extended. The most obvious area for
improvement is a more complete theory of ellipsis. Another interesting
extension is to build dynamic accessibility relations into the denition
of anaphoric links and make the eects of anaphora on quantier scope
28 Markus Egg, Alexander Koller, Joachim Niehren
explicit by reasoning on underspecied structures (Koller and Niehren,
2000). Finally, CLLS can be used to model reinterpretation (meaning
shift) of aspect and NPs in an underspecied way (Striegnitz, 1999; Egg,
1999; Koller et al., 1999).
On the other hand, there are various more formal aspects of CLLS
that can be pursued in the future. One essential problem for any under-
specication formalism is to raise operations on the object level, such
as deduction, to the level of underspecied descriptions. Although there
are some rst results (Jaspars and Koller, 1999), the entire eld is still
in its infancy. Furthermore, it is necessary to nd tractable algorithms
for processing parallelism constraints (Erk and Niehren, 2000).

Acknowledgements

This work was supported by the SFB 378 (project chorus) at the
Universitat des Saarlandes. The article is an updated and revised version
of Egg et al. (1998) and Egg et al. (1999); we are indebted to
Peter Ruhrberg and Feiyu Xu for their contributions to these papers.
The authors wish to thank Manfred Pinkal, Gert Smolka, all members
of the SFB 378 projects chorus, lisa, negra, and nep, and
the commentators and participants at the Bad Teinach workshop on
underspecication.



--R


CHORUS Project:
de/cl/projects/chorus/demo.



Arbeitspapiere der FG Sprachwissenschaft
de/cl/projects/chorus/papers/egg99.





Anaphora and Quanti

Pustejovsky and P.















Deletion and Logical Form.






--TR

--CTR
Manuel Bodirsky , Katrin Erk , Joachim Niehren , Alexander Koller, Underspecified beta reduction, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.74-81, July 06-11, 2001, Toulouse, France
Katrin Erk , Joachim Niehren, Well-nested parallelism constraints for ellipsis resolution, Proceedings of the tenth conference on European chapter of the Association for Computational Linguistics, April 12-17, 2003, Budapest, Hungary
Alexander Koller , Stefan Thater, An improved redundancy elimination algorithm for underspecified representations, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL, p.409-416, July 17-18, 2006, Sydney, Australia
Michael Schiehlen, Ellipsis resolution with underspecified scope, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania
Katrin Erk , Joachim Niehren, Dominance constraints in stratified context unification, Information Processing Letters, v.101 n.4, p.141-147, February, 2007
Manuel Bodirsky , Denys Duchier , Joachim Niehren , Sebastian Miele, A new algorithm for normal dominance constraints, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
Alexander Koller , Joachim Niehren , Stefan Thater, Bridging the gap between underspecification formalisms: hole semantics as dominance constraints, Proceedings of the tenth conference on European chapter of the Association for Computational Linguistics, April 12-17, 2003, Budapest, Hungary
Ralph Debusmann , Denys Duchier , Alexander Koller , Marco Kuhlmann , Gert Smolka , Stefan Thater, A relational syntax-semantics interface based on dependency grammar, Proceedings of the 20th international conference on Computational Linguistics, p.176-es, August 23-27, 2004, Geneva, Switzerland
Alexander Koller , Stefan Thater, Efficient solving and exploration of scope ambiguities, Proceedings of the ACL 2005 on Interactive poster and demonstration sessions, p.9-12, June 25-30, 2005, Ann Arbor, Michigan
Joachim Niehren , Stefan Thater, Bridging the gap between underspecification formalisms: minimal recursion semantics as dominance constraints, Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, p.367-374, July 07-12, 2003, Sapporo, Japan
Ruth Fuchss , Alexander Koller , Joachim Niehren , Stefan Thater, Minimal recursion semantics as dominance constraints: translation, evaluation, and analysis, Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, p.247-es, July 21-26, 2004, Barcelona, Spain
Ernst Althaus , Denys Duchier , Alexander Koller , Kurt Mehlhorn , Joachim Niehren , Sven Thiel, An efficient graph algorithm for dominance constraints, Journal of Algorithms, v.48 n.1, p.194-219, August
Denys Duchier, Dominance constraints with Boolean connectives: a model-eliminative treatment, Theoretical Computer Science, v.293 n.2, p.321-343, 6 February
Manuel Bodirsky , Martin Kutz, Determining the consistency of partial tree descriptions, Artificial Intelligence, v.171 n.2-3, p.185-196, February, 2007
underspecification;ellipsis;anaphora;tree descriptions;scope ambiguity