Linearization of Syntactic Dependency Graphs
in terms of Traversal Algorithms
Miyoko Yasui
Dokkyo University
1-1 Gakuencho, Soka, Saitama 340-0043 JAPANmyasui@dokkyo.ac.jp
Abstract
Assuming dependency graphs as syntactic representations instead of phra se structure
trees, this study attempts to derive the major word orders, SVO, SOV and VOS, via theset of three tree traversal algorithms common in graph theory and computer scie nce, andto explain their correlations with some of the syntactic differences: (i) clause-internal
scrambling in V-peripheral languages and its absence in SVO languages, (ii) obligatory
wh-movement in SVO languages and its absence in V-peripheral languages; and (iii)
pseudo-cleft wh-questions in V-initial languages besides in-situ wh-phrases.

The pro-posed word order parameter is three-valued in contrast to the more familiar two-valued
one, offering finer distinctions between SVO and VSO languages, which are both head initial.
Keywords: Dependency Graph, Traversal Algorithms, Scrambling, Wh-movement, Word
Order

1. Dependency Graphs with Bound Morphemes as Independent Nodes
We can identify two kinds of syntactic representations in the current theories
of syntax: phrase structure tree adopted in Chomsky (1957) and subsequent work,and dependency tree employed under various frameworks (e.g., Hudson (1984),
Mel’čuk (1988), Debusmann & Kuhlmann (2008), and Joshi (1985)). Formally,
they are both trees, with a root node dominating all the other nodes and each nonroot being immediately dominated by exactly one node (see Diestel 1997). Their PF
interpretations, however, are totally different; only the terminal nodes of a phrase
structure tree are pronounced, whereas every node is relevant to PF interpretation ina dependency tree. The contrast is illustrated by a pair of subtrees in (1a,b).

- 1612 -(1) a.

VP
b.
hit
2
1
V
DP
John
1
1
hit
John
(1a) is a phrase structure of the generative tradition. Its non-terminal nodes are
not pronounced, whether they are reanalyzed according to the bare phrase structure
theory of Chomsky (1995) or not. On the other hand, the two nodes of the dependency tree in (1b) are to be pronounced.
Another related difference is that a phrase structure tree like (1a), if the orderof sister nodes is specified by phrase structure rules or a particular value of the headparameter, is mapped into a single word ordering via a very simple algorithm: pronouncing the terminal nodes from left to right. A dependency tree like (1b), in
contrast, is not associated with any self-evident ordering algorithm. In fact, drawing on the idea in Gazdar et al. (1985), a dependency tree is decomposed into twoparts: immediate domination (ID) and linear precedence (LP) trees. Of course, theircorrespondence should not be totally free, and a number of formal constraints havebeen proposed such as projectivity and nestedness.i
A tree is a kind of data structure and its properties have been extensively studied in graph theory and computer science, where several algorithms have beenformulated and used widely to traverse all the nodes. The left-to-right PF interpretation mentioned above appears to be taken for granted among linguists, but it
has almost no resemblance to the common traversal algorithms on trees. Following Yasui (2003, 2004), I will adopt one set of standard graph-theoretic traversal
algorithms and apply them to dependency-based syntactic representations.ii The
key syntactic assumption taken from the generative tradition is that tenses, which
are bound morphemes in many languages, constitute independent syntactic nodes.
This is not adopted in most dependency-based studies and explicitly denied by
Hudson (1984) and Sugiyama & Hudson (2006). I will show that the morphologicalproperties of tenses and other bound morphemes in a dependency structure are crucial in causing displaced phenomena in its PF realization, which include scrambling,
wh-movement and verb-second.

