Balder ten Cate
Title: Transitive closure logic, nested tree walking automata,
I will discuss three kinds of formalisms that are interpreted on finite trees
(XML documents) and whose expressive power lies in-between that of first-order
logic and monadic second-order logic:
Monadic transitive closure logics such as FO(detMTC), FO(posMTC) and FO(MTC)
Tree-walking automata, extended with limited forms of negation and/or
Algebras of binary relations such as (Regular) XPath.