Miyoko Yasui 1

An Order-Free Representation of Syntactic Structure and the Head-Parameter
Miyoko Yasui
Dokkyo University
myasui@dokkyo.ac.jp
2006(slightly revised version of the paper published in
Dokkyo University Studies in English Vol. 60 (2004), 3-31)

1.

Trees as abstract data structures

A given piece of data can be represented in a number of ways, and the choice depends on
what task should be performed on that data. It is well-known in computer science that if anappropriate data structure is chosen, the algorithms to be used to carry out the task often
become relatively obvious.
In the field of generative syntax, syntactic structure has been represented by the abstract
data structure called tree. A tree such as (1) consists of a finite set of nodes and a finite set ofedges connecting them with the following two properties: (i) there is one node, called the root,that dominates all the other nodes and (ii) every node other than the root has exactly one nodethat immediately dominates it.
(1)

V
W
a

X
Y

Z

b

c

Since some ordering is almost inevitably imposed on the subtrees of each node, computerscience adopts trees that have one more property: (iii) the nodes each node immediately
dominates are ordered linearly. The kind of tree adopted widely in generative research ofnatural languages has property (iii). Moreover, it crucially distinguishes terminal andMiyoko Yasui 2
non-terminal nodes; only the former are subject to PF-interpretation. Because of property (iii),
the task of PF-interpretation is trivial. Take (2) for example.
(2)

IP
DP
D

I'
INFL

VP

John will

V

DP

meet

D
Mary

Reading the terminal nodes of (2) from left to right yields its PF-interpretation. The nonterminal nodes are ignored under this task but have functions such as defining constituentsand important syntactic relations holding among them such as binding.
The theory of bare phrase structure proposed by Chomsky (1994) and pursued in
Chomsky (1995, 1999, 2000, 2001) and others is innovative in simplifying the node labelingsystem by eliminating non-branching intermediate nodes and using input lexical items as
projection labels. In particular, the bare phrase structure representation of (2) is (3), where
lexical items as projection labels are asterisked here for ease of illustration.
(3)

will*
John

will*
will

meet*
meet

Mary

(3) is no different from (2) in retaining the traditional distinction between terminal nodes,
which have PF value, and non-terminal nodes, which do not. Thus, the trivial algorithm fordeducing word order mentioned above is available. Chomsky, however, does not adopt it,
abstractly assuming a tree representation without property (iii). Along this line, Kayne (1994),
Takano (1996), and Fukui and Takano (1998) propose ingenious theories of word order,
rejecting the algorithm inherent to a tree representation. These attempts appear to be against

Miyoko Yasui 3
the afore-mentioned insight in computer science; choosing an ordered tree makes its
PF-interpretation extremely easy, but this naturally given algorithm is turned down. If word
order plays no substantial role in the core syntactic computation, we should adopt a truly
order-free representation.
In fact, linearization of terminal nodes has no significant meaning in more typicalusages of tree as data structure. For example, all the workers of a company can be naturally
represented as a tree: the president is the root node, and those who are next in theadministrative hierarchy are directly dominated by the president and so on.

In this case, theterminal nodes are clerks without any subordinates and lining them up is not particularly
meaningful. More important are the subtrees rooted by each of the non-terminal nodes, whichcorrespond to the departments and subdepartments of the company, as described below:(4)

President
Director1

Division Head 1abcDivision Head 2

Company

Director 2

...

...
Finance Department...

The whole tree is the company, and the subtree rooted by Director 1 is one of its departments,
say, Finance Department, which in turn has several divisions. In this way, each non-terminal
node in (4) has the double function of representing a department/section of the company andits chief. Going back to (2), the two terminal nodes meet and Mary form the constituent that isheaded by meet, which is represented by the projection node VP. By analogy to (4), we cansay that Mary belongs to the group headed by the verb meet. Then, constituency represented
by projection nodes in (2) should be expressible by subtrees without them. (3) might be closer
to (4) in that a lexical head is used as the label of the constituent it heads in addition to that ofitself, but its multiple appearance is superfluous.

Miyoko Yasui 4
The nodes of (4) are persons working for the company, and there are a number of ways
to list them up. For instance, we can start from the president, list up all the department
directors, followed by the section heads and so on. Another systematic way is to line up all
the members of one of the smallest sections of some department, followed by those of anothersection of the same department, and so on. Other orderings of the workers are conceivable.
(4) is thus not inherently associated with a fixed ordering of its nodes unlike (2) and (3),although all of them are trees. If the configurational property of a sentence is expressed on apar with (4) rather than (2) and (3), it can be regarded as an order-free representation. In thispaper, I will propose a theory of order-free syntactic representation along this line.
The rest of this paper is organized as follows: I will discuss in Section 2 how arithmetic
expressions can be represented in an order-free manner and mapped into multiple orderingsby the simple tree traversal algorithms commonly used in computer science. In Section 3, I
will extend the order-free notation that dispenses with projection labels to Japanese andEnglish sentences without losing an explanatory basis for constituency and core syntactic
relations, which have been defined in terms of PF-vacuous projection labels in standard tree
representations. Section 4 will be concerned with the limited application of the order-freenotation in Brody (2000) and its weaknesses. In Section 5, I will argue that the left/right
distinction of each node's children, which is crucial for the traversal algorithms to work, canbe properly made according to the derivational history of structure building. I will further
claim that two of the major parametric differences between Japanese and English are
attributed to the distinct modes of traversal: word order variation in Japanese and its absence
in English, and overt movement properties in English and their absence in Japanese. Section 6
will be devoted to an elaboration of the traversal algorithms in terms of the abstract data
structure called stack. Remaining issues will be briefly discussed in the last section.

2.

