Systems and Computers in Japan, Vol. 36, No. 2, 2005
Translated from Denshi Joho Tsushin Gakkai Ronbunshi, Vol. J86-D-II, No. 1, January 2003, pp. 84–97

Incremental Dependency Parsing Based on Headed
Context-Free Grammar
Yoshihide Kato,1 Shigeki Matsubara,2 Katsuhiko Toyama,3 and Yasuyoshi Inagaki4
1

Graduate School of International Development, Nagoya University, Nagoya, 464-8601 Japan
2

Information Technology Center, Nagoya University, Nagoya, 464-8601 Japan

3

Graduate School of Information Science, Nagoya University, Nagoya, 464-8603 Japan

4

Faculty of Information Science and Technology, Aichi Prefectural University, Aichi, 480-1198 JapanSUMMARY

1. Introduction
The analysis of natural language is to clarify thesyntactic relation and the semantic relation among theconstituents of the sentence. Most of the methods proposed
to date consider the analysis for the whole sentence. In theanalysis of spoken language, however, such an approach is
not always adequate. The reason for this is as follows. The
speech appears as a time continuation of phonemes, anddepending on the spoken language processing system, theanalysis must sometimes proceed in parallel to the speech
input.
In the real-time interactive speech system, for example, which should generate the word of agreement or interruption during the utterance of the user with an adequate
timing [8, 19], the system must understand the speech evenin the course of the user’s utterance [1, 16, 20]. As anotherscene, in the simultaneous translation system that outputs
the translated sentence in parallel to the utterance of the
speaker [13, 17], it is required to convert the syntax to thetarget language, even in the course of utterance of theoriginal sentence [3, 12].
In those scenes, where the language must be processed simultaneously with the speech input, the incremental
parsing procedure for the natural language—that is, “themethod to generate successively the result of parsing for theThis paper proposes the incremental dependency
parsing method based on the context-free grammar withdependency information. In the proposed method, thereachability, which represents the relation between categories, is used. In parallel to the inputting of sentence, thedependency, which is the relation between the modifying
word and the modified word, is computed. In the proposed
method, the parse tree to cover the inputted fragment of thesentence is not needed. Consequently, the method can compute the dependency more efficiently than the method thatcomputes the dependency from the parse tree. As a resultof a parsing experiment using ATIS corpus, the proposed
method utilizing the reachability is demonstrated to beeffective in reducing the parsing time. © 2005 Wiley Periodicals, Inc. Syst Comp Jpn, 36(2): 63–77, 2005; Published
online in Wiley InterScience (www.interscience.
wiley.com). DOI 10.1002/scj.10524

Key words: incremental parsing; dependency; dependency parsing; reachability; incremental interpretation.

© 2005 Wiley Periodicals, Inc.
63

sentence fragments read up to that moment, in the courseof scanning the input sentence following the order of its
occurrence”—is required.
One of the representations, for the result generated
by the natural language analysis, is the dependency structure. The dependency structure is the analysis focusing on
the modifying and modified relations among the words. The
importance of such an approach has been widely recognized in recent years, and there are studies of the analysis
procedure [4, 7, 9, 21]. Proposed have been a method toresolve the syntactic ambiguity based on the dependency
structure [5], and a method to generate the translated sentence based on the dependency structure [2, 14]. There havebeen few studies, however, on the incremental analysis of
the dependency structure.
The dependency parsing procedure can largely be
divided, in general, into the following two approaches.

grammar with attached dependency information, and generates all grammatically possible dependency structures forthe sentence fragments in the course of input. It is shown
first that, by combining the incremental parsing based on
the context-free grammar with the dependency computation from the parse tree, such an incremental dependency
parsing can be realized.
As the next step, a method is proposed to realize thedependency parsing, which is equivalent to or more efficient than the above method, namely, an incremental parsing method based on the reachability. In the proposed
method, it is not necessary to generate the parse tree for the
inputted sentence fragment. Consequently, efficient parsing
can be realized, and the method is suited to the incremental
spoken language processing.
The validity of the proposed method is shown theoretically. A parsing experiment is run using ATIS corpus
contained in Penn Treebank [11], and it is shown that the
proposed method is effective in reducing the parsing time.
Compared to the direct dependency parsing procedure described in Section 2, based on the incremental chart parsing,
the parsing time is reduced to approximately 1/1000 on the
average.
This paper is structured as follows. In Section 2, theparsing method based on the incremental chart parsing is
described. Section 3 proposes the incremental dependency
parsing method based on reachability. For Theorem 8 asserting the validity of the method, the detailed proof is givenin the Appendix. Section 4 outlines the experiment, andevaluates the proposed method based on the result of experiment.

(1) The method where the dependency is generated
based on the dependency constraint [7, 21](2) The head information is attached to the grammatical rule, and the parse tree is converted to the dependency
structure based on that information [4, 5, 9]
In either method, there arises a problem when the incremental dependency parsing is to be realized.
When method (1) is simply applied to the fragmentsof the sentence in the course of input, the incremental
dependency parsing is not realized. The reason for this isthat, even if the constraint used in method (1) is adequate
as the constraint for the dependency structure of the sentence, it is not always adequate as the constraint for the
dependency structure of the sentence fragment. The situation is as follows.
Method (1) utilizes the constraint that “Except for theword representing the semantics of the whole sentence,each word always modifies another word, and the word to
be modified is unique” (uniqueness constraint). For somewords appearing in the fragment of the sentence in thecourse of input, it may happen that the word to be modified
is not yet inputted. In that case, the dependency structure of
the sentence fragment does not always satisfy the uniqueness constraint. It is not clear in such a situation what
processing should be applied in the approach of method (1).
In method (2), on the other hand, the parse tree forthe whole sentence must be constructed before computing
the dependency structure. If the dependency structure is tobe computed after generating such a parse tree, the incremental parsing property will be degraded greatly.
From such a viewpoint, this paper proposes the following method. Each time a word is inputted successively
from the left, the dependency structure is computed for thesentence fragment, which is inputted up to that stage. The
method proposed in this paper is based on the context-free

2. Incremental Dependency Parsing
The dependency is the relation between the modifying word and the modified word. It can be calculated fromthe parse tree, if the dependency information amongphrases is attached to each rule of the context-free grammar(CFG), which defines the phrase structure [5]. In order tocompute the dependency among the words incrementallyin the order of word occurrence, the following procedure
should be executed.
(1) The CFG-based incremental parsing, which issimilar to the incremental chart parsing, the partial parsetree for the input sentence fragment is generated.
(2) Following the method in Ref. 5, the dependency
among the words is computed from the partial parse tree
generated in (1).
In this section, as the first step, the computation forthe dependency from the parse tree is described. Then, theincremental chart parsing method, which is one of the64incremental parsing methods, as well as the dependency
computation based on the method are described.
2.1. Dependency structure
Fig. 2. Grammar and lexicon.

