892 Theorems about Tree Pattern Containment

Prelegent(ci)

Paweł Parys

Afiliacja

Uniwersytet Warszawski

Termin

28 stycznia 2015 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Wojciech Czerwiński, Wim Martens and Marcin Przybyłko

Seminarium

Seminarium „Teoria automatów”

---

We study the following problem of tree pattern containment: given two tree patterns, is it the case that the second pattern can be embedded into every tree into which the first pattern can be embedded. We also study containment with respect to a DTD, that is when we consider only trees satisfying a given DTD. Beside of the most general problem, we can analyze the situation when the patterns come from a restricted fragment: when they cannot use child or descendant edges, wildcards, or when no branching is allowed (paths instead of trees). Different restrictions may be put on each of the two patterns, so this gives a lot of cases. Our goal was to determine the complexity of all these variants of the problem, which was achieved in most cases. It varies between PTIME, coNP and EXPTIME. I will present few most interesting theorems.

---