Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Topological Dependency Trees: A Constraint Based Account of Linear Precedence

De
8 pages
Topological Dependency Trees: A Constraint-Based Account of Linear Precedence Denys Duchier Programming Systems Lab Universitat des Saarlandes, Geb. 45 Postfach 15 11 50 66041 Saarbrucken, Germany Ralph Debusmann Computational Linguistics Universitat des Saarlandes, Geb. 17 Postfach 15 11 50 66041 Saarbrucken, Germany Abstract We describe a new framework for de- pendency grammar, with a modular de- composition of immediate dependency and linear precedence. Our approach distinguishes two orthogonal yet mutu- ally constraining structures: a syntactic dependency tree and a topological de- pendency tree. The syntax tree is non- projective and even non-ordered, while the topological tree is projective and partially ordered. 1 Introduction Linear precedence in so-called free word order languages remains challenging for modern gram- mar formalisms. To address this issue, we pro- pose a new framework for dependency gram- mar which supports the modular decomposition of immediate dependency and linear precedence. Duchier (1999) formulated a constraint-based ax- iomatization of dependency parsing which char- acterized well-formed syntax trees but ignored is- sues of word order. In this article, we develop a complementary approach dedicated to the treat- ment of linear precedence. Our framework distinguishes two orthogonal, yet mutually constraining structures: a syntactic dependency tree (ID tree) and a topological de- pendency tree (LP tree).

  • option- ally extraposed

  • mann zu

  • infinitive zu

  • edge constraints

  • fieldext

  • versucht

  • must satisfy

  • fieldint

  • verb


Voir plus Voir moins

