Paper: Characterizing Structural Descriptions Produced By Various Grammatical Formalisms

ACL ID P87-1015
Title Characterizing Structural Descriptions Produced By Various Grammatical Formalisms
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1987
Authors

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 recogni...