2. A Dependency Graph and its Traversals
An infix arithmetic expression like (2a) has the prefix and postfix variants in- 1613 -(2b,c).
(2) a. x+y
b. +xyc. xy+(2a-c) can be associated with the single hierarchical structure in (3), where the operator + immediately dominates its operands.
(3)+{<+, x>, <+, y>}xyThe graphical configuration in (3) can be defined by the set of two edges or orderedpairs on its right; the set-theoretic notation will be adopted below. (2a-c) can bederived from (3) in terms of the well-known recursive algorithms on trees, i.e., bystarting a depth-first traversal from the root and pronouncing each node between,
before, and after visiting its child nodes, respectively (cf. Knuth (1997:318-320)).
They are called inorder, preorder, and postorder traversals. If the right child istraversed before its left child, the three more orderings given in (4a-c) are obtained.
(4) a. y+x
b. +yxc. yx+(2a-c) and (4a-c) have the same value if '+' is taken as addition.
It is reasonable to extend this line of analysis to word order variation found innatural languages exemplified in (5a-c).
(5) a. He scolded her.
b. Kare-ga kanozyo-o sikatta.
he-NOM she-ACC scolded'He scolded her.'c. Ha-fahan si Maria i bistidu-ña gi tenda.
3S-buy Mariathe dress-3S LOC store'Maria bought her dress at the sore.'(Chung 1990: 562)
The inorder and postorder traversal algorithms mentioned above derive (5a, b) fromthe common dependency structure defined in (6), which is given in English for easeof illustration.
(6) {<scolded, he>, <scolded, her>}(5c) can be derived analogously with irrelevant details set aside. As in (4), the childnodes of the verb are commutative in Japanese and Chamorro but are not in English.
(7) a. *Her scolded he.

- 1614 -b. Kanozyo-o kare-ga sikatta.
c. Ha-fahan i bistidu-ña gi tenda si Maria.
(Chung 1990: 563)
Examples of clause-internal scrambling like (7b) have been extensively studied
since Saito (1985), and they are attested in other head-final languages (see Choe
(1995) for Korean, Mahajan (1990) for Hindi, and Haider & Rosengren (2003) for
German among others). iii Steel (1978) reports that about half of the VSO languages in her sample have VOS as an alternative as Chamorro does. As for languages
arguably with SVO as their basic word order, S and O cannot be swapped in French,
Italian, Spanish, and Icelandic. Though it is hard to make strong typological generalizations especially on V-initial languages, I will assume that the paradigms exemplified in (5a-c) and (7a-c) hold in a substantial number of languages.iv

3. Clause-internal Scrambling: Commutability of S and O
I have been assuming a finite verb in a dependency structure to be divided into its bare form and the tense morpheme. So, (6) is to be replaced by (8).
(8){<[past], he, 2>,(nominative Case checking)<[past], scold, 1>,(c-selection)<scold, he, 2>,(-marking) v<scold, her, 1>}(-marking/accusative Case checking)
The first two elements of each triplet define directed edges that express the local
syntactic relations given in parentheses, and the third element is an annotation to
distinguish among child nodes, i.e., the relation of the second element (child) to thefirst element (mother) in contrast to the latter’s other child node. The graph defined in (8) is one way to embody the following familiar assumptions: (i) the nominative case is contingent on a tense, while the accusative is on a transitive verb;(ii) the subject (if not expletive) and object are both arguments of the verb but thelatter is more closely related to the verb (see Williams (1981), Frampton & Gutmann (2002), Marantz (1984), and Haider & Rosengren (2003)); and (iii) the selection by a finite tense of a verb phrase precedes its agreement with a nominative NP.
A more general statement combining (ii) and (iii) under the derivational view ofsyntactic building is that the local relation of a head with its complement is esta blished prior to that with its non-complement (or specifier).vi This distinction is
encoded in the third element of each triplet: 1 and 2 mean first and second Merge inthe sense of Chomsky (2008), respectively.

- 1615 -The local syntactic relations listed above are directional; (8) defines a directed graph with the matrix tense as its root. It is, however, not a tree since thesubject is directly governed by more than one element (i.e., the tense and the verb).
The standard traversal algorithms take trees as inputs but also work properly withrooted acyclic directed graphs like (8) if formulated as in (9):(9) Given a node A in a graph G and A has not been pronounced,
i. traverse A's child 2,
ii. pronounce A, andiii. traverse A's child 1.vii
The order of the three components in (9) is inorder; the preorder and postorder traversals are (ii)-(i)-(iii), and (i)-(iii)-(ii), respectively. The italicized proviso prevents
a doubly-connected node from being pronounced twice.
The inorder, postorder and preorder traversals of (8) yield (10a-c), wherechild 2 is traversed before child 1.
(10) Child 2 of [past] and child 2 of scold traversed firsta.
b.

