Constraints on Strong Generative Power

Constraints on strong generative power David Chiang University of Pennsylvania Dept of Computer and Information Science 200 S 33rd St Philadelphia, PA 19104 USA dchiang@cis.upenn.edu Abstract We consider the question “How much strong generative power can be squeezed out of a formal system without increasing its weak generative power?” and propose some theoret- ical and practical constraints on this problem. We then introduce a formal- ism which, under these constraints, maximally squeezes strong generative power out of context-free grammar. Finally, we generalize this result to formalisms beyond CFG. 1 Introduction “How much strong generative power can be squeezed out of a formal system without increas- ing its weak generative power?” This question, posed by Joshi (2000), is important for both lin- guistic description and natural language process- ing. The extension of tree adjoining grammar (TAG) to tree-local multicomponent TAG (Joshi, 1987), or the extension of context free gram- mar (CFG) to tree insertion grammar (Schabes and Waters, 1993) or regular form TAG (Rogers, 1994) can be seen as steps toward answering this question. But this question is difficult to answer with much finality unless we pin its terms down more precisely. First, what is meant by strong generative power? In the standard definition (Chomsky, 1965) a grammar G weakly generates a set of sentences L(G) and strongly generates a set of structural descriptions Σ(G); the strong genera- tive capacity of a formalism F is then {Σ(G) | F provides G}. There is some vagueness in the literature, however, over what structural descrip- tions are and how they can reasonably be com- pared across theories (Miller (1999) gives a good synopsis). (a) X ϵ X X∗ a X X∗ b (b) XNA a X b X∗ a b Figure 1: Example of weakly context-free TAG. The approach that Vijay-Shanker et al. (1987) and Weir (1988) take, elaborated on by Becker et al. (1992), is to identify a very general class of formalisms, which they call linear context- free rewriting systems (CFRSs), and define for this class a large space of structural descriptions which serves as a common ground in which the strong generative capacities of these formalisms can be compared. Similarly, if we want to talk about squeezing strong generative power out of a formal system, we need to do so in the context of some larger space of structural descriptions. Second, why is preservation of weak generative power important? If we interpret this constraint to the letter, it is almost vacuous. For example, the class of all tree adjoining grammars which gen- erate context-free languages includes the gram- mar shown in Figure 1a (which generates the lan- guage {a, b}∗). We can also add the tree shown in Figure 1b without increasing the grammar’s weak generative capacity; indeed, we can add any trees we please, provided they yield only as and bs. In- tuitively, the constraint of weak context-freeness has little force. This intuition is verified if we consider that weak context-freeness is desirable for computa- tional efficiency. Though a …

Content truncated to 500 words