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
Author: Yli-Jyrä, Anssi
Editor: Vogler, Heiko; Maletti, Andreas
Contributor: University of Helsinki, Language Technology
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 Proceedings of the Conference
Belongs to series: Proceedings of the International Conference on Finite-State Methods and Natural Language Processing
ISBN: 978-1-950737-96-3
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.
Subject: 113 Computer and information sciences
graph representation
encoding
siirtymäjärjestelmöt
6121 Languages
dependency syntax
Rights:


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