INORDER: [past]-he-[past]-scold-(he)-scold-her-scold-[past]=> he [past] scold her (SVO)
POSTORDER: [past]-he-[past]-scold-(he)-scold-her-scold-[past]=> he her scold [past] (SOV)c. PREORDER: [past]-he-[past]-scold-(he)-scold-her-scold-[past]=> *[past] he scold her
Each node is to be pronounced where it is underlined in (10a-c); the occurrence ofhe after it has been pronounced is parenthesized. The resultant sequences are given
after the arrows. If we make a reasonable assumption that a tense morpheme must
be adjacent to the verb it is affixed to in the output of traversal, (10a,b) satisfy it but(10c) does not. The output of (10c) is asterisked in this sense.
If traversals are relaxed so as to let either child be traversed first at the two
branching nodes, three more sets of outputs are obtained.
(11) Child 1 of [past] and child 2 of scold traversed firsta. INORDER: [past]-scold-he-scold-her-scold-[past]-(he)-[past]=> *he scold her [past]b. POSTORDER: [past]-scold-he-scold-her-scold-[past]-(he)-[past]=> he her scold [past] (SOV)c. PREORDER: [past]-scold-he-scold-her-scold-[past]-(he)-[past]=> [past] scold he her (VSO)(12) Child 1 of [past] and child 1 of scold traversed first- 1616 -a.

INORDER: [past]-scold-her-scold-he-scold-[past]-(he)-[past]=> *her scold he [past]b. POSTORDER: [past]-scold-her-scold-he-scold-[past]-(he)-[past]=> her he scold [past] (OSV)c. PREORDER: [past]-scold-her-scold-he-scold-[past]-(he)-[past]=> [past] scold her he (VOS)(13) Child 2 of [past] and child 1 of scold traversed firsta. INORDER: [past]-he-[past]-scold-her-scold-(he)-scold-[past]=> *he [past] her scoldb.
c.

POSTORDER: [past]-he-[past]-scold-her-scold-(he)-scold-[past]=> he her scold [past] (SOV)PREORDER: [past]-he-[past]-scold-her-scold-(he)-scold-[past]=> *[past] he scold her

The asterisked outputs in (10)-(13) violate the verb-tense adjacency. Note, first,
that all the four outputs of postorder traversal satisfy the condition, resulting in
SOV and OSV. In postorder traversals, heads are pronounced after all their childnodes regardless of which child is traversed first; so they appear adjacent to eachother in clause-final position. As for inorder traversal, of the four outputs, only
(10a) is allowed, which yields SVO. viii In this way, the present theory predicts thecorrelation between the possibility of clause-internal scrambling and the position ofheads in SOV and SVO languages, which is confirmed by data from Japanese andEnglishOf the four outputs of preporder traversal, (11c) and (12c) are morphologically well-formed, yielding VSO and VOS. Thus, with respect to the S-O reversal,
Chamorro is correctly predicted to behave on a par with postorder languages rather
than inorder languages.
On closer examination, however, preorder traversals are
more restricted than postorder traversals. In particular, while the postorder trave rsal of (8) can visit either child of the root first, the preorder traversal necessarilychooses the edge between the tense and the verb, skipping the other edge with thesubject; otherwise, the verb-tense adjacency would be disrupted. Suppose that agiven word order counts as basic or unmarked if derived by a consistent traversal:
either child is given priority throughout. Then, the basic order obtai ned in inorderis SVO, with each node traversed as in (10a), whereas the preorder traversal should
proceed as in (12c), in which child 1 is traversed first and VOS results. This accords with the observation that V-initial languages like Malagasy and Palauan, unlike Chamorro, have the rigid VOS order, though the syntactic status of the so-- 1617 -called ‘subject’ has attracted much controversy (see Chung (2005a) and Pearson(2005) among others). I reserve my conclusion on this issue.