In discussing the dependency, the modified word iscalled the head, and the modifying word is called thedependent. In the following, the dependency, in which thehead is wh and the dependent is wd, is written as〈wd → wh〉. The set of dependencies among the words in the
inputted sentence is called the dependency structure for thesentence. Figure 1(b) shows an example of the dependency
structure.

(1) If σ = [w]x, the head word of σ is w.
(2) If σ = [[ ⋅ ⋅ ⋅ ] x1 ⋅ ⋅ ⋅ [ ⋅ ⋅ ⋅ ] xh ⋅ ⋅ ⋅ [ ⋅ ⋅ ⋅ ] xm]A and
if the head child of the grammatical rule A →X1 ⋅ ⋅ ⋅ Xh ⋅ ⋅ ⋅ Xm used in composing σ is Xh, that is, if
A → X1 ⋅ ⋅ ⋅ X∗h ⋅ ⋅ ⋅ Xm, then the head word of σ is the head"
word of [ ⋅ ⋅ ⋅ ]xh.
In the following, the head word of parse tree σ iswritten as head(σ). When the head word of parse tree isdefined, the dependency structure can be computed fromthe parse tree.

2.2. Dependency computation based on parsetree
The dependency structure for the sentence can becomputed from the parse tree for the sentence, by defining
the category for each rule in CFG, called head child [5]. The
only one category on the right-hand side of each grammatical rule is called head child. It implies that the phrase withthe category being the head child is modified by otherphrases. In the following, the head child is indicated using
an asterisk. In the grammar of Fig. 2, for example, the headchild in the rule s → np vp∗ is vp.
By defining the head child in each grammatical rule,the head word, which is the word representing the semanticsof the whole parse tree, is defined as follows.

[Definition 2] (dependency structure of parse tree)
Let σ be a parse tree. The function dep is defined as follows.
(1) If σ = [w]x, dep(σ) = φ.
(2) Let σ = [[ ⋅ ⋅ ⋅ ]x1 ⋅ ⋅ ⋅ [ ⋅ ⋅ ⋅ ]xh ⋅ ⋅ ⋅ [ ⋅ ⋅ ⋅ ]xm]A.
Then, the head child of the grammatical rule
A → X1 ⋅ ⋅ ⋅ Xh ⋅ ⋅ ⋅ Xm is Xh. In other words, if
A → X1 ⋅ ⋅ ⋅ X∗h ⋅ ⋅ ⋅ Xm, then[Definition 1] (head word of parse tree) Let σ be theparse tree.

In the above, d(σ) is defined as follows:"dep(σ) is the dependency structure, which is computedfrom σ. Figure 1 indicates that, when the computation is
executed from parse tree of (a) according to Definition 2,
the dependency structure is obtained as in (b). The word inparentheses next to the category is the head word of parsetree with that category as the root.
2.3. Incremental chart parsing anddependency structure computation
The incremental dependency parsing can be realized
by applying the dependency structure computation from theparse tree described in the previous section to the partial
parse tree generated by the incremental parsing based on
CFG. This section describes, as the first step, the incremental chart parsing, which generates the partial parse tree
for the sentence fragment incrementally. Then, a method isFig. 1. An example of computing dependencies fromparse tree.

65

(Operation 5) replacement of term by term of active
edge: Let (i, j, σ) be an active edge in the chart, and let theleftmost undecided term of σ be [?]X. Then, if there exists
an active edge (j, k, σ′), such that the category of term σ′ isX, the edge with the term, which is obtained by replacing
the leftmost term of σ by σ′, as the label, is added between
the nodes i and k of the chart.
In other words, the incremental chart parsing introduces the application of the grammatical rule to the active
edge, as well as the operation to replace the leftmost undecided term of the term labeled to the active edge by the termlabeled to another active edge.
As an example, consider the parsing of sentence
fragment “The boy saw.” In the standard bottom-up chartparsing, the following terms are generated:shown where the dependency structure is computed basedon the incremental chart parsing.
2.3.1. Incremental chart parsing
The incremental chart parsing retains the result ofanalysis, using the graph called chart, as in the conventional
chart parsing [10]. The chart is composed of the set of nodes
and the set of edges. The node is placed between words inthe inputted sentence. The node between the i-th word wi
and the (i + 1)-th word wi+1 is labeled as number i. In thefollowing, the node with label i is simply called node i. Theedge connects nodes, with the parse tree for the part coveredby that edge in the inputted sentence as the label.
The parse tree is represented by the data structure
called term, and is represented by the notation [α]X, where
X is a category and α is a word, symbol ? or a list of terms.
For the term σ, which is [α]X, X is called the category of σ.
The term including ?, such as [?]X, is called the undecided
term, indicating that the structure is not yet determined.
Among the undecided terms appearing in the term, theleftmost term is called the leftmost undecided term. Whenan undecided term appears in the terms, which are attachedas the label to the edge, the edge is called active edge; if not,the edge is called inactive edge.
Incremental chart parsing is the procedure where a
new manipulation is introduced into the standard bottomup chart parsing. In the standard bottom-up chart parsing,
the following three operations are executed. In the following, the edge with label σ, connecting nodes i and j of thechart, is written as (i, j, σ).
(Operation 1) dictionary consultation: If the categoryof i-th word wi is X, the inactive edge (i − 1, i, [wi]X) is
added to the chart.
(Operation 2) application of grammatical rule: Whenthe inactive edge (i, j, [ ⋅ ⋅ ⋅ ]X) exists in the chart, if there
exists the grammatical rule A → XY ⋅ ⋅ ⋅ Z, the edge(i, j, [[ ⋅ ⋅ ⋅ ]X[?]Y ⋅ ⋅ ⋅ [?]Z]A) is added to the chart.
(Operation 3) replacement of term: Let (i, j, σ) be an
active edge in the chart, and the leftmost undecided term of
σ be [?]X. Then, if there exists an inactive edge (j, k, σ′) inthe chart, such that the category of term σ′ is X, the edge
with the term, which is obtained by replacing the leftmost
undecided term of σ by σ′, as the label, is added between
the nodes i and k of the chart.
In the incremental chart parsing, the following two
operations are further added, in order to realize the application of the grammatical rule to the active edge and thereplacement of the term by active edge.
(Operation 4) application of grammatical rule to active edge: When there exists active edge (i, j, σ) in the chart,
if the category of σ is X and there exists the grammaticalrule A → XY ⋅ ⋅ ⋅ Z, the edge (i, j, [σ[?]Y ⋅ ⋅ ⋅ [?]Z]A) is added
to the chart.

(1)