Order-free representations of arithmetic expressions

Miyoko Yasui 5
Arithmetic expressions familiar to most of us such as (5) can be represented by the two kindsof trees in (6a,b).
(5)

a+b*c

(6) a.

E
E

b.

+

T

T

T

F

F

a

b

*

+
a

F

*
b

c

c

(6a) is on a par with trees assumed in generative syntax; the non-terminal nodes of (6a) haveno PF values and (5) is derived straightforwardly by lining up its terminal nodes from left toright. (6b), on the other hand, does not so simply define the order in (5); + immediately
dominates a and * but it neither precedes nor follows them.
There is a well-established algorithm that derives (5) from (6b) (cf. Knuth (1997)
among others). The nature of a tree is recursive in that any of its subtrees has a tree structurewith the properties (i)-(iii) mentioned in Section I, which offers the following recursivealgorithm for ordering the nodes in (6b):(7)

If there is a node p, theni.

traverse p's left child,ii.

pronounce p, andiii.

traverse p's right child.

If (7) is applied to the root of (6b), (7) is called again and applied to its left child, namely, a.
Since a has no child nodes, (7i,iii) are skipped and only (7ii) is executed, which results in the
pronunciation of a. At this stage, (7i) of the first application of (7) to the root has been carriedout, so that (7ii) is executed, which results in the pronunciation of the root +. Then, (7iii) of
the initial application of (7) is carried out, which eventually leads to the pronunciation of theremaining nodes in the order b * c. (7) is referred to as inorder traversal algorithm inMiyoko Yasui 6
computer science, and (5) is the PF-interpretation of (6b) obtained through it. Applying (7ii)
before and after (7i,iii) yield (8a,b), respectively.
(8)

a.

+a*bc

b.

abc*+

The two algorithms at stake are called preorder and postorder traversals, respectively. (5) and(8a,b) have the same interpretation if multiplication (*) is given priority to addition (+) in (5)as is usually assumed.
According to (7) and their preorder and postorder counterparts, the nodes are traversed
exactly in the same order but they are pronounced at different times, as illustrated below:(9)a.

preorder:+a+*b*c*+(=(8a))b.

inorder:+a+*b*c*+(=(5))

c.

postorder:+a+*b*c*+(=(8b))

Each symbol is pronounced in the underlined position. In this way, (6b), which itself does notdefine any word order, can be rendered into (5) and (8a,b) by the independently definedalgorithm given in (7) and its variants. In contrast, (6a) is associated only with the infix
expression in (5); (8a,b) require distinct trees in (10a,b).
(10) a.

E
+

b.

E

E

T

E

T *

T F

T

T

F

F

F

F

F

c

a

b

a

b

c

T

+
*

It can be said that (6b) is an order-free or purely configurational representation shared by thethree arithmetic expressions in (5) and (8a,b).

3. An initial extension of order-free representations to natural languages

Miyoko Yasui 7
Addition and multiplication are two-argument functions like transitive verbs in natural
languages. The arithmetic expressions in (5) and (8b), therefore, can be regarded on a par withsentences of head-initial and head-final languages, respectively. In particular, the English andJapanese sentences in (11a,b) can be associated with the bilingual tree in (12) if thepredicate-internal subject hypothesis is not taken and other details are set aside:(11) a.
b.

Mary says that John helped Tom.
Mary-ga John-ga Tom-o
Nom

(12)

Nom

tasuke-ta

toittei-ru

Acc help past Comp say-pressays/itteiru
Mary/Mary-ga

that/tohelped/tasuketa

John/John-ga

Tom/Tom-o(12) has almost the same configuration as that of (6b); thus, (11a,b) are expected to be
derivable by pronouncing the nodes in (12) in the inorder and postorder manners stated in
Section 2, respectively. One proviso is that the traversal algorithms work properly only if eachnode's left and right child are distinguished. I will argue in Section 5 that the distinction ismade based on the derivational history of sentence formation.1
While Kayne (1994) argues that Japanese shares the universal SVO or SHC order withEnglish, I will stand on a more conservative position: they are hierarchically the same but
linearly different. What is innovative in the present theory is that an order-free representationsuch as (12) is adopted to capture the configurational properties of a sentence and it is mapped
into more than one ordering. The two kinds of traversals mentioned above constitute theparameter for deducing word order differences. The spirit is quite close to Kayne's idea of
mapping asymmetric c-command into linear ordering in that the whole configurational1

The theory to be proposed below is an extension of Yasui (2002, 2003a, 2003b, 2004).

Miyoko Yasui 8
representation of a sentence determines its word ordering but the claim is quite the contrary. 2
Let us examine how constituency can be defined in the order-free notation. (2) and its
equivalent under the bare phrase structure theory in (3) can be simplified as in (13):
(13)

will
John

meet
Mary

(13) will be elaborated in Section 5 by incorporating the light verb and the predicate-internal
subject hypothesis. (13) has two non-trivial (sub)trees: the whole tree rooted by will and theone rooted by meet. The two (sub)trees are the constituents expressed by the upper will* andmeet* in (3). (13) has no subtree that corresponds to the lower will* in (3) or the intermediate2

Whitman (2001) presents several pieces of evidence to support the head-initial underlying

structure for Japanese.
(1990:291-292).

One of them is the contrast observed in Saito and Murasugi

Second, Whitman, following Kayne's idea, assumes that the nominative

case-marker takes a clause on its right and a noun phrase moves out of the clause to its spec
position.

If this is correct, the nominative case-marker and the preceding noun phrase do notform a constituent. Whitman argues that this conclusion is supported by the fact that anominative phrase resists scrambling, as exemplified below:(i)*[sono hon -gai, [Taroo-ga [ ti ii
thatbook-Nom

Nom

to ]

good Compomotteiru ]] (koto)

