Transition-Based Coding and Formal Language Theory for Ordered Digraphs

Show simple item record

dc.contributor.author Yli-Jyrä, Anssi
dc.contributor.editor Vogler, Heiko
dc.contributor.editor Maletti, Andreas
dc.date.accessioned 2019-11-11T12:51:01Z
dc.date.available 2019-11-11T12:51:01Z
dc.date.issued 2019-09-23
dc.identifier.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
dc.identifier.citation conference
dc.identifier.other PURE: 127685902
dc.identifier.other PURE UUID: 8dace6f1-d8ac-4b08-b355-c00d4436a61a
dc.identifier.other ORCID: /0000-0003-0731-2114/work/64663284
dc.identifier.uri http://hdl.handle.net/10138/306880
dc.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/).
dc.description.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. fi
dc.description.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. en
dc.format.extent 14
dc.language.iso eng
dc.publisher The Association for Computational Linguistics
dc.relation.ispartof The 14th International Conference on Finite-State Methods and Natural Language Processing
dc.relation.ispartofseries Proceedings of the International Conference on Finite-State Methods and Natural Language Processing
dc.relation.isversionof 978-1-950737-96-3
dc.rights cc_by
dc.rights.uri info:eu-repo/semantics/openAccess
dc.subject 113 Computer and information sciences
dc.subject graph representation
dc.subject encoding
dc.subject siirtymäjärjestelmöt
dc.subject 6121 Languages
dc.subject dependency syntax
dc.title Transition-Based Coding and Formal Language Theory for Ordered Digraphs en
dc.title.alternative Järjestettyjen verkkojen siirtymäpohjainen koodaus ja formaalien kielten teoria fi
dc.type Conference contribution
dc.contributor.organization Language Technology
dc.contributor.organization Department of Digital Humanities
dc.description.reviewstatus Peer reviewed
dc.relation.doi https://doi.org/10.18653/v1/w19-3115
dc.rights.accesslevel openAccess
dc.type.version publishedVersion
dc.identifier.url https://www.aclweb.org/anthology/volumes/W19-31/

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 simple item record