Tree inclusion problems

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

doi:10.1051/ita:2007052

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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 1, pp. 5-20.

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$ ).

MR Zbl

DOI : 10.1051/ita:2007052

Classification : 68Q25, 68W05
Mots-clés : subtree inclusion, algorithm

@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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita:2007052/

Bibliographie
Cité par

[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 | Zbl

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

[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 | Zbl

Cité par Sources :