(2)
(3)
The term for “The boy saw,” however, is not generated.
In the incremental chart parsing, on the other hand,
the grammatical rule vp → vp1 adv is applied to term (3),and the term
(4)
is generated. By replacing the leftmost undecided term of(1) by term (4), the term
(5)
is generated for “The boy saw.”
2.3.2. Dependency structure computation
The dependency structure for the sentence fragment
can be computed by applying the function dep, which isdefined in Definition 2 to compute the dependency struc-Fig. 3. An example of computing dependencies for
initial fragment.

66

ture, to the term generated by the incremental chart parsing.
For the term contained in term (5), for example, the head
word is derived as in Fig. 3(a), and the dependency structure
for the sentence fragment “The boy saw” is computed as inFig. 3(b).

[Definition 3] (reachability) If there exists grammatical rule A → XY ⋅ ⋅ ⋅ Z, it is written that X C A. C * isdefined as the reflexive transition closure of C. If X C * Y,
X is called reachable to Y.
"
When X is reachable to Y, it implies that the parse treewith Y as the root can have X as the left-end descendent.
In order to compute the dependency structure, thehead word of parse tree must be determined. In order todetermine the head word without actually applying thegrammatical rule, the reachability is classified in the proposed method. The reachability of X to Y implies that by
applying several grammatical rules to term [ ⋅ ⋅ ⋅ ]X, a termwith Y as the category is obtained. The classification isbased on the relation between the head word of the term
obtained in the above way and the head word of [. . . ]X. In
the following, the position of the head child of grammaticalrule r is written as hc(r).

3. Incremental Dependency Parsing
By the procedure of the previous section, the dependency structure for the sentence fragment can be computed
incrementally. The procedure, however, is not efficient, andthere is a possibility that many terms with the same dependency structure are generated. In the incremental chart parsing for “The boy saw,” not only the term of Eq. (5), but also
the following terms are generated:(6)[Definition 4] Let C and C be the relation between
categories. They are defined as follows. If there exists thegrammatical rule r = A → XY ⋅ ⋅ ⋅ Z such that hc(r) = 1, ithis written that X C A. If there exists the grammatical ruler = A → XY ⋅ ⋅ ⋅ Z such that hc(r) ≠ 1, it is written that X
d
"
C A.
h ∗
X C Y implies that, when several grammatical rules
are applied to term [. . . ]X, a term with Y as the category is
obtained, and the head word of [. . . ]X propagates to thatdterm. X C* C C* Y, on the other hand, implies that, whenseveral grammatical rules are applied to term [. . . ]X, a termwith Y as the category is obtained, and the head word of[. . . ]X does not propagate to that term.
h

(7)

(8)
The same dependency structure is derived from terms(5) to (8). If only the determination of the dependency
structure is the concern, it is desirable from the viewpointof the parsing efficiency that the dependency structure iscorrectly computed without generating many such termswith the same dependency structure. One of the reasons forgenerating the terms with the same dependency structure is
the application operation of the grammatical rule. In otherwords, even if there is more than one application of grammatical rules to a term, it can happen that some of the terms
obtained by applying the rules have the same dependency
structure.
In the incremental chart parsing, the grammaticalrules are applied, not only to the inactive edge, but also to
the active edge, and the above situation has a larger effect.
From such a viewpoint, this section proposes the connection operation for the terms based on the concept of reachability, as a substitute for the application of grammaticalrule to the active edge. It is shown that the dependency
structure can be computed incrementally by such an approach.

d3.2. Incremental dependency parsing based onreachability
By the above preparation, the dependency parsing
procedure based on reachability is proposed. The method
is composed of the following three procedures.
(Procedure 1) The term is generated by the standard
bottom-up chart parsing.
(Procedure 2) The generated terms are connected
through reachability.
(Procedure 3) The dependency structure is computedfrom the connected terms.
In the proposed method, it is theoretically guaranteedthat the dependency structure derived by the method is thesame as the structure derived by the method described in
Section 2. Furthermore, a much more efficient incremental
dependency parsing is realized. Those properties are shownin the following.

3.1. Reachability
Reachability is the relation between categories. It isdefined as follows.

67

In the following, the head word of the connecting
term τ is written as headC(τ). In Procedure 3, the dependency structure is computed based on the connecting terms,
by the following definition.
[Definition 7] (dependency structure of connectingterm) Let τ be the connecting term. The function depC is
defined as follows.
(1) If τ is the term which is generated by the standard
bottom-up chart parsing, depC(τ) = dep(τ).
(2) Let τ = σ1R1σ2R2 ⋅ ⋅ ⋅ Rn−1σn, and let
σ1 = [[ ⋅ ⋅ ⋅ ]X1[ ⋅ ⋅ ⋅ ]Xk−1[?]Xk ⋅ ⋅ ⋅ [?]Xm]A. Then,In Procedure 2, the terms, which are connected
through the reachability, are called the connecting terms.
They are defined as follows.
[Definition 5] (connecting terms) Letσi(i = 1, . . . , n) be the terms which are generated by thestandard bottom-up chart parsing. For each i, let the category of σi be Xi, and the category of the leftmost undecided
term be Yi. Let Ri ∈ {&h, &d} (where &h and &d are thenotations indicating that the terms are connected throughhdC ∗ and C*C C*, respectively). The sequence
σ1R1 ⋅ ⋅ ⋅ Ri−1σiRi ⋅ ⋅ ⋅ Rn−1σn satisfying the following (i)and (ii) is called the connecting terms.
h ∗(i) If Ri = &h, Xi+1 C Yi.
d(ii) If Ri = &d, Xi+1C ∗CC∗ Yi.

"

In Procedure 2, the terms which are generated by thestandard bottom-up chart parsing are connected. The manipulation is as follows.
(Procedure 2) Let (i, j, σ) be an active edge in thechart, and let the leftmost undecided term of the term σ be[?]Y. Let (j, k, σ1R1 ⋅ ⋅ ⋅ Rn−1σn) be the edge with the connecting term in the chart as the label, and let the categoryh ∗of σ1 be X. Then, if X C
Y, the edge(i, k, σ&hσ1R1 ⋅ ⋅ ⋅ Rn−1σn) is added to the chart. If X C*dC C* Y the edge (i, k, σ&dσ1R1 ⋅ ⋅ ⋅ Rn−1σn) is added to thechart.
Terms (1) and (2), for example, are connected as inFig. 4.
In Procedure 3, the dependency structure is computed
based on the connecting terms. The head word of connecting term is defined first.

where dC(τ) is defined as follows. Let h = hc(A → X1
⋅ ⋅ ⋅ Xm).
(a1) If R1 = &h and h = k,(a2) If R1 = &h and h ≠ k,(b) If R1 = &d, dC(τ) = d(σ1).

