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

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

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.

Translated title of the contribution	Järjestettyjen verkkojen siirtymäpohjainen koodaus ja formaalien kielten teoria
Original language	English
Title of host publication	The 14th International Conference on Finite-State Methods and Natural Language Processing : Proceedings of the Conference
Editors	Heiko Vogler, Andreas Maletti
Number of pages	14
Place of Publication	Stroudsburg
Publisher	The Association for Computational Linguistics
Publication date	23 Sept 2019
Pages	118–131
ISBN (Electronic)	978-1-950737-96-3
DOIs	https://doi.org/10.18653/v1/w19-3115
Publication status	Published - 23 Sept 2019
MoE publication type	A4 Article in conference proceedings
Event	International Conference on Finite State Methods and Natural Language Processing - Dresden, Germany Duration: 23 Sept 2019 → 25 Sept 2019 Conference number: 14

Publication series

Name	Proceedings of the International Conference on Finite-State Methods and Natural Language Processing
Publisher	Association for Computational Linguistics

Bibliographical 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/).

Fields of Science

113 Computer and information sciences
6121 Languages

Access to Document

10.18653/v1/w19-3115Licence: CC BY

W19-3115Final published version, 344 KBLicence: CC BY

Cite this

Yli-Jyrä, A. (2019). Transition-Based Coding and Formal Language Theory for Ordered Digraphs. In H. Vogler, & A. Maletti (Eds.), The 14th International Conference on Finite-State Methods and Natural Language Processing: Proceedings of the Conference (pp. 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. editor / Heiko Vogler ; Andreas Maletti. Stroudsburg : The Association for Computational Linguistics, 2019. pp. 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. in H Vogler & A Maletti (eds), 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, pp. 118–131, International Conference on Finite State Methods and Natural Language Processing, Dresden, Germany, 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. ed. / Heiko Vogler; Andreas Maletti. Stroudsburg: The Association for Computational Linguistics, 2019. p. 118–131 (Proceedings of the International Conference on Finite-State Methods and Natural Language Processing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › 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. In Vogler H, Maletti A, editors, The 14th International Conference on Finite-State Methods and Natural Language Processing: Proceedings of the Conference. Stroudsburg: The Association for Computational Linguistics. 2019. p. 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

Abstract

Publication series

Bibliographical note

Fields of Science

Access to Document

Other files and links

Universal Dependencies version 2.4

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

Cite this

Transition-Based Coding and Formal Language Theory for Ordered Digraphs

Abstract

Publication series

Bibliographical note

Fields of Science

Access to Document

Other files and links

Datasets

Universal Dependencies version 2.4

Activities

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

Cite this