A Fundamental Algorithm for Dependency Parsing (With Corrections)

• URL: http://arxiv.org/abs/2510.19996v1
• Date: Wed, 22 Oct 2025 19:48:38 GMT
• Title: A Fundamental Algorithm for Dependency Parsing (With Corrections)
• Authors: Michael A. Covington,
• Abstract summary: This paper presents a fundamental algorithm for parsing natural language sentences into dependency trees.<n>Unlike phrase-structure parsing, this algorithm operates one word at a time, attaching each word as soon as it can be attached.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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^3)$, but in human language, the worst case occurs only for small $n$.

Related papers

• Integrating Supertag Features into Neural Discontinuous Constituent Parsing [0.0]
  Traditional views of constituency demand that constituents consist of adjacent words, common in languages like German. Transition-based parsing produces trees given raw text input using supervised learning on large annotated corpora.
  arXiv  Detail & Related papers  (2024-10-11T12:28:26Z)
• Urdu Dependency Parsing and Treebank Development: A Syntactic and Morphological Perspective [0.0]
  We use dependency parsing to analyze news articles in Urdu. We achieve a best-labeled accuracy (LA) of 70% and an unlabeled attachment score (UAS) of 84%.
  arXiv  Detail & Related papers  (2024-06-13T19:30:32Z)
• Structured Tree Alignment for Evaluation of (Speech) Constituency Parsing [43.758912958903494]
  We present the structured average intersection-over-union ratio (STRUCT-IOU), a similarity metric between constituency parse trees motivated by the problem of evaluating speechs. To compute the metric, we project the ground-truth parse tree to the speech domain by forced alignment, align the projected ground-truth constituents with the predicted ones under certain structured constraints, and calculate the average IOU score across all aligned constituent pairs.
  arXiv  Detail & Related papers  (2024-02-21T00:01:17Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  Four formalisms are equivalent to tree-adjoining grammars (TAG), linear indexed grammars (LIG), pushdown-adjoining automata (PAA) and embedded pushdown automata (EPDA) We design new algorithms for computing their stringsum derivations (the weight of all automatons of a string) and allsums (the weight of all derivations) For EPDA, our algorithm is both more space-efficient and time-efficient than the algorithm of Alonso et al. (2001) by factors of $mathcalO(|Gamma|2)$ and $
  arXiv  Detail & Related papers  (2023-10-23T18:26:00Z)
• Hexatagging: Projective Dependency Parsing as Tagging [63.5392760743851]
  We introduce a novel dependency, the hexatagger, that constructs dependency trees by tagging the words in a sentence with elements from a finite set of possible tags. Our approach is fully parallelizable at training time, i.e., the structure-building actions needed to build a dependency parse can be predicted in parallel to each other. We achieve state-of-the-art performance of 96.4 LAS and 97.4 UAS on the Penn Treebank test set.
  arXiv  Detail & Related papers  (2023-06-08T18:02:07Z)
• Penn-Helsinki Parsed Corpus of Early Modern English: First Parsing Results and Analysis [2.8749014299466444]
  We present the first parsing results on the Penn-Helsinki Parsed Corpus of Early Modern English (PPCEME), a 1.9 million word treebank. We describe key features of PPCEME that make it challenging for parsing, including a larger and more varied set of function tags than in the Penn Treebank.
  arXiv  Detail & Related papers  (2021-12-15T23:56:21Z)
• Generalized Optimal Linear Orders [9.010643838773477]
  The sequential structure of language, and the order of words in a sentence specifically, plays a central role in human language processing. In designing computational models of language, the de facto approach is to present sentences to machines with the words ordered in the same order as in the original human-authored sentence. The very essence of this work is to question the implicit assumption that this is desirable and inject theoretical soundness into the consideration of word order in natural language processing.
  arXiv  Detail & Related papers  (2021-08-13T13:10:15Z)
• Head-driven Phrase Structure Parsing in O($n^3$) Time Complexity [48.683350567504604]
  Constituent and dependency parsing, the two classic forms of syntactic parsing, have been found to benefit from joint training and decoding under a uniform formalism. We propose an improved head scorer that helps achieve a novel performance-preserved in $O$($n3$) time complexity.
  arXiv  Detail & Related papers  (2021-05-20T15:33:51Z)
• Strongly Incremental Constituency Parsing with Graph Neural Networks [70.16880251349093]
  Parsing sentences into syntax trees can benefit downstream applications in NLP. Transition-baseds build trees by executing actions in a state transition system. Existing transition-baseds are predominantly based on the shift-reduce transition system.
  arXiv  Detail & Related papers  (2020-10-27T19:19:38Z)
• Fast semantic parsing with well-typedness guarantees [78.76675218975768]
  AM dependency parsing is a principled method for neural semantic parsing with high accuracy across multiple graphbanks. We describe an A* and a transition-based for AM dependency parsing which guarantee well-typedness and improve parsing speed by up to 3 orders of magnitude.
  arXiv  Detail & Related papers  (2020-09-15T21:54:01Z)
• A Simple Global Neural Discourse Parser [61.728994693410954]
  We propose a simple chart-based neural discourse that does not require any manually-crafted features and is based on learned span representations only. We empirically demonstrate that our model achieves the best performance among globals, and comparable performance to state-of-art greedys.
  arXiv  Detail & Related papers  (2020-09-02T19:28:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.