Edit distance between unlabeled ordered trees

Anne Micheli; Dominique Rossin

RAIRO - Theoretical Informatics and Applications (2006)

  • Volume: 40, Issue: 4, page 593-609
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Micheli, Anne, and Rossin, Dominique. "Edit distance between unlabeled ordered trees." RAIRO - Theoretical Informatics and Applications 40.4 (2006): 593-609. <http://eudml.org/doc/249700>.

@article{Micheli2006,
abstract = { 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. },
author = {Micheli, Anne, Rossin, Dominique},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Edit distance; trees.; one-stack sortable permutation; pattern avoidance},
language = {eng},
month = {11},
number = {4},
pages = {593-609},
publisher = {EDP Sciences},
title = {Edit distance between unlabeled ordered trees},
url = {http://eudml.org/doc/249700},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Micheli, Anne
AU - Rossin, Dominique
TI - Edit distance between unlabeled ordered trees
JO - RAIRO - Theoretical Informatics and Applications
DA - 2006/11//
PB - EDP Sciences
VL - 40
IS - 4
SP - 593
EP - 609
AB - 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.
LA - eng
KW - Edit distance; trees.; one-stack sortable permutation; pattern avoidance
UR - http://eudml.org/doc/249700
ER -

References

top
  1. P. Bose, J.F. Buss and A. Lubiw, Pattern matching for permutations. Inf. Proc. Lett.65 (1998) 277–283.  
  2. M. Bousquet-Mélou, Sorted and/or sortable permutations. Disc. Math.225 (2000) 25–50.  
  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.  
  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.  
  7. D.E. Knuth, The Art of Computer Programming: Fundamental Algorithms. Addison-Wesley (1973) 533.  
  8. P.A. MacMahon, Combinatorial Analysis1–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. Paris240 (1955) 1188–1189.  
  10. T.V. Narayana, A partial order and its application to probability theory. Sankhyā21 (1959) 91–98.  
  11. A. Reifegerste, On the diagram of 132-avoiding permutations. Technical Report 0208006, Math. CO (2002).  
  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.  
  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.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.