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

Speaker(s)

Eryk Kopczyński

Affiliation

Uniwersytet Warszawski

Date

Feb. 27, 2013, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---