[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/parsers-1993-sleator-parsing-english-link-grammar/) [home](https://md.mova.elamur.ai/free/en/) / [docs](https://md.mova.elamur.ai/free/en/docs/) / [papers](https://md.mova.elamur.ai/free/en/docs/papers/) / [English](https://md.mova.elamur.ai/free/en/docs/papers/en/) / Parsing English with a Link Grammar # Parsing English with a Link Grammar **Authors:** Daniel D. Sleator, Davy Temperley · **Year:** 1993 · **Venue:** Proceedings of the Third International Workshop on Parsing Technologies **Link:** [aclanthology.org/1993.iwpt-1.22](https://aclanthology.org/1993.iwpt-1.22/) · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) — summary only [**220** citations](https://openalex.org/works?filter=cites:W2123796147) openalex-snapshot · 2026-10-14[**119** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/parsers-1993-sleator-parsing-english-link-grammar/) of the 140673 papers whose bibliographies we read[Proceedings of the Third International Workshop on Parsing Technologies](https://aclanthology.org/volumes/1993.iwpt-1/)[licence](https://creativecommons.org/licenses/by-nc-sa/3.0/) - [Publisher's page](https://aclanthology.org/1993.iwpt-1.22/) - [PDF](https://aclanthology.org/1993.iwpt-1.22.pdf) - [OpenAlex](https://openalex.org/W2123796147) **Authors (2)** 1. [Daniel D. Sleator](https://openalex.org/A5003281880) h 33 · 11655 citations · 90 works 2. [Davy Temperley](https://openalex.org/A5002961208) h 2 · 350 citations · 3 works Citations and author metrics from openalex-snapshot (2026-10-14); authors with the same name are not always told apart. ## 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/} } ``` - [← previous NOPE: A Corpus of Naturally-Occurring Presuppositions in English](https://md.mova.elamur.ai/free/en/docs/papers/parrish-2021-nope-corpus-naturally-occurring-presuppositions/) - [next → On building a more efficient grammar by exploiting types](https://md.mova.elamur.ai/free/en/docs/papers/parsers-2000-flickinger-building-more-efficient-grammar/) - [↑ back to English](https://md.mova.elamur.ai/free/en/docs/papers/en/) ## 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](https://scholar.google.com/scholar?q=%5B1%29+Y%2E+Bar%2DHillel%2C+Language+and+information%3B+se+lected+essays+on+their+theory+and+application%2E+Addison%2DWesley%2C+1964%2E) 2. [2) Cormen, T. H . , C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press and McGraw-Hill, 1990. [find](https://scholar.google.com/scholar?q=%5B2%29+Cormen%2C+T%2E+H+%2E+%2C+C%2E+E%2E+Leiserson%2C+and+R%2E+L%2E+Rivest%2C+Introduction+to+Algorithms%2C+MIT+Press+and+McGraw%2DHill%2C+1990%2E) 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](https://scholar.google.com/scholar?q=%5B3%29+Fraser%2C+N%2E%2C+%22Parsing+and+dependency+gram+mar%2C%22+In%3A+Carston%2C+Robyn+%28ed%2E%29+UCL+Work+ing+Papers+in+Linguistics+1+%2C+University+Col+lege+London%2C+London%2C+1989+Pages+296%2D3+19%2E) 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](https://scholar.google.com/scholar?q=%5B4%29+Fraser%2C+N%2E+%2C+%22Prolegomena+to+a+formal+theory+of+dependency+grammar%2C%22+In%3A+UCL+Working+Papers+in+Linguistics+2%2C+University+College+London%2C+London%2C+1990+Pages+298%2D3+19%2E) 5. [5) Gaifman, H., "Dependency systems and phrase-structure systems," Information and Control 8, 1965, Pages 304-337. [↗](https://doi.org/10.1016/s0019-9958(65)90232-9) 6. [6) Hudson, R . , Word Grammar, Basil Black well, 1984. [find](https://scholar.google.com/scholar?q=%5B6%29+Hudson%2C+R+%2E+%2C+Word+Grammar%2C+Basil+Black+well%2C+1984%2E) 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](https://scholar.google.com/scholar?q=%5B7%29+Hudson%2C+R%2E%2C+%22Towards+a+computer+testable+word+grammar+of+English%2C%22+In%3A+Carston%2C+Robyn+%28ed%2E%29+UCL+Working+Papers+in+Lin+guistics+1+%2C+University+College+London%2C+Lon+don%2C+1989%2C+Pages+321%2D339%2E) 8. [8] Hudson, R . , English Word Grammar, Basil Blackwell, 1990. [find](https://scholar.google.com/scholar?q=%5B8%5D+Hudson%2C+R+%2E+%2C+English+Word+Grammar%2C+Basil+Blackwell%2C+1990%2E) 9. [9) Joshi, A. K . , "Natural Language Process ing," Science , Volume 253 , No. 5025, (Sept. 13 , 1991), Pages 1242-1249. [find](https://scholar.google.com/scholar?q=%5B9%29+Joshi%2C+A%2E+K+%2E+%2C+%22Natural+Language+Process+ing%2C%22+Science+%2C+Volume+253+%2C+No%2E+5025%2C+%28Sept%2E+13+%2C+1991%29%2C+Pages+1242%2D1249%2E) 10. [10] Melcuk, I. A. Dependency Syntax: Theory and Practice, State University of New York Press 1988. [find](https://scholar.google.com/scholar?q=%5B10%5D+Melcuk%2C+I%2E+A%2E+Dependency+Syntax%3A+Theory+and+Practice%2C+State+University+of+New+York+Press+1988%2E) 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. [↗](https://doi.org/10.21236/ada256365) 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](https://scholar.google.com/scholar?q=%5B12%29+Oehrle%2C+R%2E+T%2E%2C+E%2E+Bach%2C+and+D%2E+Wheeler%2C+Ed+itors+Categorial+Grammars+and+Natural+Lan+guage+Structures+D%2E+Reidel+Publishing+Com+pany%2C+1988%2E) 13. [13] Y. Schabes. "Stochastic lexicalized tree adjoining grammars." In Proceedings of COLING-92, Nantes, France, July 1992. [find](https://scholar.google.com/scholar?q=%5B13%5D+Y%2E+Schabes%2E+%22Stochastic+lexicalized+tree+adjoining+grammars%2E%22+In+Proceedings+of+COLING%2D92%2C+Nantes%2C+France%2C+July+1992%2E) 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](https://scholar.google.com/scholar?q=%5B14%5D+Sleator%2C+D%2E+D%2E%2C+D%2E+Temperley%2C+%22Parsing+En+glish+with+a+Link+Grammar%2C%22+Technical+re+port+CMU%2DCS%2D91%2D196%2C+Carnegie+Mellon+Uni+versity%2C+School+of+Computer+Science%2C+October+1991%2E) 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](https://scholar.google.com/scholar?q=%5B15%29+van+Zuijlen%2C+J%2E%2C+M%2E%2C+%22Probabilistic+methods+in+dependency+grammar+parsing%2C%22+Proceed+ings+of+the+International+Workshop+on+Pars+ing+Technologies%2C+Carnegie+Mellon+Univer+sity%2C+1989%2C+Pages+142%2D250%2E)