[Definition 6] (head word of connecting term) Let τ
be a connecting term.
(1) If τ is a term which is generated by the standard
bottom-up chart parsing, the head word of τ is head(τ).
(2) Let τ = σ1R1σ2R2⋅ ⋅ ⋅ Rn−1σn and let σ1 =[[ ⋅ ⋅ ⋅ ]X1 ⋅ ⋅ ⋅ [ ⋅ ⋅ ⋅ ]Xk−1[?]Xk ⋅ ⋅ ⋅ Xm]A. Then, if R1 = &h, and
Xk is the head child, the head word of τ is the head word ofσ2R2 ⋅ ⋅ ⋅ Rn−1σn. If otherwise, the head word of τ is"head(σ1).

"

In the proposed method, if terms are connected
through &h, the head word of the term in connected terms
is propagated [Fig. 5(a)]. If terms are connected through&d, the head word is not propagated [Fig. 5(b)]. By thus
utilizing the reachability, the dependency structure of thesentence fragment can be computed incrementally, without

Fig. 5. Head word propagation based on reachability
relation.

Fig. 4. Connecting terms.

68method based on the standard bottom-up chart parsing(described later) are implemented on Linux PC (Pentium
IV 2 GHz, with main memory 2 GB) using GNU Common
Lisp. As the object of the experiment, all 578 sentences in
ATIS corpus with parse tree, recorded in Penn Treebank[11], are used. There are 509 grammatical rules used in theexperiment, which are extracted from the parse tree of the
corpus. The position of the head child in the grammaticalrule is defined, following the method in Ref. 6.

Fig. 6. An example of head word propagation.

4.1. Experiment for parsing time
In order to evaluate the parsing efficiency of the
proposed method, the parsing time is compared between the
proposed method and the method in Section 2. Figure 7
shows the average parsing time per sentence as a functionof the sentence length.† The average parsing time per sentence is 0.017 s in the proposed method. On the other hand,
it is 11.081 s in the method of Section 2. Thus, the proposed
method based on the reachability effectively reduces theparsing time in the incremental dependency parsing.
The number of edges to cover the inputted sentence
fragment is less in the proposed method than in the methodof Section 2. This helps to reduce the parsing time. Figure
8 shows, for example, the number of edges, which are
generated for the English sentence

applying the grammatical rule to the active edge. Even
though there are many ways to apply the grammatical rule,the number of classified cases concerning the reachability
is at most 2. Consequently, the dependency structure can becomputed more efficiently. The dependency structure computed by the proposed method is equivalent to the structure
computed by the method in Section 2. In other words, thefollowing theorem applies.
[Theorem 8] Let w be the word sequence, let I(w) be
the set of terms for w generated by the incremental chartparsing, and let C(w) be the set of connecting terms for w.
"
Then, dep(I(w)) = depC(C(w)).
The proof is shown in the Appendix.

(10)

3.3. Example of parsing

The number of edges with the generated connecting terms
as the labels is obviously less than the number of edges
generated by the incremental chart parsing.
Examining the case where the 5th word “dinner” isinputted, approximately 6 × 104 edges are generated in theincremental chart parsing, but only about 100 edges are
generated in the proposed method. Figure 9 shows theparsing time for the same sentence. It is seen that the parsing
time is greatly reduced by the time “dinner” is inputted.

As an example, consider the parsing for the sentence
fragment “The boy saw.” For this fragment, the proposed
method applies the standard bottom-up chart parsing, andgenerates terms (1) and (2). The category of (2) is v, and thecategory of the leftmost undecided term of (1) is vp. Sinceh ∗v C vp, (1) and (2) are connected, and the following
connecting term is generated:(9)
The head word of this connecting term (9) is computed as
h ∗in Fig. 6. Using v C vp, “saw” as the head word of (2) is
propagated to the leftmost undecided term of (1). By applying the function depC to determine the dependency structureof connecting term (9), the dependency structure of “Theboy saw” is determined as {〈the → boy〉, 〈boy → saw〉}. It
is the same as the dependency structure, which is computedby the method of Section 2 from terms (5) to (8).

4.2. Accuracy of parsing under time limitation
When the incremental dependency parsing procedure
is introduced into the spoken language processing system,
such as real-time speech conversation and simultaneoustranslation, it is necessary that the parsing time for the user’sutterance be less than the time of the user’s utterance. If theparsing time is longer than the time of utterance, simultaneous progress with the sentence input cannot be continued

4. Experiment and Discussion of Results†

When the parsing time exceeds 60 s per word, the parsing is terminated.
The result shown here is for 154 sentences, for which parsing is not
terminated in the method of Section 2. In the proposed method, parsing is
not terminated for all of the 514 sentences, including the above 154
sentences.

In order to evaluate the proposed method, a dependency parsing experiment is run as follows. The proposed
method, the method in Section 2, and the straightforward69

Fig. 9. The parsing time per word for the sentence, “Ineed to have dinner served.”

Fig. 7. Parsing time per sentence.

eventually, even if the incremental dependency parsing isapplied.
This section analyzes the accuracy of parsing withsuch a time restriction. As the first step, the correct dependency structure for the fragment x of sentence s is defined asfollows.

