Loops and overloops for TreeWalking Automata TreeWalking Automata (TWA) have lately received renewed interest thanks to their tight connection to XML. This paper introduces the notion of tree overloops, which is closely related to tree loops, and investigates the use of both for the following common operations on TWA: testing membership, transformation into a BottomUp Tree Automaton (BUTA), and testing emptiness. Notably, we argue that the transformation into a BUTA is slightly less straightforward than was previously assumed, show that using overloops yields much smaller BUTA in the deterministic case, and provide a polynomial overapproximation of this construction which detects emptiness with surprising accuracy against randomly generated TWA.

On the expressive power of hybrid branchingtime logics Abstract   Hybrid branchingtime logics are a powerful extension of branchingtime logics like CTL, CTLxe2x81x8e or even the modal xcexbccalculus through the addition of binders, jumps and variable tests. Their expressiveness is not restricted by bisimulationinvariance anymore. Hence, they do not retain the tree model property, and the finite model property is equally lost. Their satisfiability problems are typically undecidable, their model checking problems (on finite models) are decidable with complexities ranging from polynomial to nonelementary time.  In this paper we study the expressive power of such hybrid branchingtime logics. We extend the hierarchy of branchingtime logics CTL, CTL, CTLxe2x81x8e and the modal xcexbccalculus to their hybrid extensions. We show that most separation results can be transferred to the hybrid world, even though the required techniques become more involved. We also present collapse results for linear, treeshaped and finite models.