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.