Geodesic
Tree inclusions in windows and slices
Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 38-53 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

A labelled tree $P$ is an embedded subtree of a labelled tree $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 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. Given two trees (a target $T$ and a pattern $P$) and a natural number $w$, we address two problems: 1) counting the number of windows of $T$ having height exactly $w$ and containing the pattern $P$ as an embedded subtree, and 2) counting the number of slices of $T$ having height exactly $w$ and containing the pattern $P$ as an embedded subtree. Our algorithms run in time $O(|T|(w-h(P)+2)^{4|P|})$, where $|T|$ (resp., $|P|$) is the size of $T$ (resp., $P$), and $h(P)$ is the height of $P$. Bibl. – 10 titles. 
@article{ZNSL_2008_358_a2,
     author = {I. Guessarian and P. C\'egielski},
     title = {Tree inclusions in windows and slices},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {38--53},
     year = {2008},
     volume = {358},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a2/}
}
TY  - JOUR
AU  - I. Guessarian
AU  - P. Cégielski
TI  - Tree inclusions in windows and slices
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2008
SP  - 38
EP  - 53
VL  - 358
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a2/
LA  - en
ID  - ZNSL_2008_358_a2
ER  - 
%0 Journal Article
%A I. Guessarian
%A P. Cégielski
%T Tree inclusions in windows and slices
%J Zapiski Nauchnykh Seminarov POMI
%D 2008
%P 38-53
%V 358
%U http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a2/
%G en
%F ZNSL_2008_358_a2
I. Guessarian; P. Cégielski. Tree inclusions in windows and slices. Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 38-53. http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a2/

[1] P. Bille, “A survey on tree edit distance and related problems”, Theor. Comput. Sci., 337 (2005), 217–239 | DOI | MR | Zbl

[2] L. Boasson, P. Cegielski, I. Guessarian, Yu. Matiyasevich, “Window accumulated subsequence matching is linear”, Annals Pure Appl. Logic, 113 (2001), 59–80 | DOI | MR

[3] P. Cegielski, I. Guessarian, Yu. Matiyasevich, “Tree inclusion problems”, RAIRO, 42:1 (2008), 5–20 | MR | Zbl

[4] P. Cegielski, I. Guessarian, Y. Lifshits, Yu. Matiyasevich, “Window subsequence problems for compressed texts”, CSR' 06, Lecture Notes Comp. Sci., 3697, 2006, 127–136 | MR

[5] Y. Chi, R. Muntz, S. Nijssen, J. Kok, “Frequent subtree mining – an overview”, Fundamenta Informaticae, 66 (2005), 161–198 | MR | Zbl

[6] A. Durand, E. Grandjean, “First-order queries on structures of bounded degree are computable with constant delay”, ACM Trans. Comp. Logic, 8:4 (2007), Article No 21 | MR

[7] J. Flum, M. Grohe, Parameterized Complexity Theory, Springer-Verlag, Berlin, 2006 | MR

[8] C. Hoffmann, M. O'Donnell, “Pattern matching in trees”, J. ACM, 28:1 (1982), 68–95 | DOI | MR

[9] P. Kilpelainen, Tree matching problems with applications to structured text databases, PhD Thesis, Helsinki, 1992; http:// ethesis.helsinki.fi/julkaisut/mat/ tieto/vk/kilpelainen

[10] P. Kilpelainen, H. Mannila, “Ordered and Unordered Tree Inclusion”, SIAM J. Comp., 24:2 (1995), 340–356 | DOI | MR