A Fundamental Algorithm for Dependency Parsing (With Corrections)

2025/10/22 by Michael A. Covington, Covington, Michael A.
Computer Science · #Algorithms and Data Compression #Computation and Language (cs.CL) #FOS: Computer and information sciences #Machine Learning and Algorithms #Natural Language Processing Techniques

paper · pdf · doi:10.48550/arxiv.2510.19996

openalex publication_date 2025/10/22 · openalex created_date 2025/10/25 · openalex updated_date 2026/07/28

Abstract

This paper presents a fundamental algorithm for parsing natural language sentences into dependency trees. Unlike phrase-structure (constituency) parsers, this algorithm operates one word at a time, attaching each word as soon as it can be attached, corresponding to properties claimed for the parser in the human brain. Like phrase-structure parsing, its worst-case complexity is O(n³), but in human language, the worst case occurs only for small n.

Citations

• An Efficient Implementation of the Head-Corner Parser

Related

• Parsing as Reduction
• Dependency Parsing as Head Selection
• Please Mind the Root: Decoding Arborescences for Dependency Parsing
• Universal Dependency Parsing from Scratch
• A Survey of Unsupervised Dependency Parsing