社団法人	 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS

信学技報
	 IEICE Technical Report

A Phase Theory-Based Computational Model of Sentence Generation
Jason GINSBURG††Center for Language Research, University of Aizu

Aizuwakamatsu, Fukushima, 965-8580 Japan

E-mail: †jginsbur@gmail.com
Abstract This paper presents a computational model of sentence generation, based on Phase Theory, that attempts to model
on a computer the innate structures of the human mind that are utilized for language generation and processing. This model
automatically constructs the derivation of a sentence from a numeration, which is a set that consists of subnumerations(language chunks) that contain lexical items. This model presents a simple algorithm for selection and Merge of lexical items
from subnumerations to create sentences of English and Japanese.
Keywords Syntax, Phase Theory, Computational Modeling

1. Introduction

with respect to the timing of Spell-Out. In one version [1-2] in (1),This paper presents a computational model of sentence

when the phase head v* is Merged, the complement of v*, the VP,

generation, based on recent work in Phase Theory ([1-3]) thatis sent to Spell-Out. In the other version [3], when the phase headattempts to replicate on a computer the innate structures of theC* is Merged, the complement of v*, the VP, is sent to Spell-Out.2

mind that enable humans to produce and understand sentences. We(1)created a computer model (implemented in Python) that produces

Once a phrase is sent to Spell-Out, its contents are no longer

detailed step-by-step derivations of sentences from underlying

accessible to higher operations.

[CP C* [TP T [vP* v* [VP V ...]]]]

numerations. Our goal is to create a more refined and precise

Another important component of Phase Theory is the idea thattheory of language generation, based on Phase Theory, thata head can function as a probe that Agrees with a matching goal,accounts for how sentences are generated in various languages. In

where the probe c-commands (or at least is higher in the tree than)

this paper, we discuss how this computational model constructs a

the goal, thus resulting in a feature checking relation. Crucially, aderivation from a numeration and we demonstrate how this modelprobe can only Agree with a goal that has not been sent to Spell-constructs the derivations of some English and Japanese sentences.

Out.

2. Assumptions

Our computational implementation of sentence generation

In Phase Theory, a sentence is constructed from the bottom-up

utilizes a modified version of Phase Theory that incorporates: a) an

via a process of selection and Merge of Lexical Items (LIs) from a

explicit theory of feature valuation, b) explicit methods fornumeration. A numeration consists of subnumerations, and aselection of LIs from a subnumeration, and c) a one-to-one

subnumeration is a set of LIs that can corresponds to a phase, withcorrespondence between 'phase-hood' and Spell-Out.

a phase head v* or C*, or to a subject or adjunct, which must be

Feature valuation is an important component for driving a

constructed in a separate derivational space from the main spine ofderivation. Our model incorporates the types of features in (2).

a derivation (cf. [4]), since a subject/adjunct can be a complete

There are unvalued (2a) and valued (2b-c) features. Unvalued

clause, as in “That she won an award bothered him.”features (2a), where the “:_” signifies the lack of a value, must be

1

A derivation is subject to the Phase Impenetrability Condition

valued by forming an Agree relation with matching valued features(PIC), which has been formulated in at least two ways that differ(2b-c), where the “:X” signifies a value. An example of an

1 The * indicates a phase head; thus v* and C* are phase heads.

2 See [5] for discussion of the different versions of the PIC.

Copyright ©20●●

by

IEICE

unvalued feature of type (2a) would be unvalued phi-features(2) Features:

We incorporate EPP features into our model as subfeatures offeatures, along the lines of [7]. In our approach, a feature of type(2b), a '[+Feat:X]' feature (a feature that must be assigned), canFeatureDescription(a)Unvalued[Feat:_](b)

Valued[+Feat:X]

