Algebra for Tree Languages

Abstract There are at least as many interesting classes of regular tree languages as there are of regular word languages. However, much less is known about the former ones. In particular, very few effective characterizations of tree language classes are known. Since for words most known characterizations are obtained using algebra, it seems to be a good idea to look for an algebra for tree languages. I will talk about one such attempt, which is called forest algebra. (Other frameworks in the literature include pre-clones of Ésik and Weil or tree algebra of Wilke. Another approach is to forget about algebra and study the structure of a tree automaton.)

Authors

• Mikolaj Bojanczyk

Keywords

No keywords are indexed for this paper.