abstract
- In this work, two methods of how to make derivation in a Tree Adjoining Grammar (TAG) a regular process without loss of expressive power are presented and compared. In a TAG, derivation relies upon the expansion of inner nodes into trees. The first regularization method is based on an algebraic operation called Lifting which could be described as a way to make the internal structure of a term more explicit, while the second method exploits an additional dimension in space by transforming the components of a TAG into three-dimensional trees. Both methods have the effect that all inner nodes of the elementary TAG trees are turned into leaves and can consequently be more simply expanded, viz. by a regular mechanism. Regularized grammars generate two different kinds of “encoded” trees, from which, however, the intended ones can be easily reconstructed by a simple decoding function. At the end of this work the equivalence of the two presented TAG regularization methods is established by giving a formal translation between lifted and three-dimensional trees and then proving that via this translation it is possible to switch from each of the encodings into the other one without losing the information necessary for the reconstruction of the originally intended trees.