---
title: "An Alternative Conception of Tree-Adjoining Derivation (1994)"
description: "The proposed \"extended derivation\" lets several modifier auxiliary trees adjoin at one node, while… 23 references, cited by 69 papers here."
authors: ["Yves Schabes", "Stuart M. Shieber"]
year: 1994
venue: "Computational Linguistics"
source: "https://aclanthology.org/J94-1004/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/schabes-1994-alternative-conception-tree-adjoining-derivation/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/schabes-1994-alternative-conception-tree-adjoining-derivation/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1994](https://md.research.elamur.ai/free/en/papers/1994/) / An Alternative Conception of Tree-Adjoining Derivation

# An Alternative Conception of Tree-Adjoining Derivation

**Authors:** [Yves Schabes](https://md.research.elamur.ai/free/en/authors/yves-schabes/) and [Stuart M. Shieber](https://md.research.elamur.ai/free/en/authors/stuart-m-shieber/) · **Year:** 1994 · **Venue:** [Computational Linguistics](https://md.research.elamur.ai/free/en/venues/cl/) ([Computational Linguistics 1994](https://md.research.elamur.ai/free/en/venues/cl/1994/)) · **Publisher:** [The MIT Press](https://md.research.elamur.ai/free/en/publishers/the-mit-press/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/J94-1004/) · [PDF](https://aclanthology.org/J94-1004.pdf) · [OpenAlex](https://openalex.org/W2952318402)

**Citations:** 34 citations (OpenAlex, 2026-10-14) · [69](https://md.research.elamur.ai/free/en/papers/schabes-1994-alternative-conception-tree-adjoining-derivation/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## 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 University](https://md.research.elamur.ai/free/en/universities/harvard-university/) — University, Cambridge, United States · 73 works · 37,309 citations

Also on the byline: [Mitsubishi Electric (United States)](https://ror.org/053jnhe44) · [Mitsubishi Electric Research Laboratories](https://ror.org/00e2e3n51).

📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,085 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,888 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 116 works

🧭 Topics (1): [📐 Syntax & grammar formalisms](https://md.research.elamur.ai/free/en/topics/syntax-grammar/) · 162 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.

```bibtex
@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/}
}
```

- [← previous Comlex Syntax: Building a Computational Lexicon](https://md.research.elamur.ai/free/en/papers/grishman-1994-comlex-syntax-building-computational-lexicon/)
- [next → Adaptive Sentence Boundary Disambiguation](https://md.research.elamur.ai/free/en/papers/palmer-1994-adaptive-sentence-boundary-disambiguation/)
- [↑ back to papers of 1994](https://md.research.elamur.ai/free/en/papers/1994/)

## 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](https://scholar.google.com/scholar?q=Abeill6%2C+Anne%3B+Schabes%2C+Yves%3B+and+Joshi%2C+Aravind+K%2E+%281990%29%2E+%22Using+lexicalized+tree+adjoining+grammars+for+machine+translation%2E%22+In+Proceedings%2C+13th+International+Conference+on+Computational+Linguist)
2. Gazdar, Gerald; Klein, Ewan; Pullum, Geoffrey K.; and Sag, Ivan A. (1985). Generalized Phrase Structure Grammar. Blackwell. [find](https://scholar.google.com/scholar?q=Gazdar%2C+Gerald%3B+Klein%2C+Ewan%3B+Pullum%2C+Geoffrey+K%2E%3B+and+Sag%2C+Ivan+A%2E+%281985%29%2E+Generalized+Phrase+Structure+Grammar%2E+Blackwell%2E)
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](https://scholar.google.com/scholar?q=Joshi%2C+A%2E+K%2E%3B+Kosaraju%2C+S%2E+R%2E%3B+and+Yamada%2C+H%2EM%2E+%281972a%29%2E+%22String+adjunct+grammars%3A+I%2E+Local+and+distributed+adjunction%2E%22+Information+and+Control%2C+21%282%29%2C+93%2D116%2E)
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](https://scholar.google.com/scholar?q=Joshi%2C+A%2E+K%2E%3B+Kosaraju%2C+S%2E+R%2E%3B+and+Yamada%2C+H%2E+M%2E+%281972b%29%2E+%22String+adjunct+grammars%3A+II%2E+Equational+representation%2C+null+symbols%2C+and+linguistic+relevance%2E%22+Information+and+Control%2C+21+%283%29%2C+235%2D260%2E)
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](https://scholar.google.com/scholar?q=Joshi%2C+Aravind+K%2E%3B+Levy%2C+L%2E+S%2E%3B+and+Takahashi%2C+M%2E+%281975%29%2E+%22Tree+adjunct+grammars%2E%22+Journal+of+Computer+and+System+Sciences%2C+10%281%29%2C+136%2D163%2E)
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](https://scholar.google.com/scholar?q=Kroch%2C+Anthony+S%2E+%281989%29%2E+%22Asymmetries+in+long+distance+extraction+in+a+TAG+grammar%2E%22+In+Alternative+Conceptions+of+Phrase+Structure%2C+edited+by+M%2E+Baltin+and+A%2E+Kroch%2C+66%2D98%2E+University+of+Chicago+Pre)
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](https://scholar.google.com/scholar?q=Kroch%2C+Anthony+S%2E%2C+and+Joshi%2C+Aravind+K%2E+%281985%29%2E+%22The+linguistic+relevance+of+tree+adjoining+grammar%2E%22+Technical+Report+MS%2DCIS%2D85%2D18%2C+Department+of+Computer+and+Information+Science%2C+University+of+Penn)
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](https://scholar.google.com/scholar?q=Pereira%2C+Fernando+C%2E+N%2E%2C+and+Warren%2C+David+H%2E+D%2E+%281983%29%2E+%22Parsing+as+deduction%2E%22+In+Proceedings%2C+21st+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2C+137%2D144%2E+Cambridge%2C+MA%2E)
9. Quirk, Randolph; Greenbaum, Sidney; Leech, Geoffrey; and Svartvik, Jan (1985). A Comprehensive Grammar of the English Language. Longman. [find](https://scholar.google.com/scholar?q=Quirk%2C+Randolph%3B+Greenbaum%2C+Sidney%3B+Leech%2C+Geoffrey%3B+and+Svartvik%2C+Jan+%281985%29%2E+A+Comprehensive+Grammar+of+the+English+Language%2E+Longman%2E)
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](https://scholar.google.com/scholar?q=Resnik%2C+Philip+%281992%29%2E+%22Probabilistic+tree%2Dadjoining+grammar+as+a+framework+for+statistical+natural+language+processing%2E%22+In+Proceedings%2C+14th+International+Conference+on+Computational+Linguistics%2C+41)
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](https://scholar.google.com/scholar?q=Schabes%2C+Yves+%281991%29%2E+%22The+valid+prefix+property+and+left+to+right+parsing+of+tree%2Dadjoining+grammar%2E%22+In+Proceedings%2C+Second+International+Workshop+on+Parsing+Technologies%2C+21%2D30%2E+Cancun%2C+Mexico%2E)
12. Schabes, Yves (1992). "Stochastic lexicalized tree-adjoining grammars." In Proceedings, 14th International Conference on Computational Linguistics, 426-432. Nantes, France. [find](https://scholar.google.com/scholar?q=Schabes%2C+Yves+%281992%29%2E+%22Stochastic+lexicalized+tree%2Dadjoining+grammars%2E%22+In+Proceedings%2C+14th+International+Conference+on+Computational+Linguistics%2C+426%2D432%2E+Nantes%2C+France%2E)
13. Schabes, Yves, and Shieber, Stuart M. (1992). "An alternative conception of tree-adjoining derivation." Technical Report 08-92, Harvard University, Cambridge, MA. [find](https://scholar.google.com/scholar?q=Schabes%2C+Yves%2C+and+Shieber%2C+Stuart+M%2E+%281992%29%2E+%22An+alternative+conception+of+tree%2Dadjoining+derivation%2E%22+Technical+Report+08%2D92%2C+Harvard+University%2C+Cambridge%2C+MA%2E)
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](https://scholar.google.com/scholar?q=Schabes%2C+Yves%2C+and+Waters%2C+Richard+C%2E+%281993a%29%2E+%22Lexicalized+context%2Dfree+grammars%2E%22+In+Proceedings%2C+31st+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2C+121%2D129%2E+Columbus%2C+OH%2E)
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](https://scholar.google.com/scholar?q=Schabes%2C+Yves%2C+and+Waters%2C+Richard+C%2E+%281993b%29%2E+%22Stochastic+lexicalized+context%2Dfree+grammars%2E%22+In+Proceedings%2C+Third+International+Workshop+on+Parsing+Technologies%2C+257%2D266%2E+Tilburg%2C+The+Netherlands+a)
16. Shieber, Stuart M. (1992). Constraint-Based Grammar Formalisms. MIT Press. [find](https://scholar.google.com/scholar?q=Shieber%2C+Stuart+M%2E+%281992%29%2E+Constraint%2DBased+Grammar+Formalisms%2E+MIT+Press%2E)
17. Shieber, Stuart M. (in press). "Restricting the weak-generative capacity of synchronous tree-adjoining grammars." Computational Intelligence. [find](https://scholar.google.com/scholar?q=Shieber%2C+Stuart+M%2E+%28in+press%29%2E+%22Restricting+the+weak%2Dgenerative+capacity+of+synchronous+tree%2Dadjoining+grammars%2E%22+Computational+Intelligence%2E)
18. Shieber, Stuart M., and Schabes, Yves (1990). "[Synchronous tree-adjoining grammars](https://md.research.elamur.ai/free/en/papers/shieber-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](https://md.research.elamur.ai/free/en/papers/shieber-1990-synchronous-tree-adjoining-grammars/).
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](https://scholar.google.com/scholar?q=Vijay%2DShanker%2C+K%2E+%281987%29%2E+A+Study+of+Tree+Adjoining+Grammars%2E+Doctoral+dissertation%2C+Department+of+Computer+and+Information+Science%2C+University+of+Pennsylvania%2C+Philadelphia%2C+PA%2E)
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](https://scholar.google.com/scholar?q=Vijay%2DShanker%2C+K%2E%2C+and+Joshi%2C+Aravind+K%2E+%281985%29%2E+%22Some+computational+properties+of+tree+adjoining+grammars%2E%22+In+Proceedings%2C+23rd+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2C+82%2D93)
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](https://scholar.google.com/scholar?q=Vijay%2DShanker%2C+K%2E%2C+and+Joshi%2C+Aravind+K%2E+%281988%29%2E+%22Feature+structure+based+tree+adjoining+grammars%2E%22+In+Proceedings%2C+12th+International+Conference+on+Computational+Linguistics%2C+714%2D%2D719%2E+Budapest%2C+Hung)
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](https://scholar.google.com/scholar?q=Vijay%2DShanker%2C+K%2E%2C+and+Weir%2C+David+J%2E+%281990%29%2E+%22Polynomial+parsing+of+extensions+of+context%2Dfree+grammars%2E%22+In+Current+Issues+in+Parsing+Technologies%2C+edited+by+Masaru+Tomita%2C+191%2D206%2E+Kluwer+Academic+)

*Updated 24 October 2026*