Characterizations of subregular tree languages

We first recall the well-known regular tree languages, their properties, and several of their characterizations. We then move on to classes of subregular tree languages that are relevant in natural language processing. Despite their rather bad closure properties, the local tree languages are particularly attractive in applications, since they are easy to infer from data. In addition, their expressive power is well understood. A more expressive formalism, called tree substitution grammars, is similarly popular despite its even worse closure properties, but their expressive power is not understood at all. We review the existing results and present the open problems.