Consistency of injective tree patterns

Prelegent(ci)

Filip Murlak

Afiliacja

Uniwersytet Warszawski

Termin

19 listopada 2014 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Claire David and Nadime Francis

Seminarium

Seminarium „Teoria automatów”

---

I will talk about satisfiability problems for tree patterns under different semantics. I will focus on the following problem: decide if a given tree pattern can be matched injectively in some tree from a fixed regular language. This variant is motivated by the database task of deciding if incomplete information about an XML document in DOM model is consistent with the schema. It is easy to see that the problem is in NP; the challenge is to pinpoint the exact complexity.

---