Relationship between strong and weak generative power of formal systems

The relationship between strong and weak generative powers of formal systems is explored, in particular, from the point of view of squeezing more strong power out of a formal system without increasing its weak generative power. We examine a whole range of old and new results from this perspective. However, the main goal of this paper is to investigate the strong generative power of Lambek categorial grammars in the context of crossing dependencies, in view of the recent work of Tiede (1998). Introduction Strong generative power (SGP) relates to the set of structural descripti ons (such as derivation trees, dags, proof trees, etc.) assigned by a formal system to the strings that it specifies. Weak generative power (WGP) refers to the set of strings characterized by the formal system. SGP is clearly the primary object of interest from the linguistic point of view. WGP is often used to locate a formal system within one or another hierarchy of formal grammars 1. Clearly a study of the relationship between WGP and SGP is highly relevant, both formally and l inguistically. Although there has been interest in the study of this relationship, almost from the be ginning of the work in mathematical linguistics, the results are few, as this rela tionship is quite complex and not always easy to study mathematically (see Miller (1969) for a recent c omprehensive discussion of SGP). Our main goals in this paper are (1) to look at some old and recent results and try to put them in a general framework, a framework that can best be described by the slogan–How to squeeze more strong generative power out of a grammatical system?– and (2) to present a n w result concerning Lambek categorial grammars. Our general discussion of the relations hip f SGP and WGP will be in the context of context-free grammars, categorial grammars and lexicalized tree-adjoining grammars. 1. Context-Free Grammar (CFG) McCawley(1967) was the first person to point out that the use of context-sensitive rule s by linguists was really for checking structural descriptions (thus related to S GP) and not for generating strings (i.e., WGP), suggesting that this use of context-sensitive rule s possibly does not This work was partially supported by NSF Grant SBR8920230 1SGP is also relevant in the context of annotated corpora. The annotations reflect aspects of SGP and not of the rules of a grammar and therefore WGP. give more SGP than CFG’s. Peters and Ritchie (1969) showed that this was indee d the case. These results are closely related to the notion of recognizable sets of tree s (structural descriptions) as explained below. In a CFG,G, the derivation trees of G correspond to the possible structural descriptions assignable byG. It is easily shown that there are tree sets whose yield language is contextfre but the tree sets are not the tree sets of any CFG. That is, we are able to squeeze more s trong power out of CFG’s indirectly. Here is a simple example.


Introduction
Strang generative power (SGP) relates to the set of structural descriptions (such as derivation trees, dags, proof trees, etc.) assigned by a formal system to the strings that it specifies. Weak generative power (WGP) refers to the set of strings characterized by the formal system. SGP is clearly the primary object of interest from the linguistic point of view. WGP is often used to locate a formal system within one or another hierarchy of formal grammars 1 • Clearly a study of the relationship between WGP and SGP is highly relevant, both formally and linguistically. Although there has been interest in the study of this relationship, almost from the beginning of the work in mathematical linguistics, the results are few, as this relationship is quite complex and not always easy to study mathematically (see Miller (1969) for a recent comprehensive discussion of SGP). Our main goals in this paper are (1) to Jook at some old and recent rcsult~ :md try to put them in a general framework, a framework that can best be described by the slogan-How to squeeze more strong generative power out of a grammatical system?-and (2) to present a new result concerning .Lambek categorial grammars. Our general discussion of the relationship of SGP and WGP will be in the context of context-free grammars, categorial grammars and Iexicalized tree-adjoining grammars.

