Tree-Adjoining Grammars as Abstract Categorial Grammars Philippe de Groote LORIA UMR no 7503 – INRIA Campus Scientifique, B.P. 239 54506 Vandœuvre l`es Nancy Cedex – France e-mail: [email protected]

1. Introduction We recently introduced abstract categorial grammars (ACGs) (de Groote, 2001) as a new categorial formalism based on Girard linear logic (Girard, 1987). This formalism, which derives from current type-logical grammars (Carpenter, 1996; Moortgat, 1997; Morrill, 1994; Oehrle, 1994), offers some novel features: • Any ACG generates two languages, an abstract language and an object language. The abstract language may be thought as a set of abstract grammatical structures, and of the object language as the set of concrete forms generated from these abstract structures. Consequently, one has a direct control on the parse structures of the grammar. • The langages generated by the ACGs are sets of linear λ-terms. This may be seen as a generalization of both string-langages and tree-langages. • ACGs are based on a small set of mathematical primitives that combine via simple composition rules. Consequently, the ACG framework is rather flexible. Abstract categorial grammars are not intended as yet another grammatical formalism that would compete with other established formalisms. It should rather be seen as the kernel of a grammatical framework — in the spirit of (Ranta, 2002) — in which other existing grammatical models may be encoded. This paper illustrates this fact by showing how tree-adjoining grammars (Joshi and Schabes, 1997) may be embedded in abstract categorial grammars. This embedding exemplifies several features of the ACG framework: • The fact that the basic objects manipulated by an ACG are λ-terms allows higher-order operations to be defined. Typically, tree-adjunction is such a higher-order operation (Abrusci, Fouquer´e and Vauzeilles, 1999; Joshi and Kulick, 1997; M¨onnich, 1997). • The flexibility of the framework allows the embedding to be defined in two stages. A first ACG allows the tree langage of a given TAG to be generated. The abstract language of this first ACG corresponds to the derivation trees of the TAG. Then, a second ACG allows the corresponding string language to be extracted. The abstract language of this second ACG corresponds to the object language of the first one. 2. Abstract Categorial Grammars This section defines our notion of an abstract categorial grammar. We first introduce the notions of linear implicative types, higher-order linear signature, linear λ-terms built upon a higher-order linear signature, and lexicon. Let A be a set of atomic types. The set T (A) of linear implicative types built upon A is inductively defined as follows: 1. if a ∈ A, then a ∈ T (A); 2. if α, β ∈ T (A), then (α −◦ β) ∈ T (A). A higher-order linear signature consists of a triple Σ = hA, C, τ i, where: 1. A is a finite set of atomic types; c 2002 Philippe de Groote. Proceedings of the Sixth International Workshop on Tree Adjoining Grammar and Related Frame works (TAG+6), pp. 101–106. Universit´a di Venezia.

102

Proceedings of TAG+6

2. C is a finite set of constants; 3. τ : C → T (A) is a function that assigns to each constant in C a linear implicative type in T (A). Let X be a infinite countable set of λ-variables. The set Λ(Σ) of linear λ-terms built upon a higher-order linear signature Σ = hA, C, τ i is inductively defined as follows: 1. if c ∈ C, then c ∈ Λ(Σ); 2. if x ∈ X, then x ∈ Λ(Σ); 3. if x ∈ X, t ∈ Λ(Σ), and x occurs free in t exactly once, then (λx. t) ∈ Λ(Σ); 4. if t, u ∈ Λ(Σ), and the sets of free variables of t and u are disjoint, then (t u) ∈ Λ(Σ). Λ(Σ) is provided with the usual notion of capture avoiding substitution, α-conversion, and β-reduction (Barendregt, 1984). Given a higher-order linear signature Σ = hA, C, τ i, each linear λ-term in Λ(Σ) may be assigned a linear implicative type in T (A). This type assignment obeys an inference system whose judgements are sequents of the following form: Γ −Σ t : α where: 1. Γ is a finite set of λ-variable typing declarations of the form ‘x : β’ (with x ∈ X and β ∈ T (A)), such that any λ-variable is declared at most once; 2. t ∈ Λ(Σ); 3. α ∈ T (A). The axioms and inference rules are the following: −Σ c : τ (c) (cons) x : α −Σ x : α

(var)

Γ, x : α −Σ t : β Γ −Σ (λx. t) : (α −◦ β) Γ −Σ t : (α −◦ β)

(abs)

∆ −Σ u : α

Γ, ∆ −Σ (t u) : β

(app)

Given two higher-order linear signatures Σ1 = hA1 , C1 , τ1 i and Σ2 = hA2 , C2 , τ2 i, a lexicon L : Σ1 → Σ2 is a realization of Σ1 into Σ2 , i.e., an interpretation of the atomic types of Σ1 as types built upon A2 together with an interpretation of the constants of Σ1 as linear λ-terms built upon Σ2 . These two interpretations must be such that their homomorphic extensions commute with the typing relations. More formally, a lexicon L from Σ1 to Σ2 is defined to be a pair L = hF, Gi such that: 1. F : A1 → T (A2 ) is a function that interprets the atomic types of Σ1 as linear implicative types built upon A2 ; 2. G : C1 → Λ(Σ2 ) is a function that interprets the constants of Σ1 as linear λ-terms built upon Σ2 ; 3. the interpretation functions are compatible with the typing relation, i.e., for any c ∈ C1 , the following typing judgement is derivable: −Σ2 G(c) : Fˆ (τ1 (c)), where Fˆ is the unique homomorphic extension of F . We are now in a position of defining the notion of abstract categorial grammar. An abstract categorial grammar is a quadruple G = hΣ1 , Σ2 , L , si where:

Ph. de Groote

103

1. Σ1 and Σ2 are two higher-order linear signatures; they are called the abstract vovabulary and the object vovabulary, respectively ; 2. L : Σ1 → Σ2 is a lexicon from the abstract vovabulary to the object vovabulary; 3. s is an atomic type of the abstract vocabulary; it is called the distinguished type of the grammar. The abstract language generated by G (A(G )) is defined as follows: A(G ) = {t ∈ Λ(Σ1 ) | −Σ1 t : s is derivable} In words, the abstract language generated by G is the set of closed linear λ-terms, built upon the abstract vocabulary Σ1 , whose type is the distinguished type s. On the other hand, the object language generated by G (O(G )) is defined to be the image of the abstract language by the term homomorphism induced by the lexicon L : O(G ) = {t ∈ Λ(Σ2 ) | ∃u ∈ A(G ). t = L (u)} 3. Representing Tree-Adjoining Grammars In this section, we explain how to construct an abstract categorial grammar that generates the same tree langage as a given tree-adjoining grammar. Let G = hΣ, N, I, A, Si be a tree-adjoining grammar, where Σ, N , I, A, and S are the set of terminal symbols, the set of non-terminal symbols, the set of initial trees, the set of auxiliary tree, and the distinguished non-terminal G G G symbol, respectively. We associate to G an ACG G G = hΣG 1 , Σ2 , L , s i as follows. G The set of atomic types of Σ1 is made of two copies of the set of non-terminal symbols. Given α ∈ N , we write αS and αA for the two corresponding atomic types. Then, we associate a constant cT : γ1 A −◦ · · · γm A −◦ β1 S −◦ · · · βn S −◦ αS to each initial tree T whose root node is labelled by α, whose substitution nodes are labeled by β1 , . . . , βn , and whose interior nodes are labeled by γ1 , . . . , γm . Similarly, we associate a constant cT 0 : γ1 A −◦ · · · γm A −◦ β1 S −◦ · · · βn S −◦ αA −◦ αA to each auxiliary tree T 0 whose root node is labelled by α, whose substitution nodes are labeled by β1 , . . . , βn , and whose interior nodes are labeled by γ1 , . . . , γm . Finally, we also associate to each non-terminal symnbol α ∈ N , a constant Iα of type αA . This concludes the specification of the abstract vocabulary. The object vocabulary ΣG 2 allows labelled trees to be represented. Its set of atomic types contains only one element : τ (for tree). Then, its set of constants consists in: 1. constants of type τ corresponding to the terminal symbols of G; 2. for each non-terminal symbol α, constants αi : τ −◦ · · · τ −◦ τ | {z } i times

for 1 ≤ i ≤ k, where k is the maximal branching of the interior nodes labelled with α that occur in the initial and auxiliary trees of G. Clearly, the terms of type τ that can be built by means of the above set of constants correspond to trees whose frontier nodes are terminal symbols and whose interior nodes are labelled with non-terminal symbols. It remains to define the lexicon L G . The rough idea is to represent the initial trees as trees (i.e., terms of type τ ) and the auxiliary trees as functions over trees (i.e., terms of type τ −◦ τ ). Consequently, for each α ∈ N , we let L G (αS ) = τ and L G (αA ) = τ −◦ τ . Accordingly, the susbstitution nodes will be represented as first-order λvariables of type τ , and the adjunction nodes as second-order λ-variables of type τ −◦ τ . The object representation of the elementary trees is then straightforward. Consider, for instance, the following initial tree and auxiliary tree:

104

Proceedings of TAG+6

y S DDD yy DD y D yy NP↓ VP @ @@ {{ { @@ { {{ NP↓ V

VP B BB }} BB } }} V VP∗ has

loved According to our construction, the two abstract constants corresponding to these trees have the following types: Cloved : SA −◦ VPA −◦ VA −◦ NPS −◦ NPS −◦ SS

and

Chas : VPA −◦ VA −◦ VPA −◦ VPA

Then, the realization of these two constants is as follows: L G (Cloved ) = λF. λG. λH. λx. λy. F (S2 x (G (VP2 (H (V1 loved)) y))) L G (Chas ) = λF. λG. λH. λx. F (VP2 (G (V1 has)) (H x)) In order to derive actual trees, the second-order variables should eventually disappear. The abstract constants Iα have been introduced to this end. Consequently they are realized by the identity function, i.e., L G (Iα ) = λx. x. Finally, the distinguished type of G G is defined to be SS . This completes the definition of the ACG G G associated to a TAG G. Then, the following proposition may be easily established. P ROPOSITION Let G be a TAG. The tree-language generated by G is isomorphic to the object language of the ACG G G associated to G. t u 4. Example Consider the TAG with the following initial tree and auxiliary tree:

S c

SA }} AAA } A }} a e SA }} AAA } A }} S∗ b d

It generates a non context-free language whose intersection with the regular language a∗ b∗ c d∗ e∗ is an bn c dn en . According to the construction of Section 3, this TAG may be represented by the ACG, G = hΣ1 , Σ2 , L , Si, where: Σ1 = h {SS , SA }, {ci , ca , I}, {ci 7→ (SA −◦ SS ), ca 7→ (SA −◦ (SA −◦ (SA −◦ SA ))), I 7→ SA } i Σ2 = h {τ }, {a, b, c, d, e, S1 , S3 }, {a, b, c, d, e 7→ τ, S1 7→ (τ −◦ τ ), S3 7→ (τ −◦ (τ −◦ (τ −◦ τ )))} i L = h {SS 7→ τ, SA 7→ (τ −◦ τ )}, {ci 7→ λf. f (S1 c), ca 7→ λf. λg. λh. λx. f (S3 a (g (S3 b (h x) d)) e), I 7→ λx. x} i

Ph. de Groote

105

5. Extracting the string languages There is a canonical way of representing strings as linear λ-terms. It consists of encoding a string of symbols as a composition of functions. Consider an arbitrary atomic type σ, and define the type ‘string’ to be (σ −◦ σ). Then, a string such as ‘abbac’ may be represented by the linear λ-term: λx. a (b (b (a (c x)))), where the atomic strings ‘a’, ‘b’, and ‘c’ are declared to be constants of type (σ −◦ σ). In this setting, the empty word is represented by the identity function: 4 = λx. x and concatenation is defined to be functional composition: 4

α + β = λα. λβ. λx. α (β x), which is indeed an associative operator that admits the identity function as a unit. G G This allows a second ACG, G 0 , to be defined. Its abstract vocabulary is the object vocabulary ΣG 2 of G . Its object vocabulary allows string of terminal symbols to be represented. Its lexicon interprets each constant of type G τ as an atomic string, and each constant αi as a concatenation operator. This second ACG, G 0 , extracts the yields G of the trees. Then, by composing G G with G 0 , one obtains an ACG which generates the same string-language as G. Let us continue the example of Section 4. The second ACG, G 0 = hΣ01 , Σ02 , L 0 , S 0 i, is defined as follows: Σ01 = Σ2 Σ02 = h {σ}, {a, b, c, d, e}, {a, b, c, d, e 7→ (σ −◦ σ)} i L 0 = h {τ 7→ (σ −◦ σ)}, {a 7→ λx. a x, b 7→ λx. b x, c 7→ λx. c x, d 7→ λx. d x, e 7→ λx. e x, S1 7→ λf. λx. f x, S3 7→ λf. λg. λh. f (g (h x))} i 6. Expressing Adjoining constraints Adjunction, which is enabled by second-order variables at the object level, is explicitly controlled at the abstract level by means of types. This typing discipline may be easily refined in order to express adjoining constraints such as selective, null, or obligatory adjunction. Consider again the TAG given in Section 4. By adding the following null adjunction constraints on its auxiliary tree: SNAD DD zz DD z z D zz a e SC {{ CCC { CC { {{ ∗ S b d NA one obtains a grammar that generates exactly the non context-free language an bn c dn en . These constraints may be expressed in a simple and natural way. It suffices to exclude the constrained nodes from the arguments of the λ-term corresponding to the auxiliary tree. This gives the following modified ACG: Σ1 = h {SS , SA }, {ci , ca , I}, {ci 7→ (SA −◦ SS ), ca 7→ (SA −◦ SA ), I 7→ SA } i

106

Proceedings of TAG+6

Σ2 = h {τ }, {a, b, c, d, e, S1 , S3 }, {a, b, c, d, e 7→ τ, S1 7→ (τ −◦ τ ), S3 7→ (τ −◦ (τ −◦ (τ −◦ τ )))} i L = h {SS 7→ τ, SA 7→ (τ −◦ τ )}, {ci 7→ λf. f (S1 c), ca 7→ λf. λx. S3 a (f (S3 b x d)) e, I 7→ λx. x} i The other kinds of adjunction constraints may be expressed in a similar way.

References Abrusci, M., C. Fouquer´e and J. Vauzeilles. 1999. Tree-adjoining grammars in a fragment of the Lambek calculus. Computational Linguistics, 25(2):209–236. Barendregt, H.P. 1984. The lambda calculus, its syntax and semantics. revised edition. North-Holland. Carpenter, B. 1996. Type-Logical Semantics. Cambridge, Massachussetts and London England: MIT Press. de Groote, Ph. 2001. Towards Abstract Categorial Grammars. In Association for Computational Linguistics, 39th Annual Meeting and 10th Conference of the European Chapter, Proceedings of the Conference, pages 148–155. Girard, J.-Y. 1987. Linear Logic. Theoretical Computer Science, 50:1–102. Joshi, A. K. and S. Kulick. 1997. Partial Proof Trees as Building Blocks for a Categorial Grammar. Linguistic & Philosophy, 20:637–667. Joshi, A. K. and Y. Schabes. 1997. Tree-adjoining grammars. In G. Rozenberg and A. Salomaa, editors, Handbook of formal languages, volume 3. Springer, chapter 2. M¨onnich, U. 1997. Adjunction as substitution. In G.-J. Kruijff, G. Morrill and D. Oehrle, editors, Formal Grammar, pages 169–178. FoLLI. Moortgat, M. 1997. Categorial Type Logic. In J. van Benthem and A. ter Meulen, editors, Handbook of Logic and Language. Elsevier, chapter 2. Morrill, G. 1994. Type Logical Grammar: Categorial Logic of Signs. Dordrecht: Kluwer Academic Publishers. Oehrle, R. T. 1994. Term-labeled categorial type systems. Linguistic & Philosophy, 17:633–678. Ranta, A. 2002. Grammatical Framework, a type-theoretical grammar formalism. Working paper, submitted for publication.

1. Introduction We recently introduced abstract categorial grammars (ACGs) (de Groote, 2001) as a new categorial formalism based on Girard linear logic (Girard, 1987). This formalism, which derives from current type-logical grammars (Carpenter, 1996; Moortgat, 1997; Morrill, 1994; Oehrle, 1994), offers some novel features: • Any ACG generates two languages, an abstract language and an object language. The abstract language may be thought as a set of abstract grammatical structures, and of the object language as the set of concrete forms generated from these abstract structures. Consequently, one has a direct control on the parse structures of the grammar. • The langages generated by the ACGs are sets of linear λ-terms. This may be seen as a generalization of both string-langages and tree-langages. • ACGs are based on a small set of mathematical primitives that combine via simple composition rules. Consequently, the ACG framework is rather flexible. Abstract categorial grammars are not intended as yet another grammatical formalism that would compete with other established formalisms. It should rather be seen as the kernel of a grammatical framework — in the spirit of (Ranta, 2002) — in which other existing grammatical models may be encoded. This paper illustrates this fact by showing how tree-adjoining grammars (Joshi and Schabes, 1997) may be embedded in abstract categorial grammars. This embedding exemplifies several features of the ACG framework: • The fact that the basic objects manipulated by an ACG are λ-terms allows higher-order operations to be defined. Typically, tree-adjunction is such a higher-order operation (Abrusci, Fouquer´e and Vauzeilles, 1999; Joshi and Kulick, 1997; M¨onnich, 1997). • The flexibility of the framework allows the embedding to be defined in two stages. A first ACG allows the tree langage of a given TAG to be generated. The abstract language of this first ACG corresponds to the derivation trees of the TAG. Then, a second ACG allows the corresponding string language to be extracted. The abstract language of this second ACG corresponds to the object language of the first one. 2. Abstract Categorial Grammars This section defines our notion of an abstract categorial grammar. We first introduce the notions of linear implicative types, higher-order linear signature, linear λ-terms built upon a higher-order linear signature, and lexicon. Let A be a set of atomic types. The set T (A) of linear implicative types built upon A is inductively defined as follows: 1. if a ∈ A, then a ∈ T (A); 2. if α, β ∈ T (A), then (α −◦ β) ∈ T (A). A higher-order linear signature consists of a triple Σ = hA, C, τ i, where: 1. A is a finite set of atomic types; c 2002 Philippe de Groote. Proceedings of the Sixth International Workshop on Tree Adjoining Grammar and Related Frame works (TAG+6), pp. 101–106. Universit´a di Venezia.

102

Proceedings of TAG+6

2. C is a finite set of constants; 3. τ : C → T (A) is a function that assigns to each constant in C a linear implicative type in T (A). Let X be a infinite countable set of λ-variables. The set Λ(Σ) of linear λ-terms built upon a higher-order linear signature Σ = hA, C, τ i is inductively defined as follows: 1. if c ∈ C, then c ∈ Λ(Σ); 2. if x ∈ X, then x ∈ Λ(Σ); 3. if x ∈ X, t ∈ Λ(Σ), and x occurs free in t exactly once, then (λx. t) ∈ Λ(Σ); 4. if t, u ∈ Λ(Σ), and the sets of free variables of t and u are disjoint, then (t u) ∈ Λ(Σ). Λ(Σ) is provided with the usual notion of capture avoiding substitution, α-conversion, and β-reduction (Barendregt, 1984). Given a higher-order linear signature Σ = hA, C, τ i, each linear λ-term in Λ(Σ) may be assigned a linear implicative type in T (A). This type assignment obeys an inference system whose judgements are sequents of the following form: Γ −Σ t : α where: 1. Γ is a finite set of λ-variable typing declarations of the form ‘x : β’ (with x ∈ X and β ∈ T (A)), such that any λ-variable is declared at most once; 2. t ∈ Λ(Σ); 3. α ∈ T (A). The axioms and inference rules are the following: −Σ c : τ (c) (cons) x : α −Σ x : α

(var)

Γ, x : α −Σ t : β Γ −Σ (λx. t) : (α −◦ β) Γ −Σ t : (α −◦ β)

(abs)

∆ −Σ u : α

Γ, ∆ −Σ (t u) : β

(app)

Given two higher-order linear signatures Σ1 = hA1 , C1 , τ1 i and Σ2 = hA2 , C2 , τ2 i, a lexicon L : Σ1 → Σ2 is a realization of Σ1 into Σ2 , i.e., an interpretation of the atomic types of Σ1 as types built upon A2 together with an interpretation of the constants of Σ1 as linear λ-terms built upon Σ2 . These two interpretations must be such that their homomorphic extensions commute with the typing relations. More formally, a lexicon L from Σ1 to Σ2 is defined to be a pair L = hF, Gi such that: 1. F : A1 → T (A2 ) is a function that interprets the atomic types of Σ1 as linear implicative types built upon A2 ; 2. G : C1 → Λ(Σ2 ) is a function that interprets the constants of Σ1 as linear λ-terms built upon Σ2 ; 3. the interpretation functions are compatible with the typing relation, i.e., for any c ∈ C1 , the following typing judgement is derivable: −Σ2 G(c) : Fˆ (τ1 (c)), where Fˆ is the unique homomorphic extension of F . We are now in a position of defining the notion of abstract categorial grammar. An abstract categorial grammar is a quadruple G = hΣ1 , Σ2 , L , si where:

Ph. de Groote

103

1. Σ1 and Σ2 are two higher-order linear signatures; they are called the abstract vovabulary and the object vovabulary, respectively ; 2. L : Σ1 → Σ2 is a lexicon from the abstract vovabulary to the object vovabulary; 3. s is an atomic type of the abstract vocabulary; it is called the distinguished type of the grammar. The abstract language generated by G (A(G )) is defined as follows: A(G ) = {t ∈ Λ(Σ1 ) | −Σ1 t : s is derivable} In words, the abstract language generated by G is the set of closed linear λ-terms, built upon the abstract vocabulary Σ1 , whose type is the distinguished type s. On the other hand, the object language generated by G (O(G )) is defined to be the image of the abstract language by the term homomorphism induced by the lexicon L : O(G ) = {t ∈ Λ(Σ2 ) | ∃u ∈ A(G ). t = L (u)} 3. Representing Tree-Adjoining Grammars In this section, we explain how to construct an abstract categorial grammar that generates the same tree langage as a given tree-adjoining grammar. Let G = hΣ, N, I, A, Si be a tree-adjoining grammar, where Σ, N , I, A, and S are the set of terminal symbols, the set of non-terminal symbols, the set of initial trees, the set of auxiliary tree, and the distinguished non-terminal G G G symbol, respectively. We associate to G an ACG G G = hΣG 1 , Σ2 , L , s i as follows. G The set of atomic types of Σ1 is made of two copies of the set of non-terminal symbols. Given α ∈ N , we write αS and αA for the two corresponding atomic types. Then, we associate a constant cT : γ1 A −◦ · · · γm A −◦ β1 S −◦ · · · βn S −◦ αS to each initial tree T whose root node is labelled by α, whose substitution nodes are labeled by β1 , . . . , βn , and whose interior nodes are labeled by γ1 , . . . , γm . Similarly, we associate a constant cT 0 : γ1 A −◦ · · · γm A −◦ β1 S −◦ · · · βn S −◦ αA −◦ αA to each auxiliary tree T 0 whose root node is labelled by α, whose substitution nodes are labeled by β1 , . . . , βn , and whose interior nodes are labeled by γ1 , . . . , γm . Finally, we also associate to each non-terminal symnbol α ∈ N , a constant Iα of type αA . This concludes the specification of the abstract vocabulary. The object vocabulary ΣG 2 allows labelled trees to be represented. Its set of atomic types contains only one element : τ (for tree). Then, its set of constants consists in: 1. constants of type τ corresponding to the terminal symbols of G; 2. for each non-terminal symbol α, constants αi : τ −◦ · · · τ −◦ τ | {z } i times

for 1 ≤ i ≤ k, where k is the maximal branching of the interior nodes labelled with α that occur in the initial and auxiliary trees of G. Clearly, the terms of type τ that can be built by means of the above set of constants correspond to trees whose frontier nodes are terminal symbols and whose interior nodes are labelled with non-terminal symbols. It remains to define the lexicon L G . The rough idea is to represent the initial trees as trees (i.e., terms of type τ ) and the auxiliary trees as functions over trees (i.e., terms of type τ −◦ τ ). Consequently, for each α ∈ N , we let L G (αS ) = τ and L G (αA ) = τ −◦ τ . Accordingly, the susbstitution nodes will be represented as first-order λvariables of type τ , and the adjunction nodes as second-order λ-variables of type τ −◦ τ . The object representation of the elementary trees is then straightforward. Consider, for instance, the following initial tree and auxiliary tree:

104

Proceedings of TAG+6

y S DDD yy DD y D yy NP↓ VP @ @@ {{ { @@ { {{ NP↓ V

VP B BB }} BB } }} V VP∗ has

loved According to our construction, the two abstract constants corresponding to these trees have the following types: Cloved : SA −◦ VPA −◦ VA −◦ NPS −◦ NPS −◦ SS

and

Chas : VPA −◦ VA −◦ VPA −◦ VPA

Then, the realization of these two constants is as follows: L G (Cloved ) = λF. λG. λH. λx. λy. F (S2 x (G (VP2 (H (V1 loved)) y))) L G (Chas ) = λF. λG. λH. λx. F (VP2 (G (V1 has)) (H x)) In order to derive actual trees, the second-order variables should eventually disappear. The abstract constants Iα have been introduced to this end. Consequently they are realized by the identity function, i.e., L G (Iα ) = λx. x. Finally, the distinguished type of G G is defined to be SS . This completes the definition of the ACG G G associated to a TAG G. Then, the following proposition may be easily established. P ROPOSITION Let G be a TAG. The tree-language generated by G is isomorphic to the object language of the ACG G G associated to G. t u 4. Example Consider the TAG with the following initial tree and auxiliary tree:

S c

SA }} AAA } A }} a e SA }} AAA } A }} S∗ b d

It generates a non context-free language whose intersection with the regular language a∗ b∗ c d∗ e∗ is an bn c dn en . According to the construction of Section 3, this TAG may be represented by the ACG, G = hΣ1 , Σ2 , L , Si, where: Σ1 = h {SS , SA }, {ci , ca , I}, {ci 7→ (SA −◦ SS ), ca 7→ (SA −◦ (SA −◦ (SA −◦ SA ))), I 7→ SA } i Σ2 = h {τ }, {a, b, c, d, e, S1 , S3 }, {a, b, c, d, e 7→ τ, S1 7→ (τ −◦ τ ), S3 7→ (τ −◦ (τ −◦ (τ −◦ τ )))} i L = h {SS 7→ τ, SA 7→ (τ −◦ τ )}, {ci 7→ λf. f (S1 c), ca 7→ λf. λg. λh. λx. f (S3 a (g (S3 b (h x) d)) e), I 7→ λx. x} i

Ph. de Groote

105

5. Extracting the string languages There is a canonical way of representing strings as linear λ-terms. It consists of encoding a string of symbols as a composition of functions. Consider an arbitrary atomic type σ, and define the type ‘string’ to be (σ −◦ σ). Then, a string such as ‘abbac’ may be represented by the linear λ-term: λx. a (b (b (a (c x)))), where the atomic strings ‘a’, ‘b’, and ‘c’ are declared to be constants of type (σ −◦ σ). In this setting, the empty word is represented by the identity function: 4 = λx. x and concatenation is defined to be functional composition: 4

α + β = λα. λβ. λx. α (β x), which is indeed an associative operator that admits the identity function as a unit. G G This allows a second ACG, G 0 , to be defined. Its abstract vocabulary is the object vocabulary ΣG 2 of G . Its object vocabulary allows string of terminal symbols to be represented. Its lexicon interprets each constant of type G τ as an atomic string, and each constant αi as a concatenation operator. This second ACG, G 0 , extracts the yields G of the trees. Then, by composing G G with G 0 , one obtains an ACG which generates the same string-language as G. Let us continue the example of Section 4. The second ACG, G 0 = hΣ01 , Σ02 , L 0 , S 0 i, is defined as follows: Σ01 = Σ2 Σ02 = h {σ}, {a, b, c, d, e}, {a, b, c, d, e 7→ (σ −◦ σ)} i L 0 = h {τ 7→ (σ −◦ σ)}, {a 7→ λx. a x, b 7→ λx. b x, c 7→ λx. c x, d 7→ λx. d x, e 7→ λx. e x, S1 7→ λf. λx. f x, S3 7→ λf. λg. λh. f (g (h x))} i 6. Expressing Adjoining constraints Adjunction, which is enabled by second-order variables at the object level, is explicitly controlled at the abstract level by means of types. This typing discipline may be easily refined in order to express adjoining constraints such as selective, null, or obligatory adjunction. Consider again the TAG given in Section 4. By adding the following null adjunction constraints on its auxiliary tree: SNAD DD zz DD z z D zz a e SC {{ CCC { CC { {{ ∗ S b d NA one obtains a grammar that generates exactly the non context-free language an bn c dn en . These constraints may be expressed in a simple and natural way. It suffices to exclude the constrained nodes from the arguments of the λ-term corresponding to the auxiliary tree. This gives the following modified ACG: Σ1 = h {SS , SA }, {ci , ca , I}, {ci 7→ (SA −◦ SS ), ca 7→ (SA −◦ SA ), I 7→ SA } i

106

Proceedings of TAG+6

Σ2 = h {τ }, {a, b, c, d, e, S1 , S3 }, {a, b, c, d, e 7→ τ, S1 7→ (τ −◦ τ ), S3 7→ (τ −◦ (τ −◦ (τ −◦ τ )))} i L = h {SS 7→ τ, SA 7→ (τ −◦ τ )}, {ci 7→ λf. f (S1 c), ca 7→ λf. λx. S3 a (f (S3 b x d)) e, I 7→ λx. x} i The other kinds of adjunction constraints may be expressed in a similar way.

References Abrusci, M., C. Fouquer´e and J. Vauzeilles. 1999. Tree-adjoining grammars in a fragment of the Lambek calculus. Computational Linguistics, 25(2):209–236. Barendregt, H.P. 1984. The lambda calculus, its syntax and semantics. revised edition. North-Holland. Carpenter, B. 1996. Type-Logical Semantics. Cambridge, Massachussetts and London England: MIT Press. de Groote, Ph. 2001. Towards Abstract Categorial Grammars. In Association for Computational Linguistics, 39th Annual Meeting and 10th Conference of the European Chapter, Proceedings of the Conference, pages 148–155. Girard, J.-Y. 1987. Linear Logic. Theoretical Computer Science, 50:1–102. Joshi, A. K. and S. Kulick. 1997. Partial Proof Trees as Building Blocks for a Categorial Grammar. Linguistic & Philosophy, 20:637–667. Joshi, A. K. and Y. Schabes. 1997. Tree-adjoining grammars. In G. Rozenberg and A. Salomaa, editors, Handbook of formal languages, volume 3. Springer, chapter 2. M¨onnich, U. 1997. Adjunction as substitution. In G.-J. Kruijff, G. Morrill and D. Oehrle, editors, Formal Grammar, pages 169–178. FoLLI. Moortgat, M. 1997. Categorial Type Logic. In J. van Benthem and A. ter Meulen, editors, Handbook of Logic and Language. Elsevier, chapter 2. Morrill, G. 1994. Type Logical Grammar: Categorial Logic of Signs. Dordrecht: Kluwer Academic Publishers. Oehrle, R. T. 1994. Term-labeled categorial type systems. Linguistic & Philosophy, 17:633–678. Ranta, A. 2002. Grammatical Framework, a type-theoretical grammar formalism. Working paper, submitted for publication.