Characterizing Structural Descriptions Produced by Various Grammatical Formalisms

CHARACTERIZING STRUCTURAL DESCRIPTIONS PRODUCED BY VARIOUS. GRAMMATICAL FORMALISMS* K. Vijay-Shanker David J. Weir Aravind K. Joshi Deparunent of Computer and Information Science University of Pennsylvania Philadelphia, Pa 19104 ABSTRACT We consider the structural descriptions produced by vari- ous grammatical formalisms in ~ of the complexity of the paths and the relationship between paths in the sets of structural descriptions that each system can generate. In considering the relationship between formalisms, we show that it is useful to abstract away from the details of the formalism, and examine the nature of their derivation process as reflected by properties of their deriva:ion trees. We find that several of the formalisms considered can be seen as being closely related since they have derivation tree sets with the same structure as those produced by Context-Free C-ramma~. On the basis of this observation, we describe a class of formalisms which we call Linear Context- Free Rewriting Systems, and show they are recognizable in poly- nomial time and generate only semilinear languages. 1 Introduction Much of the study of grammatical systems in computational linguistics has been focused on the weak generative capacity of grammatical forma~sm- Little attention, however, has been paid to the structural descriptions that these formalisms can assign to strings, i.e. their strong generative capacity. This aspect of the formalism is beth linguistically and computationally important. For example, Gazdar (1985) discusses the applicability of In- dexed Grammars (IG's) to Natural Language in terms of the structural descriptions assigned; and Berwick (1984) discusses the strong generative capacity of Lexical-Functional Grammar CLFG) and Government and Bindings grammars (GB). The work of Thatcher (1973) and Rounds (1969) define formal systems that generate tree sets that are related to CFG's and IG's. We consider properties of the tree sets generated by CFG's, Tree Adjoining Grammars (TAG's), Head GrammarS (HG's), Categorial Grammars (CG's), and IG's. We examine both the complexity of the paths of trees in the tree sets, and the kinds of dependencies that the formalisms can impose between paths. These two properties of the tree sets are not only linguistically relevant, but also have computational importance. By consider- ing derivation trees, and thus abstracting away from the details of the composition operation and the structures being manipuht_ed, we are able to state the similarities and differences between the "This work was partially supported by NSF grants MCS-82-19116-CER, MC$- $2-07294 and DCR-84-10413, ARO grant DAA 29-84-9-0027, and DARPA grant N00014-85-K001& We are very gateful to Tony Kroch, Michael Palis, Sunii Shende, and Mark $teedman for valuable discussions. formalisms. It is striking that from this point of view many for- malisms can be grouped together as having identically s~'uctm'ed derivation tree sets. This suggests that by generalizing the notion of context-freeness in CFG's, we can define a class of grarnmati- ca] formalisms that manipulate more complex structures. In this paper, we outline how such family of formalisms can be defined, and show that like CFG's, each member possesses a number of desirable linguistic and computational properties: in particular, the …

Content truncated to 500 words