Tree inclusion problems

Cégielski, Patrick; Guessarian, Irène; Matiyasevich, Yuri

Cégielski, Patrick ; Guessarian, Irène ; Matiyasevich, Yuri

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 5-20 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé

Given two trees (a target $T$ and a pattern $P$ ) and a natural number $w$ , window embedded subtree problems consist in deciding whether $P$ occurs as an embedded subtree of $T$ and/or finding the number of size (at most) $w$ windows of $T$ which contain pattern $P$ as an embedded subtree. $P$ is an embedded subtree of $T$ if $P$ can be obtained by deleting some nodes from $T$ (if a node $v$ is deleted, all edges adjacent to $v$ are also deleted, and outgoing edges are replaced by edges going from the parent of $v$ (if it exists) to the children of $v$ ). Deciding whether $P$ is an embedded subtree of $T$ is known to be NP-complete. Our algorithms run in time $O (| T | 2^{2^{| P |}})$ where $| T |$ (resp. $| P |$ ) is the size of $T$ (resp. $P$ ).

Publié le : 2008-01-01

MR 2382541 | Zbl 1149.68040

DOI : https://doi.org/10.1051/ita:2007052
Classification: 68Q25, 68W05

@article{ITA_2008__42_1_5_0,
     author = {C\'egielski, Patrick and Guessarian, Ir\`ene and Matiyasevich, Yuri},
     title = {Tree inclusion problems},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {42},
     year = {2008},
     pages = {5-20},
     doi = {10.1051/ita:2007052},
     mrnumber = {2382541},
     zbl = {1149.68040},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2008__42_1_5_0}
}

Cégielski, Patrick; Guessarian, Irène; Matiyasevich, Yuri. Tree inclusion problems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) pp. 5-20. doi : 10.1051/ita:2007052. http://gdmltest.u-ga.fr/item/ITA_2008__42_1_5_0/

Bibliographie

[1] L. Boasson, P. Cegielski, I. Guessarian and Yu. Matiyasevich, Window accumulated subsequence matching is linear. Ann. Pure Appl. Logic 113 (2001) 59-80. | MR 1875736 | Zbl 0998.68042

[2] Y. Chi, R. Muntz, S. Nijssen and J. Kok, Frequent subtree mining - an overview. Fund. Inform. 66 (2005) 161-198. | MR 2347731 | Zbl 1096.68044

[3] P. Kilpelainen, Tree matching problems with applications to structured text databases. Ph.D. thesis, Helsinki (1992). http://ethesis.helsinki.fi/julkaisut/mat/tieto/vk/kilpelainen/

[4] P. Kilpelainen and H. Mannila, Ordered and unordered tree inclusion. SIAM J. Comput. 24 (1995) 340-356. | MR 1320214 | Zbl 0827.68050