Transition-Based Coding and Formal Language Theory for Ordered Digraphs

Anssi Yli-Jyrä

doi:10.18653/v1/w19-3115

Transition-Based Coding and Formal Language Theory for Ordered Digraphs

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

Sammanfattning

Transition-based parsing of natural language uses transition systems to build directed annotation graphs (digraphs) for sentences. In this paper, we define, for an arbitrary ordered digraph, a unique decomposition and a corresponding linear encoding that are associated bijectively with each other via a new transition system. These results give us an efficient and succinct representation for digraphs and sets of digraphs. Based on the system and our analysis of its syntactic properties, we give structural bounds under which the set of encoded digraphs is restricted and becomes a context-free or a regular string language. The context-free restriction is essentially a superset of the encodings used previously to characterise properties of noncrossing digraphs and to solve maximal subgraphs problems. The regular restriction with a tight bound is shown to capture the Universal Dependencies v2.4 treebanks in linguistics.

Bidragets översatta titel	Järjestettyjen verkkojen siirtymäpohjainen koodaus ja formaalien kielten teoria
Originalspråk	engelska
Titel på värdpublikation	The 14th International Conference on Finite-State Methods and Natural Language Processing : Proceedings of the Conference
Redaktörer	Heiko Vogler, Andreas Maletti
Antal sidor	14
Utgivningsort	Stroudsburg
Förlag	The Association for Computational Linguistics
Utgivningsdatum	23 sep. 2019
Sidor	118–131
ISBN (elektroniskt)	978-1-950737-96-3
DOI	https://doi.org/10.18653/v1/w19-3115
Status	Publicerad - 23 sep. 2019
MoE-publikationstyp	A4 Artikel i en konferenspublikation
Evenemang	International Conference on Finite State Methods and Natural Language Processing - Dresden, Tyskland Varaktighet: 23 sep. 2019 → 25 sep. 2019 Konferensnummer: 14

Publikationsserier

Namn	Proceedings of the International Conference on Finite-State Methods and Natural Language Processing
Förlag	Association for Computational Linguistics

Bibliografisk information

