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

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\left(|T|{2}^{{2}^{|P|}}\right)$ where $|T|$ (resp. $|P|$) is the size of $T$ (resp. $P$).

DOI : https://doi.org/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},
zbl = {1149.68040},
mrnumber = {2382541},
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
DA  - 2008///
SP  - 5
EP  - 20
VL  - 42
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007052/
UR  - https://zbmath.org/?q=an%3A1149.68040
UR  - https://www.ams.org/mathscinet-getitem?mr=2382541
UR  - https://doi.org/10.1051/ita:2007052
DO  - 10.1051/ita:2007052
LA  - en
ID  - ITA_2008__42_1_5_0
ER  -
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/

 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

 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

 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/

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

Cité par Sources :