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/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

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ösJärjestettyjen verkkojen siirtymäpohjainen koodaus ja formaalien kielten teoria
Alkuperäiskielienglanti
OtsikkoThe 14th International Conference on Finite-State Methods and Natural Language Processing : Proceedings of the Conference
ToimittajatHeiko Vogler, Andreas Maletti
Sivumäärä14
JulkaisupaikkaStroudsburg
KustantajaThe Association for Computational Linguistics
Julkaisupäivä23 syyskuuta 2019
Sivut118–131
ISBN (elektroninen)978-1-950737-96-3
DOI - pysyväislinkit
TilaJulkaistu - 23 syyskuuta 2019
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Conference on Finite State Methods and Natural Language Processing - Dresden, Saksa
Kesto: 23 syyskuuta 201925 syyskuuta 2019
Konferenssinumero: 14

Julkaisusarja

NimiProceedings of the International Conference on Finite-State Methods and Natural Language Processing
KustantajaAssociation 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

Siteeraa tätä