Tree inclusions in windows and slices

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| (respectively, |P|) is the size of T (respectively, P), and h(P) is the height of P. Bibliography: 10 titles. Dedicated to Yu. Matiyasevich on the occasion of his 60th birthday. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 358, 2008, pp. 3–53.