Context~Free Grammar (CFG)
McCawley(l 967) was the first person to point out that the use of context-sensitive rules by linguists was really for checking structural descriptions (thus related to SGP) and not for generating strings (i.e" WGP), suggesting that this use of context-sensitive rules possibly does not 7his work was partially supported by NSF Grant SBR8920230 1 SGP is also relevant in the context of annotated co.rpora. Tue annotations reßect aspects of SGP and not of the rules of a grammar and therefore WGP.
.. nCFd's. Peters and Ritchie (1969) showed that this was indeed the case. i~'ffäfüy related to the notion of recognizable sets of trees (structural descrip-aih~d below .
. ~q.G, the derivation trees of G correspond to the possible structural descriptions assignable yc. Jlis easily shown that there are tree sets whose yield language is context-free but the tree · are not ehe tree sets of any CFG. That is, we are able to squeeze more strong power out of CFG's indirectly. Here is a simple example.
Let T be the set of trees defined by trees such as is not a set of derivation trees for any CFG. Clearly in any CFG G, the rules for A will get mixed up and there will be no way we can make sure that all a's are on the left and all b's are on the right. The srring Janguage is, of course, { anbm Im, n > 1 }, which is a context-free Janguage. What is the relationship between the trees ofthe CFG corresponding to this Janguage and the set T? Thatcher (1967) showed that the relationship is very close. Sets such as T, called recognizable sets, are the same as the tree sets of CFG's (called local sets) except possibly for relabeling. lt turns out that the tree sets 'analyzable' (i.e., checkable) by context-sensitive rules, as suggested by McCawley are indeed recognizable sets. All these systems have the property that they allow checking of 'Jocal' constraints around a node in a tree. Thatcher's result shows that this notion of 'locality' can be captured by finite state tree automata. Later Joshi, Levy, and Yueh (I 975) and Rogers (1997) showed that the notion of 'local context (local tree domains)' can be made substanti ally richer yet maintaining characterizability by finite state tree automata. All these results can be interpreted as attempts to squeeze more strong power out of a formal system, in this case, context-free grammars.

Lexicalized Tree-Adjoining Grammars (LTAG)
The earliest indication that more strong power can be obtained from LTAG by going to tree-local multicomponent TAG (still preserving the weak power of LTAG) is in Weir (1987) and Kroch and Joshi (1989). Shieber and Schabes (1992) introduced the notion of multiple adjoining at the same node in a derivation tree. This move can also be seen as an attempt to get more strong power out of LTAG without going beyond the weak power of LTAG. In fact, the whole range of recent works (Candito (1997), Joshi and Vijay-Shanker (1998), Kulick (2000), Kallmeyer and Joshi ( 1999) can be seen as attempts to get more SGP from LTAG without going beyond the WGP of LTAG. This is achieved by providing ftexibility in interpreting the derivation trees in LTAG. In particular, in Joshi and Vijay-Shanker (1998), Kulick (2000) 2 , and Kallmeyer and Joshi (1999), all of which use tree-local multi-component LTAG, flexibility is introduced in the derivation in LTAG resulting in increased streng power without exceeding the weak power of LTAG. This notion of flexibility (flexibility in composition, i.e" in the directionality of the composition) can be briefty defined as follows, at least for the approaches in Joshi and Vijay-Shanker (1998) and Kallmeyer and Joshi (1999). Given a pair of trees, say, 1(1) and 1(2) the composition (i.e., attachments by substitution and adjoining 3 ) can proceed from 1(1) to '1'(2), i.e" 1(1) composes with 7(2) if /'(2) is an elementary tree, otherwise '1'(2) composes with 1(1) if 1(1) is an elementary tree, assuming, of course, that 1(1) and 1(2) are semantically related, i.e" composition of arbitrary unrelated trees is not allowed. Such a notion of flexibility can be introduced in CFG's as weil as in Categorial Grammars. However, as far as I know, such a move does not open the door for squeezing more SGP out of the formal system. This is due to the fact that CFG's and Categorial Grammars are essentially stri ng rewriting systems, while systems such as LTAG are tree rewriting systems and the complex topology of the initial trees, when combined with the flexibility discussed above, allows the possibility of augmenting the SGP of the system.

Categorial Gr!:lmmars (CG)
lt is weil known that the Ajdukiewicz and Bar-Hillel categorial grammars (CG(AB)) are weakly equivalent to CFG's. The derivation trees of CG(AB) are essentially the same as the derivation trees of CFG's (i.e., local sets and therefore recognizable sets (see Tiede (1998)). The relationship of recognizable tree sets to the derivation trees of CG(AB) is not discussed by Tiede. The relationship is the same as between the derivation trees of CFG's and recognizable sets, i.e" they are the same except for relabeling 4 • However, for Lambek Grammars (LG) the situation can be different. In LG, the assignment of categories to lexical items is similar to the assignments in CG(AB) but we have the inference rules associated with the calculus. Although LG's (Lambek, 1958) were long conjectured to be weakly equivalent to CFG's, the conjecture was only recently proved tobe true by Pentus (1993). So now the question arises: Do LG's provide more streng generative power than CFG's, in other words, is it possible to characterize the proof trees ofLG in terms of something Jike the recognizable sets or even beyond recognizable sets. This question was raised by Buszkowski and van Benthem 5 • However, only recently a serious attempt has been made by Tiede (1998) to try to answer this question. Tiede (1998) covers a number of aspects and, in particular, · suggests that the proof trees of LG may be beyond recognizable sets, i.e., there is a Lambek grammar whose proof tree Janguage is not regular. In fact, he suggests that it will be possible to characterize crossing dependencies. Our main point in this paper is to show that this claim is very limited and that the crossing dependencies that can be described are very degenerate (i.e" the dependencies are between a lexical item and a lexically empty element). First, note that if indeed true (i.e" nondegenerate) crossing dependencies can be characterized by the proof trees of LG then this would be very surprising indeed. From all that we know 2 Thc exacl equivalence of the system in Kulick (2000) to tree-local TAG's has not been eslablished yet. ~Adjoining al the root and substitution at the foot can be 1rea1ed as attachmcnls ofthe same kind.

4
Another recent work concerning SGP and WGP of calegorial grammars is by Jäger (1998) who has investigatcd lhe generative capacity of multimodal catcgorial grammars. so far, any fonnal characterizes crossing dependencies (say, between the a's and b's in anbn) is more powerful than CFG's, for example, TAG's, Combinatory Categoriai grammars (CCG); Linear Indexed Grammars (LIG), etc. because they can all generate the Ianguage {anbncnln ~· l}. Figure 2 shows the topologies needed to obtain the nondegenerate crossing dependencies6. Now once we have trees with this topology it is easy to see that the same topology can be used to generate the Janguage { anbncnln ~ 1 }. The relevant tree will be the same as the tree on the left in Figure 2 with c replacing t. Given that LG characterize only context-free languages, this would Jead to a paradox.
Tree topologies needed for nondegenerate crossing dependencies 'the assumptions are withdrawn in the deduction as is required in the natural deduction proof. The assumptions that are introduced and then withdrawn have to appear always at the periphery of the proof tree. In our example in Figure 3 they appear at the right periphery. The dependencies between the a's and t's (corresponding to the assumptions) can be seen as follows. In the second [/E) step in the deduction (second from the top) the category NA is eliminated in combination with S/(AIA) corresponding to a(2). The category AfA in this step resulted from the withdrawal of the assumption [A] (corresponding to t(2)) at the top level. Thus a(2) corresponds to t(2). Similarly a(l) corresponds to t(l). lt is easy to see that a natural deduction proof can be constructed for each string in L. Thus we have crossing dependencies between the a's and t's. For 'true' crossing dependencies both the elements have to be non-empty. The way this is accomplished is by creating two sets of nested dependencies, say between a's and t's and between t's and b's, where the t's are empty elements. Then the resulting dependencies between the a's and b's become crossed as shown in Figure 2 above. The dependencies between a's and t's are nested and those between t's and b's are also nested, resulting in crossing dependencies between a's and b's. Note that the empty elements, t 's, are not at the periphery. lt is not possible to achieve this in LG because the empty elements have tobe at the periphery in the Lambek deduction. So in a real sense the crossing dependencies which Tiede talks about are degenerate and LG is incapable of capturing true crossing dependencies. Since the Tree-Insertion Grammars (TIG) of Schabes and Waters ( 1993) are weakly equivalent to CFG's but not strongly, we will explore the implications of TIG for Tiede's work. In fact, we will show that the degenerate case studied by Tiede can be characterized in a TIG. In a TIG, both substitution and adjoining are used. However, adjoining is limited in the following way. First, in each auxiliary tree the footnode is the leftmost (or rightmost) daughter of the ;·vv:. Further, adjoining is only allowed an the right (or left) frontier. Schabes and Waters ( 1993) have shown that TIG's are weakly equivalent to CFG's, They do not explore the issue of strong power. Their motivation was to show that TIG's lexicalize CFG's without going beyond the weak power of CFG. We show that strong power is increased, although only to the extent of covering the ·case of degenerate crossing d~pendencies considerea by Tiede. This suggests the tamalizing conjecture that TIG's are adequate to characte1~.<:.c th"' prod w.es of LG. We have no complete proof of this conjecture at this time. The proof of the claim that TIG can characterize the degenerate case of crossing dependencies follows from the fact that these dependencies can be implemented by using the TIG in Figure  4 . In the tree b 1 the footnode is not the rightmost non terminal an the frontier, however, the frontier to the right of this footnode is lexically empty 7 . Surprisingly, this possibility is a!Jowed in the definition of TIG as it is crucially needed by Schabes and Waters to prove their main result-TIG's are equivalent to CFG's. Now it is easily seen how the degenerate crossing dependencies of Tiede can be described in this TIG (see Figure 5; b 1 is adjoined to al at the indicated node in al ).  out of a formal system without increasing its weak generative power. We have also presented some new results conceming the SGP of Lambek categorial grammars as they relate to crossing deperidencies.