Elamur Research⌕
☰
home / papers / 1994 / An Alternative Conception of Tree-Adjoining Derivation

An Alternative Conception of Tree-Adjoining Derivation

Paper · 1994 · Yves Schabes and Stuart M. Shieber

Summary

The authors (Schabes and Shieber, Computational Linguistics, 1994) revisit what a derivation should be in tree-adjoining grammars (TAG). The standard definition, due to Vijay-Shanker (1987), forbids more than one adjunction at the same node of an elementary tree. As a result, stacked modifiers get attached to each other instead of to the phrase they modify. This distorts the dependencies that selective adjoining constraints, stochastic TAG and synchronous TAG semantics depend on. The paper motivates the problem with examples such as directional and temporal adverbials that must agree with the verb even when other adjuncts intervene.

The proposed "extended derivation" lets several modifier auxiliary trees adjoin at one node, while predicative auxiliary trees remain limited to one per node. Formally, derivations are treated as equivalence classes of ordered derivation trees. Operationally, TAGs are compiled into linear indexed grammars (LIG) and parsed with an Earley-style algorithm. The result is a definition that is both precise and usable in practice, and it reflects linguistic modification more faithfully.

Key points

  • Problem with the standard definition: Vijay-Shanker's normal form maps each derivation tree to a single derived tree. However, it rules out "independent" derivations, in which multiple auxiliary trees attach at the same address.
  • Three motivating extensions:
    • Selective-adjoining constraints, shown with an example sentence about Brockway taking his Labrador for a walk, where the temporal adverb "yesterday" comes between the verb phrase and a directional phrase heading toward a yacht club.
    • Stochastic TAG probabilities.
    • Synchronous TAG semantics.
  • Formalization: Ordered derivation trees are grouped into equivalence classes. An appendix proves that swapping adjacent siblings with different tree addresses leaves the derived tree unchanged.
  • Compilation: The paper builds on the Vijay-Shanker–Weir TAG-to-LIG compilation, adapting it so that the LIG makes extended derivations explicit.
  • Parsing: An Earley-based recognizer/parser over the compiled LIG recovers extended derivations from its items. A further modification builds the derivation tree incrementally during parsing, which the authors present as a novel contribution useful for incremental processing.

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

 Institutions

🎓Harvard UniversityCambridge · United States73 works · 37,309 citations

Also on the byline: Mitsubishi Electric (United States) · Mitsubishi Electric Research Laboratories.

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 worksComputational Theory and Mathematics · 116 works

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

Cite

Cite as Yves Schabes and Stuart M. Shieber. 1994. An Alternative Conception of Tree-Adjoining Derivation. Computational Linguistics.

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

@article{schabes1994alternative,
  title = {{An Alternative Conception of Tree-Adjoining Derivation}},
  author = {Yves Schabes and Stuart M. Shieber},
  journal = {Computational Linguistics},
  year = {1994},
  url = {https://aclanthology.org/J94-1004/}
}

References

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

  1. Abeill6, Anne; Schabes, Yves; and Joshi, Aravind K. (1990). "Using lexicalized tree adjoining grammars for machine translation." In Proceedings, 13th International Conference on Computational Linguistics, Volume 3, 1-6, Helsinki, Finland. find
  2. Gazdar, Gerald; Klein, Ewan; Pullum, Geoffrey K.; and Sag, Ivan A. (1985). Generalized Phrase Structure Grammar. Blackwell. find
  3. Joshi, A. K.; Kosaraju, S. R.; and Yamada, H.M. (1972a). "String adjunct grammars: I. Local and distributed adjunction." Information and Control, 21(2), 93-116. find
  4. Joshi, A. K.; Kosaraju, S. R.; and Yamada, H. M. (1972b). "String adjunct grammars: II. Equational representation, null symbols, and linguistic relevance." Information and Control, 21 (3), 235-260. find
  5. Joshi, Aravind K.; Levy, L. S.; and Takahashi, M. (1975). "Tree adjunct grammars." Journal of Computer and System Sciences, 10(1), 136-163. find
  6. Kroch, Anthony 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
  7. Kroch, Anthony S., and Joshi, Aravind K. (1985). "The linguistic relevance of tree adjoining grammar." Technical Report MS-CIS-85-18, Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA. find
  8. Pereira, Fernando C. N., and Warren, David H. D. (1983). "Parsing as deduction." In Proceedings, 21st Annual Meeting of the Association for Computational Linguistics, 137-144. Cambridge, MA. find
  9. Quirk, Randolph; Greenbaum, Sidney; Leech, Geoffrey; and Svartvik, Jan (1985). A Comprehensive Grammar of the English Language. Longman. find
  10. Resnik, Philip (1992). "Probabilistic tree-adjoining grammar as a framework for statistical natural language processing." In Proceedings, 14th International Conference on Computational Linguistics, 418-424. Nantes, France. find
  11. Schabes, Yves (1991). "The valid prefix property and left to right parsing of tree-adjoining grammar." In Proceedings, Second International Workshop on Parsing Technologies, 21-30. Cancun, Mexico. find
  12. Schabes, Yves (1992). "Stochastic lexicalized tree-adjoining grammars." In Proceedings, 14th International Conference on Computational Linguistics, 426-432. Nantes, France. find
  13. Schabes, Yves, and Shieber, Stuart M. (1992). "An alternative conception of tree-adjoining derivation." Technical Report 08-92, Harvard University, Cambridge, MA. find
  14. Schabes, Yves, and Waters, Richard C. (1993a). "Lexicalized context-free grammars." In Proceedings, 31st Annual Meeting of the Association for Computational Linguistics, 121-129. Columbus, OH. find
  15. Schabes, Yves, and Waters, Richard C. (1993b). "Stochastic lexicalized context-free grammars." In Proceedings, Third International Workshop on Parsing Technologies, 257-266. Tilburg, The Netherlands and Durbuy, Belgium. find
  16. Shieber, Stuart M. (1992). Constraint-Based Grammar Formalisms. MIT Press. find
  17. Shieber, Stuart M. (in press). "Restricting the weak-generative capacity of synchronous tree-adjoining grammars." Computational Intelligence. find
  18. Shieber, Stuart M., and Schabes, Yves (1990). "Synchronous tree-adjoining grammars." In Proceedings, 13th International Conference on Computational Linguistics, Volume 3, 253-258. Helsinki, Finland.
  19. Shieber, Stuart M., and Schabes, Yves (1991). "Generation and synchronous tree adjoining grammars." Computational Intelligence, 4(7), 220-228.
  20. Vijay-Shanker, K. (1987). A Study of Tree Adjoining Grammars. Doctoral dissertation, Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA. find
  21. Vijay-Shanker, K., and Joshi, Aravind K. (1985). "Some computational properties of tree adjoining grammars." In Proceedings, 23rd Annual Meeting of the Association for Computational Linguistics, 82-93. Chicago, IL. find
  22. Vijay-Shanker, K., and Joshi, Aravind K. (1988). "Feature structure based tree adjoining grammars." In Proceedings, 12th International Conference on Computational Linguistics, 714–719. Budapest, Hungary. find
  23. Vijay-Shanker, K., and Weir, David J. (1990). "Polynomial parsing of extensions of context-free grammars." In Current Issues in Parsing Technologies, edited by Masaru Tomita, 191-206. Kluwer Academic Publishers. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/schabes-1994-alternative-conception-tree-adjoining-derivation/