The ISBN of the host publication can be found on the web site of the conference (https://wwwtcs.inf.tu-dresden.de/fsmnlp2019/accepted_papers/).

Vetenskapsgrenar

113 Data- och informationsvetenskap
6121 Språkvetenskaper

Åtkomst av dokument

10.18653/v1/w19-3115Licens: CC BY

W19-3115Slutlig publicerad version, 344 KBLicens: CC BY

Andra filer och länkar

https://www.aclweb.org/anthology/volumes/W19-31/

Universal Dependencies version 2.4
Rueter, J. (Skapad av), Tyers, F. M. (Medverkande) & Zeman, D. (Medverkande), Universal Dependencies Consortium, 15 maj 2019
http://hdl.handle.net/11234/1-2988.
Datauppsättning

1 Akademisk besök på annan institution

The Rachel and Selim Benin School of Engineering and Computer Science, The Hebrew University of Jerusalem, Israel
Anssi Yli-Jyrä (Besökande forskare), Mirjam Ronning (Annan roll), Halvor Ronning (Annan roll) & Omri Abend (Annan roll)
1 jan. 2020 → 17 jan. 2020
Aktivitet: Typer för besök till extern institution › Akademisk besök på annan institution

Citera det här

Yli-Jyrä, A. (2019). Transition-Based Coding and Formal Language Theory for Ordered Digraphs. I H. Vogler, & A. Maletti (Red.), The 14th International Conference on Finite-State Methods and Natural Language Processing: Proceedings of the Conference (s. 118–131). (Proceedings of the International Conference on Finite-State Methods and Natural Language Processing). The Association for Computational Linguistics. https://doi.org/10.18653/v1/w19-3115

Yli-Jyrä, Anssi. / Transition-Based Coding and Formal Language Theory for Ordered Digraphs. The 14th International Conference on Finite-State Methods and Natural Language Processing: Proceedings of the Conference. redaktör / Heiko Vogler ; Andreas Maletti. Stroudsburg : The Association for Computational Linguistics, 2019. s. 118–131 (Proceedings of the International Conference on Finite-State Methods and Natural Language Processing).

@inproceedings{8dace6f1d8ac4b08b355c00d4436a61a,

title = "Transition-Based Coding and Formal Language Theory for Ordered Digraphs",

abstract = "Transition-based parsing of natural language uses transition systems to build directed annotation graphs (digraphs) for sentences. In this paper, we define, for an arbitrary ordered digraph, a unique decomposition and a corresponding linear encoding that are associated bijectively with each other via a new transition system. These results give us an efficient and succinct representation for digraphs and sets of digraphs. Based on the system and our analysis of its syntactic properties, we give structural bounds under which the set of encoded digraphs is restricted and becomes a context-free or a regular string language. The context-free restriction is essentially a superset of the encodings used previously to characterise properties of noncrossing digraphs and to solve maximal subgraphs problems. The regular restriction with a tight bound is shown to capture the Universal Dependencies v2.4 treebanks in linguistics.",

keywords = "113 Computer and information sciences, graph representation, encoding, siirtym{\"a}j{\"a}rjestelm{\"o}t, 6121 Languages, dependency syntax",

author = "Anssi Yli-Jyr{\"a}",

note = "The ISBN of the host publication can be found on the web site of the conference (https://wwwtcs.inf.tu-dresden.de/fsmnlp2019/accepted_papers/).; International Conference on Finite State Methods and Natural Language Processing, FSMNLP 2019 ; Conference date: 23-09-2019 Through 25-09-2019",

year = "2019",

month = sep,

day = "23",

doi = "10.18653/v1/w19-3115",

language = "English",

series = "Proceedings of the International Conference on Finite-State Methods and Natural Language Processing",

publisher = "The Association for Computational Linguistics",

pages = "118–131",

editor = "Heiko Vogler and Andreas Maletti",

booktitle = "The 14th International Conference on Finite-State Methods and Natural Language Processing",

address = "United States",

}

Yli-Jyrä, A 2019, Transition-Based Coding and Formal Language Theory for Ordered Digraphs. i H Vogler & A Maletti (red), The 14th International Conference on Finite-State Methods and Natural Language Processing: Proceedings of the Conference. Proceedings of the International Conference on Finite-State Methods and Natural Language Processing, The Association for Computational Linguistics, Stroudsburg, s. 118–131, International Conference on Finite State Methods and Natural Language Processing, Dresden, Tyskland, 23/09/2019. https://doi.org/10.18653/v1/w19-3115

Transition-Based Coding and Formal Language Theory for Ordered Digraphs. / Yli-Jyrä, Anssi.

The 14th International Conference on Finite-State Methods and Natural Language Processing: Proceedings of the Conference. red. / Heiko Vogler; Andreas Maletti. Stroudsburg : The Association for Computational Linguistics, 2019. s. 118–131 (Proceedings of the International Conference on Finite-State Methods and Natural Language Processing).

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

TY - GEN

T1 - Transition-Based Coding and Formal Language Theory for Ordered Digraphs

AU - Yli-Jyrä, Anssi

N1 - Conference code: 14

PY - 2019/9/23

Y1 - 2019/9/23

N2 - Transition-based parsing of natural language uses transition systems to build directed annotation graphs (digraphs) for sentences. In this paper, we define, for an arbitrary ordered digraph, a unique decomposition and a corresponding linear encoding that are associated bijectively with each other via a new transition system. These results give us an efficient and succinct representation for digraphs and sets of digraphs. Based on the system and our analysis of its syntactic properties, we give structural bounds under which the set of encoded digraphs is restricted and becomes a context-free or a regular string language. The context-free restriction is essentially a superset of the encodings used previously to characterise properties of noncrossing digraphs and to solve maximal subgraphs problems. The regular restriction with a tight bound is shown to capture the Universal Dependencies v2.4 treebanks in linguistics.

AB - Transition-based parsing of natural language uses transition systems to build directed annotation graphs (digraphs) for sentences. In this paper, we define, for an arbitrary ordered digraph, a unique decomposition and a corresponding linear encoding that are associated bijectively with each other via a new transition system. These results give us an efficient and succinct representation for digraphs and sets of digraphs. Based on the system and our analysis of its syntactic properties, we give structural bounds under which the set of encoded digraphs is restricted and becomes a context-free or a regular string language. The context-free restriction is essentially a superset of the encodings used previously to characterise properties of noncrossing digraphs and to solve maximal subgraphs problems. The regular restriction with a tight bound is shown to capture the Universal Dependencies v2.4 treebanks in linguistics.

KW - 113 Computer and information sciences

KW - graph representation

KW - encoding

KW - siirtymäjärjestelmöt

KW - 6121 Languages

KW - dependency syntax

UR - https://www.aclweb.org/anthology/volumes/W19-31/

U2 - 10.18653/v1/w19-3115

DO - 10.18653/v1/w19-3115

M3 - Conference contribution

T3 - Proceedings of the International Conference on Finite-State Methods and Natural Language Processing

SP - 118

EP - 131

BT - The 14th International Conference on Finite-State Methods and Natural Language Processing

A2 - Vogler, Heiko

A2 - Maletti, Andreas

PB - The Association for Computational Linguistics

CY - Stroudsburg

T2 - International Conference on Finite State Methods and Natural Language Processing

Y2 - 23 September 2019 through 25 September 2019

ER -

Yli-Jyrä A. Transition-Based Coding and Formal Language Theory for Ordered Digraphs. I Vogler H, Maletti A, redaktörer, The 14th International Conference on Finite-State Methods and Natural Language Processing: Proceedings of the Conference. Stroudsburg: The Association for Computational Linguistics. 2019. s. 118–131. (Proceedings of the International Conference on Finite-State Methods and Natural Language Processing). doi: 10.18653/v1/w19-3115

Transition-Based Coding and Formal Language Theory for Ordered Digraphs

Sammanfattning

Publikationsserier

Bibliografisk information

Vetenskapsgrenar

Åtkomst av dokument

Andra filer och länkar

Forskningsdatauppsättningar

Universal Dependencies version 2.4

Aktiviteter

The Rachel and Selim Benin School of Engineering and Computer Science, The Hebrew University of Jerusalem, Israel

Citera det här