4. Moved and In-Situ Wh-phrases
4.1 Overt Wh-movement in Inorder Languages
The S-V-O order in tensed declarative clauses can be generalized into specifier-head-complement, which subsumes wh-movement. It is worth examining how
much of its parametric differences can be deducible from the theory advocated here.
First, English moves a wh-phrase obligatorily into the specifier of CP, whereas Japanese and Chamorro do not. Take (14) as an example, with its dependency
graph defined in (15).
(14) What did John buy?
(15) {<[WH], what, 2>, <[WH], [past], 1>, <[past], John, 2>, <[past], buy, 1>,<buy, John, 2>, <buy, what, 1>}
It has been proved that within the subgraph rooted by a tense, the edges marked
with 2 (i.e., specifiers) need to be traversed first in English. Let us suppose thaton the CP level headed by [WH], edge 2 is traversed first, which results in (16):(16)[WH]-what-[WH]-[past]-John-[past]-buy-(John)-buy-(what)-buy-[past][WH] ==> what [WH] John [past] buy
Traversing edge 1 first on the CP level yields (17).
(17) [WH]-[past]-John-[past]-buy-(John)-buy-what-buy-[past]-[WH]-(what)[WH] ==> John [past] buy what [WH]
[WH] is adjacent to what in both (16) and (17), but in neither is [WH] adjacent to[past]. Of the two outputs, (16) appears to be the more plausible for (14). As afirst approximation, suppose that [WH] needs to be adjacent to a tense just like averb is. Then, this morphological condition can be met in (16) if [past] moves to
COMP followed by Do-support, which are well-justified processes. ix The traversal output in (17), on the other hand, does not seem to be salvaged by any known
syntactic operation. Syntactic wh-movement is captured in the present theory as
obligatory traversal of the edge between the interrogative marker and the wh-phrase.
I will assume that this line of analysis can be extended to overt wh-movement inother SVO languages as well as the so-called verb second property in Germanic
languages.

- 1618 -Note that the subject-auxiliary inversion does not apply if the matrix subject
is a wh-phrase as in (18), with its dependency graph defined in (19a).
(18) Who brought it?
(19) a. {<[WH], who, 2>, <[WH], [past], 1>, <,[past], who, 2>, <[past], buy, 1>,<buy, who, 2>, <buy, it, 1 >}b. [WH]-who-[WH]-[past]-(who)-[past]-buy-(who)-buy-it-buy-[past]-[WH]==> who [WH] [past] buy it
Traversing (19a) in inorder with child 2 always first will yield (19b), where [WH],[past] and the verb are not interrupted by the initial wh-phrase; hence, the inversion
is unnecessary. It remains to explain why the inversion is absent entirely in theembedded context. I will assume that selection of [WH] by a higher interrogative
predicate somehow remedies its morphologically dependent status.
4.2 In-situ Wh-phrases in Postorder and Preorder Languages
Second, Japanese and Korean do not obligatorily front a wh-phrase. For instance, Japanese allows the two orderings corresponding to (14).
(20) a. John-ga nani-okaw-ta ka/no?
NOM what-ACC buy-PAST Q

b.

Nani-o John-ga
kaw-ta ka/no?
what-ACC
NOM buy-PAST Q'What did John buy?'
Suppose that (20a,b) share the configuration in (15), apart from the phonetic co ntent of each element. It is easy to verify that (20a, b) are obtained in postorder bygiving priority to child 1 and child 2 at each branching node, respectively. In e ither case, the interrogative marker, tense and verb are pronounced clause-finally
due to the head-last nature of the postorder traversal. Note that unlike in English,<[WH], what, 2> in (15) can but need not be traversed in Japanese. In this sense,
Japanese lacks syntactic wh-movement, and (20b) is an instance of clause-internal
scrambling discussed in Section 3.
As for V-initial languages, Georgopoulos (1991), Potsdam (2006), and thereferences cited therein show that quite a few of them allow a wh-phrase in situ.
Consider the Malagasy example in (21a), which is assumed here to have the configuration defined in (15) apart from irrelevant details.
(21) a. nividy inona i Bao?
buy.ACT what

Bao

