Generic Axiomatization of Families of Noncrossing Graphs in Dependency\n Parsing

2017/06/11 by Anssi Yli-Jyrä, Yli-Jyrä, Anssi, Carlos Gómez‐Rodríguez +1 · 2 citations
Computer Science · #68Q45 #68T50 #Algorithms and Data Compression #Computation and Language (cs.CL) #F.4.2 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #I.2.7 #Natural Language Processing Techniques #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1706.03357

openalex publication_date 2017/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a simple encoding for unlabeled noncrossing graphs and show how\nits latent counterpart helps us to represent several families of directed and\nundirected graphs used in syntactic and semantic parsing of natural language as\ncontext-free languages. The families are separated purely on the basis of\nforbidden patterns in latent encoding, eliminating the need to differentiate\nthe families of non-crossing graphs in inference algorithms: one algorithm\nworks for all when the search space can be controlled in parser input.\n

Cited by

• Hierarchical Bracketing Encodings for Dependency Parsing as Tagging
• Not All Linearizations Are Equally Data-Hungry in Sequence Labeling\n Parsing

Related

• Sequential Graph Dependency Parser
• Polynomial Graph Parsing with Non-Structural Reentrancies
• Dependency Graph Parsing as Sequence Labeling
• Please Mind the Root: Decoding Arborescences for Dependency Parsing
• Graph representation of context-free grammars