has a '[+Case_EPP:NOM]' feature, a valued nominative feature(c)Valued[Feat:X]with an EPP subfeature. In a successful derivation, thehave an EPP subfeature which requires that an LI with a matchingunvalued feature Merge locally. For example, the English finite T'[Phi:_]' on T that must be valued by the matching valued '[Phi:X]','[+Case_EPP:NOM]' feature of T probes for and finds a matchingof type (2c), of a subject. Valued features come in two varieties.

unvalued feature in a subject at the v*P edge. The EPP subfeature

One variety (2b), contains a “+” which signifies that this feature

forces the subject to undergo movement and re-Merge with T. The

must value a matching unvalued feature. We model theta-roles andresult is that the Case feature of T values the unvalued Case feature

Case features as features of this type. For example, “*I like” is ill-of the subject, and the EPP subfeature is eliminated.

formed because the verb 'like' has '[+Theta:X]' and '[+Case:ACC]'

In Phase Theory, it is assumed that elements are selected fromfeatures that are unable to value matching unvalued features, sincesubnumerations. However, it is not clear why they are selected inthere is no object. A valued feature of type (2c) also can value athe particular order that they are selected in. Assuming that (3a),matching unvalued feature, but there is no inherent need for it to dowith the numeration in (3b), is built from the bottom-up, 'dinner' isso – thus it lacks a '+'. Phi-features '[Phi:X]' on a nominal are of

selected before the verb 'ate'. However, the subnumeration of thethis type. Most features that determine the meaning of an LI are

v*P, contained in the numeration (3b), is an unordered set of LIs

probably of type (2c). For example, an N may have various features(where the subject has its own subnumeration), which raises thethat determine its meaning (e.g., features that determine that the LI

issue of how the grammar module 'knows' what to select first. Why'dog' refers to a four legged mammal), but that do not need towould 'dinner' be selected before v*, etc.?

undergo any feature valuation relations. An unvalued feature (2a)(3) (a) I ate dinner.

(b) {T, C*,{{I}, v*, ate, dinner}}}or an unassigned valued feature (2b) can function as a probe, when

In our model we propose an explicit algorithm, given in (4), forit occurs in the label LI (head) of a tree, that searches for aselection of LIs from a subnumeration. Crucially, our algorithm

matching goal within a Merged tree structure. Crucially, asucessfully derives bottom-up selection of LIs from aderivation will crash if any unvalued features (2a) or unassigned

subnumeration.

valued features (2b) are sent to Spell-Out.3(4) (a) If the label LI of a tree contains an unvalued feature (2a),In the Minimalist Program [6], as well as in Phase Theory,or a valued feature that must be assigned (2b), then search

movement of LIs is often accounted for with the EPP feature,

for an LI in a subnumeration with a matching feature.

which is thought to motivate movement of subjects, as well as(b) Otherwise, search for an LI in a subnumeration according

other elements; [1] suggests that EPP features in phase heads force

to a default selection order: N > D > V > v/v* > T > C*.

movement of a wh-phrase in languages such as English.

In accord with (4a), if the label LI of a tree is v* with a'[+Theta:X]' feature, there is a search within a subnumeration for

3 In the Minimalist Program [6], as well as in Phase Theory, it isgenerally assumed that there are interpretable and uninterpretablefeatures that appear on LIs. Interpretable features must remain to
the level at which a derivation is interpreted (LF), whereas
uninterpretable features must be eliminated from a derivation
before the level of interpretation. We make no claims about
whether or not features are eliminated. Rather, there must be no
unvalued features and no unassigned features at the point at which
a syntactic structure is interpreted.

an LI with a matching '[Theta:_]' feature. If an LI, such as a
subject, with a '[Theta:_]' feature is found, then it is selected andMerged with the tree. When (4a) cannot apply, either because there
is nothing in the derivational workspace (at the initial stages of a
derivation) or because the head of a tree lacks unvalued features

(2a) or valued features that must be assigned (2b), then the

our computational implementation utilizes.

