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

Speaker(s)

Paweł Parys

Affiliation

Uniwersytet Warszawski

Date

Jan. 28, 2015, 2:15 p.m.

Room

room 5870

Title in Polish

892 Theorems about Tree Pattern Containment

Seminar

Seminar Automata Theory

---

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.

---