- 1619 -'What did Bao buy?' (Potsdam 2006: 2158 with a slight modification)
b. [WH]-[past]-buy-what-buy-Bao-buy-[past]-(Bao)-[past]-[WH]-(what)[WH] ==> [WH] [past] buy what Bao
The in-situ ordering is obtained from (15) by consistently giving priority to child 1
as in (21b).
So far, Malagasy apparently behaves on a par with Japanese, which is V-final.
If the counterpart of (20b) is considered, some crucial differences arise. If child 2of the root is traversed first (and the rest is analogous to (21b)), (22) is obtained.
(22) [WH]-what-[WH]-[past]-buy-(what)-buy-Bao-buy-[past]-(Bao)-[WH]==> [WH] what [past] buy Bao
If (22) were to surface, the wh-object inona in (21a) would simply be fronted. In
fact, the construction with the clause-initial wh-object should be (23).
(23)

inona no novidin'

i Bao?

what PRT buy.PASS Bao'What was bought by Bao?'(Potsdam 2006: 2159)

While the Japanese scrambled wh-question in (20b) does not differ from (20a) apartfrom the word order, (23) differs from (21a) in two respects: the verbal morphology
is changed and the particle no is required. Setting aside the first point, much evidence has been offered that (23) is a kind of pseudocleft on a par with (24); both
involve the particle no.
(24)

ny mofo [ nonovidin-dRasoa ]the bread PRT buy.PASS-Rasoa'It was the bread that was bought by Rasoa.'(Potsdam 2006: 2169)

The pseudocleft strategy for clause-initial wh-phrases and focused phrases is attested in other Austoronesian languages. x

It differs from scrambling of a wh-phrase in V-final languages and overt wh-movement in SVO languages.
Before going into the pseudocleft analysis of (23) in more detail, it should be
noted that (22) violates the morphological condition on an interrogative marker te ntatively proposed for the English wh-question in (14): [WH] needs to be adjacent to
the tense. Presumably, the clause-initial position is by far the most salient perceptually in languages of any word order, and it should be able to host a semanticallyspecial expression like a wh-phrase and topic. English meets this need with its
child 2-first inorder traversal, while Japanese employs scrambling permissible in its
postorder traversal. I will claim that as (22) is unavailable, Malagasy and some- 1620 -other Austronesian languages resort to the pseudocleft strategy.
4.3 Clause-initial Wh-phrases in Preorder Languages
If (23) is a kind of pseudocleft, the verb is part of the headless relative rather
than the matrix element. In other words, (23) lacks a matrix tense and a copula
just as predicative constructions like (25a-c).
(25) a.

[ NP vorona ratsy feo]
bird

bad

ny

goaika.

voice the crow'The crow is a bird with an ugly voice.'b.

[AP falyamin' ny

proud PREPc.

[PP any

zanany]Rasoa.

the child.3SG Raso

an-tsena]'Rasoa is proud of her children.'aho.

