Link Grammar

Link Grammar Parser

The original homepage hosted at the Carnegie Mellon University lists an extensive bibliography (mirror) referencing several dozen older (pre-2004) papers pertaining to the Link Grammar Parser. More recent publications and announcements are listed below.

Recent Applications and Publications

Linas Vepstas, Combinatory Categorial Grammar and Link Grammar are Equivalent, (July 2022).
Ben Goertzel, Andres Suarez Madrigal, Gino Yu, Guiding Symbolic Natural Language Grammar Induction via Transformer-Based Sequence Probabilities, (May 2020) arXiv:2005.12533
Vignav Ramesh, Anton Kolonin, Interpretable Natural Language Segmentation Based on Link Grammar, 2020 Science and Artificial Intelligence conference (S.A.I.ence) Novosibirsk, Russia 14-15 Nov. 2020 https://doi.org/10.1109/S.A.I.ence50533.2020.9303220
Alex Glushchenko, Andres Suarez, Anton Kolonin, Ben Goertzel, Oleg Baskov, A framework for relationship extraction from unstructured text via link grammar parsing, Proceedings Volume 10653, Next-Generation Analyst VI; 106530K (2018) https://doi.org/10.1117/12.2306550 Event: SPIE Defense + Security, 2018, Orlando, Florida, United States 27 April 2018
Lei Zhang, Yong Yu, Learning to Generate CGs from Domain Specific Sentences International Conference on Conceptual Structures, ICCS-ConceptStruct 2001: Conceptual Structures: Broadening the Base pp 44-57 Lecture Notes in Computer Science (LNCS, volume 2120)
Jianming Li, Lei Zhang, Yong Yu, Learning to Generate Semantic Annotation for Domain Specific Sentences Semannot@K-CAP 2001.
Batura T., Bakiyeva A., Yerimbetova A., Mitkovskaya M., Semenova N. "Methods for constructing natural language analyzers based on link grammar and rhetorical structure theory" // Computer Science. — 2016. — # 40. — P. 37–51.
Batura T., Murzin F., Semich D., Bakiyeva A., Yerimbetova A. "On some graphs connected with texts in a natural language, link grammar and the summarization process" // Computer Science. — 2015. — # 38. — P. 37-49.
Batura T., Murzin F., Bakiyeva A., Yerimbetova A. "The methods of estimation of the degree of similarity of sentences in a natural language based on the link grammar" // Computer Science. — 2014. — # 37. — P. 55-69.
Sajadi, A., Borujerdi, M. “Machine Translation Based on Unification Link Grammar” Journal of Artificial Intelligence Review. DOI=10.1007/s10462-011-9261-7, Pages 109-132, 2013.
Nguyễn Thị Thu Hương, Nguyễn Thúc Hải, Nguyễn Thanh Thủy, "Parsing complex - compound sentences with an extension of Vietnamese link parser combined with discourse segmenter", Journal of Computer Science and Cybernetics, Vol 28, No 4 (2012) DOI: 10.15625/1813-9663/28/4/1451 researchgate link
Jeff Elmore, "Parsing sentences with the OTHER natural language tool: LinkGrammar" YouTube video of presentation at the Python Convention, PYCON US 2012 (See also: the abstract).
Sajadi, A., Abdollahzadeh, A. “Farsi Syntactic Knowledge Representation using Link Grammar”, 2nd The Persian Language and Computer (Persian Coling), Volume 2, pp 659-684, 2010 (In Farsi)
Lonsdale, Deryle, and Hitokazu Matsushita. "Annotating and exploring Lushootseed morphosyntax." 44th Annual International Conference on Salish and Neighbouring Languages,(Eds. John Lyon and Joel Dunham), University of British Columbia Working Papers in Linguistics. Vol. 30. 2011.
Blake Lemoine, NLGen2: A Linguistically Plausible, General Purpose Natural Language Generation System (2009).
Alan Akbik, Jürgen Broß, "Wanderlust: Extracting Semantic Relations from Natural Language Text Using Dependency Grammar Patterns" SEMSE 2009
Akshar Bharati, Dipti Misra Sharma, Sukhada, Adapting Link Grammar Parser (LGP) to Paninian Framework Mapping of Parser Relations for Indian Languages (2009) National Seminar on Computer Science and its Applications in Traditional Shastras (CSATS'09) Report No: IIIT/TR/2009/218
Norshuhani Zamin, "Information Extraction Using Link Grammar", CSIE '09 Proceedings of the 2009 WRI World Congress on Computer Science and Information Engineering - Volume 05 Pages 149-153
Jorg Hakenberg, et al. Molecular event extraction from Link Grammar parse trees Proceedings of the Workshop on BioNLP: Shared Task, pages 86–94, Boulder, Colorado, June 2009
Teguh Bharata Adji, Baharum Baharudin, Norshuhani Zamin, "Applying Link Grammar Formalism in the Development of English-Indonesian Machine Translation System", Intelligent Computer Mathematics, 9th International Conference, AISC 2008, 15th Symposium, Calculemus 2008, 7th International Conference, MKM 2008, Birmingham, UK, Proceedings pp 17-23 DOI 10.1007/978-3-540-85110-3_3
Qingquan Wang, Lili Rong, Kai Yu, "Toward a Categorical Link Grammar for Knowledge Piece Generation in Emergency Decision-Making Support", NCM '08 Proceedings of the 2008 Fourth International Conference on Networked Computing and Advanced Information Management - Volume 02 Pages 732-735. doi 10.1109/NCM.2008.145
Denis Bechet, k-Valued Link Grammars are Learnable from Strings. 2008 Proceedings of FGVienna: The 8th Conference on Formal Grammar.
A.Sajadi and M.Borujerdi, "Syntactic Analysis using Unification Link Grammar", 12th Annual International CSI Computer Conference (CSISC'2007), Shahid Beheshti University, 20-22 February 2007)
Armin Sajadi, Abdollahzadeh, A., "Farsi Syntactic Analysis using Link Grammar" (In Farsi), Letter of Research Center of Intelligent Signal Processing, Vol 1(9), 25-37 (In Farsi), 2006.
Sajadi, A., Homayounpour, M., “Representation of Farsi Morphological Knowledge using Link Grammar” (In Farsi), Letter of Research Center of Intelligent Signal Processing, Vol 1(9), 41-55, 2006.
Filip Ginter, Sampo Pyysalo, Jorma Boberg, and Tapio Salakoski "Regular Approximation of Link Grammar", FinTAL 2006, LNAI 4139, pp. 564–575, 2006.
Sampo Pyysalo, Tapio Salakoski, Sophie Aubin and Adeline Nazarenko, "Lexical Adaptation of Link Grammar to the Biomedical Sublanguage: a Comparative Evaluation of Three Approaches". BMC Bioinformatics 2006.
Luis Tari and Chitta Baral, Using AnsProlog with Link Grammar and WordNet for QA with deep reasoning 9th International Conference on Information Technology (ICIT'06) pp.125-128 doi.ieeecomputersociety.org/10.1109/ICIT.2006.90
Schneider, Gerold (1998). "A Linguistic Comparison Constituency, Dependency, and Link Grammar". Masters Thesis, University of Zurich.
Özlem Istek, Ilyas Cicekli "A Link Grammar for an Agglutinative Language", Proceedings of Recent Advances in Natural Language Processing (RANLP 2007), Borovets, Bulgaria, 2007, pp: 285-290. (but also EACL-06 Proceedings ??)
Özlem Istek, "A Link Grammar for Turkish", Thesis, 2006
Shailly Goyal and Niladri Chatterjee, "Study of Hindi Noun Phrase Morphology for Developing a Link Grammar Parser", Language in India, Volume 5 : 8 August 2005
Fabian M. Suchanek, Georgiana Ifrim, Gerhard Weikum, "Combining Linguistic and Statistical Analysis to Extract Relations from Web Documents" (2006)
P. Szolovits, "Adding a Medical Lexicon to an English Parser". Proc. AMIA 2003 Annual Symposium. Pages 639-643. 2003.
Jing Ding, Daniel Berleant, Jun Xu, Andy W. Fulmer, "Extracting Biochemical Interactions from MEDLINE Using a Link Grammar Parser" Proceedings ICTAI 2003 Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence
Rania A. Abul Seoud, Nahed H. Solouma, Abou-Baker M. Youssef, and Yasser M. Kadah, "PIELG: A Protein Interaction Extraction System using a Link Grammar Parser from Biomedical Abstracts". International Journal of Biological, Biomedical and Medical Sciences 3;3 www.waset.org Summer 2008
I. Marshall and E. Safar, "Extraction of semantic representations from syntactic CMU link grammar linkages"
Trude Gentenaar, Job Tiel Groenestege, Ronald Poell, "Enhancement of unstructured and structured information". CLIN 2004 Proceedings Abstract Information Extraction.
Skripsi: Syntax Analysis of Bahasa Indonesia using Link Grammar Parsing Algorithm and ANALISIS SINTAKSIS BAHASA INDONESIA DENGAN ALGORITMA PENGURAI LINK GRAMMAR
Using LG and WordNet on Travel Domain.ppt (www.public.asu.edu)
Sandra Kubler "Learning a Lexicalized Grammar for German" NeMLaP3/CoNLL '98 Proceedings of the Joint Conferences on New Methods in Language Processing and Computational Natural Language Learning Pages 11-18

Some miscellaneous facts

Any categorical grammar can be easily converted to a link grammar; see section 6 of Daniel Sleator and Davy Temperley. 1993. "Parsing English with a Link Grammar." Third International Workshop on Parsing Technologies.
Link grammars can be learned by performing a statistical analysis on a large corpus: see John Lafferty, Daniel Sleator, and Davy Temperley. 1992. "Grammatical Trigrams: A Probabilistic Model of Link Grammar." Proceedings of the AAAI Conference on Probabilistic Approaches to Natural Language, October, 1992.

Psycholinguistic research on dependency

There are a number of interesting psychological and experimental analysis of the dependency properties of languages. Below is a selection that offers insight.

It turns out that writing an algorithm for a no-crossing minimum spanning tree is surprisingly painful; enforcing the no-crossing constraint requies treatment of a number of special cases. But perhaps this is not actually required! R. Ferrer i Cancho in “Why do syntactic links not cross?” EPL (Europhysics Letters) 76, 6 (2006), pp. 1228-1234. shows that, when attempting to arrange a random set of points on a line, in such a way as to minimize euclidean distances between connected points, one ends up with trees that almost never cross!
Crossings are rare: Havelka, J. (2007). Beyond projectivity: multilingual evaluation of constraints and measures on non-projective structures. In: Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics (ACL-07): 608-615. Prague, Czech Republic: Association for Computational Linguistics.
Hubbiness is a better model of sentence complexity than mean dependency distance: Ramon Ferrer-i-Cancho (2013) “Hubiness, length, crossings and their relationships in dependency trees”, ArXiv 1304.4086 --- also states: maximum number of crossings is bounded above by mean dependency length. Also, mean dependency length is bounded below by variance of degrees of vertexes (i.e. variance in number of connectors a word can have).
Language tends to be close to the theoretical minimum possible dependency distance, if it was legal to re-arrange words arbitrarily. See Temperley, D. (2008). Dependency length minimization in natural and artificial languages. Journal of Quantitative Linguistics, 15(3):256-282.
Park, Y. A. and Levy, R. (2009). Minimal-length linearizations for mildly context-sensitive dependency trees. In Proceedings of the North American Chapter of the Association for Computational Linguistics - Human Language Technologies (NAACL-HLT) conference.
Sentences with long dependencies are hard to understand: The original claim is from Yngve, 1960, having to do with phrase-structure depth. See -- Gibson, E. (2000). The dependency locality theory: A distance-based theory of linguistic complexity. In Marantz, A., Miyashita, Y., and O'Neil, W., editors, Image, Language, Brain. Papers from the first Mind Articulation Project Symposium. MIT Press, Cambridge, MA.
(Cite this, its good) Mean dependency distance is a good measure of sentence complexity -- for 20 languages -- Haitao Liu gives overview starting from Yngve. [Liu2008]. Haitao Liu “Dependency distance as a metric of language comprehension difficulty”, 2008, Journal of Cognitive Science, v9.2 pp 159-191 http://www.lingviko.net/JCS.pdf
Sentences with long dependencies are rarely spoken: Hawkins, J. A. (1994). A Performance Theory of Order and Constituency. Cambridge University Press, Cambridge, UK. ----Hawkins, J. A. (2004). Efficiency and Complexity in Grammars. Oxford University Press, Oxford, UK. ----Wasow, T. (2002). Postverbal Behavior. CSLI Publications, Stanford, CA. Distributed by University of Chicago Press.
Dependency-length minimzation is universal: Richard Futrell, Kyle Mahowald, and Edward Gibson, “Large-scale evidence of dependency length minimization in 37 languages” (2015), doi: 10.1073/pnas.1502134112

Of related interest

Genia tagger: The Genia tagger is useful for named entity extraction. BSD license source.
After the Deadline: After the Deadline is a GPL-licensed language-checking tool. If you just want to have your text proof-read, this is probably a good choice.