A Memory-Based Approach to the Treatment of Serial Verb Construction in Combinatory Categorial Grammar Prachya Boonkwan School of Informatics National Electronics University of Edinburgh and Computer Technology Center 10 Crichton Street 112 Phahon Yothin Rd. Edinburgh EH8 9AB, UK Pathumthani 12120, Thailand Email: p.boonkwan@sms.ed.ac.uk Abstract CCG, one of the most prominent grammar frameworks, efficiently deals with deletion under coordination in natural languages. However, when we expand our attention to more analytic languages whose degree of pro-dropping is more free, CCG's decomposition rule for dealing with gapping becomes incapable of parsing some patterns of intra-sentential ellipses in serial verb construction. Moreover, the decomposition rule might also lead us to overgeneration problem. In this paper the composition rule is replaced by the use of memory mechanism, called CCG-MM. Fillers can be memorized and gaps can be induced from an input sentence in functional application rules, while fillers and gaps are associated in coordination and serialization. Multimodal slashes, which allow or ban memory operations, are utilized for ease of resource management. As a result, CCG-MM is more powerful than canonical CCG, but its generative power can be bounded by partially linear indexed grammar. the mildly context-sensitive grammar class (VijayShanker and Weir, 1994). CCG accounts for gapping in natural languages as a major issue. Its combinatory operations resolve deletion under coordination, such as rightnode raising (SV&SVO) and gapping (SVO&SO). In case of gapping, a specialized rule called decomposition is used to handle with forward gapping (Steedman, 1990) by extracting the filler required by a gap from a complete constituent. However, serial verb construction is a challenging topic in CCG when we expand our attention to more analytic languages, such as Chinese and Thai, whose degree of pro-dropping is more free. In this paper, I explain how we can deal with serial verb construction with CCG by incorporating memory mechanism and how we can restrict the generative power of the resulted hybrid. The integrated memory mechanism is motivated by anaphoric resolution mechanism in Categorial Type Logic (Hendriks, 1995; Moortgat, 1997), Type Logical Grammar (Morrill, 1994; J¨ ger, 1997; J¨ ger, 2001; Oehrle, 2007), and CCG a a (Jacobson, 1999), and gap resolution in MemoryInductive Categorial Grammar (Boonkwan and Supnithi, 2008), as it is designed for associating fillers and gaps found in an input sentence. Theoretically, I discuss how this hybrid efficiently helps us deal with serial verb construction and how far the generative power grows after incorporating the memory mechanism. Outline: I introduce CCG in §2, and then motivate the need of memory mechanism in dealing with serial verb construction in CCG in §3. I describe the hybrid model of CCG and the filler-gap memory in §4. I then discuss the margin of generative power introduced by the memory mechanism in §5. Finally, I conclude this paper in §6. 1 Introduction Combinatory Categorial Grammar (CCG, Steedman (2000)) is a prominent categorial grammar framework. Having a strong degree of lexicalism (Baldridge and Kruijff, 2003), its grammars are encoded in terms of lexicons; that is, each lexicon is assigned with syntactic categories which dictate the syntactic derivation. One of its striking features is the combinatory operations that allow coordination of incomplete constituents. CCG is nearly context-free yet powerful enough for natural languages as it, as well as TAG, LIG, and HG, exhibits the lowest generative power in Proceedings of the EACL 2009 Student Research Workshop, pages 10­18, Athens, Greece, 2 April 2009. c 2009 Association for Computational Linguistics 10 2 Combinatory Categorial Grammar CCG is a lexicalized grammar; i.e. a grammar is encoded in terms of lexicons assigned with one or more syntactic categories. The syntactic categories may be atomic elements or curried functions specifying linear directions in which they seek their arguments. A word is assigned with a syntactic category by the turnstile operator . For example, a simplified English CCG is given below. (1) John np sandwiches eats s\np/np np composition (B), type raising (T), and substitution (S), namely. Classified by directions, the functional composition and type raising rules are described in (6) and (7), respectively. (6) (7) X/Y Y/Z Y\Z X\Y X X X/Z X\Z [> B] [< B] [> T] [< T] Y/(Y\X) Y\(Y/X) The categories X\Y (and X/Y) denotes that X seeks the argument Y from the left (right) side. Combinatory rules are used to combine words forming a derivation of a sentence. For basic combination, forward (>) and backward (<) functional applications, defined in (2), are used. (2) X/Y Y Y X\Y X X [>] [<] These rules permit associativity in derivation resulting in that coordination of incomplete constituents with similar types is possible. For example, we can derive the sentence John likes but Mary dislikes sandwiches in (8). (8) John np >T likes but Mary np >T dislikes s\np/np >B sandwiches np s\np/np & >B s/(s\np) s/np s/(s\np) s/np >& [s/np]& <& s/np s > We can derive the sentence John eats sandwiches by the rules and the grammar in (1) as illustrated in (3). CCG is semantic-transparent; i.e. a logical form can be built compositionally in parallel with syntactic derivation. However, semantic interpretation is suppressed in this paper. (3) John eats sandwiches np CCG also allows functional composition with permutation called disharmonic functional composition to handle constituent movement such as heavy NP shift and dative shift in English. These rules are defined in (9). (9) X/Y Y\Z Y/Z X\Y X\Z X/Z [> B× ] [< B× ] np s\np/np s\np s By disharmonic functional composition rules, we can derive the sentence I wrote briefly a long story of Sinbad as (10). (10) I wrote briefly >B× For coordination of two constituents, the coordination rules are used. There are two types of coordination rules regarding their directions: forward coordination (> &) and backward coordination (< &), defined in (4). (4) & X X [X]& [X]& X [> &] [< &] a long story of Sinbad np > < np s\np/np s\np\(s\np) s\np/np np s By the coordination rules, we can derive the sentence John eats sandwiches and drinks coke in (5). (5) John np eats s\np/np s\np sandwiches and np > drinks coke np > >& & s\np/np s\np [s\np]& To handle the gapping coordination SVO&SO, the decomposition rule was proposed as a separate mechanism from CCG (Steedman, 1990). It decomposes a complete constituent into two parts for being coordinated with the other incomplete constituent. The decomposition rule is defined as follows. (11) X Y X\Y [D] <& s\np s < Beyond functional application and coordination, CCG also makes use of rules motivated by combinators in combinatory logics: functional where Y and X\Y must be seen earlier in the derivation. The decomposition rule allows us to derive the sentence John eats sandwiches, and Mary, noodles as (12). Steedman (1990) stated that English is forward gapping because gapping always 11 takes place at the right conjunct. (12) John np eats s\np/np s\np < sandwiches and Mary np > noodles np B× & np >T s/VP VP\(VP/np) s\(VP/np) D >& it syntactically similar to coordination where the connective is implicit. The serialization rule () was initially defined by imitating the forward coordination rule in (14). (14) X [X]& [] s VP/np s\(VP/np) [s\(VP/np)]& <& s\(VP/np) s < where VP = s\np. A multimodal version of CCG (Baldridge, 2002; Baldridge and Kruijff, 2003) restricts generative power for a particular language by annotating modalities to the slashes to allow or ban specific combinatory operations. Due to the page limitation, the multimodal CCG is not discussed here. This rule allows us to derive by CCG some types of SVC in Chinese and Thai as exemplified in (15) and (16), respectively. (15) w zh´ zh zu` y´ ge h´ zi o e i o i e I fold paper make one CL box `I fold paper to make a box.' kh §o r¢Xp % ¢x kh ¢Xm th n§n % o (16) he hurry run cross road `He hurriedly runs across the road.' 3 Dealing with Serial Verb Construction CCG deals with deletion under coordination by several combinatory rules: functional composition, type raising, disharmonic functional composition, and decomposition rule. This enables CCG to handle a number of coordination patterns such as SVO&VO, SV&SVO, and SVO&SO. However, the decomposition rule cannot solve some patterns of SVC in analytic languages such as Chinese and Thai in which pro-dropping is prevalent. The notion serial verb construction (SVC) in this paper means a sequence of verbs or verb phrases concatenated without connectives in a single clause which expresses simultaneous or consecutive events. Each of the verbs is marked or understood to have the same grammatical categories (such as tense, aspect, and modality), and shares at least one argument, i.e. a grammatical subject. As each verb is tensed, SVC is considered as coordination with implicit connective rather than subordination in which either infinitivization or subclause marker is made use. Motivated by Li and Thompson (1981)'s generalized form of Chinese SVC, the form of Chinese and Thai SVC is generalized in (13). (13) (Subj)V1 (Obj1 )V2 (Obj2 ) . . . Vn (Objn ) One can derive the sentence (15) by considering zh´ `fold' and zu` `make' as s\np/np and ape o plying the serialization rule in (14). In (16), the derivation can be done by assigning r¢Xp `hurry' % and ¢x `run' as s\np, and kh ¢Xm `cross' as % s\np/np. Since Chinese and Thai are pro-drop languages, they allow some arguments of the verbs to be prodropped, particularly in SVC. For example, let us consider the following Thai sentence. (17) kl¢X p©j l©Xj t©Xm h§X t Xk n©j r¢jY¢i y p©j t©X d Kla goDIR followV1 seekV2 in cane-field findV3 t d©Xn d Laay FUT walkV4 leaveV5 goDIR Lit: `Kla goes out, he follows Laay (his cow), he seeks it in the cane field, and he finds that it will walk away.' Sem: `Kla goes out to seek Laay in the cane field and he finds that it is about to walk away.' The subject Subj and any objects Obji of the verb Vi can be dropped. If the subject or one of the objects is not dropped, it will be understood as linearly shared through the sequence. Duplication of objects in SVC is however questionable as it deteriorates the compactness of utterance. In order to deal with SVC in CCG, I considered The sentence in (17) are split into two SVCs: the series of V1 to V3 and the series of V4 to V5 , because they do not share their tenses. The directional verb p©j `go' performs as an adverb identi fying the outward direction of the action. Syntactically speaking, there are two possible analyses of this sentence. First, we can consider the SVC V4 to V5 as a complement of the SVC V1 to V3 . Pro-drops occur at the object positions of the verbs V1 , V2 , and V3 . On the other hand, we can also consider the SVC V1 to V3 and the SVC V4 to V5 as adjoining construction (Muansuwan, 2002) which indicates resultative events in Thai (Thepkanjana, 1986) as exemplified in (18). (18) p t t©X x©X %% % u t k n¡Xm o Piti hit snake fall water `Piti hits a snake and it falls into the water.' 12 In this case, the pro-drop occurs at the subject position of the SVC V4 to V5 , and can therefore be treated as object control (Muansuwan, 2002). However, the sentence in (17) does not show resultative events. I then assume that the first analysis is correct and will follow it throughout this paper. We have consequently reached the question that the verb t©X `find' should exhibit object control d by taking two arguments for the object and the VP complementary, or it should take the entire sentence as an argument. To explicate the proliferation of arguments in SVC, we prefer the first choice to the second one; i.e. the verb t©X `find' is d preferably assigned as s\np/(s\np)/np. In (17), the object l©Xj `Laay' is dropped from the verbs V1 and V2 but appears as one of V3 's arguments. Let us take a closer look on the CCG analysis of (17). It is useful to focus on the SVCs of the verbs V1 -V2 and V3 . It is shown below that the decomposition rule fails to parse the tested sentence through its application illustrated in (19). (19) Kla go follow seek in cane-field np s\np/np find s\np/(s\np)/np s\np/(s\np) > tactic categories resulting in ungrammatical sentences generated. For example we can derive the ungrammatical sentence *Mary eats noodles and quickly by means of the decomposition rule in (20). (20) * Mary np eats s\np/np s\np D noodles np > and quickly >& & s\np\(s\np) [s\np\(s\np)]& <& s\np s\np\(s\np) s\np\(s\np) < s\np s < Laay FUT walk leave go np > The issues of handling ellipses in SVC and overgeneration of the decomposition rule can be resolved by replacing the decomposition rule with a memory mechanism that associates fillers to their gaps. The memory mechanism also makes grammar rules more manageable because it is more straightforward to identify particular syntactic categories allowed or banned from prodropping. I will show how the memory mechanism improves the CCG's coverage of serial verb construction in the next section. s\np 4 D s\np CCG with Memory Mechanism (CCG-MM) The verbs V1 and V2 are transitive and assigned as s\np/np, while V4 and V5 are intransitive and assigned as s\np. From the case (19), it follows that the decomposition rule cannot capture some patterns of intra-sentential ellipses in languages whose degree of pro-dropping is more free. Both types of intra-sentential ellipses which are prevalent in SVC of analytic languages should be captured for the sake of applicability. The use of decomposition rule in analytic languages is not appealing for two main reasons. First, the decomposition rule does not support certain patterns of intra-sentential ellipses which are prevalent in analytic languages. As exemplified in (19), the decomposition rule fails to parse the Thai SVC whose object of the left conjunct is prodropped, since the right conjunct cannot be decomposed by (11). To tackle a broader coverage of intra-sentential ellipses, the grammar should rely on not only decomposition but also a supplement memory mechanism. Second, the decomposition rule allows arbitrary decomposition which leads to over-generation. From their definitions the variable Y can be arbitrarily substituted by any syn- As I have elaborated in the last section, CCG needs a memory mechanism (1) to resolve intrasentential ellipses in serial verb construction of analytic languages, and (2) to improve resource management for over-generation avoidance. To do so, such memory mechanism has to extend the generative power of the decomposition rule and improve the ease of resource management in parallel. The memory mechanism used in this paper is motivated by a wide range of previous work from computer science to symbolic logics. The notion of memory mechanism in natural language parsing can be traced back to HOLD registers in ATN (Woods, 1970) in which fillers (antecedents) are held in registers for being filled to gaps found in the rest of the input sentence. These registers are too powerful since they enable ATN to recognize the full class of context-sensitive grammars. In Type Logical Grammar (TLG) (Morrill, 1994; J¨ ger, 1997; J¨ ger, 2001; Oehrle, 2007), a a Gentzen's sequent calculus was incorporated with variable quantification to resolve pro-forms and VP ellipses to their antecedents. The variable quantification in TLG is comparable to the use of memory in storing antecedents and anaphora. 13 In Categorial Type Logic (CTL) (Hendriks, 1995; Moortgat, 1997), gap induction was incorporated. Syntactic categories were modified with modalities which permit or prohibit gap induction in derivation. However, logical reasoning obtained from TLG and CTL are an NP-complete problem. In CCG, Jacobson (1999) attempted to explicitly denote non-local anaphoric requirement whereby she introduced the anaphoric slash (|) and the anaphoric connective (Z) to connect anaphors to their antecedents. However, this framework does not support anaphora whose argument is not its antecedent, such as possessive adjectives. Recently, a filler-gap memory mechanism was again introduced to Categorial Grammar, called Memory-Inductive Categorial Grammar (MICG) (Boonkwan and Supnithi, 2008). Fillers and gaps, encoded as memory modalities, are modified to syntactic categories, and they are associated by the gap-resolution connective when coordination and serialization take place. Though their framework is successful in resolving a wide variety of gapping, its generative power falls between LIG and Indexed Grammar, theoretically too powerful for natural languages. The memory mechanism introduced in this paper deals with fillers and gaps in SVC. It is similar to anaphoric resolution in ATN, Jacobson's model, TLG, and CTL. However, it also has prominent distinction from them: The anaphoric mechanisms mentioned earlier are dealing with unbounded dependency or even inter-sentential ellipses, while the memory mechanism in this paper is dealing only with intra-sentential bounded dependency in SVC as generalized in (13). Moreover, choices of filler-gap association can be pruned out by the use of combinatory directionality because the word order of analytic languages is fixed. It is noticeable that we can simply determine the grammatical function (subject or object) of arbitrary np's in (13) from the directionality (the subject on the left and the object on the right). With these reasons, I therefore adapted the notions of MICG's memory modalities and gap-resolution connective (Boonkwan and Supnithi, 2008) for the backbone of the memory mechanism. In CCG with Memory Mechanism (CCG-MM), syntactic categories are modalized with memory modalities. For each functional application, a syntactic category can be stored, or memorized, into the filler storage and the resulted category is modalized with the filler 2. A syntactic category can also be induced as a gap in a unary derivation called induction and the resulted category is modalized with the gap 3. There are two constraint parameters in each modality: the combinatory directionality d {< , >} and the syntactic category c, resulting in the filler and the gap denoted in the forms 2d and 3d , c c respectively. For example, the syntactic category 2< 3> s has a filler of type np on the left side and np np a gap of type np on the right side. The filler 2d and the gap 3d of the same dic c rectionality and syntactic categories are said to be symmetric under the gap-resolution connective ; that is, they are matched and canceled in the gap resolution process. Apart from MICG, I restrict the associative power of to match only a filler and a gap, not between two gaps, so that the generative power can be preserved linear. This topic will be discussed in §5. Given two strings of modalities m1 and m2 , the gap-resolution connective is defined in (21). (21) 2d m1 3d m2 c c 3d m1 2d m2 c c m1 m2 m1 m2 The notation denotes an empty string. It means that a syntactic category modalized with an empty modality string is simply unmodalized; that is, any modalized syntactic categories X are equivalent to the unmodalized ones X. Since the syntactic categories are modalized by a modality string, all combinatory operations in canonical CCG must preserve the modalities after each derivation step. However, there are two conditions to be satisfied: Condition A: At least one operands of functional application must be unmodalized. Condition B: Both operands of functional composition, disharmonic functional composition, and type raising must be unmodalized. Both conditions are introduced to preserve the generative power of CCG. This topic will be discussed in §5. As adopted from MICG, there are two memory operations: memorization and induction. Memorization: a filler modality is pushed to the top of the memory when an functional application rule is applied, where the filler's syntactic category must be unmodalized. Let m be a modal- 14 ity string, the memorization operation is defined in (22). (22) X/Y mY mX/Y Y Y mX\Y mY X\Y 2< mX X/Y 2> mX Y 2< mX Y > 2X\Y mX [> MF ] [> MA ] [< MA ] [< MF ] Table 1: Slash modalities for memory operations. - Left - Right + Right + Left · Induction: a gap modality is pushed to the top of the memory when a gap of such type is induced at either side of the syntactic category. Let m be a modality string, the induction operation is defined in (23). (23) mX/Y mY mX\Y mY 3> mX Y 3< mX X/Y 3< mX Y 3> mX X\Y [> IA ] [> IF ] [< IA ] [< IF ] Because the use of memory mechanism elucidates fillers and gaps hidden in the derivation, we can then replace the decomposition rule of the canonical CCG with the gap resolution process of MICG. Fillers and gaps are associated in the coordination and serialization by the gap-resolution connective . For any given m1 , m2 , if m1 m2 exists then always m1 m2 . Given two modality strings m1 and m2 such that m1 m2 exists, the coordination rule () and serialization rule () are redefined on in (24). (24) m1 X & m2 X m1 X m2 X X X [] [] Once we instantiate X1 and X2 , the derivation obtained in (25) is quite more straightforward than the derivation in (12). The filler eats is introduced on the left conjunct, while the gap of type s\np/np is induced on the right conjunct. The coordination operation associates the filler and the gap resulting in a complete derivation. A significant feature of the memory mechanism is that it handles all kinds of intra-sentential ellipses in SVC. This is because the coordination and serialization rules allow pro-dropping in either the left or the right conjunct. For example, the intra-sentential ellipses pattern in Thai SVC illustrated in (19) can be derived as illustrated in (26). (26) Kla go follow seek in cane-field np s\np/np >IA 3> s\np np find s\np/(s\np)/np Laay FUT walk leave go np s\np >MA 2> s\np/(s\np) np 2> s\np np s\np s > < At present, the memory mechanism was developed in Prolog for the sake of unification mechanism. Each induction rule is nondeterministically applied and variables are sometimes left uninstantiated. For example, the sentence in (12) can be parsed as illustrated in (25). (25) John np eats s\np/np sandwiches and Mary np >MF < noodles np 3< X 1 /np >IF X1 < & np 2< s\np s\np/np 2< s s\np/np 3< X 2 \np/np X2 s Let us consider the derivation in the right conjunct. The gap induction is first applied on np resulting in 3< 1 /np X1 , where X1 is an uninstantiated variX able. Then the backward application is applied, so that X1 is unified with X2 \np. Finally, the left and the right conjuncts are coordinated yielding that X2 is unified with s and X1 with s\np. For convenience of type-setting, let us suppose that we can always choose the right type in each induction step and suppress the unification process. By replacing the decomposition rule with the memory mechanism, CCG accepts all patterns of pro-dropping in SVC. It should also be noted that the derivation in (20) is per se prohibited by the coordination rule. Similar to canonical CCG, CCG-MM is also resource-sensitive; that is, each combinatory operation is allowed or prohibited with respect to the resource we have (Baldridge and Kruijff, 2003). Baldridge (2002) showed that we can obtain a cleaner resource management in canonical CCG by the use of modalized slashes to control combinatory behavior. His multimodal schema of slash permissions can also be applied to the memory mechanism in much the same way. I assume that there are four modes of memory operations according to direction and allowance of memory operations as in Table 1. The modes can be organized into the type hierarchy shown in Figure 1. The slash modality , the most limited mode, does not allow any memory operations on both sides. The slash modalities and allow memorization and induction on the 15 ? ??? ?? ? ?? ?? ?? ?? · We will follow the equivalent proof of VijayShanker and Weir (1994) to investigate the generative power of CCG-MM. Let us first assume that we are going to construct an LIG G = (VN , VT , VS , S, P ) that subsumes CCG-MM. To construct G, let us define each of its component as follows. VN is a finite set of syntactic categories, VT is a finite set of terminals, VS is a finite set of stack symbols having the form 2d , 3d , /c, or \c, c c S VN is the start symbol, and P is a finite set of productions, having the form A[] A[ l] a A1 [] . . . Ai [ l ] . . . An [] Figure 1: Hierarchy of slash modalities for memory operations. left and right sides, respectively. Finally, the slash modality · allows memorization and induction on both sides. In order to distinguish the memory operation's slash modalities from Baldridge's slash modalities, I annotate the first as a superscript and the second as a subscript of the slashes. For example, the syntactic category s\× np denotes that s\np allows permutation in crossed functional composition (×) and memory operations on the left side ( ). As with Baldridge's multimodal framework, the slash modality · can be omitted from writing. By defining the slash modalities, it follows that the memory operations can be defined in (27). (27) mX/ Y Y X/ Y mY Y mX\ Y mY X\ Y mX/ Y mY mX\ Y mY 2> mX Y 2< Y mX X/ 2< mX Y > 2X\ Y mX 3> mX Y 3< Y mX X/ 3< mX Y 3> Y mX X\ [> MF ] [> MA ] [< MA ] [< MF ] [> IA ] [> IF ] [< IA ] [< IF ] where each Ak VN , d {<, >}, c VN , l, l VS , and a VT { }. When incorporating with the memory mechanism and the slash modalities, CCG becomes flexible enough to handle all patterns of intrasentential ellipses in SVC which are prevalent in analytic languages, and to manage its lexical resource. I will now show that CCG-MM extends the generative power of the canonical CCG. The notation for stacks uses [ l] to denote an arbitrary stack whose top symbol is l. The linearity of LIG comes from the fact that in each production there is only one daughter that share the stack features with its mother. Let us also define () as the homomorphic function that converts each modality in a modality string into its symmetric counterpart, i.e. a filler 2d into a gap 3d , and vice c c versa. The stack in this LIG is used for storing (1) tailing slashes of a syntactic category for harmonic/disharmonic functional composition rules, and (2) modalities of a syntactic category for gap resolution. We start out by transforming the lexical item. For every lexical item of the form w X where X is a syntactic category, add the following production to P : (28) X[] w 5 Generative Power We add two unary rules for converting between tailing slashes and stack values. For every syntactic category X and Y1 , . . . , Yn , the following rules are added. (29) X|1 Y1 . . . |n Yn [] X[ |1 Y1 . . . |n Yn ] X[ |1 Y1 . . . |n Yn ] X|1 Y1 . . . |n Yn [] In this section, we will informally discuss the margin of generative power introduced by the memory mechanism. Since Vijay-Shanker (1994) showed that CCG and Linear Indexed Grammar (LIG) (Gazdar, 1988) are weakly equivalent; i.e. they generate the same sets of strings, we will first compare the CCG-MM with the LIG. As will be shown, its generative power is beyond LIG; we will find the closest upper bound in order to locate it in the Chomsky's hierarchy. where the top of must be a filler or a gap, or must be empty. This constraint preserves the ordering of combinatory operations. We then transform the functional application rules into LIG productions. From Condition A, we can generalize the functional application rules in (2) as follows. 16 (30) mX/Y Y X/Y mY mY X\Y Y mX\Y mX mX mX mX where m is a modality string. Condition A preserves the linearity of the generative power in that it prevents the functional application rules from involving the two stacks of the daughters at once. We can convert the rules in (30) into the following productions. (31) X[] X[] X[] X[] X[ /Y] Y[] X[/Y] Y[] Y[] X[\Y] Y[] X[ \Y] erly more powerful than CCG. We therefore have to find an upper bound of its generative power. Though CCG-MM is more powerful than CCG and LIG, the rules in (35) reveal a significant property of Partially Linear Indexed Grammar (PLIG) (Keller and Weir, 1995), an extension of LIG whose productions are allowed to have two or more daughters sharing stack features with each other but these stacks are not shared with their mother as shown in (36). (36) A[] A1 [] . . . Ai [] . . . Aj [] . . . An [] We can generalize the harmonic and disharmonic, forward and backward composition rules in (6) and (9) as follows. (32) X/Y Y|1 Z1 . . . |n Zn Y|1 Z1 . . . |n Zn X\Y X|1 Z1 . . . |n Zn X|1 Z1 . . . |n Zn where each |i {\, /}. By Condition B, we obtain that all operands are unmodalized so that we can treat only tailing slashes. That is, Condition B prevents us from processing both tailing slashes and memory modalities at once where the linearity of the rules is deteriorated. We can therefore convert these rules into the following productions. (33) X[] X[] X[/Y] Y[] Y[] X[\Y] Whereby restricting the power of the gapresolution connective, the two stacks of the daughters are shared but not with their mother. An interesting trait of PLIG is that it can generate the language {wk |w is in a regular language and k N }. This is similar to the pattern of SVC in which a series of verb phrase can be reduplicated. To conclude this section, CCG-MM is more powerful than LIG but less powerful than PLIG. From (Keller and Weir, 1995), we can position the CCG-MM in the Chomsky's hierarchy as follows: CFG < CCG = TAG = HG = LIG < CCG - MM PLIG LCFRS < CSG. 6 Conclusion and Future Work The memorization and induction rules described in (27) are transformed into the following productions. (34) X[ 2< ] X/Y X[ 2> ] Y X[ 2< ] Y > X[ 2X\Y ] X[ 3> ] Y X[ 3< ] X/Y X[ 3< ] Y X[ 3> ] X\Y X[/Y] Y[] X[ /Y] Y[] Y[] X[ \Y] Y[] X[\Y] X[ /Y] Y[] X[ \Y] Y[] However, it is important to take into account the coordination and serialization rules, because they involve two stacks which have similar stack values if we convert one of them into the symmetric form with . Those rules can be transformed as follows. (35) X[] X[] X[] X[] &[] X[()] X[()] It is obvious that the rules in (35) are not LIG production; that is, CCG-MM cannot be generated by any LIGs; or more precisely, CCG-MM is prop- I have presented an approach to treating serial verb construction in analytic languages by incorporating CCG with a memory mechanism. In the memory mechanism, fillers and gaps are stored as modalities that modalize a syntactic category. The fillers and the gaps are then associated in the coordination and the serialization rules. This results in a more flexible way of dealing with intrasentential ellipses in SVC than the decomposition rule in canonical CCG. Theoretically speaking, the proposed memory mechanism increases the generative power of CCG into the class of partially linear indexed grammars. Future research remains as follows. First, I will investigate constraints that reduce the search space of parsing caused by gap induction. Second, I will apply the memory mechanism in solving discontinuous gaps. Third, I will then extend this framework to free word-ordered languages. Fourth and finally, the future direction of this research is to develop a wide-coverage parser in which statistics is also made use to predict memory operations occuring in derivation. 17 References Jason Baldridge and Geert-Jan M. Kruijff. 2003. Multimodal combinatory categorial grammar. In Proceedings of the 10th Conference of the European Chapter of the ACL 2003, pages 211­218, Budapest, Hungary. Jason Baldridge. 2002. Lexically Specified Derivational Control in Combinatory Categorial Grammar. Ph.D. thesis, University of Edinburgh. Prachya Boonkwan and Thepchai Supnithi. 2008. Memory-inductive categorial grammar: An approach to gap resolution in analytic-language translation. In Proceedings of The Third International Joint Conference on Natural Language Processing, volume 1, pages 80­87, Hyderabad, India, January. Gerald Gazdar. 1988. Applicability of indexed grammars to natural languages. In U. Reyle and C. Rohrer, editors, Natural Language Parsing and Linguistic Theories, pages 69­94. Reidel, Dordrecht. Petra Hendriks. 1995. Ellipsis and multimodal categorial type logic. In Proceedings of Formal Grammar Conference, pages 107­122. Barcelona, Spain. Pauline Jacobson. 1999. Towards a variable-free semantics. Linguistics and Philosophy, 22:117­184, October. Gerhard J¨ ger. 1997. Anaphora and ellipsis in typea logical grammar. In Proceedings of the 11th Amsterdam Colloquium, pages 175­180, Amsterdam, the Netherland. ILLC, Universiteit van Amsterdam. Gerhard J¨ ger. 2001. Anaphora and quantification a in categorial grammar. In Lecture Notes in Computer Science; Selected papers from the 3rd International Conference, on logical aspects of Computational Linguistics, volume 2014/2001, pages 70­89. Bill Keller and David Weir. 1995. A tractable extension of linear indexed grammars. In In Proceedings of the 7th European Chapter of ACL Conference. Charles N. Li and Sandra A. Thompson. 1981. Mandarin Chinese: A Functional Reference Grammar. Berkeley: University of California Press. Michael Moortgat. 1997. Categorial type logics. In van Benthem and ter Meulen, editors, Handbook of Logic and Language, chapter 2, pages 163­170. Elsevier/MIT Press. Glyn Morrill. 1994. Type logical grammar. In Categorial Logic of Signs. Kluwer, Dordrecht. Nuttanart Muansuwan. 2002. Verb Complexes in Thai. Ph.D. thesis, University at Buffalo, The State University of New York. Richard T. Oehrle, 2007. Non-Transformational Syntax: A Guide to Current Models, chapter Multimodal Type Logical Grammar. Oxford: Blackwell. Mark Steedman. 1990. Gapping as constituent coordination. Linguistics and Philosophy, 13:207­263. Mark Steedman. 2000. The Syntactic Process. The MIT Press, Cambridge, Massachusetts. Kingkarn Thepkanjana. 1986. Serial Verb Constructions in Thai. Ph.D. thesis, University of Michigan. K. Vijay-Shanker and David J. Weir. 1994. The equivalence of four extensions of context-free grammars. Mathematical Systems Theory, 27(6):511­546. William A. Woods. 1970. Transition network grammars for natural language analysis. Communications of the ACM, 13(10):591­606, October. 18