language component relies on a default selection order (4b). ThereOur model utilizes a bare phrase structure [9] in which a tree isis a search within a subnumeration for LIs with particular labels inconstructed via iterative Merge of LIs. After each Merger, thethe order given in (4b), where labels on the left are searched for

newly formed tree has the label of one of the Merged elements.

before those on the right. For example, first there is a search for anFirst Merge with an LI results in a head-complement structure, andLI with label N. If no LI of this type is found, then there is a search

further Merge operations with the same LI result in head-

for a D, and so on. The default selection order (4b) is a hypothesis

spec/adjunct structures.

about the way that language is structured in the brain. There is a
default selection order that the human mind relies on in an
elsewhere condition, when (4a) cannot apply.
Notable in Phase Theory is that there is a lack of correspondence

A derivation is constructed using the following algorithms.
(6) Select a Subnumeration: Select the most embedded
subnumeration with a phase head. Search for any further
embedded subnumerations (e.g., a subject/adjunct).

between phases and Spell-Out. According to the PIC (see section(7) Select an LI: If the label LI of a tree has an unvalued feature1), the complement of a phase head is sent to Spell-Out separately(2a) or a valued feature that needs to be assigned (2b), searchfrom its associated phase head. Thus, there is not a one-to-one

for an LI in the subnumeration with a matching feature (seecorrespondence between a subnumeration of a phase and Spell-4a). Otherwise search for an LI according to the default

Out. Our model takes a different approach. When a phase head isselection order (4b). Repeat the selection process if there is

Merged, a lower phase, if present, is sent to Spell-Out. For

only one element selected (Merge requires two LIs).

example, in (5), when the phase head C* is Merged, the entire(8) Merge: Merge the selected LI with the tree (the element in thelower v* phase is sent to Spell-Out.

derivational working space). Whichever label (of an LI) has a(5) [C* [ T [v* V ]]]“+” feature is the label of the tree. If neither LI has a “+”In this manner, all elements of a phrase that originate in a single

feature, the label remains the same.

subnumeration are sent to Spell-Out as a single unit.4
Our model thus incorporates a modified version of Phase Theory
that provides explicit algorithms for feature checking, selection ofLIs, and the timing of Spell-Out.

3. Implementation
We created a computer program, in the Python programming
language, that automatically builds a derivation of a sentence froma numeration. In this section, we briefly discuss the algorithms that

(9) Feature Checking: The label LI of a tree undergoes feature
valuation relations, if possible, with matching features in atree. An unvalued feature can only be valued once.
(10) Repeat: Repeat the process of selection and Merge until asubnumeration is emptied.
(11) Reinsertion: If a subnumeration is not a phase (i.e., a subject
or adjunct), then reinsert into a higher subnumeration.
(12) Spell-Out: If a phase head is Merged, send a lower phase (ifpresent) to Spell-Out.

4 The PIC crucially makes the edge of a phase accessible to ahigher phase, thus allowing movement (e.g., of a wh-phrase) out ofa phase. A problem with this view is that something must force anelement such as a wh-phrase to move to the edge of a phase. [1]suggests that a phase head can optionally have an EPP feature thatserves this purpose. Our model does not utilize EPP features thatexist simply for the purpose of bringing an LI to a phase edge.
Although we do not have space to discuss the details here, we
account for certain movement phenomena out of phases as follows.
An LI (such as a wh-phrase) with an unvalued feature, whencontained within a phase that is about to be sent to Spell-Out, canbe reinserted into a subnumeration as a last resort, and then selected
and re-Merged in a higher position. See [8] for details of thisapproach.

(13) Crash Check: Crash (end the derivation) if there are any
unvalued features (2a) or unassigned features (2b) in theSpell-Out domain.
(14) Linearize: If the derivation does not crash, linearize the SpellOut domain. Convert the Merged phrase into a syntactic object
with linear order and apply phonological rules.
(15) Repeat: Continue repeating these processes (6-14), until theentire numeration is emptied and the complete sentence islinearized, or until the derivation crashes.

order. D and N Merge, and in accord with (8), the label of the

