Elamur Research⌕
☰
home / papers / 1990 / Semantic-Head-Driven Generation

Semantic-Head-Driven Generation

Paper · 1990 · Stuart M. Shieber, Gertjan van Noord, Fernando C. N. Pereira et al.

Summary

The paper addresses tactical generation: producing a sentence from a logical-form encoding of its meaning using unification-based or logic grammars, such as DCG, PATR-II and HPSG-style grammars. Earlier generators each restricted which grammars they could handle. Top-down regimes, even with dynamic goal reordering, can loop forever on left-recursive rules. The authors show this with a possessive NP rule and with a PATR-II complements rule, where no ordering of subgoals avoids nontermination. The Earley-style bottom-up generator works only with semantically monotonic grammars and can be highly nondeterministic. Shieber, Pereira, van Noord and Moore propose a generator that walks the analysis tree from its semantic head: it picks a pivot node, generates it, and then connects it upward to the root through chain rules. The algorithm is presented as Prolog interpreters over a node-based DCG encoding. It is a design-level contribution with no corpus evaluation. Its value is that it accepts both nonmonotonic semantics and left recursion, which makes reversible, linguistically realistic grammars usable for generation.

Key points

  • The algorithm handles two cases that defeat earlier generators: semantically nonmonotonic grammars, which the Earley-based bottom-up generator cannot use, and left recursion, which top-down methods cannot handle.
  • Dutch cross-serial verb constructions build subcategorization lists of unbounded length. This rules out ad hoc depth limits as a fix for top-down nontermination.
  • Empty heads, such as the moved verb in Dutch/German verb-second clauses, are handled with a head_gap relation. The gap is introduced only after its antecedent has been built, so the gap's information is available in time.
  • Reported uses include van Noord's BUG generator in the MiMo2 Teletext news translation system and the STREP project at CSLI for HPSG grammars. Calder et al. (1989) describe a UCG generator that seems to be a particular instance of this algorithm.
  • Proposed future work:
    • a uniform parsing/generation architecture, linked to Kay's (1990) parser and van Noord's (1989b) Horn-clause proof procedure;
    • chart-style dynamic programming to remove redundant recomputation;
    • delayed evaluation for auxiliary conditions in rules.

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🏢AT&TBedminster · United States29 works · 15,393 citations🔬SRI InternationalMenlo Park · United States9 works · 5,737 citations🎓Utrecht UniversityUtrecht · Netherlands21 works · 1,281 citations

📚 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

Cite

Cite as Stuart M. Shieber, Gertjan van Noord, Fernando C. N. Pereira and Robert C. Moore. 1990. Semantic-Head-Driven Generation. Computational Linguistics.

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

