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

Language Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

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 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 contribution	Risteämättömien verkkojen perheiden yleinen aksiomatisointi dependenssijäsentämisessä
Original language	English
Title of host publication	Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
Editors	Regina Barzilay, Min-Yen Kan
Number of pages	11
Place of Publication	Stroudsburg
Publisher	The Association for Computational Linguistics
Publication date	2017
Pages	1745-1755
ISBN (Electronic)	978-1-945626-75-3
DOIs	https://doi.org/10.18653/v1/P17-1160
Publication status	Published - 2017
MoE publication type	A4 Article in conference proceedings
Event	Annual Meeting of the Association for Computational Linguistics - Vancouver, Canada Duration: 30 Jul 2017 → 4 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

Access to Document

10.18653/v1/P17-1160

P17-1160Final published version, 242 KBLicence: CC BY

Cite this

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

@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. in R Barzilay & M-Y Kan (eds), Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). The Association for Computational Linguistics, Stroudsburg, pp. 1745-1755, Annual Meeting of the Association for Computational Linguistics, Vancouver, Canada, 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). ed. / Regina Barzilay; Min-Yen Kan. Stroudsburg : The Association for Computational Linguistics, 2017. p. 1745-1755.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › 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. In Barzilay R, Kan M-Y, editors, Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Stroudsburg: The Association for Computational Linguistics. 2017. p. 1745-1755 Epub 2017. doi: 10.18653/v1/P17-1160

Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing

Abstract

Fields of Science

Access to Document

Other files and links

ADEQSYNTAX: A Usable Finite-State Model for Adequate Syntactic Complexity

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

Department of Engineering, University of Cambridge

Cite this

Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing

Abstract

Fields of Science

Access to Document

Other files and links

Projects

ADEQSYNTAX: A Usable Finite-State Model for Adequate Syntactic Complexity

Activities

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

Department of Engineering, University of Cambridge

Cite this