Our model utilizes the algorithms in (6-15) to select and Merge

Merged syntactic object is D, since D has a “+” feature of typeelements in order to create the derivations of sentences. We next

(2b). There is a feature checking relation (9), whereby thedemonstrate how this model automatically constructs 'simple''[+DEF:X]' feature of D values the matching unvalued '[DEF:_]'

English and Japanese statements.

feature of N - D assigns a definiteness value to N. The subject, not

4. English

being a phase, is reinserted into the v* phase (11). The Selector

Our model successfully constructs the derivation of thethen works on the v* subnumeration. The processes of selection,statement in (16a) when fed the numeration in (16b), where eachMerge, and feature checking continues (10), resulting in formation

subnumeration is enclosed in set brackets. The numeration (16b) isof a complete v* phrase. Note that v* undergoes Merge twice.

a set (of unordered elements) with the phase head C*. The main

When v* is initially Merged, it is selected due to the default

numeration contains an embedded subnumeration with the phaseselection order (4b). After Merge with V, and initial featurehead v*. The v* subnumeration contains a subject, which has its

checking (9) that results in Case assignment to the object 'food', v*

own subnumeration (see section 1).5

still contains a '[+Theta:X]' feature. Thus, in accord with (7), there(16) (a) I eat food.

is a search in the subnumeration for an LI with a matching(b) {C*, PRES,{v*,{I, D}, eat, D, food}}
The computer program uses a “lexicon” to render (16b) into theunvalued feature, and the renumerated subject, with its matchingunvalued '[Theta:_]' feature, is selected and Merged.

form in (17), where each LI is a list consisting of the label, form,

Since the v* subnumeration is emptied, the Selector works onand (relevant) features of that LI. For example, the LI 'food' has thethe higher subnumeration containing T and C*. T is selected inlabel 'N', the form 'food', and the features '[Theta:_ Phi:X Case:_accord with the default selection order (4b). T contains

DEF:_]' ('food' has unvalued theta, case, and definiteness (DEF)'[+Case_EPP:Nom]' and '[Phi:_]' features. After Merge of T, there

features, and valued phi-features).

is a feature checking operation (9) in which the '[Phi:_]' feature of(17) {{[T, PRES, [+Case_EPP:Nom Phi:_ Force:_]], [C*T probes with and Agrees with the valued '[Phi:X]' feature of the[+Force:X]]},{{[D, [D [+DEF:X]], [N I [Theta:_ Phi:X

subject 'I'. The [+Case_EPP:Nom]' feature finds and Agrees with

Case:_ DEF:_]]}}, [v* [+Theta:X +Case:Acc Phi:_]the unvalued '[Case:_]' of the subject and the EPP subfeature forces[V eat [+Theta:X]]},[N food [Theta:_ Phi:X Case:_ DEF:_]],

the subject to undergo movement. The subject leaves a copy in its[D [+DEF:X]]}base position and it re-Merges with T, resulting in elimination of

The computer program applies the algorithms in (6-15) toautomatically construct a derivation from (17).

the EPP on T and valuation of the Case feature on the subject 'I'.
Next, following the default selection order (4b), C* is Selected

The derivation begins with selection of a subnumeration by theand the resulting Merged structure is (18), a Merged syntactic

Selector, the component of the human mind that selects elements

object (automatically created by the computer model) that contains

from a numeration. The Selector, in accord with (6), selects theunordered sets of Merged LIs.

most embedded subnumeration with a phase-head, in this case, the(18) {C*, [C* [+Force:X]], {T, {T, [T PRES [cCase:Nom cPhi:Xv* subnumeration, and then the Selector searches for a further

Force:_]], {v*, {v*, [v* [cTheta:X cCase:Acc cPhi:X]], {V,embedded subnumeration. It finds the subnumeration of the subject[V eat [cTheta:X]], {D, [D [cDEF:X]], [N food [cTheta:X'I'. The Selector then chooses LIs in accord with (7). Initially, thecPhi:X cCase:Acc cDEF:X]]}}}, {D(Copy), [D [cDEF:X]],

Selector chooses the N, following the default selection order (4b).

N I [cTheta:X Phi:X Case:_ cDEF:X]]}}}, {D, [D [cDEF:X]],

Then it chooses the D, again in accord with the default selection[N I [cTheta:X cPhi:X cCase:Nom cDEF:X]]}}}

