Computer Science – Computation and Language
Scientific paper
1997-07-22
Computer Science
Computation and Language
Formal Grammar Conference, Aix-en-Provence, Aug. 97, 11pp., uses AMS-LaTeX, natbib
Scientific paper
This note presents a method of interpreting the tree adjoining languages as the natural third step in a hierarchy that starts with the regular and the context-free languages. The central notion in this account is that of a higher-order substitution. Whereas in traditional presentations of rule systems for abstract language families the emphasis has been on a first-order substitution process in which auxiliary variables are replaced by elements of the carrier of the proper algebra - concatenations of terminal and auxiliary category symbols in the string case - we lift this process to the level of operations defined on the elements of the carrier of the algebra. Our own view is that this change of emphasis provides the adequate platform for a better understanding of the operation of adjunction. To put it in a nutshell: Adjoining is not a first-order, but a second-order substitution operation.
No associations
LandOfFree
Adjunction As Substitution: An Algebraic Formulation of Regular, Context-Free and Tree Adjoining Languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Adjunction As Substitution: An Algebraic Formulation of Regular, Context-Free and Tree Adjoining Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adjunction As Substitution: An Algebraic Formulation of Regular, Context-Free and Tree Adjoining Languages will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-700131