Elamur Research⌕
☰
home / papers / 1990 / The Computational Complexity of Avoiding Conversational Implicatures

The Computational Complexity of Avoiding Conversational Implicatures

Summary

The paper asks how a natural language generation system can choose referring expressions that do not lead listeners to draw unintended conversational implicatures (Grice 1975). For example, describing the only table in a room as "brown" and "wooden" suggests those details matter. Building on Dale's (1989) distinguishing-description model, Reiter treats a referring expression as a classification plus attribute-value pairs. He recasts Grice's maxims, along with the basic-level effects observed by Cruse and Hirschberg, as a trio of preference rules: a Lexical Preference rule, a rule of Local Brevity, and a constraint requiring No Unnecessary Components. A description counts as free of false implicatures when no other successful description is preferred over it. Reiter shows that descriptions that are maximal under these rules can be generated in polynomial time. Stricter alternatives, such as Full Brevity (always the shortest description) and No Unnecessary Words, make generation NP-Hard. The work matters because it uses computational cost alongside linguistic plausibility to decide how pragmatic constraints should be formalized in NLG.

Key points

  • The model treats successful descriptions and the preference relation as a partially ordered set, similar to Hirschberg's (1985) account of scalar implicatures. Choosing any description implies that no higher-ranked alternative was available.
  • Full Brevity is NP-Hard under every length measure the author examined: open-class words, words, characters, and components.
  • An exhaustive shortest-first search needs 6 steps for the toy example (N=3, L=2). It needs 175 checks for L=3, N=10, more than 6000 for L=4, N=20, and more than 2,000,000 for L=5, N=50.
  • Lexical Preference generalizes the preference for basic-level classes (Rosch 1978). Using a lexical class implies that no preferred class could have been used instead.
  • The rules can conflict when a basic-level class needs several words, as with Washing-Machine versus Appliance or Machine. In such cases the basic-level preference should take priority.

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: Linguistics & languages

Topics: Implicature

Cited by

18 papers of our library cite it (of the 140673 whose bibliographies we read); 3 of them have a page here, 15 not yet.

Cite

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

@inproceedings{reiter1990computational,
  title = {{The Computational Complexity of Avoiding Conversational Implicatures}},
  author = {Reiter, Ehud},
  booktitle = {28th Annual Meeting of the Association for Computational Linguistics},
  year = {1990},
  doi = {10.3115/981823.981836},
  url = {https://doi.org/10.3115/981823.981836}
}

References

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

  1. Appelt, D. 1985 Planning English Referring Expressions. Cambridge University Press: New York. ↗
  2. Berlin, B.; Breedlove, D,; and Raven, P. 1973 General Principles of Classification and Nomenclature in Folk Biology. American Anthropologist 75:214-242. ↗
  3. Cruse, D. 1977 The pragmatics of lexical specificity. Journal of Linguistics 13:153-164. ↗
  4. Cruse, D. 1986 Lexical Semantics. Cambridge University Press: New York. find
  5. Dale, R. 1989 Cooking up Referring Expressious. In Proceedings of the 27th Annual Meeting of the Association for Computational Linguistics. find
  6. Donnellan, K. 1966 Reference and Definite Descriptions. Philosophical Review 75:281-304. ↗
  7. Garey, M. and Johnson, D. 1979 Computers and Intractability: a Guide to the Theory of NP-Completeness. W. H. Freeman: San Francisce. find
  8. Grice, H. 1975 Logic and conversatiou. In P. Cole and J. Morgan (Eds.), Syntax and Semantics: Vol 3, Speech Acts, pg 43-58. Academic Press: New York. find
  9. Hirsehberg, J. 1985 A Theory of Scalar lmplicature. Report MS-CIS-85-56, LINC LAB 21. Department of Computer and Information Science, University of Pennsylvania. find
  10. Johnson, D. 1974 Approximation algorithms for eomhinatorial problems. Journal of Computer and Systems Sciences 9:256-178. find
  11. Kamp, H. (1975) Two Theories about Adjectives. In E. Koenan (Ed.) Formal Semantics of Natural Language, pg 123-155. Cambridge University Press: New York. ↗
  12. Reiter, E. 1990a Generating Descriptions that Exploit a User's Domain Knowledge. To appear in R. Dale0 C. MeRish, and M. Zock (F_xls.), Current Research in Natural Language Generation. Academic Press: New York. find
  13. Reiter, E. 1990b Generating Appropriate Natural Language Object Descriptions. Ph.D thesis. Aiken Computation Lab, Harvard University: Cambridge, Mass. find
  14. Rosch, E. 1978 Principles of Categorization. In E. Rosch and B. Lloyd (Eds.), Cognition and Categorization. Lawrence Erlbaum: Hillsdale, NL find

This page in Markdown → https://md.research.elamur.ai/free/papers/reiter-1990-computational-complexity-avoiding-conversational-implicatures/