5 We assume that an N must occur with a D, even if the D is silent.

Checked features are indicated with the “c” prefix. For example,

'[ cTheta:X]' on v* and on the subject 'I' indicates that both of these(21)

elements have valued theta-features.
Once C* is Merged, before any feature checking relations canapply, the embedded v* phrase is sent to Spell-Out, in accord with
(12), assuming that when a phase head is Merged, a lower phase issent to Spell-Out. The crash check operation (13) finds nounvalued or unassigned features (unvalued features in the copy ofthe subject do not count), and the phrase is linearized (14). The
linearization algorithm for English is given in (19).
(19) (a) First Merge: A label LI is Merged to the left when thelabel LI Merges for the first time.
(b) Second Merge: A non-label LI is Merged to the left when

5. Japanese
We next turn to the derivation of the simple Japanese statement(22a), which has the numeration in (22b).7(22) (a) Kare-ga tabemono-o tabeta.

the label LI has previously undergone Merge.

He-NOMFirst Merge (19a) results in the label LI appearing to the left (ahead complement structure) and second Merge (19b) results in the

food-ACC

ate'He ate food.'(b) {C*, PAST,{v*, taberu,{kare}, tabemono}}

non-label appearing to the left (a spec-head structure). The v*

The numeration (22b) is rendered into the more detailed format inphrase that results after linearization is shown in (20), a tree that is(23), in which each LI is a list consisting of the label, form, andautomatically drawn by our program. The line through the v* edge

features.

signifies that the v* phrase has been sent to Spell-Out and(23) {[T PAST [+Case_EPP:Nom Phi:_ Force:_]], [C*linearized. Also note this phrase contains a linearized copy of the[+Force:X]], {[V, taberu, [+Theta:X]], {[N kare [Theta:_

subject – the actual subject has moved to the T edge.

Phi:X Case:_]]}, [N tabemono [Theta:_ Phi:X Case:_]], [v*(20)[+Theta:X +Case:Acc Phi:_]]}}The derivation, beginning with (23) is carried out in a virtually
identical manner to that of the previous English example (16). The
Selector finds the embedded v* subnumeration, in accord with (6).
The v* phrase is constructed via the continuous process of selection(7) and Merge (8) of LIs, feature checking (9), and reinsertion of
the subject (11). This is followed by selection and Merge of T. As
in English, the EPP subfeature of '[+Case_EPP:Nom]' on T forces

Once the v* phrase is completed, feature checking (9) occurs in thethe subject to leave a copy in the v* phrase and re-Merge with T. 8

matrix clause. C contains a [+Force:X] feature (see 18) that values

Once C* is Merged, the resulting structure is (24).

a matching unvalued '[Force:_]' feature on T - we assume that(24) {C*, [C* [+Force:X]], {T, {T, [T PAST [cCase:Nom cPhi:X

Force determines whether a clause is matrix or embedded. 6 Then,

Force:_]], {v*, {v*, [v* [cTheta:X cCase:Acc cPhi:X]], {V,since the entire numeration has been emptied, the Spell-Out process

V taberu [cTheta:X]], [N tabemono [cTheta:X cPhi:X

applies again. The derivation does not crash (13) and linearizationcCase:Acc]]}}, {N(Copy), kare, [cTheta:X Phi:X Case:_]}}},(14) applies, resulting in the well-formed tree in (21), where theline through the C* edge indicates that the tree has been linearized.
6 This is a modified version of Force proposed by [10].

7 We assume that in Japanese, an N can occur without acorresponding D.
8 We assume that there is an EPP feature in T in Japanese,following [11].

{N, kare, [cTheta:X cPhi:X cCase:Nom]}}}(27)

