Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing

Anssi Mikael Yli-Jyrä, Carlos Gómez-Rodríguez

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


We present a simple encoding for unlabeled noncrossing graphs and show how its latent counterpart helps us to represent several families of directed and undirected graphs used in syntactic and semantic
parsing of natural language as context-free languages. The families are separated purely on the basis of forbidden patterns in latent encoding, eliminating the need to differentiate the families of non-crossing
graphs in inference algorithms: one algorithm works for all when the search space can be controlled in parser input.
Translated title of the contributionRisteämättömien verkkojen perheiden yleinen aksiomatisointi dependenssijäsentämisessä
Original languageEnglish
Title of host publicationProceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
EditorsRegina Barzilay, Min-Yen Kan
Number of pages11
Place of PublicationStroudsburg
PublisherThe Association for Computational Linguistics
Publication date2017
ISBN (Electronic)978-1-945626-75-3
Publication statusPublished - 2017
MoE publication typeA4 Article in conference proceedings
EventAnnual Meeting of the Association for Computational Linguistics - Vancouver, Canada
Duration: 30 Jul 20174 Aug 2017
Conference number: 55

Fields of Science

  • 6121 Languages
  • dependency graphs
  • semantic graphs
  • ambiguity
  • 113 Computer and information sciences
  • homomorphic representations of languages
  • context-free parsing
  • constrained inference
  • dependency graphs
  • acyclicity
  • connectivity
  • ambiguity
  • monadic second-order logic
  • Courcelle's theorem
  • 111 Mathematics
  • integer sequences
  • OEIS
  • enumerative graph theory

Cite this