joint work with Claire David and Nadime Francis

Speaker(s)

Filip Murlak

Affiliation

Uniwersytet Warszawski

Date

Nov. 19, 2014, 2:15 p.m.

Room

room 5870

Title in Polish

Consistency of injective tree patterns

Seminar

Seminar Automata Theory

---

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.

---