Voir la notice de l'article provenant de la source Numdam
There exists a bijection between one-stack sortable permutations (permutations which avoid the pattern ) and rooted plane trees. We define an edit distance between permutations which is consistent with the standard edit distance between trees. This one-to-one correspondence yields a polynomial algorithm for the subpermutation problem for pattern-avoiding permutations. Moreover, we obtain the generating function of the edit distance between ordered unlabeled trees and some special ones. For the general case we show that the mean edit distance between a rooted plane tree and all other rooted plane trees is at least . Some results can be extended to labeled trees considering colored Dyck paths or, equivalently, colored one-stack sortable permutations.
@article{ITA_2006__40_4_593_0,
author = {Micheli, Anne and Rossin, Dominique},
title = {Edit distance between unlabeled ordered trees},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {593--609},
publisher = {EDP-Sciences},
volume = {40},
number = {4},
year = {2006},
doi = {10.1051/ita:2006043},
mrnumber = {2277052},
zbl = {1114.05031},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2006043/}
}
TY - JOUR AU - Micheli, Anne AU - Rossin, Dominique TI - Edit distance between unlabeled ordered trees JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2006 SP - 593 EP - 609 VL - 40 IS - 4 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2006043/ DO - 10.1051/ita:2006043 LA - en ID - ITA_2006__40_4_593_0 ER -
%0 Journal Article %A Micheli, Anne %A Rossin, Dominique %T Edit distance between unlabeled ordered trees %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 593-609 %V 40 %N 4 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2006043/ %R 10.1051/ita:2006043 %G en %F ITA_2006__40_4_593_0
Micheli, Anne; Rossin, Dominique. Edit distance between unlabeled ordered trees. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 593-609. doi: 10.1051/ita:2006043
Cité par Sources :