Information, Geometry, and Physics Seminar

Transductions, or mappings between finite structures like strings and trees, are a fundamental object in theoretical computer science, with many applications in linguistics, information theory, and group theory. This talk will overview recent insights into the theory of transductions in linguistics, in particular restrictions imposed by finite aperiodic semigroups. I will describe boundary conditions (mostly lower) on the kinds of mappings seen in natural language. I will also describe some bounds (again, mostly lower) on transformer sequence models, showing which functions they provably can and cannot compute.