Elamur Research⌕
☰
home / papers / 1981 / Relaxation Techniques for Parsing Grammatically Ill-Formed Input in Natural Language Understanding Systems

Relaxation Techniques for Parsing Grammatically Ill-Formed Input in Natural Language Understanding Systems

Paper · 1981 · Stan C. Kwasny and Norman K. Sondheimer

Summary

Natural language understanding (NLU) systems often receive input their grammar does not cover. Examples include agreement errors, sentence fragments, superfluous words, and coordination, which grammars rarely encode. Kwasny and Sondheimer argue such input should be interpreted rather than rejected. They propose relaxation techniques inside the Augmented Transition Network (ATN) model. A normative grammar defines well-formed input. When a relaxable arc blocks the parse, the parser saves a weakened version of that arc as a backtracking alternative. These alternatives are explored only after all grammatical paths fail, so correct input is parsed exactly as before.

The techniques include:

  • relaxing arc tests and word categories;
  • pattern arcs for contextual and telegraphic ellipsis and for gapping;
  • a word-skipping mode for extraneous material;
  • treating conjunction as sentence joining plus ellipsis.

Each relaxed parse carries a deviance note describing how the input departed from grammatical form. The paper is an implemented design study, not a quantitative evaluation. Its contribution is a single framework covering many kinds of ill-formedness while keeping the original grammar's structure and efficiency intact.

Key points

  • Phenomena covered: co-occurrence violations (e.g., number agreement), contextual vs. telegraphic ellipsis, extraneous terms, and conjunction (simple, gapping, list, correlative).
  • Test relaxation: grammar writers mark predicates as absolutely violable (the predicate is negated) or conditionally violable (a substitute predicate is used, e.g., TRANS in place of INTRANS). Arc type failures are handled through a category hierarchy.
  • Motivating data: Thompson (1980) found 7.6% terse questions and 10.3% terse replies among 882 parsed human-to-computer messages. Shores (1977) found nonstandard inflection patterns in 56 freshman essays. Malhotra (1975) supplied telegraphic queries.
  • Comparisons: the approach is contrasted with Woods' SYSCONJ in LUNAR, LIFER's ellipsis handling, and Weischedel and Black (1980). Unlike SYSCONJ, it handles gapping and correlatives, but it struggles with cataphoric ellipsis.
  • Stated limitations:
    • the SKIP mode is too unselective;
    • relaxations work best when developed together with the grammar;
    • the longest-path heuristic for choosing which blockage to relax can overshoot the real error;
    • idioms, misspellings, and word-order errors are not addressed.

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, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

Cite

Cite as Stan C. Kwasny and Norman K. Sondheimer. 1981. Relaxation Techniques for Parsing Grammatically Ill-Formed Input in Natural Language Understanding Systems. Computational Linguistics.

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

@article{kwasny1981relaxation,
  title = {{Relaxation Techniques for Parsing Grammatically Ill-Formed Input in Natural Language Understanding Systems}},
  author = {Stan C. Kwasny and Norman K. Sondheimer},
  journal = {Computational Linguistics},
  year = {1981},
  url = {https://aclanthology.org/J81-2002/}
}

References

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

  1. Bates, M., "The Theory and Practice of Augmented Transition Network Grammars," in Natural Language Communication with Computers, L. Bolc (Ed.), 191-259, Springer-Verlag, Berlin, 191-259, 1978. find
  2. Burton, Richard R., "Semantic Grammar: An Engineering Technique for Constructing Natural Language Understanding Systems," Bolt Beranek and Newman, Report No. 3453, December, 1976. find
  3. Chomsky, N., "Degrees of Grammaticalness," in The Structure of Language: Readings in the Philosophy of Language, Fodor, J.A. and J.J. Katz (Eds.), 384-389, Prentice-Hall, Englewood Cliffs, New Jersey, 1964. find
  4. Halliday, M.A.K. and R. Hasan, Cohesion in English, Longman, London, 1976. find
  5. Hayes, P., and G. Mouradian, "Flexible Parsing," Proceedings of the 18th Annual Meeting of the Association for Computational Linguistics, 97-103, Philadelphia, June, 1980. find
  6. Hendrix, G.G., E.D. Sacerdoti, D. Sagalowicz, and J. Slocum, "Developing a Natural Language Interface to Complex Data," ACM Transactions on Database Systems, 3, 2, 105-147, June, 1978. find
  7. Katz, J.J., "Semi-Sentences," in The Structure of Language: Readings in the Philosophy of Language, Fodor, J.A. and J.J. Katz (Eds.), 400-416, Prentice-Hall, Englewood Cliffs, New Jersey, 1964. find
  8. Relaxation Techniques for Parsing lU-Formed Input Kwasny, S.C., "Treatment of Ungrammatical and Extragrammatical Phenomena in Natural Language Understanding Systems," PhD dissertation, Ohio State University, 1980, (available through the Indiana University Linguistics Club, Bloomington, Indiana). find
  9. Malhotra, A., "Design Criteria for a Knowledge-Based English Language System for Management: An Experimental Analysis," MAC TR-146, M.I.T., Cambridge, MA, February, 1975. find
  10. Miller, L.A., G.E. Heidorn, and K. Jensen, "Text-Critiquing with the EPISTLE System: An Author's Aid to Better Syntax," Proceedings of the National Computer Conference, 50, 649-655, AFIPS Press, Arlington, VA, 1981. find
  11. Parkison, R.C., K.M. Colby, and W.S. Faught, "Conversational Language Comprehension Using Integrated Pattern-Matching and Parsing," Artificial Intelligence 9, 2, 111-134, October, 1977. find
  12. Quirk, R., S. Greenbaum, G. Leech, and J. Svartik, A Grammar of Contemporary English, Seminar Press, New York, 1972. find
  13. Riesbeck, C.K., and R.C. Schank, "Comprehension by Computer: Expectation-Based Analysis of Sentences in Context," Yale University, Research Report 78, October, 1976. find
  14. Shores, D.L., "Black English and Black Attitudes," in Papers in Language Variation, D.L Shores and C.P. Hines (Ed.), The University of Alabama Press, University, Alabama, 1977. find
  15. Sondheimer, N.K., and R.M. Weischedel, "A Rule-Based Approach to Ill-Formed Input," COLING 80: Proceedings of the Eighth International Conference on Computational Linguistics, 46-53, Tokyo, October, 1980. find
  16. Thompson, B.H., "Linguistic Analysis of Natural Language Communication with Computers," COLING 80: Proceedings of the Eighth International Conference on Computational Linguistics, 190-201, Tokyo, October, 1980. find
  17. Weischedel, R.M., and J. Black, "Responding Intelligently to Unparsable Inputs," American Journal of Computational Linguistics, 6, 2, 97-109, 1980.
  18. Wilks, Y., "Natural Language Understanding Systems Within the A.I. Paradigm: A Survey," American Journal of Computational Linguistics, microfiche 40, 1, 1976. find
  19. Woods, W.A., "An Experimental Parsing System for Transition Network Grammars," in Natural Language Processing, R. Rustin (Ed.), 111-154, Algorithmics Press, New York, 1973. find
  20. Stan C. Kwasny is an Assistant Professor in the find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/kwasny-1981-relaxation-techniques-parsing-grammatically-ill/