Transition-Based Coding and Formal Language Theory for Ordered Digraphs

Show full item record



Permalink

http://hdl.handle.net/10138/306880

Citation

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

Title: Transition-Based Coding and Formal Language Theory for Ordered Digraphs
Alternative title: Järjestettyjen verkkojen siirtymäpohjainen koodaus ja formaalien kielten teoria
Author: Yli-Jyrä, Anssi
Other contributor: Vogler, Heiko
Maletti, Andreas
Contributor organization: Language Technology
Department of Digital Humanities
Publisher: The Association for Computational Linguistics
Date: 2019-09-23
Language: eng
Number of pages: 14
Belongs to series: The 14th International Conference on Finite-State Methods and Natural Language Processing
Belongs to series: Proceedings of the International Conference on Finite-State Methods and Natural Language Processing
ISBN: 978-1-950737-96-3
DOI: https://doi.org/10.18653/v1/w19-3115
URI: http://hdl.handle.net/10138/306880
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 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.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.
Description: 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/).
Subject: 113 Computer and information sciences
graph representation
encoding
siirtymäjärjestelmöt
6121 Languages
dependency syntax
Peer reviewed: Yes
Rights: cc_by
Usage restriction: openAccess
Self-archived version: publishedVersion


Files in this item

Total number of downloads: Loading...

Files Size Format View
W19_3115.pdf 343.8Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record