On Dependency Analysis via Contractions and Weighted FSTs

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

Abstract

Arc contractions in syntactic dependency graphs can be used to decide which graphs are trees. The paper observes that these contractions can be expressed with weighted finite-state transducers (weighted FST) that operate on string-encoded trees. The observation gives rise to a finite-state parsing algorithm that computes the parse forest and extracts the best parses from it. The algorithm is customizable to functional and bilexical dependency parsing, and it can be extended to non-projective parsing via a multi-planar encoding with prior results on high recall. Our experiments support an analysis of projective parsing according to which the worst-case time complexity of the algorithm is quadratic to the sentence length, and linear to the overlapping arcs and the number of functional categories of the arcs. The results suggest several interesting directions towards efficient and highprecision dependency parsing that takes advantage of the flexibility and the demonstrated ambiguity-packing capacity of such a parser.
Original languageEnglish
Title of host publicationShall We Play the Festschrift Game?
EditorsDiana Santos, Wanjiku Nganga, Krister Lindén
Volume2012
Place of PublicationBerlin Heidelberg
PublisherSpringer-Verlag
Publication date2012
Pages133-158
ISBN (Print)978-3-642-30772-0
DOIs
Publication statusPublished - 2012
MoE publication typeA3 Book chapter

Fields of Science

  • 6121 Languages
  • DEPENDENCE TREES
  • dependency syntax
  • Dependency grammar
  • parsing
  • parsing theory
  • finite-state methods
  • regular expressions
  • weighted grammars
  • COMPLEXITY
  • 113 Computer and information sciences
  • complexity
  • finite-state transducers
  • weighted automata

Cite this

Yli-Jyrä, A. M. (2012). On Dependency Analysis via Contractions and Weighted FSTs. In D. Santos, W. Nganga, & K. Lindén (Eds.), Shall We Play the Festschrift Game? (Vol. 2012, pp. 133-158). Berlin Heidelberg: Springer-Verlag. https://doi.org/10.1007/978-3-642-30773-7_10
Yli-Jyrä, Anssi Mikael. / On Dependency Analysis via Contractions and Weighted FSTs. Shall We Play the Festschrift Game?. editor / Diana Santos ; Wanjiku Nganga ; Krister Lindén. Vol. 2012 Berlin Heidelberg : Springer-Verlag, 2012. pp. 133-158
@inbook{b05e818ecbc9477d96382a052032e905,
title = "On Dependency Analysis via Contractions and Weighted FSTs",
abstract = "Arc contractions in syntactic dependency graphs can be used to decide which graphs are trees. The paper observes that these contractions can be expressed with weighted finite-state transducers (weighted FST) that operate on string-encoded trees. The observation gives rise to a finite-state parsing algorithm that computes the parse forest and extracts the best parses from it. The algorithm is customizable to functional and bilexical dependency parsing, and it can be extended to non-projective parsing via a multi-planar encoding with prior results on high recall. Our experiments support an analysis of projective parsing according to which the worst-case time complexity of the algorithm is quadratic to the sentence length, and linear to the overlapping arcs and the number of functional categories of the arcs. The results suggest several interesting directions towards efficient and highprecision dependency parsing that takes advantage of the flexibility and the demonstrated ambiguity-packing capacity of such a parser.",
keywords = "6121 Languages, DEPENDENCE TREES, dependency syntax, Dependency grammar, parsing, parsing theory, finite-state methods, regular expressions, weighted grammars, COMPLEXITY, 113 Computer and information sciences, complexity, finite-state transducers, weighted automata",
author = "Yli-Jyr{\"a}, {Anssi Mikael}",
year = "2012",
doi = "10.1007/978-3-642-30773-7_10",
language = "English",
isbn = "978-3-642-30772-0",
volume = "2012",
pages = "133--158",
editor = "Diana Santos and Wanjiku Nganga and Krister Lind{\'e}n",
booktitle = "Shall We Play the Festschrift Game?",
publisher = "Springer-Verlag",
address = "Germany",

}

Yli-Jyrä, AM 2012, On Dependency Analysis via Contractions and Weighted FSTs. in D Santos, W Nganga & K Lindén (eds), Shall We Play the Festschrift Game?. vol. 2012, Springer-Verlag, Berlin Heidelberg, pp. 133-158. https://doi.org/10.1007/978-3-642-30773-7_10

On Dependency Analysis via Contractions and Weighted FSTs. / Yli-Jyrä, Anssi Mikael.

Shall We Play the Festschrift Game?. ed. / Diana Santos; Wanjiku Nganga; Krister Lindén. Vol. 2012 Berlin Heidelberg : Springer-Verlag, 2012. p. 133-158.

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

TY - CHAP

T1 - On Dependency Analysis via Contractions and Weighted FSTs

AU - Yli-Jyrä, Anssi Mikael

PY - 2012

Y1 - 2012

N2 - Arc contractions in syntactic dependency graphs can be used to decide which graphs are trees. The paper observes that these contractions can be expressed with weighted finite-state transducers (weighted FST) that operate on string-encoded trees. The observation gives rise to a finite-state parsing algorithm that computes the parse forest and extracts the best parses from it. The algorithm is customizable to functional and bilexical dependency parsing, and it can be extended to non-projective parsing via a multi-planar encoding with prior results on high recall. Our experiments support an analysis of projective parsing according to which the worst-case time complexity of the algorithm is quadratic to the sentence length, and linear to the overlapping arcs and the number of functional categories of the arcs. The results suggest several interesting directions towards efficient and highprecision dependency parsing that takes advantage of the flexibility and the demonstrated ambiguity-packing capacity of such a parser.

AB - Arc contractions in syntactic dependency graphs can be used to decide which graphs are trees. The paper observes that these contractions can be expressed with weighted finite-state transducers (weighted FST) that operate on string-encoded trees. The observation gives rise to a finite-state parsing algorithm that computes the parse forest and extracts the best parses from it. The algorithm is customizable to functional and bilexical dependency parsing, and it can be extended to non-projective parsing via a multi-planar encoding with prior results on high recall. Our experiments support an analysis of projective parsing according to which the worst-case time complexity of the algorithm is quadratic to the sentence length, and linear to the overlapping arcs and the number of functional categories of the arcs. The results suggest several interesting directions towards efficient and highprecision dependency parsing that takes advantage of the flexibility and the demonstrated ambiguity-packing capacity of such a parser.

KW - 6121 Languages

KW - DEPENDENCE TREES

KW - dependency syntax

KW - Dependency grammar

KW - parsing

KW - parsing theory

KW - finite-state methods

KW - regular expressions

KW - weighted grammars

KW - COMPLEXITY

KW - 113 Computer and information sciences

KW - complexity

KW - finite-state transducers

KW - weighted automata

U2 - 10.1007/978-3-642-30773-7_10

DO - 10.1007/978-3-642-30773-7_10

M3 - Chapter

SN - 978-3-642-30772-0

VL - 2012

SP - 133

EP - 158

BT - Shall We Play the Festschrift Game?

A2 - Santos, Diana

A2 - Nganga, Wanjiku

A2 - Lindén, Krister

PB - Springer-Verlag

CY - Berlin Heidelberg

ER -

Yli-Jyrä AM. On Dependency Analysis via Contractions and Weighted FSTs. In Santos D, Nganga W, Lindén K, editors, Shall We Play the Festschrift Game?. Vol. 2012. Berlin Heidelberg: Springer-Verlag. 2012. p. 133-158 https://doi.org/10.1007/978-3-642-30773-7_10