PREP ACC -market 1SG. NOM'I am at the market.'(Potsdam 2006: 2157)
Predicative constructions without a finite copula are not uncommon in natural la nguages. Then, it is necessary to reconsider the morphological conditions on atense and an interrogative marker assumed for English.
If a clause contains a bound tense morpheme, it must be affixed on some appropriate free morpheme: a verbal in English and an adjective as well in Japanese,
for instance. If a language allows a tenseless clause, the adjacency condition is
vacuously satisfied.
As for an interrogative marker, Chung's (1991) clausal typing theory cruciallydepends on the assumption that languages like English lack it; they are forced tofront a wh-phrase to type a clause as interrogative. In contrast, I have been assuming that an interrogative marker exists in all questions, including a covert one inEnglish. Languages with overt wh-movement typically exhibit the verb-second
property, which I have claimed to be deducible from the adjacency condition between a phonetically empty interrogative marker and a tense. I thus need to claimthat tenseless questions like (23) contain a phonetically empty interrogative marker.
Since (23) is well-formed, the abstract interrogative marker should be morphologically innocuous without the presence of tense.
Note that the interrogative marker ka in Japanese can follow not only verbs
and adjectives but also nouns and prepositions in their predicative usages:(26) Kore-wa nani ka/dare-kara ka?
this-TOP what Q who from Q- 1621 -'What is this/Who is this from?'(26) are tenseless clauses with the wh-phrases in situ. If Malagasy is strictly headinitial, (23) can be analyzed as containing the abstract interrogative marker initiallyas the head of the entire sentence, followed by the wh-phrase in-situ, which, as
Potsdam (2006) and others argue, is the focus predicate of a pseudocleft, with theno-marked constituent as the complex subject. This is an instance of the unmarked head-initial order and is the mirror image of the head-final Japanese word
order: subject-predicate-ka.
If an interrogative bound morpheme in general needs to attach to a predic ative constituent rather than a tense, the morphological condition on the English a bstract interrogative marker proposed earlier should be revised accordingly; it should
be adjacent to a predicate in the matrix context, which is a constituent headed by afinite verbal element including the copula be.
In summary, to place a semantically special expression like a wh-phrase
clause-initially, natural languages employ different strategies depending on theirbasic word order or traversal mode: overt wh-movement as an instance of inorder
traversal, clause-internal scrambling inherently available in postorder traversal, andthe pseudocleft strategy in preorder languages.
4.4 In-situ Wh-phrases in Chinese and Indonesian
Potential counterexamples to the present theory in favor of Chung's (1991)
clausal typing theory are Chinese and Indonesian, which are SVO like English but
allow a wh-phrase in-situ like Japanese. As is well-known, Chinese is head-final
in N projections. If the interrogative marker is under C, as Chung (1991: 26) andothers assume, C projections are also head-final at least on the surface level.
Some Germanic languages are mixed as to the position of head across categories.
Then, it is necessary to specify the mode of traversal for each category in these la nguages rather than for an entire language once. Any typological study would beburdened with this much of complication. If Chinese is head-final within C projections, its in-situ strategy for wh-phrases is not surprising.
As for Indonesian, Chung (1991) analyzes in-situ and fronted wh-phrases on apar with those in other V-initial Austronesian languages like Palauan. Moreover,Cole et al. (2005) argue that the clause-initial 'subject' in verbal sentences of Standard Indonesian is like the clause-final 'subject' in other Austronesian languages in
disallowing a wh-phrase; a pseudocleft construction needs to be adopted instead. If- 1622 -Indonesian exhibits typical syntactic properties as V-initial languages, one possibility in my theory is to claim that its surface SVO order derives from some V-initialstructure. In fact, the Indonesian existential construction with the verb ada is Vinitial. As for apa(kah), which marks yes/no questions in Indonesian, it is clearlya free morpheme, and its presence in clause-initial position is not problematic (seeSneddon (1996)). Needless to say, much is to be worked out especially on what isoften referred to as subject in Indonesian as well as in V-initial languages.