Since the phase head C* is Merged, the lower v* phrase is sent toSpell-Out (12). The crash check operation (13) finds no unvalued
or unassigned features (the copy of the subject is ignored), and thelinearization process (14) applies. The linearization algorithm forJapanese is as follows.
(25) (a) First Merge: A label LI is Merged to the right when thelabel LI Merges for the first time.
(b) Second Merge: A non-label LI is Merged to the left when
the label LI has previously undergone Merge.
(25) results in heads being Merged to the right of complements andfrom a numeration and for sending phrases to Spell-Out at specificspecifiers being Merged to the left.9 The resulting linearized v*P,

times in the course of a derivation. This model shows that a limited

automatically constructed by our program, is shown in (26). Noteamount of built in grammatical structure can be utilized to createthat application of phonological rules results in the verb taberu 'eat'sentences in different languages. In future work, we hope to extend

being pronounced in the past tense form tabeta 'ate', due to thethis model to generate a wide variety of sentences in English,

occurrence of the Past tense T in the higher phrase, and theJapanese, and other languages. We hope that this model can beaccusative case particle -o appears on the object tabemono 'food'.

utilized to help further understanding of how humans produce and(26)

process language.
REFERENCES

Next, C* and T undergo a feature checking relation (9), resulting
in valuation of the Force feature on T. Since the numeration isempty and all feature checking operations have completed, theentire phrase is sent to Spell-Out, where it is linearized andphonological rules apply (the nominative case particle -ga appearson the subject), resulting in (27).

5. Conclusion
We have demonstrated how this model derives the structures of
two simple sentences in English and Japanese using precise
algorithms, based on Phase Theory, for selecting and Merging LIs

9 This ordering algorithm is suitable for the relevant Japaneseexample, but it may require some refinement for otherconstructions.

[1] N. Chomsky, Derivation by Phase, MIT Occasional Papers
in Linguistics Number 18, Cambridge, MA, 1999.
[2] N. Chomsky, Minimalist Inquiries: The Framework, in Stepby step, eds., R. Martin, D. Michaels, and J. Uriagereka, pp.
89-155, MIT Press, Cambridge, MA, 2000.
[3] N. Chomsky, Beyond Explanatory Adequacy, MIT
Occasional Papers in Linguistics Number 20, Cambridge,
MA, 2001.
[4] K. Johnson, Towards an Etiology of Adjunct Islands, Ms.,
University of Massachusetts at Amherst, 2002.
[5] G. Grewendorf and J. Kremers, Phases and Cyclicity: Some
Problems with Phase Theory, The Linguistic Review, vol. 26,
pp. 385-430, 2009.
[6] N. Chomsky, The Minimalist Program, MIT Press,
Cambridge, MA, 1995.
[7] D. Pesetsky and E. Torrego, T-to-C Movement: Causes andConsequences, in Ken Hale: A life in Language, ed., M.
Kenstowicz, pp. 355-426, MIT Press, Cambridge, MA, 2001.
[8] J. Ginsburg, A Computational Model of Language Generation
Applied to English Wh-Questions, In Preparation.
[9] N. Chomsky, Bare phrase structure, in Evolution and
Revolution in Linguistic Theory, eds., H. Campos and P.
Kempchinsky, pp. 51-109, Georgetown University Press,
Washington, DC, 1995.
[10] L. Rizzi, The Fine Structure of the Left Periphery, inElements of Grammar, ed., L. Haegeman, pp. 281-337,
Kluwer, Dordrecht, 1997.
[11] S. Miyagawa, EPP, Scrambling and Wh-in-situ, in Ken Hale:A life in Language, ed., M. Kenstowicz, pp. 293-338, MIT
Press, Cambridge, MA, 2001.