The expected sum of edge lengthsin planar linearizations of trees

Dependency trees have proven to be a very successful model to rep-resent the syntactic structure of sentences of human languages. Inthese structures, vertices are words and edges connect syntactically-dependent words. The tendency of these dependencies to be short hasbeen demonstrated using random baselines for the sum of the lengthsof the edges or their variants. A ubiquitous baseline is the expectedsum in projective orderings (wherein edges do not cross and the rootword of the sentence is not covered by any edge), that can be com-puted in timeO(n). Here we focus on a weaker formal constraint,namely planarity. In the theoretical domain, we present a characteri-zation of planarity that, given a sentence, yields either the number ofplanar permutations or an efficient algorithm to generate uniformlyrandom planar permutations of the words. We also show the relation-ship between the expected sum in planar arrangements and the ex-pected sum in projective arrangements. In the domain of applications,we derive aO(n)-time algorithm to calculate the expected value ofthe sum of edge lengths. We also apply this research to a parallel cor-pus and find that the gap between actual dependency distance and therandombaselinereducesasthestrengthoftheformalconstraintonde-pendency structures increases, suggesting that formal constraints ab-sorbpartofthedependencydistanceminimizationeffect.Ourresearchpaves the way for replicating past research on dependency distanceminimization using random planar linearizations as random baseline.

---

Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).