<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="yli-jyra-2019-transition">
    <titleInfo>
        <title>Transition-Based Coding and Formal Language Theory for Ordered Digraphs</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Anssi</namePart>
        <namePart type="family">Yli-Jyrä</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2019-09</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <relatedItem type="host">
        <titleInfo>
            <title>Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing</title>
        </titleInfo>
        <name type="personal">
            <namePart type="given">Heiko</namePart>
            <namePart type="family">Vogler</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Andreas</namePart>
            <namePart type="family">Maletti</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <originInfo>
            <publisher>Association for Computational Linguistics</publisher>
            <place>
                <placeTerm type="text">Dresden, Germany</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">conference publication</genre>
    </relatedItem>
    <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.</abstract>
    <identifier type="citekey">yli-jyra-2019-transition</identifier>
    <identifier type="doi">10.18653/v1/W19-3115</identifier>
    <location>
        <url>https://aclanthology.org/W19-3115</url>
    </location>
    <part>
        <date>2019-09</date>
        <extent unit="page">
            <start>118</start>
            <end>131</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Conference Proceedings
%T Transition-Based Coding and Formal Language Theory for Ordered Digraphs
%A Yli-Jyrä, Anssi
%Y Vogler, Heiko
%Y Maletti, Andreas
%S Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing
%D 2019
%8 September
%I Association for Computational Linguistics
%C Dresden, Germany
%F yli-jyra-2019-transition
%X 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.
%R 10.18653/v1/W19-3115
%U https://aclanthology.org/W19-3115
%U https://doi.org/10.18653/v1/W19-3115
%P 118-131

Markdown (Informal)

[Transition-Based Coding and Formal Language Theory for Ordered Digraphs](https://aclanthology.org/W19-3115) (Yli-Jyrä, FSMNLP 2019)

• Transition-Based Coding and Formal Language Theory for Ordered Digraphs (Yli-Jyrä, FSMNLP 2019)

ACL

• Anssi Yli-Jyrä. 2019. Transition-Based Coding and Formal Language Theory for Ordered Digraphs. In Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing, pages 118–131, Dresden, Germany. Association for Computational Linguistics.