Luc Segoufin: Sequential tree automata and TC-logic vs bottom-up tree automata and MSO

Abstract

It is well known that bottom-up tree automata form a robust class of tree languages, known as the regular tree languages. In particular it corresponds to MSO definability on trees. However bottom-up tree automata induce inherently a parallel processing of the tree : one needs to first evaluate both the left and right subtree before being able to proceed to next level. Several models of sequential tree automata have then been proposed and studied extending tree-walking automata.

In this talk I will present several of these models and show the connection with the extension of First-Order logic by a unary transitive closure operator. We will then see that all the models of sequential automata introduced are strictly weaker than regular tree languages.