thinking is fact"(that) that book, Taroo thinks is good"
Scrambling of a nominative phrase is possible if it is semantically easy to associate with its
original position as in (ii).
(ii)[ Inoue Koose koso-gai[ daremo-ga

exactly-Nom
omottei-ru ]]everyone-Nom[ti mottomo tuyoi juudo-ka da] tomoststrong judo man is Comp(koto)

thinking-present fact"(that) Kosei Inoue, everyone thinks is the strongest judo man"
Then, the ungrammaticality of (i) does not show the non-constituency of the scrambled phrase
but a difficulty in its reconstruction.

Miyoko Yasui 9
projection I' in (2). This is a welcome result if an intermediate projection is syntactically andsemantically invisible as Chomsky (1994:10) claims.
C-command can also be defined without recourse to projection labels. (14) shows atypical contrast in reflexive binding, and its bare phrase structure and order-free
representations are (15a,b), respectively.
(14)

The mother of the boy talked about herself/*himself.

(15) a.

[past]*
the*themother*motherof*ofb.
[past]*

thetalk[past]

motherabout

about*

ofherself/himself

herself/himself

the

talk*

talk

the* aboutthe[past]boyboy

In (15a), the upper the* is immediately dominated by the root, which dominates the reflexive,
but the lower the* is immediately dominated by of*, which does not dominate the reflexive:the latter does not c-command and hence does not bind the reflexive. Applying the samedefinition of c-command to (15b) can account for the contrast; the upper the c-commands thereflexive but the lower the does not. Note that in the subject of (15a), the upper the
c-commands of, the lower the and boy, while it is not the case in (15b). Long-distance binding,which holds between phrases, is attested in many languages, but heads are not known to berelated non-locally. This supports (15b) over (15a); a head fails to c-command distant heads
within its complement. A local movement of a head to the head selecting it can be formulated
simply as the reduction of the two nodes by removing the edge between them, which does notradically change the overall configuration. A (non-cyclic) long-distance head-movement, if itexisted and were formulated as edge elimination, would not only combine the two heads atstake but also eliminate the nodes between them.

Miyoko Yasui 10
It can be said that constituency and core syntactic relations such as binding can be
defined in the order-free notation, without recourse to PF-vacuous projection nodes that havebeen standardly assumed in syntactic representations.3

4.

Brody's (2000) Mirror Theory and Kayne's (1994) Universal Order Hypothesis

In an order-free representation like (15b), a head immediately dominates its spec andcomplement just as an arithmetic operator directly connects to its operands in (3b) and adepartment director of a company directly dominates his or her subordinate in (4). (3b) and(4) presumably look natural but (15b) might not to most linguists in the long tradition ofgenerative grammar. Brody (2000) is an exception, adopting the order-free notation in alimited part of syntactic representation, but his usage of the notation is motivated to express
the head-complement order directly under Kayne's universal order hypothesis, contrary to theposition here.
The most important in Brody's theory is the mirror principle in (16).
(16) X is the complement of Y in syntactic structure only if X-Y form a morphological unit.4(16) is intended to account for the symmetry observed between syntactic structures ofhead-initial languages like English and their morphological structures. In particular, the orderof a verb and its associated functional heads in English is the mirror image of their

3

Explicitly defined notions like c-command and binding are to be eliminated in minimalist

syntax.

Following Reuland (2001), I argued in Yasui (2006) that they can be largely

reduced to probe-goal relations.
4

The original statement in Brody (2000:29) is: "X is the complement of Y in syntactic

structure only if Y-X form a morphological unit." As a reply to my clarification question,
Brody (p.c.) says that "Y-X in this statement does not imply linear order, and probably ...
X-Y... would have been more transparent." I modified the statement accordingly in (16).
The mirror principle stated in Brody (2000: 42) is clearer but is not adopted here to avoid
referring to the notion of specifier in morphology.

Miyoko Yasui 11
morphological realization. Consider the schematic clausal structure in (17a).
(17) a.

IP
SU

b.
I'

Infl
SU

INFL

vP

(SU)
v

v
(SU)

v'

V
OBJ

VP
OBJ

V'
V

In (17a), INFL selects a projection of the light verb v, which selects a projection of V; thethree elements appear linearly in the order INFL-v-V. They form a morphological unit
"V-v-INFL." To express this inverse relation directly, Brody reduces (17a) to (17b), where thethree morphemes in question are directly connected without projection nodes in the reverse
order of the morphological unit they form. The order-free notation is adopted here to express
the head-complement relations established by INFL, v and V.
If a representation without projection nodes is suitable to express head-complement
relations such as those holding between INFL, v and V in English, it is not unreasonable toextend it to other types of head-complement relations as well as spec-head relations. What(16) says, however, is that X is the complement of Y only if Y is a suffix that is to be attachedto the right of X; if Y is a free morpheme, X is not the complement of Y but a spec of Y or the
spec of some element of Y. In particular, the overt complementizer that and a modal likeshould do not form a morphological unit; neither does should form a morphological unit withthe following main verb. Brody is forced to conclude that the main verb should be analyzed asa spec of should, which in turn should be analyzed as a spec of the complementizer.
Moreover, when a [WH] COMP selects a clause headed by the modal should, a wh-phrase it
attracts and should have to be analyzed as specs of it (and some functional head related to it).
Instead of adopting Brody's radical definition of head-complement relation, I will

Miyoko Yasui 12
maintain that all constituents that have long been regarded as complements are in factcomplements, but represent them without projection nodes as in (15b). It is partly because themirror principle in (16) has some unwanted arbitrariness, which comes from the question of
why the constituents of a morphological unit must appear in reverse syntactically; they might
as well appear in the same order. Actually, in Japanese and many other head-final languages,
a verb and its associated bound morphemes like tense and aspect appear in the same order insyntax and morphology. Brody cites the Hungarian example in (18b) to support his mirror
theory, and (18b) is a similar example from Japanese.
(18) a.

olvas-hat-om
read-permissive -1sg,presentb.

yom - er-ta
read-can-past

The order of the three morphemes in (18a) is mirrored in (19a).
(19) a.

TP

b.

T

TP

ModP
Mod

-om

-hat

ModP
VP

VP

V

V

olvas

yom

T

Mod

-er

-ta

For (18b), I assume a conservative analysis in (19b) without adopting Kayne's universal SHC
order hypothesis. The order of the morphemes in (18b) coincides with that in (19b).
Applying the order-free notation to (19a,b) yields the bilingual representation in (20).
(20)-om/ta...

-hat/-er...

olvas/yomOn the other hand, Brody reduces only (19a) into (20), providing (19b) with a head-initial
representation involving abstract functional heads and movement triggered by them. It isMiyoko Yasui 13
well-known that a morphological unit is universally right-headed (c.f., Williams (1984));
however, syntactic structure is left-headed in English, Hungarian and others while rightheaded in languages like Japanese and Korean at least on the superficial level. In theory,
syntactic head-complement structure and morphological structure can be (i) in a mirror-image
relation or (ii) a normal-image relation, and the universal word order can be (iii) head-initial
as in (19a) or (iv) head-final as in (19b). Brody adopts the combination of (i) and (iii) basedon the fact exemplified by (18a), but what (18b) straightforwardly suggests is that (ii) and (iv)
are correct.5 The morphemes in (18a,b) appear to be equally strongly bound with each other,disallowing any material to intervene among them. If (i) and (iii) are assumed, thestraightforward account of the morphological unity of (18a) based on the order-free notationin (20) is not applicable to that of (18b), and the opposite is true if (ii) and (iv) are assumed.
The above dilemma can be circumvented if the universal word order hypothesis,
whether it is (iii) or (iv), is given up. If syntactic structure can be left-headed or right-headed
but morphological structure is universally right-headed for some reason that does not concern
us here, a free morpheme appears according to the head-parameter value but the right-headed
principle in morphology overrides it if the element in question is a suffix. Aoyagi (1998)
pursues this line of analysis for Japanese under Kayne's hypothesis. The reasoning can beapplied in the opposite way; in head-final languages like Japanese, the head-parameter value
is respected in morphology but it is overridden in head-initial languages if suffixes are
involved as in (17a) and (18a).
Brody's mirror theory is an attempt to capture the strict locality observed on thesequence of INFL, v and V in English and others in terms of representations without
projection nodes, and to deduce the syntactic head-complement relation from morphology. I
have argued in this section that the head-complement relation should not be so narrowly

5

Kayne (1994:38-41) notices this problem, illustrating it with the compound overturn.

Miyoko Yasui 14
limited and that the order-free notation should be adopted extensively to express any local
syntactic relations regardless of whether they correspond to local morphological relations or
not.

5.

The spec/complement distinction based on the derivational history

Analyses of the word order variation or scrambling phenomena in Japanese fall into two
major types: configurational and non-configurational. The configurational approach isrepresented by Saito (1985), according to which the basic word order of Japanese is SOV, ormore generally SCH, and the spec is positioned hierarchically higher than the complement
just as in English. A so-called scrambled sentence is assumed to be derived by a syntactic
operation. The non-configurational approach is proposed by Hale (1980, 1981) and Farmer(1984), where a Japanese sentence is assumed to be 'flat' with no hierarchical distinction
among arguments. The essence of this approach is that scrambled sentences are basegenerated without recourse to a syntactic operation. Recent versions of essentially the sameidea are proposed by Boskovic and Takahashi (1998), and Ikawa (2003). The theory
advocated here is configurational in that Japanese and English are assumed to have the samehierarchical structure, but differs from Saito's position in 'base'-generating sentences withbasic and scrambled word orders, deriving them from the shared order-free representation.
The configurational approach generally assumes (21a,b).
(21) a. The selectional requirement of an internal argument of a lexical head is satisfied
before that of its external argument.
b. The selectional requirement of a functional head is satisfied before its agreement (orfeature-checking) requirement.
(21b) is uncontroversial in recent minimalist research. (21a) is based on the external/internal
distinction among arguments proposed by Marantz (1984), Williams (1984) and others. I willassume that just like ordinary trees, order-free representations are built bottom up accordingMiyoko Yasui 15
to (21a,b). Merging two objects here means adding one ordered pair or directed edge to thegraph already formed. Then, (22a,b) hold.
(22) Given a lexical item as a node p in the graph formed,a.

If p has two downward edges, the one connecting to its complement or internalargument is added before that connecting to its spec/external argument.

b.

If p has just one downward edge, it connects to its complement/internalargument.

p's left child is the spec/external argument, and p's right child, the complement/internalargument. In this way, the left/right distinction of each node's child nodes can be properly
made based on the derivational history of sentence formation, and the traversal algorithms
given in Section 2 can properly derive the SHC and SCH order from an order-free
representation like (12). This point will be elaborated in the next section.
Going back to (12), if the predicate-internal subject hypothesis is taken, it should be
replaced by (23a) or (23b):(23) a.

[present]/rub.

[present]/ru

say/ittei
Mary/Mary-ga

that/tov
Mary/Mary-ga

say/ittei[past]/ta
help/tasuke
John/John-ga

that/to[past]/ta

Tom/Tom-ov
John/John-ga

help/tasuke
Tom/Tom-o(23a) involves two verbs and they immediately dominate the heads of their external andinternal arguments. (22a,b) ensure that their left and right child nodes can be distinguished on
the basis of the derivational information on (23a). In (23b), the light verb is posited, whichhelps distinguish the external and internal arguments hierarchically. Since the light verb and aMiyoko Yasui 16
lexical verb it selects are subsequently combined by head-movement, which has been
regarded in Section 3 as the elimination of the edge between them and their reduction into one
node, (23b) will become indistinguishable from (23a) at the point where it is subject toPF-interpretation. Thus, I will assume the analysis without the light verb here for ease of
exposition.
(23a) by definition is not a tree, but it has the property (i) mentioned in Section 1 and allof its subtrees do the same. The subjects are doubly pronounced if (7) applies to (23a):
immediately before the tenses as well as the verbs. This can be avoided simply by modifying
the first part of (7) as follows:(24)

If there is a node p and p has not been pronounced, then(24) guarantees that those nodes that have been pronounced are not traversed again. The
inorder and postorder traversals of the English and Japanese versions of (23a) with themodification in (24) are given in (25a,b), respectively:(25) a.

[present] -> Mary -> [present] -> say -> that -> [past] -> John -> [past] -> help-> Tom ->help -> [past]-> that -> say -> [present](cf., (11a) Mary says that John helped Tom)b.

ru -> Mary-ga -> ru -> ittei-> to-> ta-> John-ga -> ta -> tasuke->Tom-o ->tasuke -> ta -> to -> ittei -> ru(cf., (11b) Mary-ga John-ga Tom-o tasuke ta to ittei ru)

In (25a), Mary is pronounced due to the edge coming from the matrix tense, so that it isskipped in the traversal stating from the verb say. The same is true of John in (25a) as well as
Mary-ga and John-ga in (25b).
It has been shown that two orderings have been derived from the single order-free
representation in (23a). Actually, the Japanese sentence in (11b), which has the so-calledbasic word order, has other variants given in (26b-d):(26) a.

[Mary-ga [John-ga Tom-otasuke ] ta toittei ru](=(11b))Miyoko Yasui 17
Nom

Nom

Acc help

past Comp say presentb.

[Mary-ga [Tom-o John-ga tasuke ta] to ittei ru]

c.

[[John-ga Tom-o tasuke ta] to Mary-ga ittei ru]

d.

[[Tom-o John-ga tasuke ta] to Mary-ga ittei ru]

A single application of clause-internal scrambling to the embedded and matrix clauses,
respectively, produces (26b,c), and its double application yields (26d). How can (26b-d) be
obtained from (23a)?
Note that the postorder traversal in (25b) that generates the basic word order in (26a) is
not economical in that most of the nodes are pronounced at later stages, which are indicatedby underlines. The inorder traversal in (25a) takes ten steps to pronounce all the nodes of(23a), and the last five steps have no PF effects. On the other hand, the postorder traversal in(25b) requires all the steps to pronounce the nodes of (23a). This is because a postorder
traversal starts from the root but the root is pronounced at the very end by definition. A
postorder traversal is more economical if it starts from a leaf node, which by definition is
pronounced immediately. (23a) has three leaf nodes and starting from each of them in the
postoder and depth-priority manner yields (27a-c):(27) a.

Mary-ga -> ittei-> to-> ta-> John-ga -> ta-> tasuke ->Tom-o ->tasuke -> ta -> to-> ittei -> ru (=(26a))b.

John-ga -> tasuke ->Tom-o ->tasuke -> ta -> to -> ittei -> Mary-ga -> ittei -> ru(=(26c))c.

Tom-o -> tasuke -> John-ga -> tasuke -> ta -> to -> ittei -> Mary-ga -> ittei -> ru(=(26d))(26b) can be derived as a variant of (27a) by traversing the right child of tasuke before its leftchild. (27a), which yields the same PF output as (25b) does, requires thirteen steps before all
the nodes are pronounced, while (27b,c) take only ten just like the inorder traversal given in(25a). (25a) and (27b,c) can be said to be more economical than (25b), (27a) and its variantMiyoko Yasui 18
producing (26b). Note that the complement clause in (26a,b) is center-embedded, while thatof (26c,d) is positioned on the left edge and that of the English sentence in (11a) is on theright edge. Hawkins (1994) argues that center-embedding causes parsing difficulties. In fact,(26a,b) require a pause before the beginning of the complement clause in pronouncing andunderstanding them.
It has been argued that a given order-free representation can be traversed in inorder or
postorder, which constitutes the parameter. The root is assumed to be the only starting pointin the standard traversal algorithms. The root is special in that it dominates all the other nodes.
A leaf node is special in the opposite sense: it dominates no nodes. It is natural to include leaf
nodes as possible starting points in addition to the root. I will claim that parsing decides or
imposes a preference on the starting node of each traversal: an inorder traversal starts from theroot, while a leaf node distant from the root is a preferred starting point in a postorder
traversal.6 Since an order-free representation has only one root node but usually has morethan one leaf node, head-final languages like Japanese, which are subject to the postorder
traversal algorithm, show word order variation, whereas English and other SHC languages donot.
In this connection, a case of long-distance scrambling such as (28) cannot be derived bya systematic traversal of (23a), which is a welcome result.
(28) [Tom-oi [Mar-ga [John-ga ti tasuke ta ] to-Acc -Nom-Nom help

ittei ru ]past that say present"Tom, Mary says that John helped."
To derive (28) from (23a), it is necessary to start from the embedded object, skip theembedded subject, pronounce the matrix subject, go down to the embedded verb and finally6

Alphonce and Davis (1997) present a performance-based account of the presence ofleftward overt wh-movement and the absence of comparable rightward movement.

Miyoko Yasui 19
go up to the root. This traversal is unsystematic and extremely inefficient. The scrambled
constituent is stressed and focused unlike the left-peripheral phrases in (26c,d), and it should
be analyzed as deriving from a distinct configuration with a functional category of some sort
triggering the scrambling. I will conclude that the kind of variation arising from themultiplicity of postorder traversal is limited to cases of clause-internal scrambling.
In addition to the difference in word order freedom, another major contrast between
Japanese and English can be naturally accounted for under the present theory: English has
overt leftward movement while Japanese does not. This point can be illustrated with thetraversals in (29a,b), which result in (11a) and (26c), respectively(29) a.

[present]

b.

ru

say
Mary

ittei

that

Mary-gato[past]

ta
help/tasuke

John

Tom

tasukeJohn-gaTom-oSince the inorder traversal in (29a) starts from the root, the matrix subject is pronounced dueto the edge coming from the root rather than the one from the verb say; for the same reason,
the embedded subject is traversed after the embedded tense but not after the verb, which ishierarchically lower than the tense. The edges that have not been traversed are indicated bybroken lines.

In contrast, the postorder traversal (26c) depicted in (29b) begins at theembedded subject and processes the rest of the representation in a depth-priority manner.
The two subjects are doubly-connected and the edges coming form the lower node aretraversed. According to the theory here, overt movement or displacement amounts to thepronunciation of a doubly-connected node by traversing the edge coming from a node nearer
to the root and bypassing the one from the lower node. (29a) involves overt movements in thissense, whereas (29b) does not.

Miyoko Yasui 20
Since each of the subjects in (29a,b) is dominated by the two nodes that are directly
connected to each other, displacement properties are not obvious. The contrast shows up moreclearly in case of wh-movement. (30a,b) are to be analyzed as sharing the representation in(31).
(30) a.
b.

[ Mary asked [ who John helped ]][ [ John-ga dare-otasuke ta ka ] Mary-ga tazune-ta ]Nom who-Acc help past Q

Nom

ask-past

Lit. "John helped who, Mary asked."(31)[past]/ta
ask/tazune
Mary/Mary-ga[WH]/ka[past]/ta
help/tasuke
John/John-ga

who/dare-o

The inorder traversal of the English version of (31) that starts from the root is given in (32a),
and the postorder traversal of the Japanese version that starts from the embedded subject is
described in (32b).
(32) a.
b.

[past] - Mary - [past] - ask - [WH] - who - [WH] - [past] - John - [past] - help
John-ga - tasuke - dare-o - tasuke - ta - ka - tazune - Mary-ga - tazune - ta

The edges traversed in each case are as follows:(33) a.

[past]

b.

ta

ask
Mary

tazune[WH]

Mary-ga[past]

ta
help

John

ka

who

tasukeJohn-gadare-oMiyoko Yasui 21
At the point where the inorder traversal that has started from the matrix tense reaches [WH],there are two ways to go: towards the embedded tense or wh-phrase.

Since the sentence isconstructed according to (21a,b), the edge or ordered pair with the wh-phrase has been added
later than the one with the embedded tense; the wh-phrase is the spec or left child of [WH],and the embedded tense is its complement or right child, though they are depicted in the
opposite way in (33a). It follows that the wh-phrase is traversed and pronounced before theembedded tense, and accordingly, its edge coming from the embedded verb help is nottraversed. On the other hand, the postorder traversal in (33b) starts from the embedded subject
John-ga, goes up to the branching root, tasuke (help), and makes the wh-phrase pronounced
It should be noted that since it is postorder, the traversal goes back to the branching root
instead of climbing the other edge connecting to ka (Q). In this way, wh-movement in the two
languages can be analyzed uniformly as involving a wh-phrase connected to a [WH] COMP
attracting it as well as to a lexical category selecting it. The difference is that the wh-phrase ispronounced near the [WH] COMP in English, while it is pronounced near the verb selecting it,
which is due to the distinct modes of traversal.7

6.

Stack as a Representation of Derivational History

As mentioned in the previous section, merging a head X and a non-head Y (spec orcomplement) to built up an order-free representation is to add an ordered pair <X, Y> to the7

An adjunct has no place in the present system, but adjunct wh-phrases can be analyzed

essentially along the same line. The distinction between the two languages can be generalized
as follows: obligatory leftward movement is attested only in languages of inorder traversal,
namely, SHC languages, and there is no rightward obligatory movement. This accords withthe observations by Greenberg (1970), Bach(1970) and Bresnan (1976). My account of thecorrelation between word order and leftward movements is close to Fukui's (1993) "parametervalue preservation measure," but it also covers the total absence of obligatory rightward
movement on the same basis.

Miyoko Yasui 22
set E of the ordered pairs already introduced. It has been argued that an ordered pair is createdaccording to (21a,b), from which (22a,b) follow. Let us assume that ordered pairs are indexed
incrementally as they are added to E. Then, (22a,b) can be restated as (34a,b), respectively.
(34) Given a lexical item as a node p in the graph already formed,a.

If p appears as the first member of two ordered pairs <X, Y> with index i and<X', Y'> with index j (i>j), Y is p's spec/external argument (left child) and Y' is its
complement/internal argument (right child).

b.

If p appears as the first member of one ordered pair <X, Y>, Y is p's complement/internal argument (right child).

c.

If p does not appear as the first member of any ordered pair, it is a leaf node.

d.

If p appears as the second member of two ordered pairs <X, Y> with index i and<X', Y'> with index j (i>j), X is the functional head that has attracted p, and X' is thelexical category selecting p.

(34c,d) are added, which characterize a leaf and a doubly-connected node, respectively.
(34a-d) can be illustrated with the formation of the English version of (31) repeatedbelow as (35). The ordered pairs constituting (35) are added as in (36).
(35)[past]/ta
ask/tazune
Mary/Mary-ga[WH]/ka[past]/ta
help/tasuke
John/John-ga

who/dare-oMiyoko Yasui 23
(36)
index

0

1

2

3

4

E

<help, who>

<help, John><[past], help><[past], John><[WH], [past]>

index

5

6

7

8

9

E

<[WH], who>

<ask, [WH]><ask, Mary><[past], ask><[past], Mary>

The verb help appears as the first memeber in pairs 0 and 1; the second member of pair 1 is its
external argument and that of pair 0 is its internal argument. Who appears as the second
member in pairs 0 and 5; the first member of pair 5 is the [WH] COMP that has attracted who,
and that of pair 0 is the verb selecting it. Note that the root of the whole graph is the firstmember of the last ordered pair. Intuitively speaking, traversing (36) in inorder is to processordered pairs according to the descending order of their indices: the second member of thepair with index 9 is pronounced first, its first member, which is identical to the first memberof the pair with index 8, is pronounced next, the second member of the pair with index 8 is
pronounced next, and so on. Since a node that has been pronounced is not traversed again, adoubly-connected node such as who in (36) is pronounced based on a pair with the larger
index, namely pair 5. The ordering obtained is (30a) discussed in Section 5.
This kind of data structure is called stack or last-in, first-out (LIFO) list: a piece of data
added last is to be popped up and processed first. Fukui and Takano (1998) suggest thatstructure-building and its linear realization could be based on a stack, though they do not
implement their idea along that line and they assume the head-final order to be derived
universally, contrary to the position here.8
Since the SHC order of English can be derived on a LIFO basis, the head-final order of
8

Their linealization system is the opposite of bottom-up structure-building: it decomposes agiven sentence structure in a top-down manner by detaching a maximal projection before thehead that has merged with it and pronounces the resultant sequence of maximal projections inthat order.

Miyoko Yasui 24
Japanese is expected to be obtainable in a first-in, first-out (FIFO) manner. This is in factbasically correct. Consider the Japanese counterpart of (36) given in (37).
(37)
index

0

1

2

3

4

E

<tasuke, dare-o><tasuke, John-ga><ta, tasuke><ta, John-ga><ka, ta>

index

5

6

7

8

9

E

<ka, dare-o><tazune, ka><tazune Mary-ga><ta, tazune><ta, Mary-ga>

As argued in the previous section, an economical postorder traversal should start from a leaf
node. (35) contains three leaf nodes, which appear as the second members of pairs 0, 1, 3, 5, 7
and 9. If we start with the pair with the smallest index in them, namely pair 0, its second
member is pronounced first. The first member of pair 1 is identical to that of pair 0; thesecond member of pair 1 is its external argument and thus pronounced next, followed by thepronunciation of its first member. The remaining pairs will be processed similarly according
to the ascending order of their indices. The PF output of this traversal is (38a).
(38) a.

[[ dare-o John-ga tasuke ta ka ] Mary-ga tazune ta ]b.

[[ John-ga dare-o tasuke ta ka ] Mary-ga tazune ta ]c.

[Mary-ga [ John-ga dare-o tasuke ta ka ] tazune ta ](=(30b))The starting leaf node to derive (38b) is John-ga, which appears in pairs 1 and 3; the former
has the smaller index. Since the traversal algorithms advocated here are essentially of thedepth-priority nature just like the standard algorithm given in (7), given p as the current node,
those pairs that are related to p with smaller indices (or "deeper" pairs) are to be processed
before those with larger ones.9 Processing of pairs 1 and 0 results in the embedded clause of(38b). The remaining pairs will be processed in a FIFO manner. (38c) can be obtained by
9

Since the starting node in an inorder traversal is the root, which appears in the pair withthe largest index, and only those pairs related to the root can be processed subsequently, pair 0,
for instance, cannot be processed immediately after pair 8.

Miyoko Yasui 25
starting with pair 7, processing pairs 6 to 0 and finishing up with the last two pairs.
The above algorithms based on a set of ordered pairs allow a traversal to proceed from
non-head to head as well as from head to non-head; only the latter is possible in the standard
traversal algorithm in (7). Formalization of the bi-directional algorithms is more complicatedthan (7), but they yield a wider range of orderings that are empirically attested in Japaneseand English.10

7.

Remaining Issues
This paper has been an attempt to formalize a theory of order-free syntactic

representations and to deduce from it some of the major parametric differences in word order
between Japanese and English.

First, head-movement has been sketched as the reduction of

two adjacents nodes by eliminating the edge between them, and its validity should be
examined fully on empirical bases. Another issue, which has not been explored here or solvedin other syntactic studies, is a treatment of adjuncts. It is not clear whether they are introduced
by external MERGE or some comparable operation at the edge of the graph already formed,
or they are inserted into the graph post-cyclically. Moreover, locality of overt movement has
not been discussed so far. According to the theory here, a wh-phrase is connected to a lexical
category selecting it as well as to a [WH] COMP, which is true both in Japanese and English.
It has been argued that the edge coming from the former is processed for PF-interpretation in
Japanese, while the one coming from the latter is in English. It might be the case that anedge cannot be introduced if the two nodes to be connected by it are separated by barriers,
which are to be formalized somehow in the present theory.11 I leave these problems for future
10

The scripts in C are available at http://www2.dokkyo.ac.jp/~esemi003/publications/index.html.
11

In Yasui (2006, section 6), I discussed how CED effects can be explained if order-free

representations advocated here are assumed.

Miyoko Yasui 26
research.

Miyoko Yasui 27
References:
Alphonce, C, and H. Davis (1997) "Motivating non-directional Movement."

In D.

Beermann, D. LeBlanc and H. van Riemsdijk (eds.) Rightward Movement. Amsterdam:
John Benjamins.
Aoyagi, Hiroshi (1998) On the nature of particles in Japanese and its theoretical
implications.

Doctoral dissertation, University of Southern California, Los Angeles.

Bach, Emmon (1970) "Questions." Linguistic Inquiry 2:153-166.
Boskovic, Zeliko and Daiko Takahashi (1998)

Scrambling as Last Resort.

Linguistic

Inquiry 29: 347-366.
Bresnan, Joan (1972)

Theory of Complementation in English Syntax.

Doctoraldissertation, MIT.
Brody, Michael (1998) "Projection and phrase structure." Linguistic Inquiry 29: 367398.
_____ (2000) "Mirror theory: Syntactic representation in perfect syntax." Linguistic
Inquiry 31: 29-56.
Chomsky, Noam (1994)

Bare Phrase Structure.

Department of Linguistics and Philosophy, MIT.

MIT occasional papers in linguistics 5.
Cambridge, MA.

_____ (1995) The Minimalist Program. Cambridge, MA: MIT Press.
_____ (1999) Derivation by Phase.

MIT occasional papers in linguistics 18.

Department of Linguistics and Philosophy, MIT.
_____ (2000)

Cambridge, MA.

"Minimalist inquiries: the framework." In Roger Martin, David Michaels,

and Juan Uriagereka (eds.)

Step by Step: Essays on Minimalist Syntax in Honor ofHoward Lasnik. Cambridge, MA: MIT Press, pp. 89-155.
_____ (2001) Beyond Explanatory Adequacy.
20.

MIT occasional papers in linguistics

Department of Linguistics and Philosophy, MIT.

Cambridge, MA.

Farmer, Ann (1984) Modularity in Syntax: A Study of Japanese and Syntax.

Cambridge,

Miyoko Yasui 28
MA: The MIT Press.
Fukui, Naoki (1993) "Parameters and Optionality." Linguistic Inquiry 24: 399-420.
Fukui, Naoki and Yuji Takano (1998) "Symmetry in Syntax: Merge and Demerge." Journalof East Asian Linguistics 7: 27-86.
Greenberg, Joseph H. (1963) Some universals of grammar with particular reference to theorder of meaningful elements. In Joseph H. Greenberg (ed.)

Universals of Language.

Cambridge: MIT Press, pp. 73–113.
Hale, Kenneth (1980) "Remarks on Japanese Phrase Structure: Comments on the Papers on
Japanese Syntax." In Yukio Otsu and Ann Farmer (eds.) Theoretical Issues in Japanese
Linguistics :MIT Working Papers in Linguistics Vol. 2, MIT.

_____ (1981) On the Position of Warpiri in a Typology of the Base.

Bloomington, IN:

IULC.
Hawkins, John A. (1994)

A Performance Theory of Order and Constituency. Cambridge:

Cambridge University Press.
Ikawa, Hajime (2003) "On the Internal Structure of Functional Projections in Japanese and its
Implications for the Phrase Structure of Japanese." Proceeding of LP2002 On-Line.
Meikai University, Urayasu. <http://www.wata-net.com/proceedings/HajimeIkawa/ikawa.pdf>
Kayne, Richard. S. (1994) The antisymmetry of syntax.
Knuth, Donald E. (1997)
Algorithms.

Cambridge, MA: The MIT Press.

The Art of Computer Programming, Volume 1: Fundamental

Boston: Addison-Wesley.

Marantz, Alec (1984) On the Nature of Grammatical Relations. Cambridge, MA: The MIT
Press.
Saito, Mamoru (1985) Some Asymmetries in Japanese and Their Theoretical Implications.
Doctoral dissertation, MIT.
Saito, Mamoru and Keiko Murasugi (1990) "N'-deletion in Japanese." University ofMiyoko Yasui 29
Connecticut Working Papers in Linguistics 3, Department of Linguistics, University ofConnecticut: 87-107.
Takano, Yuji (1996)

Movement and Parametric Variation in Syntax.

Doctoraldissertation, University of Irvine.
Whitman, John (1997)"Kayne 1994: p.143, fn.3." In G. M. Alexandrove and Olga

Arnaudova (eds.) The minimalist parameter. Amsterdam/Philadelphia: John Benjamins.
Williams, Edwin (1984)"Grammatical Relations." Linguistic Inquiry 15: 639-673.

Yasui, Miyoko (2002) "A Graph-theoretic Reanalysis of Bare Phrase Structure and Whmovement." Paper presented at Linguistics and Phonetics 2002: Typology and
Linguistics Theory. Meikai University. Sept. 2002.
_____ (2003a) “A graph-theoretic reanalysis of bare phrase structure theory and its
implications on parametric variation." To appear in Proceedings of the International
Conference on Linguistics and Phonetics 2002, Charles University Press.

Availabel at <http://www2.dokkyo.ac.jp/~esemi003/publications/yasui_rev.pdf>_____ (2004a) "Asymmetries in Word Order and Syntactic Structure as Lexical Graph."Ms., Dokkyo University, Soka. 2003b < http://www2.dokkyo.ac.jp/~esemi003/
publications/traversal.pdf>_____ (2004b) "Syntactic Structure Without Projection Labels." Ms., Dokkyo University,
Soka. < http://www2.dokkyo.ac.jp/~esemi003/publications/ NoLabel.pdf>_____ (2006) "Bound Pronouns without C-command, Leftness Condition, and Sideward
Movement." English Linguistics 23(2).