Abstract of Paper

On Diving in Trees
by Thomas Schwentick

Abstract:

The paper is concerned with queries on tree-structured data. It defines
fragments of first-order logic (FO) and FO extended by regular expressions
along paths. These fragments have the same expressive power as the full
logics themselves. On the other hand, they can be evaluated reasonably
efficient, even if the formula which represents the query is considered as
part of the input. The results are first established for unary queries that
can only express properties of a vertex that depend solely on the subtree
rooted at the vertex. Then they are extended to queries of arbitrary arity
that take the whole tree into account. The latter kind of result is also
obtained for the corresponding fragment of monadic second order logic that
was introduced in [Neven,Schwentick 2000].