Umeå University's logo

This thesis studies the computational expressivity of transformers from the perspective of formal language theory, circuit complexity, and transductions. It develops a unified framework that locates finite-precision transformer architectures within established constant-depth circuit classes and descriptive logics, and links their recognition power to well-known hierarchies of string-to-string functions.

The analysis focuses on architectures under explicit and realistic constraints: constant depth, O(log n) precision, and simple positional features. Under these assumptions, encoder-only transformers with average-hard attention lie within DLOGTIME-uniform TC0. With a small set of positional encodings, masked average-hard encoders can simulate a calculus that contains the aperiodic polyregular transductions. Together, these results point to constant-depth counting (e.g., prefix sums and majority) as a shared mechanism behind both recognition and transduction.

The thesis further shows that temperature-scaled softmax attention can match the selection behavior of unique-hard attention, and that for average-hard heads with a unique maximizer per query (uniform-tieless), the same outputs can be obtained without changing the learned weights by choosing a length-dependent temperature. It also characterizes trade-offs in succinct models: some table-lookup layouts can be solved by a single concise layer under structure-aware encodings, whereas structure-oblivious layouts require either additional depth or super-polylogarithmic communication size.

Throughout, constructive proofs are paired with reference implementations and learning experiments on synthetic tasks. This combination clarifies which theoretically possible behaviors emerge in practice and where learnability lags expressivity, especially for length extrapolation. The thesis concludes with open directions toward adaptive masking, resource-aware analyses, and conditions under which standard training enables the models to reach their theoretical potential, strengthening the bridge between formal methods and neural language modeling.