Mikolaj Bojanczyk - Tree automata = finite algebras

Mikolaj Bojanczyk: Tree automata = finite algebras

A (deterministic bottom-up) tree automaton is a device which has finitely many states, and which inputs a tree over a fixed signature. It begins in the leaves with some initial state, and then processes the tree in the direction of the root, with the state in a tree node being computed as a function of the states in the children. Finally, a tree is accepted or rejected depending on the state in the root. Tree automata are a popular topic in formal language theory (a branch of theoretical computer science), motivated by applications in formal verification and the theory of databases. One popular topic is the connection between tree automata and logic, most often monadic second-order logic.

A tree automaton is also the same thing as an algebra with a finite universe. In my talk, I would like to advertise questions about finite algebras that are motivated by topics in formal language theory and logic. (Incidentally, this is not the same connection as Constraint Satisfaction Problems.) My own personal favourite is the question: which finite
algebras recognise tree languages that can be defined in first-order logic?