@article{shieber1990semantic,
  title = {{Semantic-Head-Driven Generation}},
  author = {Stuart M. Shieber, Gertjan {van Noord}, Fernando C. N. Pereira and Robert C. Moore},
  journal = {Computational Linguistics},
  year = {1990},
  doi = {10.5555/89086.89097},
  url = {https://doi.org/10.5555/89086.89097}
}

References

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

  1. Calder, J.; Reape, M.; and Zeevat, H. 1989 "An Algorithm for Generation in Unification Categorial Grammar." In Proceedings of the 4th Conference of the European Chapter of the Association for Computational Linguistics, 233-240. find
  2. Colmerauer, A. 1982 PROLOG II: Manuel de R6ference et Mod61e Th6orique. Technical report, Groupe de'Intelligence Artificielle, Fa-cult6 des Sciences de Luminy, Marseille, France. find
  3. Cooper, R. 1983 "Quantification and Syntactic Theory," Volume 21 of Synthese Language Library. D. Reidel, Dordrecht, the Netherlands. find
  4. Dymetman, M. and Isabelle, P. 1988 "Reversible Logic Grammars for Machine Translation." In Proceedings of the Second International Conference on Theoretical and Methodological Issues in Machine Translation of Natural Languages. find
  5. Evers, A. 1975. The Transformational Cycle in German and Dutch. Ph.D. Thesis, University of Utrecht, Utrecht, the Netherlands. find
  6. Fodor, J. D. In press. "Cross Serial Dependencies and Subcategorization Percolation." In R. Rieber (ed.), CUNYForum, Volume 15. City University of New York, New York. find
  7. Halvorsen, P.-K. and Kaplan, R.M. 1988 "Projections and Semantic Description in Lexieal-Functional Grammar." In Proceedings of the International Conference on Fifth Generation Computer Systems, Tokyo, Japan, 1116-1122. find
  8. Hirsh, S. 1987 "P-PATR, a Compiler for Unification Based Grammars," In V. Dahl and P. Saint-Dizier (eds.), Natural Language Understanding and Logic Programming, H. Elsevier Science Publishers, New York, NY: 63-78. find
  9. Hobbs, J.R. and Shieber, S.M. 1987 An Algorithm for Generating Quantifier Scopings." Computational Linguistics, 13:47-63. find
  10. Huybrechts, R.A.C. 1984 "The Weak Inadequacy of Context-Free Phrase Structure Grammars," In G. de Haan, M. Trommelen, and W. Zonneveld (eds.), Van Periferie naar Kern. Foris, Dordrecht, the Netherlands. find
  11. Kay, M. 1990 "Head-Driven Parsing." In M. Tomita (ed.), Currentlssues in Parsing Technology. Klumer Academic Publishers, Dordrecht, the Netherlands. find
  12. Koster, J. 1975 "Dutch as an SOV Language." Linguistic Analysis, 1:(2):111-136. find
  13. Matsumoto, Y.; Tanaka, H.; Hirakawa, H.; Miyoshi, H.; and Yasukawa, H. 1983 "BUP: A Bottom-Up Parser Embedded in Prolog." New Generation Computing, 1 (2): 145-158. find
  14. Moortgat, M. 1984 "A Fregean Restriction on Meta-Rules" In Proceedings of New England Linguistic Society, 14:306-325. find
  15. Naish, L. 1986 "Negation and Control in Prolog," Volume 238 of Lecture Notes in Computer Science. find
  16. Springer-Verlag Berlin, F.R.G. van Noord, G. 1989a "BUG: A Directed Bottom-Up Generator for Unification Based Formalisms." Working Papers in Natural Language Processing 4, Katholieke Universiteit Leuven, Stichting Taaltechnolo-gie Utrecht, Utrecht, the Netherlands. van Noord, G. 1989b "An Overview o… find
  17. Pereira, F.C.N. and Shieber, S.M. 1985 "Prolog and Natural-Language Analysis," Volume 10 of CSLI Lecture Notes. Center for the Study of Language and Information, Stanford, CA. find
  18. Pereira, F.C.N. and Warren, D.H.D. 1983 "Parsing as Deduction." In Proceedings of the 21st Annual Meeting of the Association for Computational Linguistics, 137-144. find
  19. Pereira, F.C.N. 1981 "Extraposition Grammars." Computational Linguistics, 7(4):243-256. find
  20. Po'ilard, C. 1988 "Categorial Grammar and Phrase Structure Grammar: An ]Excursion on the Syntax-Semantics Frontier," In R. Oehrle, E. Bach, and D. Wheeler (eds.), Categorial Grammars and Natural Language Structures. D. Reidel, Dordrecht, the Netherlands. find
  21. Shieber, S.M. 1985a "An Introduction to Unification-Based Approaches to Grammar," Volume 4 of CSLI Lecture Notes. Center for the Study of Language and Information, Stanford, CA. find
  22. Shieber, S.M. 1985b "Using Restriction to Extend Parsing Algorithms for Complex-Feature-Based Formalisms." In Proceedings of the 23rd Annual Meeting of the Association for Computational Linguistics, 145-152. find
  23. Shieber, S.M. 1988 "A Uniform Architecture for Parsing and Generation." In Proceedings of the 12th International Conference on Computational Linguistics, 614-619. find
  24. Stcedman, M. 1985 "Dependency and Coordination in the Grammar of Dutch and English." Language, 61 (3):523-568. find
  25. Strzalkowski, T. 1989 Automated Inversion of a Unification Parser into a Unification Generator. Technical Report 465, Department of Computer Science, New York University, New York. find
  26. Wedekind, J. 1988 "Generation as Structure Driven Derivation." In Proceedings of the 12th International Conference on Computational Linguistics, 732-737. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/shieber-1990-semantic-head-driven-generation/