Given two trees (a target and a pattern ) and a natural number , window embedded subtree problems consist in deciding whether occurs as an embedded subtree of and/or finding the number of size (at most) windows of which contain pattern as an embedded subtree. is an embedded subtree of if can be obtained by deleting some nodes from (if a node is deleted, all edges adjacent to are also deleted, and outgoing edges are replaced by edges going from the parent of (if it exists) to the children of ). Deciding whether is an embedded subtree of is known to be NP-complete. Our algorithms run in time where (resp. ) is the size of (resp. ).
@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}, pages = {5--20}, publisher = {EDP-Sciences}, volume = {42}, number = {1}, year = {2008}, doi = {10.1051/ita:2007052}, mrnumber = {2382541}, zbl = {1149.68040}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ita:2007052/} }
TY - JOUR AU - Cégielski, Patrick AU - Guessarian, Irène AU - Matiyasevich, Yuri TI - Tree inclusion problems JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2008 SP - 5 EP - 20 VL - 42 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2007052/ DO - 10.1051/ita:2007052 LA - en ID - ITA_2008__42_1_5_0 ER -
%0 Journal Article %A Cégielski, Patrick %A Guessarian, Irène %A Matiyasevich, Yuri %T Tree inclusion problems %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2008 %P 5-20 %V 42 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2007052/ %R 10.1051/ita:2007052 %G en %F 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) no. 1, pp. 5-20. doi : 10.1051/ita:2007052. http://www.numdam.org/articles/10.1051/ita:2007052/
[1] Window accumulated subsequence matching is linear. Ann. Pure Appl. Logic 113 (2001) 59-80. | MR | Zbl
, , and ,[2] Frequent subtree mining - an overview. Fund. Inform. 66 (2005) 161-198. | MR | Zbl
, , and ,[3] Tree matching problems with applications to structured text databases. Ph.D. thesis, Helsinki (1992). http://ethesis.helsinki.fi/julkaisut/mat/tieto/vk/kilpelainen/
,[4] Ordered and unordered tree inclusion. SIAM J. Comput. 24 (1995) 340-356. | MR | Zbl
and ,Cité par Sources :