Zusammenfassung für den Vortrag am 29.11.2018 (11:15 Uhr)Seminar on Nonlinear Algebra
Andreas Maletti (Leipzig University)
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.