A Fundamental Algorithm for Dependency Parsing (With Corrections)
This work addresses natural language processing for linguists and AI researchers, but appears incremental as it adapts known complexity bounds to a new parsing approach.
The paper tackles dependency parsing by introducing an algorithm that processes words sequentially to build dependency trees, claiming alignment with human brain parsing properties, with a worst-case complexity of O(n^3) but noted to be rare in practice for small n.
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^3)$, but in human language, the worst case occurs only for small $n$.