A Landscape of Logics for Finite Unordered Unranked Trees
Stephan Kepser · 2008
In this paper, we draw a landscape of the expressive power of diverse logics over finite unordered unranked trees. A tree is unordered iff for each node there is no order on its children. A tree is unranked iff for each node the number of its children is independent of its label. We compare here the expressive power of logics from three non-disjoint areas: logics related to automata theory, logics from descriptive complexity theory, and secondorder logics. Several of these logics form natural hierarchies of expressive power. We will show several separation results in these hierarchies thus showing that the hierarchies are mostly proper. We also present that the automata logics are incomparable to the logics from descriptive complexity theory.