Rick Erkens: Regular tree languages and (dis)analogies with regular languages


Event Details


Tree automata are a generalisation of finite automata over words. A tree automaton accepts a set of ranked ordered trees (terms if you will) just like a DFA accepts a set of words over an alphabet. Most interesting properties that regular languages enjoy, carry over to regular tree languages in some sense. I will present some (dis)analogies from the literature that I found interesting. In particular we will discuss the conversion from nondeterministic bottom-up tree automata to deterministic ones, and that there is no such conversion possible for top-down tree automata. This negative result from the literature led to the research on pattern matching that I presented in my last talk.