joint work with Claire David and Nadime Francis

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.