Understanding the expressive power of transformers through the lens of formal language theory

What can you *learn* with transformers? I will discuss recent developments at the intersection of formal language theory and machine learning, especially with the goal to understand the expressiveness of transformers. Among others, I will discuss results connected my recent work (e.g. from ICLR’24).