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

Julkaisun otsikon käännös: Järjestettyjen verkkojen siirtymäpohjainen koodaus ja formaalien kielten teoria

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussa › Konferenssiartikkeli › Tieteellinen › vertaisarvioitu

Abstrakti

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 characterize 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.

Julkaisun otsikon käännös	Järjestettyjen verkkojen siirtymäpohjainen koodaus ja formaalien kielten teoria
Alkuperäiskieli	englanti
Otsikko	The 14th International Conference on Finite-State Methods and Natural Language Processing : Proceedings of the Conference
Toimittajat	Heiko Vogler, Andreas Maletti
Sivumäärä	14
Julkaisupaikka	Stroudsburg
Kustantaja	The Association for Computational Linguistics
Julkaisupäivä	23 syysk. 2019
Sivut	118–131
ISBN (elektroninen)	978-1-950737-96-3
DOI - pysyväislinkit	https://doi.org/10.18653/v1/w19-3115
Tila	Julkaistu - 23 syysk. 2019
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	International Conference on Finite State Methods and Natural Language Processing - Dresden, Saksa Kesto: 23 syysk. 2019 → 25 syysk. 2019 Konferenssinumero: 14

Julkaisusarja

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

Lisätietoja

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

Tieteenalat

113 Tietojenkäsittely- ja informaatiotieteet
graph representation
encoding
siirtymäjärjestelmöt
6121 Kielitieteet
dependency syntax

Pääsy asiakirjaan

10.18653/v1/w19-3115Lisenssi: CC BY

W19-3115Lopullinen julkaistu versio, 344 KBLisenssi: CC BY

Muut tiedostot ja linkit

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

Universal Dependencies version 2.4
Rueter, J. (Luoja), Tyers, F. M. (Avustaja (contributor)) & Zeman, D. (Avustaja (contributor)), Universal Dependencies Consortium, 15 toukok. 2019
http://hdl.handle.net/11234/1-2988.
Tietoaineisto

1 Akateeminen vierailu toiseen organisaatioon

The Rachel and Selim Benin School of Engineering and Computer Science, The Hebrew University of Jerusalem, Israel
Anssi Yli-Jyrä (Vieraileva tutkija), Mirjam Ronning (Muu rooli), Halvor Ronning (Muu rooli) & Omri Abend (Muu rooli)
1 tammik. 2020 → 17 tammik. 2020
Aktiviteetti: Ulkoisessa instituutiossa vierailun tyypit › Akateeminen vierailu toiseen organisaatioon

Siteeraa tätä

Yli-Jyrä, A. (2019). Transition-Based Coding and Formal Language Theory for Ordered Digraphs. teoksessa H. Vogler, & A. Maletti (Toimittajat), The 14th International Conference on Finite-State Methods and Natural Language Processing: Proceedings of the Conference (Sivut 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. Toimittaja / Heiko Vogler ; Andreas Maletti. Stroudsburg : The Association for Computational Linguistics, 2019. Sivut 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. julkaisussa H Vogler & A Maletti (toim), 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, Sivut 118–131, International Conference on Finite State Methods and Natural Language Processing, Dresden, Saksa, 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. toim. / 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).

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussa › Konferenssiartikkeli › Tieteellinen › vertaisarvioitu

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. julkaisussa Vogler H, Maletti A, toimittajat, 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

Abstrakti

Julkaisusarja

Lisätietoja

Tieteenalat

Pääsy asiakirjaan

Muut tiedostot ja linkit

Tietoaineistot

Universal Dependencies version 2.4

Aktiviteetit

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

Siteeraa tätä