Edit distance between unlabeled ordered trees
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 593-609.

There exists a bijection between one-stack sortable permutations (permutations which avoid the pattern (231)) 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 (231) 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 n/ln(n). Some results can be extended to labeled trees considering colored Dyck paths or, equivalently, colored one-stack sortable permutations.

DOI : https://doi.org/10.1051/ita:2006043
Classification : 05C12,  05C05,  05A05,  05A15
Mots clés : edit distance, trees
@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},
     zbl = {1114.05031},
     mrnumber = {2277052},
     language = {en},
     url = {http://www.numdam.org/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
DA  - 2006///
SP  - 593
EP  - 609
VL  - 40
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2006043/
UR  - https://zbmath.org/?q=an%3A1114.05031
UR  - https://www.ams.org/mathscinet-getitem?mr=2277052
UR  - https://doi.org/10.1051/ita:2006043
DO  - 10.1051/ita:2006043
LA  - en
ID  - ITA_2006__40_4_593_0
ER  - 
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. http://www.numdam.org/articles/10.1051/ita:2006043/

[1] P. Bose, J.F. Buss and A. Lubiw, Pattern matching for permutations. Inf. Proc. Lett. 65 (1998) 277-283. | MR 1620935 | Zbl 1338.68304

[2] M. Bousquet-Mélou, Sorted and/or sortable permutations. Disc. Math. 225 (2000) 25-50. | MR 1798323 | Zbl 0961.05001

[3] N.G. De Bruijn, D.E. Knuth and S.O. Rice, Graph theory and Computing. Academic Press (1972) 15-22.

[4] E. Deutsch, A.J. Hildebrand and H.S. Wilf, Longest increasing subsequences in pattern-restricted permutations. Elect. J. Combin. 9 (2003) R12. | EuDML 122597 | MR 2028291 | Zbl 1011.05008

[5] M. Garofalakis and A. Kumar, Correlating XML data streams using tree-edit distance embeddings, in Proc. PODS'03 (2003).

[6] P.N. Klein, Computing the edit-distance between unrooted ordered trees, in ESA '98 (1998) 91-102. | MR 1683332 | Zbl 0932.68066

[7] D.E. Knuth, The Art of Computer Programming: Fundamental Algorithms. Addison-Wesley (1973) 533. | MR 378456

[8] P.A. Macmahon, Combinatorial Analysis 1-2. Cambridge University Press (reprinted by Chelsea in 1960) 1915-1916.

[9] T.V. Narayana, Sur les treillis formés par les partitions d'un entier et leurs applications à la théorie des probabilités. C. R. Acad. Sci. Paris 240 (1955) 1188-1189. | MR 70648 | Zbl 0064.12705

[10] T.V. Narayana, A partial order and its application to probability theory. Sankhyā 21 (1959) 91-98. | Zbl 0168.39202

[11] A. Reifegerste, On the diagram of 132-avoiding permutations. Technical Report 0208006, Math. CO (2002). | MR 1995586 | Zbl 1031.05004

[12] E. Roblet and X.G. Viennot, Théorie combinatoire des t-fractions et approximants de Padé en deux points. Discrete Math. 153 (1996) 271-288. | Zbl 0852.05004

[13] J. West, Permutations and restricted subsequences and Stack-sortable permutations. Ph.D. thesis, M.I.T., 1990.

[14] K. Zhang and D. Shasha, Simple fast algorithms for the editing distance between trees and related problems. SIAM J. Comput. 18 (1989) 1245-1262. | Zbl 0692.68047

Cité par Sources :