Trees in trees: is the incomplete information about a tree consistent?

Prelegent(ci)

Eryk Kopczyński

Afiliacja

Uniwersytet Warszawski

Termin

27 lutego 2013 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

We are interested in the following problem: given a tree automaton $\Aut$ and an incomplete tree description $P$, does a tree $T$ exist such that $T$ is accepted by $\Aut$ and consistent with $P$? A tree description is a tree-like structure which provides incomplete information about the shape of $T$. We show that this problem can be solved in polynomial time as long as $\Aut$ and the set of possible arrangements that can be forced by $P$ are fixed. We show how our result is related to an open problem in the theory of incomplete XML information.

---