Elamur Research⌕
☰
home / papers / 1982 / Phrase Structure Trees Bear More Fruit than You Would Have Thought

Phrase Structure Trees Bear More Fruit than You Would Have Thought

Paper · 1982 · Aravind K. Joshi and Leon S. Levy

Summary

This theoretical paper argues that ordinary phrase structure trees can describe far more than is usually assumed, without going beyond context-free generative power. It responds to 1970s–80s alternatives to transformational grammar, such as Gazdar's GPSG and the linking approach of Peters and Karttunen, which enrich phrase structure grammars while trying to keep them weakly context-free. The authors revisit their earlier work on local constraints. In that framework, context-sensitive-looking conditions are applied to trees as node admissibility checks rather than as rewriting rules. They give an intuitive proof of the main theorem using interacting finite-state machines instead of tree automata theory. They then compare this approach with slashed categories and node linking. They also study skeletons, which are trees with all category labels removed. Every context-free tree set can be generated purely from such unlabeled shapes, so the grouping structure alone keeps all the structural information. This bears on psycholinguistics and on grammatical inference.

Key points

  • The paper builds on Peters and Ritchie (1969). Their result is that context-sensitive rules used as node admissibility conditions accept only context-free languages. Joshi and Levy (1977) extended this to Boolean combinations of proper analysis and domination predicates.
  • In GPSG, slashed categories (e.g., S/NP) with derived and linking rules handle unbounded dependencies and stay context-free, but they multiply the number of categories. Unconstrained metarules can exceed context-free power, for example by generating {aⁿbⁿcⁿ}.
  • The paper traces the history of categories with holes to Harris (1956, 1962). It also credits Sager, whose parser propagated holes and used them for coordination.
  • For any context-free grammar, a skeletal generating system can be built from initial skeletons and skeletal rewriting rules that yields exactly its label-free tree set (Levy and Joshi 1979).
  • Each skeletal set is recognized by a bottom-up tree automaton (Levy and Joshi 1978). If that automaton has k states, the skeletons of depth ≤ 2k fully determine the set. This suggests feeding grammatical inference with bracketed strings rather than plain strings.

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

🎓University of PennsylvaniaPhiladelphia · United States221 works · 63,234 citations🏢AT&TBedminster · United States40 works · 75,466 citations

 Fields, topics and concepts

📚 Shelves 6The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksPsychology · 1,552 worksDevelopmental and Educational Psychology · 499 works

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

Cite

Cite as Aravind K. Joshi and Leon S. Levy. 1982. Phrase Structure Trees Bear More Fruit than You Would Have Thought. Computational Linguistics.

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

@article{joshi1982phrase,
  title = {{Phrase Structure Trees Bear More Fruit than You Would Have Thought}},
  author = {Aravind K. Joshi and Leon S. Levy},
  journal = {Computational Linguistics},
  year = {1982},
  doi = {10.3115/981436.981451},
  url = {https://doi.org/10.3115/981436.981451}
}

References

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

  1. Bresnan, J.W. 1978 A Realistic transformational grammar. In Halle, M., Bresnan, J. and Miller, G.A., Ed., Linguistic Theory and Psychological Reality. The MIT Press, Cambridge, Mass. find
  2. Chomsky, N. 1965 Aspects of the Theory of Syntax, The MIT Press, Cambridge, Mass. find
  3. Gazdar, G.J.M. 1978 English as a context-free language, unpublished manuscript. find
  4. Gazdar, G.J.M. 1981 Unbounded dependencies and coordinate structure. Linguistic Inquiry 12, 2. find
  5. Gazdar. G.J.M. 1982 Phrase Structure Grammar. To appear in Jaeobson, P. and Pullam, G.K., Ed., The Nature of Syntactic Representation. Reidel, Boston, Mass. find
  6. Harris, Z.S. 1956 String analysing of language structure, manuscript. Also in manuscripts around 1958 and published in 1962 by Mouton and Co., The Hague. find
  7. Joshi, A.K. and Levy, L.S. 1977 Constraints on structural descriptions. S l A M Journal of Computing. find
  8. Joshi, A.K., Levy, L.S., and Yueh, K. 1980 Local constraints in the syntax and semantics of programming language. Journal of Theoretical Computer Science. find
  9. Kaplan, R. and Bresnan, J.W. 1979 A formal system for grammatical representation. To appear in Bresnan, J.W., Ed., The Mental Representation of Grammatical Relations. The MIT Press, Mass. find
  10. Karttunen, L. 1980 Unbounded dependencies in phrase structure grammar: slash categories versus dotted lines. Paper presented at the Third Amsterdam Colloquium: Formal Methods in the Study of Language, Amsterdam. find
  11. Levy, L.S. and Joshi, A.K. 1978 Skeletal structural descriptions. find
  12. Information and Control McCawley, J.D. 1967 Concerning the base component of a transformational grammar. Foundations of Language, Vol. 4. Reprinted in McCawley, J.D., Grammar and Meaning, Academic Press, New York, NY, 1968. find
  13. Peters, S. 1980 (Talk presented at the Workshop on Alternatives to Transformation Grammars, Stanford University, January.) find
  14. Peters, S. and Ritchie, R.W. 1969 Context-sensitive immediate constituent analysis. Proc. A C M Symposium on Theory of Computing. find
  15. Syntactic analysis of natural languages. Advances Vol. 8 ed. M. Alt and M. Rubinoff, Academic Press, New York, NY. Sager, N. in Computers, Aravind K. Joshi is a professor o f computer and information science, and that department's chairman, at the University of Pennsylvania, Philadelphia. He receive… find
  16. Leon S. Levy is a member of the technical staff of Bell Telephone Laboratories at Whippany, New Jersey. He received the Ph.D. degree in Computer Science from the University of Pennsylvania in 1970. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/joshi-1982-phrase-structure-trees-bear-more/