Topological Dependency Trees:
A Constraint-Based Account of Linear Precedence
Denys Duchier Ralph Debusmann
Programming Systems Lab Computational Linguistics
Universita¨t des Saarlandes, Geb. 45 Universita¨t des Saarlandes, Geb. 17
Postfach 15 11 50 Postfach 15 11 50
¨ ¨66041 Saarbrucken, Germany 66041 Saarbrucken, Germany
duchier@ps.uni-sb.de rade@coli.uni-sb.de
Abstract trees is formulated in terms of (a) lexicalized con-
straints and (b) principles governing e.g. climbing
We describe a new framework for de- conditions.
pendency grammar, with a modular de- In Section 2 we discuss the difficulties pre-
composition of immediate dependency sented by discontinuous constructions in free
and linear precedence. Our approach word order languages, and briefly touch on the
distinguishes two orthogonal yet mutu- limitations of Reape’s (1994) popular theory of
ally constraining structures: a syntactic ‘word order domains’. In Section 3 we introduce
dependency tree and a topological de- the concept of topological dependency tree. In
pendency tree. The syntax tree is non- Section 4 we outline the formal framework for
projective and even non-ordered, while our theory of ID/LP trees. Finally, in Section 5
the topological tree is projective and we illustrate our approach with an account of the
partially ordered. word-order phenomena in the verbal complex of
German verb final sentences.
1 Introduction 2 Discontinuous Constructions
Linear precedence in so-called free word order In free word order languages, discontinuous con-
languages remains challenging for modern gram- structions occur frequently. German, for example,
mar formalisms. To address this issue, we pro- is subject to scrambling and partial extraposition.
pose a new framework for dependency gram- In typical phrase structure based analyses, such
mar which supports the modular decomposition phenomena lead to e.g. discontinuous VPs:
of immediate dependency and linear precedence.
(1) (dass) einen Mann Maria zu lieben versucht
Duchier (1999) formulated a constraint-based ax- (that) a man Maria to love triesacc nom
iomatization of dependency parsing which char-
whose natural syntax tree exhibits crossing edges:
acterized well-formed syntax trees but ignored is-
Ssues of word order. In this article, we develop a
NP V
complementary approach dedicated to the treat-
VP
ment of linear precedence. NP V
DET NOur framework distinguishes two orthogonal,
(dass) einen Mann Maria zu lieben versucht
yet mutually constraining structures: a syntactic
Since this is classically disallowed, discontinu-dependency tree (ID tree) and a topological de-
ous constituents must often be handled indirectlypendency tree (LP tree). While edges of the ID
through grammar extensions such as traces.tree are labeled by syntactic roles, those of the
Reape (1994) proposed the theory of word or-LP tree are labeled by topological fields (Bech,
der domains which became quite popular in the1955). The shape of the LP tree is a flattening of
HPSG community and inspired others such asthe ID tree’s obtained by allowing nodes to ‘climb
Mu¨ller (1999) and Kathol (2000). Reape distin-up’ to land in an appropriate field at a host node
guished two orthogonal tree structures: (a) the un-where that field is available. Our theory of ID/LP
ordered syntax tree, (b) the totally ordered tree ofword order domains. The latter is obtained from
the syntax tree by flattening using the operation
of domain union to produce arbitrary interleav-
ings. The boolean feature [∪±] of each node con-
trols whether it must be flattened out or not. In-
finitives in canonical position are assigned [∪+]:
(dass) Maria einen Mann zu lieben versucht
S
The topological tree (LP tree) is partially ordered
NP VP[∪+] V
and projective:
NP[∪−] V
DET N
(dass) Maria einen Mann zu lieben versucht
v
n n vThus, the above licenses the following tree of
d
word order domains:
(dass) Maria einen Mann zu lieben versucht
S
Its edge labels are called (external) fields and are
NP NP V V
totally ordered: df ≺ mf ≺ vc. This induces a
DET N linear precedence among the daughters of a node
(dass) einen Mann Maria zu lieben versucht in the LP tree. This precedence is partial because
daughters with the same label may be freely per-Extraposed infinitives are assigned [∪−]:
muted.
S
In order to obtain a linearization of a LP tree,
NP V VP[∪−] it is also necessary to position each node with
NP V respect to its daughters. For this reason, each
node is also assigned an internal field (d, n, or v)
DET N
shown above on the vertical pseudo-edges. The
(dass) Maria versucht einen Mann zu lieben
set of internal and external fields is totally or-
As a consequence, Reape’s theory correctly pre- dered: d≺ df≺ n≺ mf≺ vc≺ v
dicts scrambling (2,3) and full extraposition (4), Like Reape, our LP tree is a flattened version of
but cannot handle the partial extraposition in (5): the ID tree (Reape, 1994; Uszkoreit, 1987), but
the flattening doesn’t happen by ‘unioning up’;(2) (dass) Maria einen Mann zu lieben versucht
rather, we allow each individual daughter to climb
(3) (dass) einen Mann Maria zu lieben versucht
up to find an appropriate landing place. This idea
(4) (dass) Maria versucht, einen Mann zu lieben is reminiscent of GB, but, as we shall see, pro-
ceeds rather differently.
(5) (dass) Maria einen Mann versucht, zu lieben
4 Formal Framework3 Topological Dependency Trees
The framework underlying both ID and LP trees
Our approach is based on dependency grammar.
is the configuration of labeled trees under valency
We also propose to distinguish two structures: (a)
(and other) constraints. Consider a finite set L
a tree of syntactic dependencies, (b) a tree of topo-
of edge labels, a finite set V of nodes, and E ⊆
logical dependencies. The syntax tree (ID tree) is
V ×V ×L a finite set of directed labeled edges,
unordered and non-projective (i.e. it admits cross-
′such that (V,E) forms a tree. We write w−−ℓ→w
ing edges). For display purposes, we pick an ar-
′for an edge labeled ℓ from w to w . We define the
bitrary linear arrangement:
ℓ-daughtersℓ(w) of w∈ V as follows:
′ ′ℓ(w) ={w ∈ V | w−−ℓ→w ∈ E}
subject
mf
mf
zuvinf
vc
object
det
dfb bWe writeL for the set of valency specifications ℓ the verbal complement field, xf the extraposition
defined by the following abstract syntax: field. Features of lexical entries relevant to LP
trees are grouped under table heading “Topology”
bℓ ::= ℓ | ℓ? | ℓ∗ (ℓ∈L) din Figure 1. valency assigns a F valencyextLP
to each node and is subject to the lexicalizedbA valency is a subset ofL. The tree (V,E) satis-
constraint:bLfies the valency assignment valency : V → 2 if
for all w∈ V and all ℓ∈L: valency (w) = lex(w).valencyLP LP
ℓ∈ valency(w) ⇒ |ℓ(w)| = 1 (V,E ) must satisfy the valency assignmentLP LP
ℓ?∈ valency(w) ⇒ |ℓ(w)|≤ 1 as described earlier. For example, the lexical en-
ℓ∗∈ valency(w) ⇒ |ℓ(w)|≥ 0 try for zu lieben specifies:2
otherwise ⇒ |ℓ(w)| = 0
valency (zu lieben ) ={mf∗, xf?}2LP
4.1 ID Trees
which permits 0 or more mf edges and at most
An ID tree (V,E , lex, cat, valency ) consistsID ID one xf edge; we say that it offers fields mf and xf.
of a tree (V,E ) with E ⊆ V ×V ×R, whereID ID
Unlike the ID tree, the LP tree must be projective.
the setR of edge labels (Figure 1) represents syn-
The grammar stipulates a total order on F ,ext
tactic roles such as subject or vinf (bare infinitive
thus inducing a partial linear precedence on each
argument). lex : V → Lexicon assigns a lexi-
node’s daughters. This order is partial because
cal entry to each node. An illustrative Lexicon is
all daughters in the same field may be freely per-
displayed in Figure 1 where the 2 features cats
muted: our account of scrambling rests on free
and valency of concern to ID trees are grouped
ID permutations within the mf field. In order to ob-
under table heading “Syntax”. Finally, cat and
tain a linearization of the LP tree, it is necessarybvalency assign a category and anR valency to
ID to specify the position of a node with respect to its
each node w∈ V and must satisfy:
daughters. For this reason each node is assigned
an internal field inF . The setF ∪F is to-int ext intcat(w)∈ lex(w).cats
tally ordered:valency (w) = lex(w).valency
ID ID
d≺ df≺ n≺ mf≺ vc≺ v≺ xf
(V,E ) must satisfy the valency assignment asID ID
described earlier. For example the lexical entry In what (external) field a node may land and
for versucht specifies (Figure 1): what internal field it may be assigned is deter-
mined by assignments field : V → F andext ext
valency (versucht) ={subject, zuvinf}
ID field : V → F which are subject to the lexi-int int
calized constraints:
Furthermore, (V,E ) must also satisfy theID
field (w)∈ lex(w).fieldedge constraints stipulated by the grammar ext ext
field (w)∈ lex(w).field(see Figure 1). For example, for an edge int int
′ ′w−d−e−t→w to be licensed, w must be assigned
For example, zu lieben may only land in field vc1′category det and bothw andw must be assigned
(canonical position), and zu lieben only in xf (ex-21the same agreement.
traposed position). The LP tree must satisfy:
4.2 LP Trees ′ ′w−−ℓ→w ∈ E ⇒ ℓ = field (w )LP ext
An LP tree(V,E , lex, valency , field , field )LP ext intLP
′Thus, whether an edge w−−ℓ→w is licensed de-consists of a tree (V,E ) with E ⊆LP LP
′V × V × F , where the set F of edge pends both on valency (w) and on field (w ).extext ext LP
′In other words: w must offer field ℓ and w mustlabels represents topological fields (Bech, 1955):
df the determiner field, mf the ‘Mittelfeld’, vc accept it.

