Edit distance between unlabeled ordered trees

DOI10.1051/ITA:2006043MaRDI QIDQ3423140zbMATH OpenOpenAlexFDO

Authors Anne Micheli, Dominique Rossin

Publication date 20 February 2007

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0506538, http://www.numdam.org/item?id=ITA_2006__40_4_593_0, https://eudml.org/doc/92824

zbMATH Keywords

one-stack sortable permutationpattern avoidance

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Trees (05C05) Distance in graphs (05C12)

Abstract: There exists a bijection between one stack sortable permutations --permutations which avoid the pattern 231-- and planar trees. We define an edit distance between permutations which is coherent with the standard edit distance between trees. This one-to-one correspondence yields a polynomial algorithm for the subpermutation problem for $(231)$ avoiding permutations. Moreover, we obtain the generating function of the edit distance between ordered trees and some special ones. For the general case we show that the mean edit distance between a planar tree and all other planar trees is at least $n/ln(n)$. Some results can be extended to labeled trees considering colored Dyck paths or equivalently colored one stack sortable permutations.

Recommendations

• scientific article; zbMATH DE number 2127737
• scientific article; zbMATH DE number 1305084
• On the editing distance between unordered labeled trees
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• A constrained edit distance between unordered labeled trees

Cites work

• Combinatorial theory of \(\text{T}\)-fractions and two points Padé approximants
• scientific article; zbMATH DE number 1305084 (Why is no real title available?)
• scientific article; zbMATH DE number 3270295 (Why is no real title available?)
• scientific article; zbMATH DE number 3108822 (Why is no real title available?)
• Longest increasing subsequences in pattern-restricted permutations
• On the diagram of 132-avoiding permutations
• Pattern matching for permutations
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Sorted and/or sortable permutations

Cited in

(3)

• scientific article; zbMATH DE number 2127737 (Why is no real title available?)
• Guided Forest Edit Distance: Better Structure Comparisons by Using Domain-knowledge
• Statistical limits of correlation detection in trees

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

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