Algebraic Characterization of Transformer Length Generalization

This research provides the first complete characterization of which regular languages Transformers can length-generalize on using a polynomial-time decision algorithm. The method leverages the C-RASP formalism to move beyond insufficient classical tools like Krohn-Rhodes decomposition for finite semigroups.