1 For an edgew−−ℓ→w in the ID tree, we say thatIssues of agreement will not be further considered in this
′paper. w is the head of w . For a similar edge in the LPGrammar Symbols
C ={det, n, vfin, vinf, vpast, zuvinf} (Categories)
R ={det, subject, object, vinf, vpast, zuvinf} (Syntactic Roles)
F ={df, mf, vc, xf} (External Topological Fields)ext
F ={d, n, v} (Internal Topological Fields)int
d≺ df≺ n≺ mf≺ vc≺ v≺ xf (Topological Ordering)
Edge Constraints
′ ′ ′w−−−− d−e−t−−→w ⇒ cat(w ) = det ∧ agr(w) = agr(w )
′ ′ ′w−−−s−u−bj−e−c−t→w ⇒ cat(w ) = n ∧ agr(w) = agr(w )∈ NOM
′ ′ ′w−−− o−b−je− c−t−→w ⇒ cat(w ) = n ∧ agr(w )∈ ACC
′ ′w−−−−v−in− f−−→w ⇒ cat(w ) = vinf
′ ′w−−− v− p−a−s−t−→w ⇒ cat(w ) = vpast
′ ′w−−− z−u−v−in−f−→w ⇒ cat(w ) = zuvinf
Lexicon
Word Syntax Topology
cats valency field field valencyint extID LP
einen {det} {} {d} {df} {}
Mann {n} {det} {n} {mf} {df?}
Maria {n} {} {n} {mf} {}
lieben {vinf} {object?} {v} {vc} {}
geliebt {vpast} {object?} {v} {vc} {}
konnen {vinf} {vinf} {v} {vc} {vc?}¨ 1
ko¨nnen {vinf, vpast} {vinf} {v} {xf} {mf∗, vc?, xf?}2
wird {vfin} {subject, vinf} {v} {vc} {mf∗, vc?, xf?}
haben {vinf} {vpast} {v} {xf} {mf∗, vc?, xf?}
hat {vinf} {subject, vpast} {v} {vc} {mf∗, vc?, xf?}
zu lieben {zuvinf} {object?} {v} {vc} {}1
zu lieben {zuvinf} {object?} {v} {xf} {mf∗, xf?}2
versucht {vfin} {subject, zuvinf} {v} {vc} {mf∗, vc?, xf?}
Figure 1: Grammar Fragment
′ ′tree, we say that w is the host of w or that w Principle 3 a node must land on, or climb higher
lands on w. The shape of the LP tree is a flat- than, its head
tened version of the ID tree which is obtained by ′Subject to these principles, a node w may climb
allowing nodes to climb up subject to the follow- up to any host w which offers a field licensed by
ing principles: ′field (w ).ext
Principle 1 a node must land on a transitive Definition. An ID/ LP analysis is a tuple (V,
2head E ,E , lex, cat, valency , valency , field ,ID LP extID LP
field ) such that (V,E , lex, cat, valency ) isPrinciple 2 it may not climb through a barrier int ID ID
an ID tree and (V,E , lex, valency , field ,LP extLPWe will not elaborate the notion of barrier which
field ) is an LP tree and all principles are sat-intis beyond the scope of this article, but, for exam-
isfied.
ple, a noun will prevent a determiner from climb-
Our approach has points of similarity withing through it, and finite verbs are typically gen-
(Bro¨ker, 1999) but eschews modal logic in fa-eral barriers.
vor of a simpler and arguably more perspicuous2This is Bro¨cker’s terminology and means a node in the
constraint-based formulation. It is also relatedtransitive closure of the head relation.xf
xf
to the lifting rules of (Kahane et al., 1998), but In the extraposed case, zu lieben itself offers2
where they choose to stipulate rules that license field mf:
liftings, we opt instead for placing constraints on
otherwise unrestricted climbing.
5 German Verbal Phenomena v
n v
We now illustrate our theory by applying it to the n
d
treatment of word order phenomena in the verbal
(dass) Maria versucht einen Mann zu lieben
complex of German verb final sentences. We as-
sume the grammar and lexicon shown in Figure 1. 5.2 Partial VP Extraposition
These are intended purely for didactic purposes
In example (8), the zu-infinitive zu lieben is extra-
and we extend for them no claim of linguistic ad-
posed to the right of its governing verb versucht,
equacy.
but its nominal complement einen Mann remains
in the Mittelfeld:5.1 VP Extraposition
Control verbs like versuchen or versprechen al- (8) (dass) Maria einen Mann versucht, zu lieben
low their zu-infinitival complement to be option-
In our account, Mann is restricted to land in an mfally extraposed. This phenomenon is also known
field which both extraposed zu lieben and finite2as optional coherence.
verb versucht offer. In example (8) the nominal
(6) (dass) Maria einen Mann zu lieben versucht complement simply climbed up to the finite verb:
(7) (dass) Maria versucht, einen Mann zu lieben
Both examples share the following ID tree:
v
n n v
d
(dass) Maria einen Mann versucht zu lieben
5.3 Obligatory Head-final Placement
Verb clusters are typically head-final in German:
(dass) Maria einen Mann zu lieben versucht non-finite verbs precede their verbal heads.
Optional extraposition is handled by having two (9) (dass) Maria einen Mann lieben wird
(that) Maria a man love willnom acclexical entries for zu lieben. One requires it to
land in canonical position: (10) (dass) Maria einen Mann wird lieben*
field (zu lieben ) ={vc}ext 1 The ID tree for (9) is:
the other requires it to be extraposed:
field (zu lieben ) ={xf}ext 2
In the canonical case, zu lieben does not offer1
field mf and einen Mann must climb to the finite
(dass) Maria einen Mann lieben wirdverb:
The lexical entry for the bare infinitive lieben re-
quires it to land in a vc field:
v
field (lieben) ={vc}n n v ext
d
(dass) Maria einen Mann zu lieben versucht
subject
mf
subject
mf
mf
zuvinf
vc
object
mf
mf
mf
object
df
det
df
df
det
vinfxf
vinf
xf
3therefore only the following LP tree is licensed: Thus we correctly account for examples (11) and
(12) with the following LP trees:
v
n n v
vd
n n v
(dass) Maria einen Mann lieben wird d v
(dass) Maria einen Mann lieben ko¨nnen wirdwhere mf ≺ vc ≺ v, and subject and ob-
ject, both in field mf, remain mutually unordered.
Thus we correctly license (9) and reject (10).
v5.4 Optional Auxiliary Flip
n n v
vdIn an auxiliary flip construction (Hinrichs and
(dass) Maria einen Mann wird lieben ko¨nnenNakazawa, 1994), the verbal complement of an
auxiliary verb, such as haben or werden, follows The astute reader will have noticed that other LP
rather than precedes its head. Only a certain class trees are licensed for the earlier ID tree: they are
of bare infinitive verbs can land in extraposed po- considered in the section below.
sition. As we illustrated above, main verbs do
5.5 V-Projection Raisingnot belong to this class; however, modals such as
ko¨nnen do, and may land in either canonical (11) This phenomenon related to auxiliary flip de-
or in extraposed (12) position. This behavior is scribes the case where non-verbal material is in-
called ‘optional auxiliary flip’. terspersed in the verb cluster:
(11) (dass) Maria einen Mann lieben ko¨nnen wird
(13) (dass) Maria wird einen Mann lieben ko¨nnen
(that) Maria a man love can will
(that) Maria will be able to love a man (14) (dass) Maria lieben einen Mann ko¨nnen wird*
(12) (dass) Maria einen Mann wird lieben ko¨nnen
(15) (dass) Maria lieben ko¨nnen einen Mann wird*
Both examples share the following ID tree:
The ID tree remains as before. The NP einen
Mann must land in a mf field. lieben is in canon-
ical position and thus does not offer mf, but
both extraposed ko¨nnen and finite verb wird do.2
Whereas in (12), the NP climbed up to wird, in
(13) it climbs only up to ko¨nnen.
(dass) Maria einen Mann wird lieben ko¨nnen
Our grammar fragment describes optional auxil-
iary flip constructions in two steps: v
n v
• wird offers both vc and xf fields:
n v
dvalency (wird) ={mf∗, vc?, xf?}
ID
(dass) Maria wird einen Mann lieben ko¨nnen
• ko¨nnen has two lexical entries, one canonical (14) is ruled out because ko¨nnen must be in the
and one extraposed: vc of wird, therefore lieben must be in the vc
of ko¨nnen, and einen Mann must be in the mf offield (ko¨nnen ) ={vc}ext 1
wird. Therefore, einen Mann must precede bothfield (ko¨nnen ) ={xf}ext 2
lieben and ko¨nnen. Similarly for (15).
3It is important to notice that there is no spurious ambi-
guity concerning the topological placement of Mann: lieben
in canonical position does not offer field mf; therefore Mann
must climb to the finite verb.
mf
mf
mf
mf
subject
mf
object
vc
vc
vinf
mf
vc
df
df
df
df
det
vc
mf
mf
vcvinf
xf
xf
xvinf
vpast
xf
5.6 Intermediate Placement This is satisfied by ko¨nnen which insists on being2
extraposed, thus ruling (20) out:The Zwischenstellung construction describes
cases where the auxiliary has been flipped but its field (ko¨nnen ) ={xf}ext 2
verbal argument remains in the Mittelfeld. These
Example (18) has LP tree:
are the remaining linearizations predicted by our
theory for the running example started above:
(16) (dass) Maria einen Mann lieben wird ko¨nnen
v
n n v(17) (dass) einen Mann Maria lieben wird ko¨nnen
vd
(dass) Maria einen Mann hat lieben ko¨nnenwhere lieben has climbed up to the finite verb.
In (18) einen Mann climbs up to hat, while in (19)
5.7 Obligatory Auxiliary Flip it only climbs up to ko¨nnen.
Substitute infinitives (Ersatzinfinitiv) are further
5.8 Double Auxiliary Flip
examples of extraposed verbal forms. A sub-
Double auxiliary flip constructions occur whenstitute infinitive exhibits bare infinitival inflec-
an auxiliary is an argument of another auxiliary.tion, yet acts as a complement of the perfectizer
Each extraposed verb form offers both vc and mf:haben, which syntactically requires a past partici-
thus there are more opportunities for verbal andple. Only modals, AcI-verbs such as sehen and
nominal arguments to climb to.lassen, and the verb helfen can appear in substi-
(21) (dass) Maria wird haben einen Mann liebentute infinitival inflection.
ko¨nnen
A substitute infinitive cannot land in canonical
(that) Maria will have been able to love a man
position; it must be extraposed: an auxiliary flip
(22) (dass) Maria einen Mann wird haben lieben
involving a substitute infinitive is called an ‘oblig-
ko¨nnen
atory auxiliary flip’.
(23) (dass) Maria wird einen Mann lieben haben
ko¨nnen(18) (dass) Maria einen Mann hat lieben ko¨nnen
(that) Maria a man has love can
(24) (dass) Maria einen Mann wird lieben haben(that) Maria was able to love a man
ko¨nnen
(19) (dass) Maria hat einen Mann lieben ko¨nnen (25) (dass) Maria einen Mann lieben wird haben
ko¨nnen
(20) (dass) Maria einen Mann lieben ko¨nnen hat*
These examples have ID tree:
These examples share the ID tree:
(dass) Maria einen Mann hat lieben ko¨nnen
Maria einen Mann wird haben lieben ko¨nnen
hat subcategorizes for a verb in past participle in- and (22) obtains LP tree:
flection because:
valency (hat) ={subject, vpast}
ID
v′and the edge constraint forw−−v−pa− s− t→w requires: n vn
′ vcat(w ) = vpast d
v
Maria einen Mann wird haben lieben ko¨nnen
subject
object
mf
mf
subject
object
vinf
vc
vinf
vc
det
df
df
det
mf
mf5.9 Obligatory Coherence mode as well as a mode generating all licensed
linearizations for a given input. It was used toCertain verbs like scheint require their argument
prepare all examples in this article.to appear in canonical (or coherent) position.
While the preliminary results presented here
(26) (dass) Maria einen Mann zu lieben scheint
are encouraging and demonstrate the potential of
(that) Maria a man to love seems
our approach to linear precedence, much work re-(that) Maria seems to love a man
mains to be done to extend its coverage and to
(27) (dass) Maria einen Mann scheint, zu lieben* arrive at a cohesive and comprehensive grammar
formalism.Obligatory coherence may be enforced with the
following constraint principle: if w is an obliga-
′tory coherence verb andw is its verbal argument,
References′then w must land in w’s vc field. Like barri-
Gunnar Bech. 1955. Studien u¨ber das deutsche Ver-ers, the expression of this principle in our gram-
bum infinitum. 2nd unrevised edition published
matical formalism falls outside the scope of the
1983 by Max Niemeyer Verlag, Tu¨bingen (Linguis-
present article and remains the subject of active tische Arbeiten 139).
4research.
Norbert Bro¨ker. 1999. Eine Dependenzgrammatik
zur Kopplung heterogener Wissensquellen. Lin-6 Conclusions
guistische Arbeiten 405. Max Niemeyer Verlag,
Tu¨bingen/FRG.In this article, we described a treatment of lin-
ear precedence that extends the constraint-based
Denys Duchier. 1999. Axiomatizing dependency
framework for dependency grammar proposed by parsing using set constraints. In Sixth Meeting on
Duchier (1999). We distinguished two orthogo- the Mathematics of Language, Orlando/FL, July.
nal, yet mutually constraining tree structures: un-
Erhard Hinrichs and Tsuneko Nakazawa. 1994. Lin-
ordered, non-projective ID trees which capture earizing AUXs in German verbal complexes. In
purely syntactic dependencies, and ordered, pro- Nerbonne et al. (Nerbonne et al., 1994), pages 11–
37.jective LP trees which capture topological depen-
dencies. Our theory is formulated in terms of (a)
Sylvain Kahane, Alexis Nasr, and Owen Rambow.
lexicalized constraints and (b) principles which 1998. Pseudo-projectivity: a polynomially parsable
govern ‘climbing’ conditions. non-projective dependency grammar. In Proc.
ACL/COLING’98, pages 646–52, Montre´al.We illustrated this theory with an application to
the treatment of word order phenomena in the ver- Andreas Kathol. 2000. Linear Syntax. Oxford Uni-
bal complex of German verb final sentences, and versity Press.
demonstrated that these traditionally challenging
Igor Melc´uk. 1988. Dependency Syntax: Theory and
phenomena emerge naturally from our simple and
Practice. The SUNY Press, Albany, N.Y.
elegant account.
Stefan Mu¨ller. 1999. Deutsche Syntax deklara-Although we provided here an account spe-
tiv. Head-Driven Phrase Structure Grammar fu¨r
cific to German, our framework intentionally per-
das Deutsche. Linguistische Arbeiten 394. Max
mits the definition of arbitrary language-specific Niemeyer Verlag, Tu¨bingen/FRG.
topologies. Whether this proves linguistically ad-
John Nerbonne, Klaus Netter, and Carl Pollard, edi-equate in practice needs to be substantiated in fu-
tors. 1994. German in Head-Driven Phrase Struc-
ture research.
ture Grammar. CSLI, Stanford/CA.
Characteristic of our approach is that the for-
Mike Reape. 1994. Domain union and word ordermal presentation defines valid analyses as the so-
variation in German. In Nerbonne et al. (Nerbonne
lutions of a constraint satisfaction problem which
et al., 1994), pages 151–197.
is amenable to efficient processing through con-
Hans Uszkoreit. 1987. Word Order and Constituentstraint propagation. A prototype was imple-
Structure in German. CSLI, Stanford/CA.mented in Mozart/Oz and supports a parsing
4we also thank an anonymous reviewer for pointing out
that our grammar fragment does not permit intraposition

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin