Parsing English with a Link Grammar

What it is about

Link grammar is a lexical formalism: every word carries a formula of connectors, and a sentence is grammatical when its words can be joined by links that satisfy every word's requirements, do not cross and connect the whole sentence. There are no constituents or categories. The authors write roughly 800 formulas covering about 25,000 words of formal English, handling agreement, questions, relative clauses, coordination and unbounded dependencies. Their O(n^3) parser uses pruning, a hashed fast-match on connector types and power pruning, and parses typical newspaper sentences in a few seconds. The paper also shows how costly lexical ambiguity is: "cat" has 369 ways to be used and "time" 1689 in their dictionary.

Ideas

• I1. en/src/parse.rs: build a per-word table of allowed head-dependent label pairs from en/seeds/lexicon (link-style), and use it to forbid impossible arcs during the arc-standard search; measure LAS on EWT test (must stay the same) and the candidate transitions per sentence.
• I2. en/src/udreg.rs and en/seeds/errors: flag a sentence when no complete linkage exists under the lexical patterns; measure precision and recall on a labelled set of grammatical and error-injected sentences made from our own corpus, not from external data.
• I3. en/seeds/lexicon: count the distinct valid UD patterns per word, as the paper does for "cat" and "time", and list the words whose pattern count is largest, to find the seeds that are too broad.

For Mova

The chapters are 19-lexicon-mwe-register (the lexicon as the place where most of the grammar lives) and 13-verbs (the verb frames a link formula encodes). The code is en/seeds/lexicon, en/seeds/errors, en/src/parse.rs and en/src/udreg.rs. Measure first: the lexical-pattern count of idea I3, which costs nothing and shows where the seeds are too broad.

Cite

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

@inproceedings{sleator1993parsing,
  title = {{Parsing English with a Link Grammar}},
  author = {Sleator, Daniel D. and Temperley, Davy},
  booktitle = {Proceedings of the Third International Workshop on Parsing Technologies},
  year = {1993},
  url = {https://aclanthology.org/1993.iwpt-1.22/}
}

References

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

1. [1) Y. Bar-Hillel, Language and information; se lected essays on their theory and application. Addison-Wesley, 1964. find
2. [2) Cormen, T. H . , C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press and McGraw-Hill, 1990. find
3. [3) Fraser, N., "Parsing and dependency gram mar," In: Carston, Robyn (ed.) UCL Work ing Papers in Linguistics 1 , University Col lege London, London, 1989 Pages 296-3 19. find
4. [4) Fraser, N. , "Prolegomena to a formal theory of dependency grammar," In: UCL Working Papers in Linguistics 2, University College London, London, 1990 Pages 298-3 19. find
5. [5) Gaifman, H., "Dependency systems and phrase-structure systems," Information and Control 8, 1965, Pages 304-337. find
6. [6) Hudson, R . , Word Grammar, Basil Black well, 1984. find
7. [7) Hudson, R., "Towards a computer testable word grammar of English," In: Carston, Robyn (ed.) UCL Working Papers in Lin guistics 1 , University College London, Lon don, 1989, Pages 321-339. find
8. [8] Hudson, R . , English Word Grammar, Basil Blackwell, 1990. find
9. [9) Joshi, A. K . , "Natural Language Process ing," Science , Volume 253 , No. 5025, (Sept. 13 , 1991), Pages 1242-1249. find
10. [10] Melcuk, I. A. Dependency Syntax: Theory and Practice, State University of New York Press 1988. find
11. [11] Lafferty, J, D. Sleator , D. Temperley, "Grammatical Trigrams: A Probabilistic Model of Link Grammar," Proc. of the 1992 AAAI Fall Symp. on Probabilistic Ap proaches to Natural Language, and Techni cal report CMU-CS-92-181 , School _of Com puter Science, Carnegie Mellon University, Sept 1992. find
12. [12) Oehrle, R. T., E. Bach, and D. Wheeler, Ed itors Categorial Grammars and Natural Lan guage Structures D. Reidel Publishing Com pany, 1988. find
13. [13] Y. Schabes. "Stochastic lexicalized tree adjoining grammars." In Proceedings of COLING-92, Nantes, France, July 1992. find
14. [14] Sleator, D. D., D. Temperley, "Parsing En glish with a Link Grammar," Technical re port CMU-CS-91-196, Carnegie Mellon Uni versity, School of Computer Science, October 1991. find
15. [15) van Zuijlen, J., M., "Probabilistic methods in dependency grammar parsing," Proceed ings of the International Workshop on Pars ing Technologies, Carnegie Mellon Univer sity, 1989, Pages 142-250. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/parsers-1993-sleator-parsing-english-link-grammar/