5. Two-valued and Three-valued Parameters on Word Order
My approach is quite similar to Fukui (1993), Saito & Fukui (1998) andHaider & Rosengren (2003) in that it rests on the correlation between the positionof head and word order freedom. They share the idea that scrambling is possible
if its output accords with the head parameter value of a language in question; forexample, Japanese allows leftward scrambling since it does not disturb its rightheaded or head-final structure, while the opposite holds in English. I will concentrate on Fukui (1993) as it mentions V-initial languages while the other two do not.
He cites Chamorro data as examples of rightward scrambling in a V-initial languagein parallel with leftward scrambling in Japanese, which is V-final. If Palauan andMalagasy are strictly VOS as mentioned in Section 3, however, they do notstraightforwardly fit into Fukui's theory. As for leftward movement to the otherside of V, V-initial languages are predicted to behave on a par with SVO languages.
If the pseudocleft analysis of clause-initial wh-phrases in the former is correct, it istotally different from overt wh-movement in the latter.
Moreover, Fukui (1993) mentions extraposition and heavy NP shift as instances of rightward scrambling in English.
(27) a. I read a review ti last week [of John's book] i.
(Fukui 1993: 410)
b. They brought ti into my room [the beautiful pink dress] i.
Constituents to be moved rightward need to be heavy; so (28a, b) are not acceptable.
(28) a.?*I read a review ti last week [of it] i.
b.?*They brought ti into my room [that] i.
The heaviness does not govern leftward scrambling in Japanese or rightward
scrambling in Chamorro. Fukui and the other two studies mentioned above assume a familiar two-valued head parameter. The differences exemplified in (28) andinitial wh-phrases would favor the present approach with a three-valued parameter.

- 1623 -i

According to Debusmann & Kuhlmann (2008) and others, projectivity disallows
discontinuous dependency, and nestedness forbids cross-serial dependency. Since
discontinuous dependency is amply attested, while cross-serial dependency is rare,
projectivity needs to be relaxed but in a restricted manner, by limiting the numberof discontinuities in a subtree.
The mainstream dependency-based studies focus
on mathematical aspects of dependency trees and pay little interest to parametricdifferences as to word order. Specifically, ID and LP trees are integrated into o rder-annotated trees to which tree traversal algorithms are applied but for purposes
totally different from mine.
ii
Kural (2005) adopts the same traversal algorithms but apply them to standard tree
notations, whereby only terminal nodes are PF-interpreted. Brody (2000) adopts adependency-like structure to derive the linear order of tense, light verb and mainverb but his motivation is quite different from mine.
iii
It follows from the present theory that long-distance scrambling should betreated differently. This conclusion is supported by data involving A-binding, but I
will not go any further here.
iv
Quite a few researchers claim to derive some instances of V-initial order from
SVO, adopting Kayne's (1994) LCA.
v
Layered structures proposed by Hale and Kayser (1993) and others can be
adopted here, but the choice does not affect the overall argument in this paper.
vi
If each directed edge is expressed as an (annotated) ordered pair, and such pairs
are stacked as the structure is built up, the priority of specifier over com plement
corresponds to the last-in first-out mode in all the three word order types. See Fukui and Takano (1998) for a related but distinct approach.
vii

Given a set of ordered triplet of the form <x, y, n> (i.e., the edge x-y with the annotation n on it), to traverse A's child 2 is to find a node in the second slot of thetriplet where x=A and n=2, and go on to another triplet with the obtained node in its
first slot.
viii
English modal auxiliaries are often assumed to be base-generated under T. I
assume that the existence of bound tense morpheme as an independent syntactic
node limits their traversal choice to be consistently child 2-first.
ix
Head movement can be defined as an operation on graphs called edge contra ction- 1624 -(Diestel 1997: 16).
x
Clause-initial wh-phrases in Chamorro can be analysed analogously, but see
Chung (2005b).

References
Brody, Michael. 2000. Mirror theory: syntactic representation in perfect syntax .
Linguistics Inquiry 31. 29-56.
Cheng, Lisa. Lai. 1991. On the typology of wh-questions. Cambridge, MA: MIT
dissertation.
Choe, Jae W. 1987. LF movement and pied-piping. Linguistic Inquiry 18(2). 348353.
Chomsky, Noam. 1957. Syntactic Structures. Berlin: Mouton de Gruyter.
Chomsky, Noam. 1995. Bare phrase structure. In Webelhuth, Gert (ed.), Government and binding theory and the minimalist program, 383-439. Oxford:
Blackwell.
Chomsky, Noam. 2008. On phases. In Freidin, Robert, Carlos P. Otero & Maria
Luisa Zubizarreta (eds.), Foundational issues in linguistic theory: Essays inhonor of Jean-Roger Vergnaud, 133-166. Cambridge, MA: MIT Press.
Chung, Sandra. 1990. VP's and verb movement in Chamorro. Natural Language
and Linguistic Theory 8. 559-619.
Chung, Sandra. 2005a. What fronts? on the VP raising account of verb -initial order.
In Carnie, Andrew, Heidei Harley & Sheila Ann Dooley (eds.), Verb first: papers on the syntax of verb initial languages, 9-29. Amsterdam: John Benjamins.
Chung, Sandra. 2005b. Six Arguments for Wh-movement in Chamorro.
http://people.ucsc.edu/~schung/chung.6args.pdf. (20 September, 2008.)
Cole, Peter, Gabriella Hermon & Yassir Nasanius Tjung. 2005. How irregular is
WH in situ in Indonesian? Studies in Language 29(3). 553-581.
Debusmann, Ralph & Marco Kuhlmann. 2008. Dependency grammar: classification and exploration. http://www.ps.uni-sb.de/Papers/
paper_info.php? label=debusmann2008dependency (20 September, 2008).
Diestel, Reinhard. 1997. Graph theory. New York: Springer.

- 1625 -Frampton. John & Sam Gutmann. 2002. Crash-proof syntax. In Epstein, SamuelDavid & T. Daniel Steely (eds.), Derivation and Exploration in the minimalist
program, 90-105. Malden, MA & Oxford: Blackwell.
Fukui, Naoki. 1993. Parameters and optionality. Linguistic Inquiry 24. 399-420.
Fukui, Naoki and Yuji Takano. 1998. Symmetry in syntax: merge and demerge.
Journal of East Asian Linguistics 7. 27-86.
Gazdar, Gerald, Ewan Klein, & Geofferey Pullum. 1985. Generalized phrase structure grammar. Cambridge, Mass & Oxford: Harvard University Press &Blackwell.
Georgopoulos, Carol. 1991. Syntactic variables: Resumptive pronouns and a binding in Palauan. Dordrecht: Kluwer.
Haider, Hubert & Inger Rosengren 2003. Scrambling: nontriggered chain formationin OV languages. Journal of Germanic Linguistics 15(3). 203-267.
Hale, Kenneth & Samuel Jay Kayser. 1993. On Argument Structure and the Lexical
Expression of Syntactic Relations. In Hale, Kenneth & Samuel Jay Kayser (eds.),
The View from Building 20, 53-109. Cambridge, MA: MIT Press.
Hudson, Richard. 1984. Word grammar. Oxford: B. Blackwell.
Joshi, Aravind K. 1985. Tree adjoining grammars: how much context-sensitivity isrequired to provide reasonable structural descriptions? In Dowty , David R., Lauri Karttunen, & Arnold M. Zwicky (eds.), Natural Language Parsing, 206–250.
Cambridge, Cambridgeshire: Cambridge University Press.
Kayne, Richard. S. 1994. Antisymmetry of syntax. Cambridge, Mass: MIT
Press.
Knuth, Donald E. 1997. The art of computer programming, volume 1: Fundamental
algorithms. Boston: Addison-Wesley.
Kural, Murat. 2005. Tree traversal and word order. Linguistic Inquiry 36. 367-387.
Mahajan, Anoop. 1990. The A/A-bar Distinction and Movement Theory. Cambridge,
Mass: MIT dissertation.
Marantz, Alec. 1984. On the nature of grammatical relations. Cambridge, Mass:
MIT Press.
Mel'čuk, Igor. 1988. Dependency syntax: Theory and practice. Albany: State University of New York Press.
Pearson, M. 2005. The Malagasy subject/topic as an A' element. Natural Language
and Linguistic Theory 23(2). 381-457.

- 1626 -Potsdam, Eric. 2006. More concealed pseudoclefts in Malagasy and the clausal typing hypothesis. Lingua 116. 2154-2182.
Saito, Mamoru. 1985. Some asymmetries in Japanese and their theoretical implications. Cambridge, Mass: MIT dissertation.
Saito, Mamoru and Naoki Fukui. 1998. Order in phrase structure and movement.
Linguistic Inquiry 29(3). 439-474.
Sneddon, James Neil. 1996. Indonesian: A comprehensive grammar. London: Routledge.
Steele, Susan. 1978. Word order variation: a typological study. In Greenberg, J oseph H., C. Ferguson, & E. Maravcsik (eds.), Universals of human language,
585-623. California: Stanford University.
Sugiyama, Kensei & Richard Hudson (eds.). 2006. Word grammar: new perspectives on a theory of language structure. London: Continuum.
Williams, Edwin. 1981. On the notions lexically-related and head of a word.
Linguistic Inquiry 12. 245-74.
Yasui, Miyoko. 2003. A graph-theoretic reanalysis of bare phrase structure theory
and its implications on parametric variation. Linguistics and Phonetics (LP)2002. http://www2.dokkyo.ac.jp/~esemi003/publications/Yasui_rev.pdf. (20September, 2008.)
Yasui, Miyoko. 2004. An order-free representation of syntactic structure and thehead-parameter. Dokkyo University studies in English 60. 3-31. http://
www2.dokkyo.ac.jp/~esemi003/publications/EigoKenkyu.pdf. (20 September,2008.)- 1627 -