The expected sum of edge lengths in planar linearizations of trees

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3ANHTSS7K8" target="_blank" >RIV/00216208:11320/25:NHTSS7K8 - isvavai.cz</a>

Result on the web

<a href="https://www.scopus.com/inward/record.uri?eid=2-s2.0-85188338511&doi=10.15398%2fjlm.v12i1.362&partnerID=40&md5=ae510ecacbed631e27e96f2ddead0113" target="_blank" >https://www.scopus.com/inward/record.uri?eid=2-s2.0-85188338511&doi=10.15398%2fjlm.v12i1.362&partnerID=40&md5=ae510ecacbed631e27e96f2ddead0113</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.15398/jlm.v12i1.362" target="_blank" >10.15398/jlm.v12i1.362</a>

Result language

angličtina

Original language name

The expected sum of edge lengths in planar linearizations of trees

Original language description

Dependency trees have proven to be a very successful model to represent the syntactic structure of sentences of human languages. In these structures, vertices are words and edges connect syntactically-dependent words. The tendency of these dependencies to be short has been demonstrated using random baselines for the sum of the lengths of the edges or their variants. A ubiquitous baseline is the expected sum in projective orderings (wherein edges do not cross and the root word of the sentence is not covered by any edge), that can be computed in time O(n). Here we focus on a weaker formal constraint, namely planarity. In the theoretical domain, we present a characterization of planarity that, given a sentence, yields either the number of planar permutations or an efcient algorithm to generate uniformly random planar permutations of the words. We also show the relationship between the expected sum in planar arrangements and the expected sum in projective arrangements. In the domain of applications, we derive a O(n)-time algorithm to calculate the expected value of the sum of edge lengths. We also apply this research to a parallel corpus and fnd that the gap between actual dependency distance and the random baseline reduces as the strength of the formal constraint on dependency structures increases, suggesting that formal constraints absorb part of the dependency distance minimization efect. Our research paves the way for replicating past research on dependency distance minimization using random planar linearizations as random baseline. © 2024 Institute of Computer Science, Polish Academy of Sciences. All rights reserved.

Czech name

—

Czech description

—

Type

J_SC - Article in a specialist periodical, which is included in the SCOPUS database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

—

Publication year

2024

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Journal of Language Modelling

ISSN

2299-856X

e-ISSN

—

Volume of the periodical

12

Issue of the periodical within the volume

1

Country of publishing house

US - UNITED STATES

Number of pages

42

Pages from-to

1-42

UT code for WoS article

—

EID of the result in the Scopus database

2-s2.0-85188338511