Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing

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

doi:10.18653/v1/P17-1160

Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing

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

Språkteknologi

Forskningsoutput: Kapitel i bok/rapport/konferenshandling › Konferensbidrag › Vetenskaplig › Peer review

Sammanfattning

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.

Bidragets översatta titel	Risteämättömien verkkojen perheiden yleinen aksiomatisointi dependenssijäsentämisessä
Originalspråk	engelska
Titel på värdpublikation	Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
Redaktörer	Regina Barzilay, Min-Yen Kan
Antal sidor	11
Utgivningsort	Stroudsburg
Förlag	The Association for Computational Linguistics
Utgivningsdatum	2017
Sidor	1745-1755
ISBN (elektroniskt)	978-1-945626-75-3
DOI	https://doi.org/10.18653/v1/P17-1160
Status	Publicerad - 2017
MoE-publikationstyp	A4 Artikel i en konferenspublikation
Evenemang	Annual Meeting of the Association for Computational Linguistics - Vancouver, Kanada Varaktighet: 30 juli 2017 → 4 aug. 2017 Konferensnummer: 55

Vetenskapsgrenar

6121 Språkvetenskaper
113 Data- och informationsvetenskap
111 Matematik

Åtkomst av dokument

10.18653/v1/P17-1160

P17-1160Slutlig publicerad version, 242 KBLicens: CC BY

Andra filer och länkar

https://arxiv.org/abs/1706.03357

ADEQSYNTAX: Käytettävä äärellistilainen malli adekvaatille kieliopilliselle kompleksisuudelle
Yli-Jyrä, A.
Suomen tietokirjailijat
01/09/2013 → 30/04/2019
Projekt: Forskningsprojekt

1 !!Oral presentation
1 Akademisk besök på annan institution

Embedding Properties of Graphs to the String Space (talk at the Hebrew University, Jerusalem)
Anssi Yli-Jyrä (!!Speaker)
7 nov. 2018
Aktivitet: Typer för tal eller presentation › !!Oral presentation
Department of Engineering, University of Cambridge
Anssi Yli-Jyrä (Besökande forskare)
23 sep. 2013 → 30 juni 2014
Aktivitet: Typer för besök till extern institution › Akademisk besök på annan institution

Citera det här

Yli-Jyrä, A. M., & Gómez-Rodríguez, C. (2017). Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing. I R. Barzilay, & M-Y. Kan (Red.), Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) (s. 1745-1755). The Association for Computational Linguistics. https://doi.org/10.18653/v1/P17-1160

Yli-Jyrä, Anssi Mikael ; Gómez-Rodríguez, Carlos. / Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing. Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). redaktör / Regina Barzilay ; Min-Yen Kan. Stroudsburg : The Association for Computational Linguistics, 2017. s. 1745-1755

@inproceedings{2cb6c88cb4e546acb1f43ddee0f13886,

title = "Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing",

abstract = "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 semanticparsing 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-crossinggraphs in inference algorithms: one algorithm works for all when the search space can be controlled in parser input.",

keywords = "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",

author = "Yli-Jyr{\"a}, {Anssi Mikael} and Carlos G{\'o}mez-Rodr{\'i}guez",

note = " Proceeding volume: 55; Annual Meeting of the Association for Computational Linguistics ; Conference date: 30-07-2017 Through 04-08-2017",

year = "2017",

doi = "10.18653/v1/P17-1160",

language = "English",

pages = "1745--1755",

editor = "Regina Barzilay and Min-Yen Kan",

booktitle = "Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)",

publisher = "The Association for Computational Linguistics",

address = "United States",

}

Yli-Jyrä, AM & Gómez-Rodríguez, C 2017, Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing. i R Barzilay & M-Y Kan (red), Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). The Association for Computational Linguistics, Stroudsburg, s. 1745-1755, Annual Meeting of the Association for Computational Linguistics, Vancouver, Kanada, 30/07/2017. https://doi.org/10.18653/v1/P17-1160

Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing. / Yli-Jyrä, Anssi Mikael; Gómez-Rodríguez, Carlos.

Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). red. / Regina Barzilay; Min-Yen Kan. Stroudsburg : The Association for Computational Linguistics, 2017. s. 1745-1755.

Forskningsoutput: Kapitel i bok/rapport/konferenshandling › Konferensbidrag › Vetenskaplig › Peer review

TY - GEN

T1 - Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing

AU - Yli-Jyrä, Anssi Mikael

AU - Gómez-Rodríguez, Carlos

N1 - Conference code: 55

PY - 2017

Y1 - 2017

N2 - 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 semanticparsing 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-crossinggraphs in inference algorithms: one algorithm works for all when the search space can be controlled in parser input.

AB - 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 semanticparsing 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-crossinggraphs in inference algorithms: one algorithm works for all when the search space can be controlled in parser input.

KW - 6121 Languages

KW - dependency graphs

KW - semantic graphs

KW - ambiguity

KW - 113 Computer and information sciences

KW - homomorphic representations of languages

KW - context-free parsing

KW - constrained inference

KW - dependency graphs

KW - acyclicity

KW - connectivity

KW - ambiguity

KW - monadic second-order logic

KW - Courcelle's theorem

KW - 111 Mathematics

KW - integer sequences

KW - OEIS

KW - enumerative graph theory

UR - https://arxiv.org/abs/1706.03357

U2 - 10.18653/v1/P17-1160

DO - 10.18653/v1/P17-1160

M3 - Conference contribution

SP - 1745

EP - 1755

BT - Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)

A2 - Barzilay, Regina

A2 - Kan, Min-Yen

PB - The Association for Computational Linguistics

CY - Stroudsburg

T2 - Annual Meeting of the Association for Computational Linguistics

Y2 - 30 July 2017 through 4 August 2017

ER -

Yli-Jyrä AM, Gómez-Rodríguez C. Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing. I Barzilay R, Kan M-Y, redaktörer, Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Stroudsburg: The Association for Computational Linguistics. 2017. s. 1745-1755 Epub 2017. doi: 10.18653/v1/P17-1160

Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing

Sammanfattning

Vetenskapsgrenar

Åtkomst av dokument

Andra filer och länkar

Projekt

ADEQSYNTAX: Käytettävä äärellistilainen malli adekvaatille kieliopilliselle kompleksisuudelle

Aktiviteter

Embedding Properties of Graphs to the String Space (talk at the Hebrew University, Jerusalem)

Department of Engineering, University of Cambridge

Citera det här