saw〉, 〈yesterday → saw〉}. For the fragment “The boy saw
the,” the correct dependency structure is {〈the → boy〉, 〈boy→ saw〉}.
The proposed method and the method of Section 2
are equivalent in the sense of Theorem 8. Consequently, theproposed method can always compute the correct dependency structure when the grammatical rules, which areneeded to compose the parse tree, are given. In fact, for all
sentence fragments in the experiment, for which the resultof parsing is obtained, the proposed method could computethe correct dependency structure (see Table 1).
The above property is guaranteed, however, only
when the parsing time is not limited. When the parsing time
is limited, it is not always true that the correct dependency
structure is computed. In this case, it is not clear to what
extent of accuracy the proposed method can achieve theparsing. From such a viewpoint, a time limit is set in parsing
and an experiment is run. The ratio of the sentence fragments for which the correct dependency structure is generated under the time limit, is defined as the accuracy of theincremental parsing.
In the experiment, the utterance speed in natural
English speech is considered, and the time limit for parsing
of a word is set as 0.3 s.† In other words, the words are
inputted from the left successively with an interval of 0.3 s.
The computation of the dependency structure for the sentence fragment w1 ⋅ ⋅ ⋅ wi is started when word wi is inputted(when the parsing for w1 ⋅ ⋅ ⋅ wi−1 is not completed at thattime, the computation is started when that parsing is completed). The precision of parsing is calculated as the “ratioof sentence fragments for which the correct dependency
structure is computed within the time limit.” The average(1) Parse tree for sentence s given by corpus is converted to the dependency structure based on the head information of the grammar (this is called the correct
dependency structure of s).
(2) Among the dependency structures that compose
the correct dependency structure of s, those composed onlyof words appearing in x are extracted (the dependency
structure composed of those dependency structures is called
the correct dependency structure of x).
For English sentence “The boy saw the girl yesterday.”, for example, the correct dependency structure isgiven as {〈the → boy〉, 〈boy → saw〉, 〈the → girl〉, 〈girl →Fig. 8. The number of edges for the sentence, “I need tohave dinner served.”†

Examining the English speaker utterance in CIAIR simultaneous translation database [15], the average utterance time per word is about 0.32 s.

70length of 578 sentences examined in the experiment is 8.5
words. There are 4931 sentence fragments as the object ofincremental dependency parsing.
As a method to generate incrementally the dependency structure, a more straightforward method can be considered, in which the dependency structure is computedfrom all terms generated by the standard bottom-up chartparsing. When, for example, the sentence fragment “Theboy” is analyzed by the standard bottom-up chart parsing
using the grammar of Fig. 2, the term [[the]det[boy]n]np is
generated. The dependency structure of this term is {〈the→ boy〉}, which is considered as the result of computation
for the dependency structure of “The boy.”In this method, however, it can happen that the correct
dependency structure is not generated. In fact, when thesentence fragment “The boy saw” is parsed, using the samegrammar, terms such as [[the]det[boy]n]np and[[saw]v[?]np]vpt are generated. The dependency structure forthose terms is {〈the → boy〉} or φ, and the correct dependency structure {〈the → boy〉, 〈boy → saw〉} is not generated. The method, which is based on the bottom-up chartparsing, does not connect terms. Consequently, the correct
dependency structure is not always generated for any sentence fragment, but has the feature that a fast parsing is
executed. In the following, this straightforward method iscalled the baseline method, for which the same experimentis run for comparison.
Table 1 shows the precision of the proposed method,
the method of Section 2, and the baseline method. In thefollowing, the proposed method and the method of Section
2 are compared first, and then the proposed method and thebaseline method are compared.

Table 2. The number of correctly parsed fragments
Success/failure of correct
dependency structure
Proposed method Baseline method
Success
Success
FailureFailure
Total

77.0
8.9
64.2

77.0
8.9
88.9

4931

The proposed method and the baseline method differ
in that the latter does not include the term connection basedon the reachability. Consequently, the comparison of the
proposed method and the baseline method can be interpreted as the evaluation of the effect of the term connection
based on the reachability. From such a viewpoint, 4931
sentence fragments are examined and are divided intoclasses according to the method by which the correct dependency structure is computed. Table 2 shows the results.
The number of sentence fragments for which thecorrect dependency structure is computed only by the proposed method is 968, which is considerable. For all of thosesentence fragments, the baseline method computed theresult of parsing within the time limit. In other words, forthose 968 fragments, the correct dependency structure cannot be computed unless the connecting term is generated.
On the other hand, there are 335 sentence fragments
for which the correct dependency structure is calculated
only by the baseline method. Those are the case for which
the dependency structure cannot be computed by the proposed method within the time limit. This is due to the factthat the parsing time is shorter in the baseline method, by
the amount that the term connection based on the reachability is not included.†Since the set of sentence fragments, for which thecorrect dependency structure can be computed by one of
the methods, does not include that for the other, it is notpossible to decide simply which method is better, but it isTable 1. Precision of incremental dependency parsing

Proposed method
Method of Section 2
Baseline method

2829
968
335
799

4.2.2. Comparison of proposed method andbaseline method

The method of Section 2 requires a very long parsing
time compared to the proposed method, and cannot generate the result of parsing for a considerable number ofsentence fragments. The precision is low, being 8.9%. This
result indicates that the parsing speed of the method ofRatio of sentence
fragments for which
the parsing result isobtained (%)

Success
FailureSuccess
FailureSection 2 is insufficient. On the other hand, the precision of
the proposed method is 77.0%, which is higher than themethod of Section 2 by as much as 68.1%. This result
indicates that the parsing efficiency is effectively improvedby the proposed method.

4.2.1. Comparison of proposed method andmethod of Section 2

Precision(%)

Number ofsentences†

In the baseline method, the average parsing time per sentence is 0.009 s.

71

5. Collins MJ. A new statistical parser based on bigram
lexical dependencies. Proc 34th Annu Meeting of the
Association for Computational Linguistics, p 184–
191, Santa Cruz, 1996.
6. Collins M. Head-driven statistical models for natural
language parsing. PhD dissertation, University ofPennsylvania, 1999.
7. Eisner JM. Three new probabilistic models for dependency parsing: An exploration. Proc 16th Int Conf
on Computational Linguistics, p 340–345, Copenhagen, 1996.
8. Ehsani F, Hatazaki K, Noguchi J, Watanabe T. Interactive speech dialogue system using simultaneous
understanding. Proc 3rd Int Conf on Spoken Language Processing, p 879–882, Yokohama, 1994.
9. Lombardo V, Lesmo L. An Earley-type recognizer for
dependency grammar. Proc 16th Int Conf on Computational Linguistics, p 723–728, Copenhagen, 1996.
10. Kay M. Algorithm schemata and data structures insyntactic processing. Technical Report, CSL-80-12,
Xerox PARC, 1980.
11. Marcus MP, Santorini B, Marcinkiewicz MA. Building a large annotated corpus of English: The Penn
Treebank. Computational Linguistics 1993;19:310–
330.
12. Matsubara S, Asai S, Toyama K, Inagaki Y. Chartbased parsing and transfer in incremental spoken
language translation. Proc 4th Natural Language
Processing Pacific Rim Symposium, p 521–524,
Phuket, Thailand, 1997.
13. Matsubara S, Toyama K, Inagaki Y. Sync/Trans: Simultaneous machine interpretation between English
and Japanese. Lecture Notes in Artificial Intelligence
1999;1747:134–143.
14. Matsubara S, Watanabe Y, Toyama K, Inagaki Y.
Incremental sentence production for English–Japanese spoken language translation. Tech Rep NL, Inf
Process Soc, NL-132, p 95–100, 1999.
15. Matsubara S, Takagi A, Kawaguchi N, Inagaki Y.
Bilingual spoken monologue corpus for simultaneous machine interpretation research. Proc 3rd Int
Conf on Language Resources and Evaluation, Vol. I,
p 153–159, Canary Islands, 2002.
16. Milward D, Cooper R. Incremental interpretation:
Applications, theory, and relationship to dynamic
semantics. Proc 15th Int Conf on Computational
Linguistics, p 748–754, Kyoto, 1994.
17. Mima H, Iidam H, Furuse O. Simultaneous interpretation utilizing example-based incremental transfer.
Proc 17th Int Conf on Computational Linguistics and36th Annual Meeting of the Association for Computational Linguistics, p 855–861, Montreal, 1998.
18. Murase T, Matsubara S, Kato Y, Inagaki Y. Incremental CFG parsing with statistical lexical depend-seen from Table 1 that the rate of correct result is higher inthe proposed method.

5. Conclusion
This paper considered the situation where the words
of a sentence are successively inputted from the left, andproposed a method which incrementally computes all dependency structures that are grammatically probable. It isshown that, by including a process to compute the dependency structure from the parse tree in the CFG-based incremental parsing, the incremental dependency parsing isrealized.
As a method to realize a more efficient incremental
dependency parsing, a method based on the reachability, asa relation between categories, is proposed. It is theoreticallyshown that the method based on the reachability can generate the dependency structure, which is equivalent to thatobtained by the incremental parsing. It is shown experimentally that the method is effective in reducing the parsingtime.
Up to the present, a method has been reported whichtries to improve the efficiency of the incremental parsing
by utilizing the dependency [18]. In that method, however,the dependency structure is computed from the partial parsetree. It is expected that, by combining the dependency
structure computation proposed in this paper with such amethod, the efficiency of the incremental parsing will be
improved. Such an approach will be investigated at a latertime.
Acknowledgments. The authors thank members of
the laboratory for assisting in this study. They also thankthe reviewer for providing useful comments, which helped
to improve this paper.

REFERENCES
1. Allen J, Ferguson G, Stent A. An architecture formore realistic conversational systems. Proc Intelligent User Interfaces, p 1–8, Santa Fe, NM, 2001.
2. Alshawi H, Bangalore S, Douglas S. Learning dependency translation models as collections of finite
state head transducers. Computational Linguistics
2000;26:45–60.
3. Amtrup JW. Incremental speech translation. Lecture
Notes in Artificial Intelligence No. 1735. SpringerVerlag; 1999.
4. Bröker N. Separating surface order and syntactic
relations in a dependency grammar. Proc 17th Int
Conf on Computational Linguistics and 36th Annual
Meeting of the Association for Computational Linguistics, p 174–180, Montreal, 1998.

72

encies. Proc 6th Natural Language Processing Pacific
Rim Symposium, p 353–358, Tokyo, 2001.
19. Nakano M, Miyazaki N, Hirasawa J, Dohsaka K,
Kawabata T. Understanding unsegmented user utterances in real-time spoken dialogue systems. Proc
37th Annual Meeting of the Association for Computational Linguistics, p 200–207, College Park, USA,1999.
20. Nakano M, Dosaka K. Language and dialogue processing in spoken dialogue system. J Soc Artif Intell
2002;17:271–278.
21. Sleator D, Temperley D. Parsing English with a link
grammar. Carnegie Mellon University Computer Science Tech Rep, CMU-CS-91-196, 1991.

In(w) is the set of terms which is obtained by applying
Operations 4 and 5 for n times to the terms which are
generated by applying the standard bottom-up chart parsing
to w.
For the word sequence w, the set C(w) of connecting
terms which is generated by the proposed method is defined
as follows.
[Definition 10] (set of connecting terms) For the word
sequence, the function Cn that returns the set of connecting
terms is defined as follows.
(1) For any word sequence w, let C1(w) = T(w).
(2) For any word sequence w, let
Ci+1(w)={τ| there exists σ1 ∈ T(w1) and τ2 ∈ Ci(w2)(w = w1w2)
such that τ is the connecting term σ1&hτ2 or σ1&dτ2.

APPENDIX

C(w) is defined as follows.

Proof of Theorem 8
Several definitions to be used in the proof are given
as the first step. Let T(w) be the set of terms for the word
sequence w, which is generated by the standard bottom-up
chart parsing. Let σ be a term. Then, cat(σ) represent thecategory of σ. Let τ = σ1R1 ⋅ ⋅ ⋅ Rn−1σn be a connecting
term, and let catC(τ) = cat(σ1). When the grammatical rules
are applied successively to term σ following Operation 4,
let the obtained term be apply(σ, r1 ⋅ ⋅ ⋅ rq). In the above
representation, it is tacitly assumed that r1, r2, . . . , rq canbe applied successively to σ. The term that is obtained byreplacing the leftmost undecided term of term σ by σ′ iswritten as rep(σ, σ′).
For the word sequence w, the set I(w) of terms, whichis generated by the incremental chart parsing, is defined asfollows.

"
Cn(w) is the set of connecting terms that are obtained byconnecting n terms.
The lemmas needed in the proof of Theorem 8 are as
follows.
[Lemma 11] For an arbitrary n, if σ ∈ In(w), there
exist σ′ ∈ Iop5,j(w) ∪ T(w) (j ≤ n), and grammatical rules
rp (p = 1, . . . , q = n − j) such that σ = apply(σ′, r1⋅ ⋅ ⋅ rq).
(Proof) This is obvious from the definition of In(w).
"[Lemma 12] Let σ ∈ I(w) and let r1r2 ⋅ ⋅ ⋅ rq be asequence of q grammatical rules. Then, dep(apply(σ, r1⋅ ⋅ ⋅ rq)) = dep(σ).
(Proof) This property is shown by the induction inregard to q. When q = 0, there applies apply(σ, ε) = σ, andthe lemma is obviously true. Assume that the lemma is true
for q = n. Let q = n + 1. Let r1 = A → XY ⋅ ⋅ ⋅ Z and r = r2
⋅ ⋅ ⋅ rn+1. Then,[Definition 9] (term generated by incremental chartparsing). For the word sequence, the function In that returns
the set of terms is defined as follows.
(1) For any word sequence w, let I0(w) = T(w).
(2) For any word sequence w, let Ii+1(w) =Iop4,i+1(w) ∪ Iop5,i+1(w), where Iop4,i+1(w) and Iop5,i+1(w) aredefined as follows.

(A.1)
and

Iop4,i+1(w)= {σ|σ′ ∈ Ii(w) and there exists a grammatical rule rsuch that σ = apply(σ′, r)}.
Iop5,i+1(w)= {σ| there exists σ1 ∈ T(w1), σ2 ∈ Ii(w2)(w = w1w2)
such that σ = rep(σ1, σ2)}.

Thus, Lemma 12 is shown by induction.

Furthermore, using In, I(w) is defined as"[Lemma 13] Let σ ∈ I(w), and let rp(p = 1, ⋅ ⋅ ⋅ , q) bea grammatical rule such that hc(rp) = 1. Then, head(apply(σ, r1 ⋅ ⋅ ⋅ rq)) = head(σ).

"

73(A.2)[Lemma 15] Let σ ∈ I(w), and let rp(p = 1, . . . , q) bea grammatical rule. Furthermore, assume that there exists
ri(1 ≤ i ≤ q) such that hc(ri) ≠ 1. Then, head(apply(σ,r1 ⋅ ⋅ ⋅ rq)) = ?.
(Proof) Let σ′ = apply(σ, r1 ⋅ ⋅ ⋅ ri−1), and let
ri = A → XY ⋅ ⋅ ⋅ Z. Since hc(ri) ≠ 1, letting the head childof ri be H,"

Consequently, by Lemma 14, head(apply(apply(σ′, ri),
ri+1 . . . rq)) = ?. In other words, head(apply(σ, r1), . . .
"ri−1riri+1 . . . rq)) = ? and Lemma 15 is shown.

(Proof) The property is shown by induction in regard
to q. It is obvious that the lemma is true when q = 0. Assume
that the lemma is true for q = n. Let q = n + 1. Let r1 = A →XY ⋅ ⋅ ⋅ Z and r = r2 ⋅ ⋅ ⋅ rn+1. Then, Eq. (A.1) applies. On theother hand, since hc(r1) = 1, consequently, by Definition 1,

andThus, Lemma 13 is shown by induction.

[Lemma 16] Let σ1 ∈ T(w1), and let the leftmost
undecided term of σ1 be [?]Xk. Also, let σ2 ∈ I(w2), cat(σ2)= Xk. Let σ = rep(σ1, σ2). Also, let τ2 ∈ C(w2) and let τ =σ1&hτ2 be the connecting term. Furthermore, let[Lemma 14] Let σ ∈ I(w) and let head(σ) = ?. Letrp(p = 1, . . . , q) be a grammatical rule. Then, head(apply(σ,r1 ⋅ ⋅ ⋅ rq)) = ?.
(Proof) The property is shown by induction in regard
to q. The lemma is obviously true for q = 0. Assume thatthe lemma is true for q = n. Let q = n + 1. Let r1 = A → XY
and r = r2 ⋅ ⋅ ⋅ rn+1. As the first step, it is shown for apply(σ,r1) = [σ[?]Y ⋅ ⋅ ⋅ [?]Z]A that

Then,

(A.3)

(Proof) Let σ1 = [[⋅ ⋅ ⋅ ]X1 ⋅ ⋅ ⋅ [⋅ ⋅ ⋅] Xk−1[?]Xk ⋅ ⋅ ⋅ [?]Xm]Aand let h = hc(A → X1 ⋅ ⋅ ⋅ Xk−1Xk ⋅ ⋅ ⋅ Xm). As the first step,head(σ) = headC(τ) is shown by dividing the cases into thecase of h = k and the case of h ≠ k. When h = k,

The case is divided for the case of hc(r1) = 1 and the caseotherwise.
When hc(r1) = 1:

When hc(r1) ≠ 1: Let H be the head child of r1. Then,

When h ≠ k,Thus, head(σ) = headC(τ).
As the next step, dep(σ) = depC(τ) is shown. For this,it suffices to show that d(σ) = dC(τ), using Definitions 2 and7, as well as the assumption of lemma dep(σ2) = depC(τ2).
The case is divided into the cases of h = k and h ≠ k. Whenh = k:

Thus, Eq. (A.3) is valid.
For r1r = r1r2 ⋅ ⋅ ⋅ rn+1, the length of r is n and Eq.
(A.3) is valid. Consequently, by the assumption of induction,(A.4)
Consequently,((A.1))((A.4))
Thus, by induction, Lemma 14 is shown.

"74

When h ≠ k:

(Proof) The property is shown by induction in regard
to n. When n = 0, there holds σ ∈ I0(w) = T(w) ⊆ C(w) and
it is obvious that the lemma is true by letting τ = σ. Assume
that the lemma is true when n = l. Letting σ ∈ Il+1(w), there
holds σ ∈ Iop4,l+1(w) or σ ∈ Iop5,l+1(w).
When σ ∈ Iop4,l+1(w), it suffices to show that there
exists τ ∈ C(w) satisfying condition (1) dep(σ) = depC(τ).
Since σ ∈ Iop4,l+1(w), there exists a grammatical rule r andσ′ ∈ Il(w), such that σ = apply(σ′, r). By Lemma 12, dep(σ)= dep(σ′). Since σ′ ∈ Il(w), there exists, by assumption of
induction, τ ∈ C(w) such that dep(σ′) = depC(τ), and there
holds dep(σ) = dep(σ′) = depC(τ).
When σ ∈ Iop5,l+1(w), there exist σ1 and σ2 such that
σ1 ∈ T(w1) and σ2 ∈ Il(w2), w = w1w2, and there holds σ =rep(σ1, σ2). Since σ2 ∈ Il(w2), it follows from Lemma 11
that there exist σ2g ∈ Iop5,j(w2) ∪ T(w2)(j ≤ l) and grammatical rules rp(p = 1, . . . , q = l – j), such that σ2 = apply(σ2g , r1
⋅ ⋅ ⋅ rq). Then, by the assumption of induction, there exists
τ2 ∈ C(w2), such that

Thus, there holds d(σ) = dC(τ). It follows from Definitions 2 and 7, as well as the assumption of the lemma that"dep(σ) = depC(τ). Thus, Lemma 16 is shown.
[Lemma 17] Let σ1 ∈ T(w1), and let the leftmost
undecided term of σ1 be [?]Xk. Also let σ2 ∈ I(w2), cat(σ2)= Xk and let σ = rep(σ1, σ2). Let τ2 ∈ C(w2), and let τ =σ1&dτ2 be the connecting term. Furthermore, let head(σ2)= ?, dep(σ2) = depC(τ2). Then,

(A.5)
(A.6)
(A.7)

(Proof) The proof of this property almost parallels
that of Lemma 16. Let σ1 = [[⋅ ⋅ ⋅ ]X1 ⋅ ⋅ ⋅ [⋅ ⋅ ⋅] Xk−1[?]Xk ⋅ ⋅ ⋅[?]Xm]A and let h = hc(A → X1 ⋅ ⋅ ⋅ Xk−1Xk ⋅ ⋅ ⋅ Xm). As the firststep,

Let the category of the leftmost undecided term of σ1
be X. If hc(rp) = 1 for any rp(1 ≤ p ≤ q), there holdsh ∗h ∗cat(σ2g ) C X, that is, catC(τ2) C X. Consequently, by
Definition 10, σ1&hτ2 ∈ C(w). For σ1&hτ2, there holdis shown by dividing the case into the case of h = k and thecase of h ≠ k. When h = k, there holds head(σ) = head(σ2)= ? and headC(τ) = head([?]Xk) = ?. When h ≠ k, there holds
head(σ) = head([ . . . ]Xk) = headC(τ). Thus, head(σ) =headC(τ).
The next step is to show that dep(σ) = depC(τ). For
this, it suffices to show that d(σ) = dC(τ). When h = k, bothd(σ) and dC(τ) are φ. When h ≠ k,

It follows from Lemma 16 that dep(σ) = depC(σ1&hτ2) andhead(σ) = headC(σ1&hτ2). There also holds cat(σ) = cat(σ1)= catC(σ1&hτ2).
When hc(rp) ≠ 1 for a certain rp(1 ≤ p ≤ q), thereddholds cat(σ2g ) C∗ CC∗ X, that is, catC(τ2) C∗ CC∗ X. It
follows then from Definition 10 that σ1&dτ2 ∈ C(w). By
Lemma 12, dep(σ2) = dep(σ2g ) and dep(σ2) = depC(τ2). On
the other hand, by Lemma 15, head(σ2) = ?. Consequently,
by Lemma 17, dep(σ) = depC(σ1&dτ2) and head(σ) =headC(σ1&dτ2). Furthermore, there holds cat(s) = cat(σ1) =catC(σ1&dτ2).
Thus, the lemma is valid for n = l + 1. Thus, Lemma
18 is shown by induction.
"

Consequently, d(σ) = dC(τ) and dep(σ) = depC(τ). Thus,
Lemma 17 is shown.
"[Lemma 18] For arbitrary n and a word sequence w,
if σ ∈ In(w), there exists τ ∈ C(w) satisfying the following(1) and (2):(1) dep(σ) = depC(τ).
(2) If σ ∈ Iop5,n(w) ∪ T(w), cat(σ) = catC(τ) andhead(σ) = headC(τ).

[Lemma 19] For arbitrary n and a word sequence w,
if τ ∈ Cn(w), there exists σ ∈ I(w) satisfying dep(σ) =depC(τ), head(σ) = headC(τ), and cat(σ) = catC(τ).

75

(Proof) The property is shown by induction in regard
to n. When n = 1, the lemma is obviously valid, as is seen
by setting σ = τ since τ ∈ C1(w) = T(w) ⊆ I(w). Assume
that the lemma is valid for n = l. Letting τ ∈ Cl+1(w), there
exist certain σ1 ∈ T(w1) and τ2 ∈ Cl(w2) (w = w1w2), R ∈{&h, &d}, such that τ = σ1Rτ2. By the assumption of
induction, there exists σ2 ∈ I(w2) satisfying dep(σ2) =depC(τ2)head(σ2) = headC(τ2) and cat(σ2) = catC(τ2).
Let the category of the leftmost undecided term of σ1h ∗be X. When R = &h, there holds catC(τ2) C X. Then, there
exist grammatical rules rp = Ap → Ypαp(p = 1, . . . , q) suchthat Y1 = catC(τ2), Yp = Ap−1(1 < p ≤ q), Aq = X, and hc(rp)= 1(p = 1, . . . , q) (where αp is the sequence of categories).
For σ2 in the assumption of induction, let
σ2g = apply(σ2, r1 ⋅ ⋅ ⋅ rq). Then, by Definition 9, there holds
σ2g ∈ I(w2). Since cat(σ2g ) = X, there exists rep(σ1, σ2g ),which is an element of I(w). Let it be σ. Then,

By Lemma 16, dep(σ) = depC(τ) and head(σ) = headC(τ).
Furthermore, cat(σ) = cat(σ1) = catC(τ).
dWhen R = &d, catC(τ2) C∗ CC∗ X. Consequently,
there exist grammatical rules rp = Ap → Ypαp(1 ≤ p ≤ q)such that Y1 = c aCt(τ′), Yp = Ap−1(1 < p ≤ q), and Aq = X.
For a certain rp(1 ≤ p ≤ q), there holds hc(rp) ≠ 1. Letting
σ2g = apply(σ2, r1⋅ ⋅ ⋅ rq), there holds σ2g ∈ I(w2). Sincecat(σ2g ) = X, there exists rep(σ1, σ2g ), which is an element of
I(w). Let it be σ. By Lemma 12 and the assumption of
induction, dep(σ2g ) = depC(τ2). By Lemma 15, head(σ2g ) =?. Then it follows from Lemma 17 that dep(σ) = depC(τ)
and head(σ) = headC(τ). Furthermore, cat(σ) = cat(σ1) =catC(τ). Thus, the lemma is valid for n = k + 1. In otherwords, Lemma 19 is shown by induction.
"
It is obvious from Lemma 18 that dep(I(w)) ⊆depC(C(w)). It is also obvious from Lemma 19 thatdep(I(w)) ⊇ depC(C(w)). It follows from those thatdep(I(w)) = depC(C(w)). In other words, Theorem 8 isshown.
(end of proof for Theorem 8)

AUTHORS (from left to right)

Yoshihide Kato (member) graduated from Nagoya University in 1997, completed the doctoral program in 2003, andbecame a research associate at the Graduate School of International Development. He is engaged in research on natural language
processing. He holds a D.Eng. degree, and is a member of Inf. Process. Soc. and Assoc. Natural Language Process.
Shigeki Matsubara (member) graduated from Nagoya Institute of Technology in 1993 and completed the doctoral
program in 1998. He has been an associate professor at the Information Technology Center of Nagoya University since 2002.
His research interests are natural language processing, spoken language processing, and machine translation. He holds a D.Eng.
degree, and is a member of Inf. Process. Soc., Soc. Artif. Intell., Assoc. Natural Language Process., Japan Translation Soc., and
ACL.

76

AUTHORS (continued) (from left to right)

Katsuhiko Toyama (member) graduated from Nagoya University in 1984 and completed the doctoral program in 1989.
He is now an associate professor in the Graduate School of Information Science at Nagoya University. His research interests
are logical knowledge representation and inference, as well as natural language understanding. He holds a D.Eng. degree, andis a member of Inf. Process. Soc., Assoc. Natural Language Process., Soc. Artif. Intell., and Japan Soc. Cogn. Sci.
Yasuyoshi Inagaki (member) graduated from Nagoya University in 1962 and completed the doctoral program in 1967.
After serving professor at Mie University and at Nagoya University, he has been a professor at the Aichi Prefectural University
since 2003. His research interests are theory of switching circuit, automaton and language theory, computation theory, basic
theory of software, theory of parallel processing, algebraic specification description, basic theory of artificial intelligence, andnatural language processing. He is a Vice-President and Fellow of IEICE. He holds a D.Eng. degree, and is a member of Inf.
Process. Soc., Assoc. Natural Language Process., Soc. Artif. Intell., IEEJ, Japan Soc. Software Sci., Japan OR Soc., IEEE, ACM,
and EATCS.

77