Edit distance between unlabelled ordered trees

MaRDI QIDQ3154686zbMATH OpenFDO

Authors Anne Micheli, Dominique Rossin

Publication date 14 January 2005

zbMATH Keywords

sorted permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05)

Review text

For a natural number \(n\), a sorted permutation of \(\{1,\dots, n\}\) is a permutation \(\sigma\) such that \(\sigma = InJ\) where \(I\) and \(J\) are sorted permutations on \(\{1,\dots,p\}\) and \(\{p+1,\dots,n-1\}\), for some \(0\leq p \leq n-1\). In the paper, it is shown that the sorted permutations of \(n\) elements are in one-to-one correspondence with the rooted ordered trees of order \(n\). For the entire collection see [Zbl 1047.68003].

Recommendations

• Edit distance between unlabeled ordered trees
• Computing the edit-distance between unrooted ordered trees
• Sorted and/or sortable permutations
• On the editing distance between unordered labeled trees
• Labelled trees and pairs of input--output permutations in priority queues

Cited in

(4)

• An edit distance between quotiented trees
• Sorted and/or sortable permutations
• Edit distance between unlabeled ordered trees
• Guided Forest Edit Distance: Better Structure Comparisons by Using Domain-knowledge

This page was built for publication: Edit distance between unlabelled ordered trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3154686)