Elamur Research⌕
☰
home / papers / 1992 / Using Descriptions of Trees in a Tree Adjoining Grammar

Using Descriptions of Trees in a Tree Adjoining Grammar

Paper · 1992 · K Vijay-Shanker

Summary

In the traditional view, a Tree Adjoining Grammar (TAG) builds structures by combining elementary trees through adjoining and substitution. Adjoining, however, fails to keep the structural relations stated in the input trees, so TAG does not fit cleanly into declarative, constraint-based unification frameworks such as FUG, LFG, GPSG or HPSG. Vijay-Shanker solves this by changing what a TAG is taken to operate on. Instead of trees, the grammar combines partial descriptions of trees. Following D-theory, these descriptions state immediate dominance and also allow dominance to be left partly unspecified. Their graphical form is called quasi-trees. Seen this way, combining structures only adds information. The trees the grammar actually produces are the minimal readings of the finished descriptions. The approach gives a principled basis for feature-structure-based TAG (FTAG) and refines it. It also lets adjoining constraints follow from feature statements instead of hand-listed sets. A logical formulation with its own semantics keeps grammar descriptions separate from the structures that satisfy them. The paper is purely formal and reports no corpus or experimental results.

Key points

  • Introduces quasi-trees, partial tree descriptions adapted from D-theory (Marcus, Hindle, and Fleck 1983). Under this view, adjoining keeps the dominance relations stated in the combined structures.
  • Gives a principled justification for FTAG, first defined in Vijay-Shanker (1987) and Vijay-Shanker and Joshi (1988), and refines it.
  • Handles Selective (SA), Null (NA) and Obligatory (OA) adjoining constraints through feature-structure statements rather than stipulated lists. This also removes some redundant structural specifications.
  • Provides a logical formulation of FTAG modeled on Rounds and Manaster-Ramer's (1987) treatment of Functional Unification Grammar, together with a semantics for it.
  • Raises open questions:
    • whether adjoining, and multi-component adjoining, can be reduced to substitution;
    • whether the split between initial and auxiliary structures is needed.
  • The work was supported by NSF grant IRI-9016591, and its figures were drawn with the XTAG workbench.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 works

🧭 Topics 1Research subjects and languages the work is about.Syntax & grammar formalisms · 214 works

Cite

Cite as K Vijay-Shanker. 1992. Using Descriptions of Trees in a Tree Adjoining Grammar. Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

@article{vijayshanker1992using,
  title = {{Using Descriptions of Trees in a Tree Adjoining Grammar}},
  author = {K Vijay-Shanker},
  journal = {Computational Linguistics},
  year = {1992},
  url = {https://aclanthology.org/J92-4004/}
}

References

24 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Abeille, A.; Bishop, K.; Cote, Sharon; and Schabes, Y. (1990). "A lexicalized tree adjoining grammar for English." Technical report MS-CIS-90-24, Department of Computer and Information Science, University of Pennsylvania. find
  2. Abeille, A. (1991). Une grammaire lexicalisde d'Arbres adjoints pour le Franqais: Application d~ l'analyse automatique. Doctoral dissertation, Universit6 Paris 7, Paris, France. find
  3. Gazdar, G.; Klein, E.; Pullum, S.; and Sag, I. (1985). Generalized Phrase Structure Grammar. Blackwell. find
  4. Harbusch, K. (1990). "Constraining tree adjoining grammars by unification." In Proceedings, 13th International Conference on Computational Linguistics. find
  5. Henderson, J. (1990). "Structure Unification Grammar: A Unifying Framework for Investigating Natural Language." Technical Report MS-CIS-90-94, Department of Computer and Information Science, University of Pennsylvania. find
  6. Johnson, M. (1988). Attribute Value Logic and the Theory of Grammar. University of Chicago Press. find
  7. Joshi, A. K. (1987). "An introduction to tree adjoining grammar." In Mathematics of Language, edited by A. Manaster-Ramer, 87-115. Benjamins Publishing Company. find
  8. Joshi, A. K. (1985). "How much context-sensitivity is necessary for characterizing structural descriptions — Tree Adjoining Grammars." In Natural Language Processing — Theoretical, Computational and Psychological Perspective, edited by D. Dowty, L. Karttunen, and A. Zwicky, 206-250. Cambridge Universi… find
  9. Joshi, A. K., and Vijay-Shanker, K. (1989). "Treatment of long-distance dependencies in LFG and TAG." In Proceedings, 27th Annual Meeting of the Association for Computational Linguistics, 220-227. find
  10. Joshi, A. K.; Levy, L. S.; and Takahashi, M. (1975). "Tree adjunct grammars." Journal of Computer and System Sciences, 10(1), 136-163. find
  11. Kaplan, R. M., and Maxwell, J. T. (1988). "An algorithm for functional uncertainty." In Proceedings, 12th International Conference on Computational Linguistics, 297-302. find
  12. Kasper, R., and Rounds, W. C. (1986). "A logical semantics for feature structures." In Proceedings, 24th Annual Meeting of the Association for Computational Linguistics, 257-266. find
  13. Kroch, A. S. (1989). "Asymmetries in long distance extraction in a tag grammar." In Alternative Conceptions of Phrase Structure, edited by M. Baltin and A. Kroch, 66-98. University of Chicago Press. find
  14. Kroch, A. S. (1987). "Unbounded dependencies and subjacency in a tree adjoining grammar." In Mathematics of Language, edited by A. Manaster-Ramer, 143-172. Benjamins Publishing Company. find
  15. Kroch, A., and Joshi, A. K. (1985). "Linguistic relevance of tree adjoining grammars." Technical report MS-CI-85-18, Department of Computer and Information Science, University of Pennsylvania. find
  16. Marcus, M.; Hindle, D.; and Fleck, M. M. (1983). "D-theory — talking about talking about trees." In Proceedings, 21st Annual Meeting of the Association for Computational Linguistics, 129-136. find
  17. Moshier, M. A. (1988). Extensions to unification grammar for the description of programming languages. Doctoral dissertation, University of Michigan, Ann Arbor, MI. find
  18. Rogers, J., and Vijay-Shanker, K. (1992). "Reasoning with descriptions of trees." In Proceedings, 30th Annual Meeting of the Association for Computational Linguistics, 72-80. find
  19. Rounds, W., and Manaster-Ramer, A. (1987). "A logical version of functional grammar." In Proceedings, 25th Annual Meeting of the Association for Computational Linguistics, 89-96. find
  20. Schabes, Y., and Paroubek, P. (1992). "Xtag — a graphical workbench for developing tree adjoining grammars." In Proceedings, Third Conference on Applied Natural Language Processing, 216-223. find
  21. Schabes, Y.; Abeille, A.; and Joshi, A. K. (1988). "New parsing strategies for tree adjoining grammars." In Proceedings, 12th International Conference on Computational Linguistics, 578-583. find
  22. Vijay-Shanker, K. (1987). A study of tree adjoining grammars. Doctoral dissertation, University of Pennsylvania, Philadelphia, PA. find
  23. Vijay-Shanker, K., and Joshi, A. K. (1988). "Feature structure based tree adjoining grammars." In Proceedings, 12th International Conference on Computational Linguistics, 714-719. find
  24. Vijay-Shanker, K., and Schabes, Y. (1992). "Structure sharing in a lexicalized tree adjoining grammar." In Proceedings, 14th International Conference on Computational Linguistics, 205-211. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/shanker-1992-descriptions-trees-tree-adjoining-grammar/