A Compositional Theory of Causally Masked Transformers Franz Nowak1 , Ryan Cotterell1 , Reda Boumasmoud1 {franz.nowak, ryan.cotterell}@inf.ethz.ch, [email protected] 1
ETH Zürich
arXiv:2607.26988v1 [cs.FL] 29 Jul 2026
Abstract What types of decision problems can a causally masked, finiteprecision transformer solve for inputs of arbitrary length? Existing answers often rely on idealized arithmetic, but under finite precision, rounding and evaluation order can change what information attention retains and therefore what the model can compute. We develop an algebraic formalization that derives expressivity directly from the model’s implemented dynamics. Its central object is its memory; the finite internal state computed by attention that summarizes the information from the prefix available to all future queries. Each attention head updates its own state independently within a layer, while layers compose hierarchically, providing a uniform route from model assumptions to expressivity bounds. Applying this method to transformers without positional embeddings, we obtain an expressivity hierarchy governed by the attention type under specific numerical semantics. Width-one sliding-window attention supports bounded-suffix memory, while a modified form of soft attention supports irreversible, checklist-like state, and combining the two mechanisms provides an interplay of both. Ordinary left-to-right floating-point soft attention can realize more expressive memory operations than any of the above. Algebraically, the four cases correspond to definite, R-trivial, locally R-trivial, and aperiodic semigroups. Under an explicit free-wiring assumption, all four bounds are tight.
1
Introduction
We study the computational power of masked transformer language models whose precision and parameters are fixed independently of the input length. Can they implement a reusable procedure, such as tracking latent state, enforcing a logical constraint, or counting, uniformly over arbitrarily long strings with fixed parameters? Formal language theory makes this question precise by asking which classes of languages a model family can recognize. Existing transformer expressivity analyses typically answer it through an external formalism, such as linear temporal logic (Li and Cotterell 2025), circuit complexity (Merrill, Sabharwal, and Smith 2022), or restricted programming languages such as RASP (Weiss, Goldberg, and Yahav 2021); see Strobl et al. (2024) for a survey. Such characterizations are informative, but their analytical interface often changes with the modeling assumptions. Our approach differs in two related respects. First, we derive expressivity directly from the transition dynamics re-
alized by the architecture, rather than through an external formalism. Second, we specify these dynamics at the level of the implemented arithmetic. Existing fixed-precision analyses model attention accumulation as associative and hence invariant to evaluation order. However, ordinary floatingpoint addition is not associative and can absorb small increments, so evaluation order can change both the induced state transitions and the information attention retains. Under finite precision, causal masking, and a fixed left-to-right evaluation order, each head has a finite, implementation-sensitive state: a query-indexed collection of accumulators updated recursively as the prefix is read. This finite state is a sufficient statistic of the prefix for the head’s entire future behavior (Proposition 9); it is its operational memory. Unlike the growing key–value cache, it captures only information accessible through attention; unlike the current residual activation, it covers every possible future query rather than only the current one, placing it at the right level of abstraction when analyzing transformers as transition systems. Attention is the mechanism that transforms this memory: each new key–value pair induces a transition of the head state. The architecture composes these transformations, with heads acting independently in parallel and successive layers acting hierarchically. These memory operations form transformation semigroups, making a causal transformer under our assumptions an algebraic RNN in the sense of Nowak, Cotterell, and Boumasmoud (2026), so expressivity follows from the operations available to each attention mechanism and their composition across layers. We illustrate this analytic framework on finite-precision causal transformers without positional embeddings. At the level of individual heads, width-one sliding-window attention has a definite transition semigroup, sharp soft attention has an R-trivial transition semigroup, and full floatingpoint soft attention has an aperiodic transition semigroup. Our composition results lift these head-level properties to upper bounds on complete transformers: architectures using width-one sliding-window heads recognize only definite languages, those using sharp soft-attention heads recognize only R-trivial languages, suitable cascades combining the two recognize only locally R-trivial languages, and those using full soft attention recognize only star-free languages. The last bound excludes parity and all modular counting,
irrespective of depth, width, or number of heads. Under an explicit free-wiring assumption, all four bounds are tight. The separation between sharp and full soft attention illustrates why arithmetic is part of the computational model. Under floating-point evaluation, a contribution can be lost in the normalizer while still changing the accumulated value, creating memory behavior that the sharp variant excludes. Algebraically, this is precisely the distinction between Rtrivial and aperiodic behavior.
2
Algebraic Preliminaries
Here we introduce the basic notions from semigroup theory, algebraic automata, and formal languages underlying this paper. Further preliminaries are found in Appendix A. For an accessible introduction, we refer the reader to Pin (2021). Definition 1. An alphabet is a finite, nonempty set Σ, whose elements are called symbols. A word over Σ is a finite sequence of symbols from Σ. We write Σ+ for the set of all non-empty finite words over Σ, and Σ∗ if this set additionally includes the empty word ε. Definition 2. A language over Σ is a subset L ⊆ Σ∗ . Its characteristic function is the map 1, w ∈ L, χL : Σ∗ → {0, 1}, χL (w) = (1) 0, w ∈ / L. We treat transformer language models as language recognizers. That is, the task is to compute χL rather than a distribution over the next token. Definition 3. A semigroup is a nonempty set S equipped with an associative binary operation ·: (s1 · s2 ) · s3 = s1 · (s2 · s3 ) for all s1 , s2 , s3 ∈ S. When the operation is clear from context, we denote the semigroup simply by S. For a given alphabet Σ, the set Σ+ of nonempty words over Σ is a semigroup under concatenation. It is the free semigroup on Σ. Definition 4. Let S and T be semigroups. A semigroup morphism is a map ϕ : S → T such that ϕ(s1 · s2 ) = ϕ(s1 ) · ϕ(s2 ) for all s1 , s2 ∈ S. In particular, a map from the alphabet Σ into a semigroup T determines a unique semigroup morphism from Σ+ to T by extending the map through concatenation. Definition 5. A transformation semigroup (S, Z) consists of a state set Z and a subsemigroup S ≤ Z Z . More generally, a right action of a semigroup S on Z is a semigroup morphism def ρ : S → Z Z . We write z · s = ρ(s)(z). It follows that z · (st) = (z · s) · t. Replacing S by its image ρ(S) yields the corresponding transformation semigroup. We use two compositions of transformation semigroups. Parallel composition describes components whose state updates are independent, whereas cascade composition permits the transition of one component to depend on the state of another. Definition 6. Let (S1 , Z1 ), . . . , (Sn , Zn ) be transformation semigroups. Their parallel composition is the transformation semigroup (S1 ×· · ·×Sn , Z1 ×· · ·×Zn ) with componentwise def action (z1 , . . . , zn ) · (s1 , . . . , sn ) = (z1 · s1 , . . . , zn · sn ).
Definition 7. Let (S1 , Z1 ) and (S2 , Z2 ) be transformation semigroups. Their left wreath product, denoted (S1 , Z1 ) ≀ (S2 , Z2 ), has state set Z1 × Z2 and underlying set S1 × S2Z1 , where S2Z1 is the set of maps Z1 → S2 . Its multiplication and action are given by def (s1 , ϕ1 )(s2 , ϕ2 ) = s1 s2 , z1 7→ ϕ1 (z1 )ϕ2 (z1 · s1 ) , (2) def (z1 , z2 ) · (s, ϕ) = z1 · s, z2 · ϕ(z1 ) . (3) The left-wreath convention evaluates ϕ at the first component’s state before that component is updated. Iterated wreath products are associative up to canonical isomorphism, so we omit parentheses when no ambiguity arises. Definition 8. Let S1 and S2 be semigroups. We say that S1 divides S2 , written S1 ≺ S2 , if there exist a subsemigroup T ≤ S2 and a surjective semigroup morphism ψ : T ↠ S1 . Division is a preorder on semigroups: every semigroup divides itself, and if S1 ≺ S2 and S2 ≺ S3 , then S1 ≺ S3 .
3
Algebraic Transformers
We algebraically describe a specific class of transformer language models that satisfy the following assumptions: • F: Finite-precision. All operations are carried out in constant-precision floating-point arithmetic. • M: Causally masked attention. The attention score at position t depends only on inputs ≤ t. • P: Positional embeddings are absent (NoPE). • E: Fixed evaluation order. Attention is computed sequentially from left to right.
Attention Heads Attention Heads as Transition Systems We define the state of an attention head by expressing attention as a fold over finite accumulators. Attention as a left-to-right fold. We first recall causal soft attention in its usual form. At position t, a head forms a query qt ∈ Q, keys ki ∈ K, and values vi ∈ V , where 1 ≤ i ≤ t, and Q, K, and V are the finite sets of possible queries, keys, and values (often in vector form), and returns Att(qt ; k<t , v<t ) =
exp α(qt , ki ) vi P , j<t exp α(qt , kj ) i<t
X
(4)
where α(·, ·) is usually a scaled dot product when keys and queries are vectors. Under assumption E, the sums are evaluated from left to right. For a fixed query q, define the softattention accumulator aq = (nq , dq ), representing the accumulated numerator and denominator, respectively. Let A denote the finite set of possible accumulator values. To process a sequence of key-value pairs from left to right, we initialize the accumulator at the additive identity aq,0 = (0, 0) ∈ A. Reading a new key-value pair (ki , vi ) at step i ≤ t updates the running accumulator state aq,i ∈ A via the transition function δq : A × K × V → A (5)
{0,1}
{0,1}
CLS
V*
MLP H
H
x
H
x…x
≀ MLP H
H
x
H
H
x…x
S( )
≀
MLP H
{0,1}
x
H
x…x
EMB
U*
Σ*
Σ*
Σ*
Figure 1: Abstraction of a transformer to an algebraic object to a syntactic semigroup. given by the recurrence
and the readout map is
aq,i = δq ((nq,i−1 , dq,i−1 ), (ki , vi ))
gH (z, x) = ρqry(x) z(qry(x)) . (10) Thus, the attention head induces a finite transition system
(6) = nq,i−1 + exp α(q, ki )vi , dq,i−1 + exp α(q, ki ) ,
with all operations evaluated under finite-precision semantics following assumption F. The final attention output at step t is obtained only after completing the fold over all i ≤ t, applying the readout ρq : A → Y,
ρq (n, d) = n/d
(7)
to the final accumulator state for query q. Other attention mechanisms can be formalized similarly by changing the accumulator and its update rule (see Section 5).1 The head state. We now pass from the attention implementation to the abstract state-transition system it induces. Because the arithmetic domain is finite, the set A of possible accumulator values is finite. The relevant state is therefore not the unbounded list of past keys and values, but the finite summary produced by the prescribed scan. The preceding accumulator was for a fixed query q, but a head must be reusable for any query that may be produced later. Since Q is finite, we take the attention-head state set to be the def query-indexed family of accumulators ZH = AQ . The head transitions. An element z ∈ ZH assigns to every possible query q ∈ Q the current prefix accumulator z(q) ∈ A. Writing a new key-value pair (k, v) acts on this state by updating every query accumulator: ∆(k,v) (z)(q) = δq (z(q), (k, v)),
q ∈ Q.
(8)
The current query does not determine the state transition, only which component of the state is read via ρq (z(q)). The head transition system. Let the initial head state be ◦ zH ∈ ZH . If the current input of the head is x ∈ X and the head computes query, key, and value maps q = qry(x), k = key(x), and v = val(x), then the transition map is fxH : ZH → ZH , 1
fxH (z) = ∆(key(x),val(x)) (z),
(9)
Computing attention as a single query-dependent input pass is standard in online-attention algorithms like FlashAttention (Dao et al. 2022), cf. online softmax (Milakov and Gimelshein 2018).
gH : ZH × X → Y,
◦ (ZH , zH , X, fH ),
fH (z, x) = fxH (z),
(11)
with transition semigroup def
ZH TH = fx | x ∈ X sem ≤ ZH .
(12)
The map gH then specifies how this finite state is observed via the current query. Note it does not itself affect the transition semigroup of the head. Proposition 9 (Sufficiency of the head state). Let w1 , w2 ∈ X + be prefixes reaching a common head state: def
b ◦ , w1 ) = δ(z b ◦ , w2 ). z = δ(z H H Then for every w′ ∈ X ∗ and every x ∈ X, the head produces the same output on the inputs w1 w′ x and w2 w′ x. b ◦ , w) is therefore a The proposition says that the state δ(z H sufficient statistic of the prefix w for the entire future behavior of the head. Proof. The extended transition satisfies the identity b ′ , uv) = δb δ(z b ′ , u), v , δ(z z ′ ∈ ZH , u, v ∈ X ∗ . (13) The verification is by induction on |v|. By Definition 38, the b ◦ , wi w′ ), x . output of the head on the input wi w′ x is gH δ(z H By Eq. (13), b ◦ , wi w′ ) = δb δ(z b ◦ , wi ), w′ = δ(z, b w′ ), δ(z i ∈ {1, 2}, H H an expression in which wi nolonger occurs. Both outputs b w′ ), x . therefore equal gH δ(z, By the defining equation of ∆(k,v) , coordinate q of the new state depends on coordinate q of the old state alone: every generator is a coordinatewise transformation of AQ . Coordinatewise transformations Q form a subsemigroup of ZH ZH , canonically isomorphic to q∈Q AA . The following proposition records this passage; it reduces every pseudovariety question about the head to |Q| questions about oneaccumulator semigroups.
Proposition 10 (Subdirect decomposition over queries). For def q ∈ Q, let Tq = δq (−, (key(x), val(x))) | x ∈ X sem ≤ A A . The coordinatewise transformations of ZH Qform a subZH semigroup of ZH , canonically isomorphic to q∈Q AA via def z · (fq )q (q) = z(q) · fq . Under this identification, Y TH ≤ Tq , q∈Q
with every projection surjective. In particular, if V is a pseudovariety of finite semigroups and Tq ∈ V for every q, then TH ∈ V. Proof. The displayed map is an injective semigroup morphism onto the coordinatewise transformations: coordinatewise maps compose componentwise, and such a map determines its components by evaluation. By definition of ∆(k,v) , each generator fxH is coordinatewise, with q-th component the generator δq (−, Q (key(x), val(x))) of Tq . Hence TH lies in the image of q Tq , projections carry generators onto generators, and V is closed under finite products and subsemigroups.
4
From Heads to Language Acceptors
Definition 11 (Transformer core). A transformer core with heads H1 , . . . , Hm over a common input set X is the tuple c = (Z, X, Y, f, g) with def
Z = ZH1 × · · · × ZHm ,
an accepting core, and with an initial global state z ◦ , and an encoder e : Σ → In(T ). It recognizes the language def
L(A) = {w ∈ Σ∗ | π• (FbT + (z ◦ , w)) ∈ F },
where π• : ZT + → Z• projects to the accepting-core state and the empty word is acting as idZT + . Here, for a given word w = w0 · · · w|w| ∈ Σ∗ , FbT + (z ◦ , w) denotes the global state obtained by iterating T + on the encoding e(w0 ) · · · e(w|w| ) starting from state z ◦ . Write WT + for the ambient wreath product of the core transformation semigroups of T + , and WTT+ , STT + for the realized wreath semigroup and the realized transition semigroup relative to a set T ⊆ In(T ) of admissible inputs, defined through the layer-input dependency maps exactly as in Nowak, Cotterell, and Boumasmoud (2026, §3). Proposition 12 (Factorization). For every algebraic transformer T and every T ⊆ In(T ), STT ≤ WTT ≤ WT .
def fx (z1 , . . . , zm ) = fxH1 (z1 ), . . . , fxHm (zm ) , (15) def g (z1 , . . . , zm ), x = µ gH1 (z1 , x), . . . , gHm (zm , x) , (16) where µ : Y1 × · · · × Ym → Y is a mixing map, abstracting the output projection, normalization, and feedforward block. By Definition 6, the transition semigroup of a core is a subsemigroup of the parallel composition of its head semidef groups, Sc = fx | x ∈ X sem ≤ TH1 × · · · × THm , with every projection carrying generators onto generators; the mixing map contributes quotients of readouts and no transitions. A transformer core is an algebraic core in the sense of Nowak, Cotterell, and Boumasmoud (2026, Def. 3.1): the sets are finite and both maps are total. An algebraic transformer T of depth N is an algebraic RNN in the sense of Nowak, Cotterell, and Boumasmoud (2026, §3) all of whose cores are transformer cores. We keep the nomenclature of that paper unchanged: wiring maps, input and output types In and Out, and cascade juxtaposition ▷τ are used here without restatement. An accepting core c• is a transformer core with output set {0, 1} whose readout depends on the state alone, g• (z, x) = χF (z) for an accepting region F ⊆ Z• , intermediate readouts are Mealy, acceptance is Moore. A transformer acceptor is a tuple A = (Σ, T + , z ◦ , e) with T + = T ▷τN c• , where T is an algebraic transformer, c• is
(18)
Proof. This is the factorization lemma of Nowak, Cotterell, and Boumasmoud (2026, Lem. 3.12), specialized to transformer cores; the proofs transfer to semigroups by Remark 14. The first relation is an inclusion, not merely a division: the wreath product of faithful transformation semigroups is faithful. Proposition 13 (Divisibility). For every transformer acceptor A = (Σ, T + , z ◦ , e), e(Σ)
(14)
(17)
e(Σ)
S(L(A)) ≺ ST + ≤ WT + ≤ WT + .
(19)
Proof. By Lemma 41, w 7→ FbT + (−, w) restricts to a semie(Σ) group morphism Σ+ → ST + recognizing L(A) ∩ Σ+ through the accepting region, Theorem 37 gives the division, and Proposition 12 the two inclusions. This is the acceptor divisibility chain of Nowak, Cotterell, and Boumasmoud (2026), at semigroup level. Remark 14 (Transfer of the proofs). The results of Nowak, Cotterell, and Boumasmoud (2026, §3) are stated for monoids and are used here for semigroups. Their proofs transfer verbatim, for a structural reason: every object of loc. cit. section is defined by generators and closure, the generating sets are indexed by X and never by X ∪ {ε}, and the identity occurs throughout as an inhabitant of a generated object, never as a hypothesis of an argument. A Note on Positional Embeddings With position embeddings, the encoder reads the position index alongside the symbol, e : Σ × N → In(T ), and the set of realizable inputs remains finite under F. What is lost is not finiteness but the morphism: the position-tagging map Σ+ −→ (Σ × N)+ , w 7→ (w1 , 1), . . . , (w|w| , |w|) , (20) does not commute with concatenation, since the same symbol at different positions has different images. No morphism η : Σ+ → T is induced, Definition 35 does not apply, and Theorem 37 has nothing to act on; in particular, the divisibility chain of Proposition 13 is not available.
Expressivity Consequences The divisibility chain of Proposition 13 reduces transformer expressivity to a question of finite algebra. We first fix a class of algebraic transformer acceptors by specifying the admissible attention mechanisms, finite-precision arithmetic, cores, wirings, encoders, and accepting cores. Proposition 13 then shows that every recognized language has a syntactic semigroup dividing a realized wreath semigroup obtainable from the layer transition semigroups of the architecture. This gives the following two-sided recipe, directly parallel to the algebraic RNN analysis of Nowak, Cotterell, and Boumasmoud (2026): Impossibility. For an impossibility result, it suffices to show that S(L) cannot divide any realized wreath semigroup generated by the permitted cores and wirings. Equivalently, if a group, reset behavior, or other finite-semigroup component required by the syntactic semigroup of L cannot occur in the wreath closure of the available core semigroups, then no acceptor in the class recognizes L. Krohn–Rhodes theory (Krohn and Rhodes 1965), and its extensions (Stiffler 1973), supply one standard way to make this obstruction explicit, by decomposing finite transformation semigroups into simple interpretable basic components. Construction witness. Conversely, to prove that a language is recognizable, one constructs transformer cores whose realized transition semigroups provide the necessary algebraic components, wires them so that the resulting realized wreath semigroup contains S(L) as a divisor, and chooses the accepting region F to separate the accepting syntactic classes. The accepting core matters in this last step: the syntactic semigroup of L(A) need only divide the auge(Σ) mented semigroup ST + , not the transition semigroup of the base transformer alone. For NoPE transformer acceptors, this yields a simple method to establish expressivity bounds: attention semantics determine the possible head semigroups, parallel heads determine core semigroups, and core cascades determine the realized wreath semigroups against which S(L) must be tested.2
5
Expressivity of NoPE Transformers
In this section, we derive concrete expressivity results for transformers without position embeddings (full specification in Appendix B).
Attention types We start by formally defining different types of attention similar to those used in practice. The following attention mechanisms differ only in the accumulator update and readout in Eq. (33); hence, each of them is a streaming attention mechanism in the sense fixed above. Definition 15 (Soft attention). A head uses soft attention if an,i ∈ A consists of numerator–denominator pairs (nq , dq ), the initial accumulator is an,0 = (0, 0), and its update and 2
Position embeddings require separate treatment, because having access to unbounded position information allows a transformer to recognize non-regular languages just via its encoder.
readout are given by Eq. (6) and Eq. (7), respectively. with α a (scaled) dot product, computed with fixed evaluation order under floating-point semantics. The readout at the empty prefix is fixed to be 0. Definition 16 (Sharp soft attention). A soft-attention head is sharp if, on every reachable accumulator update, either the denominator changes, or both the numerator and the denominator stay the same. I.e., if an attention score is small enough to not affect the normalizer, it is treated as zero. Writing w = exp(α(q, k)), n e = fl(nq + wv), and de = fl(dq + w), its update is ( e (e n, d), if de > dq , (21) δn,i,q ((nq , dq ), (k, v)) = (nq , dq ), otherwise. Definition 17 (Sliding-window attention of width one). Fix ◦ ◦ an initial accumulator a◦n,i,q = (kn,i , vn,i ) ∈ Kn,i × Vn,i . A head uses sliding-window attention of width one if An,i = Kn,i × Vn,i and δn,i,q (a, (k, v)) = (k, v),
ρn,i,q (k, v) = v.
(22)
Thus, at position t, the head reads only the value stored at ◦ position t − 1, with vn,i read at the first position.
Available Semigroups by Attention Type Definition 18. A semigroup S is definite, S ∈ Def , if there exists n ≥ 1 such that st = t for all s ∈ S and t ∈ S n . Definition 19. A semigroup S is R-trivial, S ∈ R, if sS 1 = tS 1 implies s = t for all s, t ∈ S. Definition 20. A semigroup S is locally R-trivial, S ∈ LR, if eSe is R-trivial for every idempotent e ∈ S. Definition 21. A semigroup S is aperiodic, S ∈ Ap, if for every s ∈ S there exists n ≥ 1 such that sn = sn+1 . Aperiodic:
abcd1234cdef_ R-trivial:
abcd1234cdef_
Last number: 4 Letters seen: ✓a ✓c x
Definite:
abcd1234cdef_ Locally R-trivial:
abcd1234cdef_
34cdef
Pairs seen: aa ✓ d1 4x
Figure 2: Illustration of the types of tasks that attention can perform depending on the variety of its transition semigroup. For intuition about the kinds of memory supported by these semigroup varieties, see Fig. 2. Aperiodic transition semigroups may retain finite-state information from arbitrarily far back, including ordering information; for example, they can record the last number seen. In an Rtrivial transition semigroup, state transformations progress
without nontrivial reversible cycles, giving memory that behaves like a checklist rather than a rewritable register. Definite semigroups capture bounded-suffix memory, such as retaining a fixed-size window of the input. Combining definite and R-trivial behavior yields locally R-trivial computations, which can retain checklist information about patterns detected within bounded windows. Remark 22. Any semigroup from the classes described above can be decomposed into a wreath product whose factors come from just three prime semigroups, called U1 , U2 , U3 (see Appendix C for their definitions). The relevant decomposition results due to Stiffler (1973) are outlined in Appendix D. We use the following lemmas (full proofs in Appendix C). Lemma 23. Every width-one sliding-window attention head has a definite transition semigroup, i.e., TH ∈ Def . proof sketch. Every nonempty input word acts as the constant map determined by its final key–value pair; hence, st = t, implying Definition 18. For every i ∈ {1, 2, 3}, we define the transformation semidef group U i = (Ui , Ui1 ) where Ui (see Definition 44) acts on 1 Ui from the right. Lemma 24. There exists a width-one sliding-window attention head H such that U 1 ≺ (TH , ZH ). proof sketch. On the invariant set consisting of the initial accumulator and two distinct key–value states, the corresponding inputs act as the two constant maps of U 1 . Lemma 25. Every sharp soft-attention head has an R-trivial transition semigroup, i.e., TH ∈ R. proof sketch. Denominators weakly increase, and sharpness makes any transition that leaves all denominators fixed a selfloop. Thus reachability is a partial order, so the transition semigroup is R-trivial. Lemma 26. There exists a sharp soft-attention head H such that U 2 ≺ (TH , ZH ). proof sketch. On an invariant two-state set straddling an absorption threshold, an underflowing input acts as the identity and a unit-weight input as the constant map to the saturated state, realizing U 2 . Lemma 27. Every finite-precision soft-attention head has an aperiodic transition semigroup. proof sketch. Under repetition of any input word, each denominator weakly increases and eventually stabilizes; thereafter each numerator coordinate evolves by an orderpreserving map of a finite chain and also stabilizes. Hence every transition has an idempotent power. Lemma 28. There exists a soft-attention head H such that U 3 ≺ (TH , ZH ), i.e., its transition semigroup is not R-trivial.
proof sketch. On a saturated-denominator invariant slice, left-to-right rounded numerator updates realize the identity and two distinct constant maps, and hence U 3 . Throughout this section, the decoder of Definition 43 is memoryless. Equivalently, it may be represented by an accepting core with trivial transition semigroup, so appending it does not change any of the semigroup classes below. Theorem 29. Any language accepted by a NoPE transformer with width-one sliding-window attention is definite. Proof. Every head transition semigroup is definite by Lemma 23. Finite direct products and subsemigroups preserve definiteness, so every core transition semigroup is definite. By Proposition 12, the realized transformer semigroup divides their cascade and is definite by Theorem 48. Its recognized language has a syntactic semigroup dividing this realized semigroup by Proposition 13; closure under division therefore makes the language definite. Theorem 30. Any language accepted by a NoPE transformer with sharp soft attention is R-trivial. Proof. By Lemma 25, every head transition semigroup is Rtrivial. Finite direct products and subsemigroups of R-trivial semigroups are R-trivial, so every core transition semigroup is R-trivial. The realized transformer semigroup divides the cascade of these core semigroups by Proposition 12; hence it is R-trivial by Theorem 49. Finally, Proposition 13 and closure under division imply that the syntactic semigroup of the accepted language is R-trivial. The above theorem recovers by an independent algebraic route a similar result obtained through linear temporal logic by Li and Cotterell (2025). Theorem 31. Any language accepted by a transformer whose lower cores have sliding-window attention and whose higher cores have sharp attention heads, is locally R-trivial. Proof. Take a transformer each of whose lower cores have width-one sliding-window attention heads and whose higher cores sharp soft-attention heads. For the lower heads, their transition semigroups are definite by Lemma 23; for the higher ones, they are R-trivial by Lemma 25. The factorization of Proposition 12 places the realized transformer semigroup below a cascade of these core semigroups. By Theorem 50, it is locally R-trivial. The syntactic semigroup of the accepted language divides the realized semigroup by Proposition 13, so it is also locally R-trivial. Theorem 32. Any language accepted by a NoPE transformer with soft attention is star-free. Proof. By Lemma 27, the transition semigroup of every attention head is aperiodic. The transition semigroup of each transformer core is a subsemigroup of the finite direct product of its head semigroups, and is therefore aperiodic. By Proposition 12, the realized transition semigroup of the transformer divides the cascade of its core semigroups. Aperiodic semigroups are closed under finite direct products, wreath products, and division; equivalently, by Corollary 47, they are
precisely the semigroups dividing finite cascades of copies of U3 . Consequently, the realized transformer semigroup is aperiodic. The encoder restricts the admissible inputs but cannot enlarge this semigroup, and the memoryless decoder adds no transitions. By Proposition 13, the syntactic semigroup of the accepted language divides the realized transformer semigroup and is therefore aperiodic. The algebraic characterization of star-free languages as those with an aperiodic syntactic semigroup (Schützenberger 1955) yields the claim. Definition 33 (Free-wiring assumption). Say a class of NoPE transformers satisfies the free-wiring assumption if the encoders, the per-head key, query, and value maps, the mixing maps, the wiring maps, and the accepting regions may be arbitrary total maps between the corresponding finite sets, and the cascade may place cores with the required attention types in the order prescribed by Theorems 48 to 50 and Corollary 47. Corollary 34. Under the free-wiring assumption, the above bounds are tight. Proof. All the lower-bound components required by the decomposition theorems are available within the corresponding attention mechanisms: width-one sliding-window attention realizes U 1 by Lemma 24, sharp soft attention realizes U 2 by Lemma 26, and floating-point soft attention realizes U 3 by Lemma 28. The decomposition theorems, Theorems 48 to 50 and Corollary 47, express every semigroup in the respective upper-bound class as a divisor of a finite cascade of these components. If the transformer wirings realize the required cascade controls and the decoder realizes the required accepting subset, the resulting transformer recognizes every language in the corresponding class. Together with the preceding upper bounds, this proves the tightness under the stated implementability condition.
Attention sliding sharp sliding + sharp soft
Primes U1 U2 U1 , U2 U1 , U2 , U3
Variety Def R LR Ap
Languages definite R-trivial loc. R-trivial star-free
Table 1: Result overview. We map the attention types to the realizable prime semigroups, the resulting semigroup varieties closed under direct product, wreath product, and division, and the corresponding languages that NoPE transformers with these attention types can recognize. Note that U1 and U2 are subsemigroups of U3 .
The Importance of Evaluation Order Assumption E aligns temporal order with the right action of the transformation semigroup. Reversing the evaluation order would exchange right zeros with left zeros and replace the R-trivial and locally R-trivial conclusions by their dual L-trivial and locally L-trivial conclusions.
6
Related Work
Our framework extends Nowak, Cotterell, and Boumasmoud’s (2026) algebraic analysis of RNN language models. We identify assumptions under which NoPE transformers become algebraic RNNs, then use refinements of Krohn– Rhodes theory to classify different attention mechanisms and derive compositional expressivity bounds. Closest are formal-language characterizations of masked transformers. Using Krohn–Rhodes theory, Yang, Chiang, and Angluin (2024) show that fixed-precision transformers with unique hard attention recognize exactly the star-free languages. Using LTL, Li and Cotterell (2025) obtain an Rtrivial characterization for fixed-precision soft attention. We recover their bound for sharp soft attention but show that it depends on the numerical semantics: left-to-right floatingpoint soft attention yields the broader aperiodic bound. Concurrently, Li and Cotterell (2026) use LTL to show that local attention yields definite languages and that combining it with idealized soft attention yields locally R-trivial languages, matching our results at the level of language classes. Using Krohn–Rhodes theory, Liu et al. (2023) obtain solvable-language expressivity under growing precision and length-dependent wiring; we instead assume fixed precision and fixed parameters.
7
Discussion
This work establishes an algebraic framework for the underlying dynamics of masked finite-precision transformers under explicit numerical semantics, by showing that they can be formalized as RNNs. This allows placing lower and upper bounds on the languages such architectures can recognize. The analysis is restricted to transformers without positional embeddings, because mapping from strings to position-indexed strings is not a morphism. This restriction is substantive: an encoder with access to unbounded position information need not induce the fixed finite input alphabet used by the semigroup analysis, and may support nonregular behavior independently of the attention mechanism. While unbounded position information cannot be assessed using this algebraic framework, certain finite or repeating position embeddings could be incorporated in future work. The query-indexed accumulator state can be extremely large. By Proposition 10, however, every pseudovariety question about a head reduces to the one-accumulator semigroups Tq , so the size of AQ is harmless for the bounds. The algebraic description is therefore primarily a structural tool for proving expressivity bounds, rather than a prescription for explicitly enumerating the transition semigroup of a trained model. The dependence of the results on numerical semantics is nevertheless practically relevant for heavily quantized architectures, where the sets of queries and accumulator values are substantially reduced (Duan et al. 2023). More broadly, the decomposition into head, core, and cascade semigroups suggests a route to architecture design: attention mechanisms can be chosen to supply particular algebraic components, while wiring maps determine how these components interact across layers. This perspective may enable attention variants whose expressivity is controlled by construction.
References Dao, T.; Fu, D.; Ermon, S.; Rudra, A.; and Ré, C. 2022. FlashAttention: Fast and memory-efficient exact attention with IO-awareness. Advances in neural information processing systems, 35: 16344–16359. Duan, G.; Zhang, J.; Zheng, X.; and Zhu, Y. 2023. Bitformer: An efficient Transformer with bitwise operation-based attention for Big Data Analytics at low-cost low-precision devices. ArXiv, abs/2311.13502. Eilenberg, S. 1976. Automata, Languages, and Machines. (with two chapters by Bret Tilson.) Pure and Applied Mathematics. Academic Press. ISBN 9780080873756. Krohn, K.; and Rhodes, J. 1965. Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines. Transactions of the American Mathematical Society, 116: 450–464. Li, J.; and Cotterell, R. 2025. Characterizing the Expressivity of Fixed-Precision Transformer Language Models. In 39th Annual Conference on Neural Information Processing Systems (NeurIPS 2025). Li, J.; and Cotterell, R. 2026. Characterizing the Expressivity of Local Attention in Transformers. In Liakata, M.; Moreira, V. P.; Zhang, J.; and Jurgens, D., eds., Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 37485–37507. San Diego, California, United States: Association for Computational Linguistics. ISBN 979-8-89176-390-6. Liu, B.; Ash, J. T.; Goel, S.; Krishnamurthy, A.; and Zhang, C. 2023. Transformers Learn Shortcuts to Automata. In The Eleventh International Conference on Learning Representations. Mealy, G. H. 1955. A Method for Synthesizing Sequential Circuits. Bell System Technical Journal, 34(5): 1045–1079. Merrill, W.; Sabharwal, A.; and Smith, N. A. 2022. Saturated Transformers are Constant-Depth Threshold Circuits. Transactions of the Association for Computational Linguistics, 10: 843–856. Milakov, M.; and Gimelshein, N. 2018. Online normalizer calculation for softmax. ArXiv, abs/1805.02867. Moore, E. F. 1956. Gedanken-Experiments on Sequential Machines. Annals of Mathematics Studies, 34: 129–153. Nowak, F.; Cotterell, R.; and Boumasmoud, R. 2026. An Algebraic View of the Expressivity of Recurrent Language Models. In Forty-third International Conference on Machine Learning. Pin, J.-É. 2021. Handbook of Automata Theory. European Mathematical Society Publishing House. Schützenberger, M.-P. 1955. Une théorie algébrique du codage. Séminaire Dubreil. Algebre et théorie des nombres, 9: 1–24. Stiffler, P. 1973. Chapter 1. Extension of the fundamental theorem of finite semigroups. Advances in Mathematics, 11(2): 159–209.
Strobl, L.; Merrill, W.; Weiss, G.; Chiang, D.; and Angluin, D. 2024. What Formal Languages Can Transformers Express? A Survey. Transactions of the Association for Computational Linguistics, 12: 543–561. Weiss, G.; Goldberg, Y.; and Yahav, E. 2021. Thinking Like Transformers. In Meila, M.; and Zhang, T., eds., Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, 11080–11090. PMLR. Yang, A.; Chiang, D.; and Angluin, D. 2024. Masked HardAttention Transformers Recognize Exactly the Star-Free Languages. In Globerson, A.; Mackey, L.; Belgrave, D.; Fan, A.; Paquet, U.; Tomczak, J.; and Zhang, C., eds., Advances in Neural Information Processing Systems, volume 37, 10202– 10235. Curran Associates, Inc.
A
Further Preliminaries
Transition Semigroups of Transducers
Recognition of Languages by Semigroups Definition 35. A semigroup S recognizes a language L ⊆ Σ+ if there exist a semigroup morphism η : Σ+ → S and a subset P ⊆ S such that L = η −1 (P ). For languages L ⊆ Σ∗ , the empty word is handled separately by whether ε ∈ L; the semigroup recognizes the nonempty part L ∩ Σ+ . This is analogous to recognition by the syntactic monoid, except that the semigroup presentation does not require the empty word to be part of the input semigroup. This choice loses no information for language recognition: any semigroup S can be made into a monoid by adjoining an identity element, and the free monoid over Σ is Σ∗ = Σ+ ∪ {ε}. Definition 36. For a language L ⊆ Σ∗ , the syntactic congruence ∼L on Σ+ is defined by u ∼L v
∗
⇐⇒
for all x, y ∈ Σ , xuy ∈ L ⇐⇒ xvy ∈ L. (23) def The quotient semigroup S(L) = Σ+ /∼L is the syntactic semigroup of L. Theorem 37. If a semigroup S recognizes L ∩ Σ+ , then S(L) ≺ S. Moreover, L is regular if and only if S(L) is finite. Thus, the syntactic semigroup is minimal up to division among the semigroups recognizing the nontrivial part of a language. It provides the algebraic interface between language recognition and the transition semigroups of concrete state machines.
Transducers and Acceptors Definition 38. A transducer is a tuple M = (Z, z ◦ , X, Y, δ, γ),
(24)
◦
where Z is a state set with initial state z ∈ Z, X and Y are input and output sets, δ : Z × X → Z is a transition map, and γ : Z × X → Y is an output map (Mealy form (Mealy 1955); the Moore form is the special case in which γ does not depend on its second argument (Moore 1956)). The transition map extends recursively to words as δb: Z × X ∗ → Z, where b ε) = z, δ(z,
b wx) = δ(δ(z, b w), x). δ(z,
(25)
Thus, on input w ∈ X ∗ , the transducer produces the output b ◦ , w)). γ(δ(z Definition 39. An acceptor over Σ is a tuple A = (Z, z ◦ , Σ, δ, F ),
Definition 40. Let M be a transducer. Each input x ∈ X induces a state transformation δx : Z → Z,
The elements of TM are precisely the state transformations induced by nonempty input words. The empty word acts as the identity transformation on Z. def
Lemma 41. The map η : X + → TM defined by z · η(w) = b w) is a semigroup morphism. δ(z, Proof. Follows readily by induction on |w|. Remark 42 (Why semigroups). The subregular classes of the case study are invisible at monoid level, so the passage to semigroups is necessary, not stylistic. A definite monoid is trivial: if 1 ∈ S n , then s · 1 = 1 for every s. Likewise 1S1 = S, so on monoids LR collapses onto R. Two of the four classes below therefore have no monoid-level content; the semigroup of a width-one window head is definite and ceases to be so the moment an identity is adjoined.
B
NoPE Transformer Architecture
We now instantiate the algebraic transformer of the preceding section as a finite-precision transformer with no position embeddings (NoPE transformer). Following the streaming formulation of attention above, a head reads the strict prefix state stored in its current state and then incorporates the key– value pair at the current position. Fix a finite arithmetic domain D, a depth N ∈ Z+ , a model dimension d ∈ Z+ , and numbers of heads m1 , . . . , mN . For every core n ∈ {1, . . . , N }, set Xn = Yn = Dd .
qryn,i : Xn → Qn,i ,
keyn,i : Xn → Kn,i ,
valn,i : Xn → Vn,i .
(31) (32)
Its attention mechanism is specified by a finite accumulator set An,i , initial accumulators a◦n,i,q ∈ An,i , and maps δn,i,q : An,i ×Kn,i ×Vn,i → An,i ,
where Z, z ◦ , and δ are as in Definition 38, and F ⊆ Z is the set of accepting states. The language recognized by A is
Zn,i = An,in,i ,
Equivalently, an acceptor is a transducer with output set {0, 1} and output map χF .
(30)
Head i of layer n has finite query, key, value, and head-output sets Qn,i , Kn,i , Vn,i , and Yn,i , together with learned maps
for every q ∈ Qn,i . Thus,
(27)
(28)
The transition semigroup of M is the transformation semigroup def (29) TM = δx | x ∈ X sem ≤ Z Z .
(26)
def b ◦ , w) ∈ F }. L(A) = {w ∈ Σ∗ | δ(z
def
δx (z) = δ(z, x).
Q
ρn,i,q : An,i → Yn,i , (33)
◦ zn,i (q) = a◦n,i,q .
(34)
The transformer core cn = (Zn , Xn , Yn , fn , gn ) has the product state mn Y Zn,i . (35) Zn = i=1
For z = (z1 , . . . , zmn ) and x ∈ Xn , its recurrence is defined componentwise by fn (z, x)i (q) = δn,i,q zi (q), keyn,i (x), valn,i (x) . (36) The head outputs and core readout are hn,i (zi , x) = ρn,i,qryn,i (x) zi (qryn,i (x)) , (37) gn (z, x) = WnO (hn,1 (z1 , x), . . . , hn,mn (zmn , x)) , (38) where WnO is the finite-precision output projection. Consequently, at position t, the core computes zn,t = fn (zn,t−1 , xn,t ), yn,t = gn (zn,t−1 , xn,t ). (39) In particular, the readout uses precisely the strict prefix accumulated before position t. Let LNn : Dd → Dd be layer normalization with learned scale and bias, and let MLPn : Dd → Dd be a finiteprecision feedforward network. The wiring from layer n to layer n + 1 is rn (x, y) = LNatt (40) n (x + y), (41) τn (x, y) = LNmlp n (rn (x, y) + MLPn (rn (x, y))) , with every operation evaluated in the fixed finite-precision semantics. This wiring includes the attention residual connection, layer normalization, the MLP, and the MLP residual connection. The encoder and decoder are set maps d
d
e: Σ → D , d : D → {0, 1}. (42) The encoder factors through the one-hot embedding Σ ,→ D|Σ| followed by a learned linear map to Dd , and the decoder is a learned linear map followed by a binary decision rule. Since neither map receives a position index, the resulting architecture has no positional embeddings. Definition 43 (NoPE transformer). A NoPE transformer is the algebraic transformer whose cores, recurrence and readout maps, wiring maps, encoder, and decoder are specified in Eqs. (33), (36), (38) and (41).
C
Available Semigroups by Attention Type
Definition 44. U1 = ({a, b}, ·) with multiplication table · a b
a a a
0 0 0
Lemma 23. Every width-one sliding-window attention head has a definite transition semigroup, i.e., TH ∈ Def . Proof. By Definition 17, reading an input x replaces every query-indexed accumulator by (key(x), val(x)), independently of the previous state. Hence, every generator fxH ∈ TH is a constant transformation. More generally, the transformation induced by a nonempty input word is the constant transformation determined by its final symbol. Therefore, for all s, t ∈ TH , st = t. In particular, this holds for every 2 t ∈ TH . Taking n = 2 in the definition of definiteness gives TH ∈ Def . Lemma 24. There exists a width-one sliding-window attention head H such that U 1 ≺ (TH , ZH ). Proof. Take a singleton key set K = {k} and choose three distinct values V = {v1 , va , vb }, so that A = {(k, v1 ), (k, va ), (k, vb )}; write z1 , za , zb for these three accumulator states. Let the admissible inputs be xa and xb , with values va and vb . By Definition 17, the induced transformations are the constant maps z · Fa = za ,
z · Fb = zb ,
(43)
θ(z1 ) = 1, θ(za ) = a, θ(zb ) = b, φ(Fa ) = a, φ(Fb ) = b, (44) satisfy θ(z · F ) = θ(z) · φ(F ) in all six cases, both sides being the label of the last-written pair. This shows the division U 1 ≺ (TH , ZH ). Lemma 25. Every sharp soft-attention head has an R-trivial transition semigroup, i.e., TH ∈ R. Proof. Consider the deterministic semiautomaton induced by the head on ZH , and equip its states with the reachability preorder ⇐⇒
z ′ = z · w for some w ∈ X ∗ .
(45)
This relation is reflexive and transitive. We show that it is also antisymmetric. Let dq (z) be the denominator of the accumulator for query q in state z. Every sharp soft-attention transition satisfies dq (z) ≤ dq (z · x)
1 0 1
z ∈ A.
A product of constant maps is its last factor, so Fx Fy = Fy for x, y ∈ {a, b}: four identities, each verified by evaluating both sides at any state. The set A is invariant, and the surjections
z ⪯ z′
b b b
U2 = ({0, 1}, ·) with multiplication table · 0 1
For each multiplication table of Ui , the entry in row x and column y is the product xy: first x, then y.
′
for all q ∈ Q.
(46)
′
Suppose z ⪯ z and z ⪯ z. Applying Eq. (46) along the two witnessing paths yields
U3 = ({a, b, 1}, ·) with multiplication table
dq (z) ≤ dq (z ′ ) ≤ dq (z)
· a b 1
for every query. Hence no denominator advances anywhere along the path from z to z ′ . By the definition of sharp soft attention, whenever a denominator does not advance, its numerator also remains unchanged. Every transition on this path is therefore a self-loop on the full head state, and z = z ′ .
a a a a
b b b b
1 a b 1
(47)
The reachability preorder is thus a partial order, so the head induces a partially ordered semiautomaton. By the standard characterization of finite partially ordered semiautomata, their transition semigroups are R-trivial. Therefore TH ∈ R. Lemma 26. There exists a sharp soft-attention head H such that U 2 ≺ (TH , ZH ). Proof. Use a scalar-valued head with one query and value zero. Let p be the significand precision, set D = 2p , and let D− = D − 1 be its immediate floating-point predecessor. Choose an input x0 whose exponential attention weight underflows to zero and an input x1 with score zero, and hence exponential attention weight 1. Consider z0 = (0, D− ),
z1 = (0, D).
(48)
The input x0 leaves both states unchanged and hence induces the identity on {z0 , z1 }. Moreover, −
fl(D + 1) = D,
fl(D + 1) = D.
(49)
Thus, the sharp update induced by x1 sends z0 to z1 and fixes z1 : at z0 the denominator advances, whereas at z1 the increment is absorbed and the entire update is suppressed. Its restriction to {z0 , z1 } is therefore the constant map E with image z1 , while x0 restricts to the identity I on the same pair of states. The products are computed by evaluation: EE = E and IE = EI = E, checked at z0 and at z1 ; this is the multiplication of Definition 44. The set {z0 , z1 } is invariant, and the surjections θ(z0 ) = 1, θ(z1 ) = 0,
φ(I) = 1, φ(E) = 0,
(50)
satisfy θ(z · F ) = θ(z) · φ(F ) in all four cases; for instance θ(z0 · E) = θ(z1 ) = 0 = 1 · 0 = θ(z0 ) · φ(E). This is the division U 2 ≺ (TH , ZH ). Lemma 27. Every finite-precision soft-attention head has an aperiodic transition semigroup. Proof. Fix a query q. Upon reading a key–value pair (k, v), the denominator is updated by dq 7−→ fl(dq + exp(α(q, k))) .
(51)
The exponential is nonnegative, including when it underflows to zero. Since floating-point addition and rounding are order-preserving under the fixed semantics, the updated denominator is at least dq . Thus every transition either strictly advances the denominator or leaves it unchanged through underflow or absorption. The same is true of every composition of transitions. Consequently, under repeated application of any transformation s ∈ TH , each denominator follows a nondecreasing sequence in a finite chain and therefore eventually stabilizes. It remains to rule out a cycle in the numerator after the denominator has stabilized. For a fixed input and query, every scalar coordinate of the numerator is updated by addition of the fixed floating-point value fl(exp(α(q, k))v) .
(52)
Addition by a fixed value and floating-point rounding are order-preserving. Hence, on each scalar numerator coordinate, every s ∈ TH acts as an order-preserving self-map of a finite chain. An order-preserving self-map of a finite chain has no nontrivial cycle: depending on whether x ≤ s(x) or s(x) ≤ x, its orbit is respectively nondecreasing or nonincreasing and must stabilize. The head state has finitely many queries and finitely many scalar accumulator coordinates. For each s, taking the maximum stabilization index over all coordinates and states gives Ns ∈ N such that sNs = sNs +1 . Since TH is finite, the maximum of the Ns gives a common N satisfying sN = sN +1 for every s ∈ TH . Therefore TH ∈ Ap. Lemma 28. There exists a soft-attention head H such that U 3 ≺ (TH , ZH ), i.e., its transition semigroup is not R-trivial. Proof. It suffices to use one scalar-valued head with a singleton as the query set. Let p be the significand precision of the floating-point format and choose the exactly representable values C = 2p+1 , D = 2p+2 . (53) These values lie in the normal range of every standard IEEE binary format. Their spacing implies fl(C + x) = C for x ∈ {−1, 0, 1}, fl(D + 1) = D. (54) Take four inputs x0 , xC , x−C , x1 whose keys all have score zero against the unique query and whose respective values are 0, C, −C, 1. Since exp(0) = 1, their numerator increments are precisely these four values, whereas each denominator increment is 1. Consider the three head states z1 = (−1, D), za = (0, D), zb = (1, D), (55) ′ and set Z = {z1 , za , zb }. By Eq. (54), the transformation induced by x0 fixes every element of Z ′ and therefore restricts to idZ ′ . Let Fa be the transformation induced by the word xC x−C . For every (n, D) ∈ Z ′ , x
x−C
C (n, D) 7−−→ (C, D) 7−−−→ (0, D) = za . (56) Thus, Fa restricts to the constant transformation with image za . Similarly, the word xC x−C x1 induces a transformation Fb such that
xC x−C
x
1 (n, D) 7−−−−−→ (0, D) 7−→ (1, D) = zb (57) ′ for every (n, D) ∈ Z . Hence, Fb restricts to the constant transformation with image zb . The set Z ′ is invariant under idZ ′ , Fa , and Fb , and a product of constant maps is its last factor, so on Z ′ Fx Fy = Fy , idZ ′ Fx = Fx idZ ′ = Fx , x, y ∈ {a, b}, (58) each identity verified by evaluating at any state. This is the multiplication in Definition 44. The surjections θ(z1 ) = 1, θ(za ) = a, θ(zb ) = b, (59) φ(idZ ′ ) = 1, φ(Fa ) = a, φ(Fb ) = b, (60) satisfy θ(z · F ) = θ(z) · φ(F ) in all nine cases, both sides being the label of the last reset, or the old label if none. This is the division U 3 ≺ (TH , ZH ).
Remark 45 (Equality against division). Here, they hold only on Z ′ : before saturation, the denominator counts letters, one per input, and a length counter separates words of different lengths. For instance (0, 0)·Fb = (1, 3) while (0, 0)·Fa Fb = (1, 5), so Fa Fb ̸= Fb in TH , and Fa Fa ̸= Fa although a is idempotent in U3 . The subsemigroup id, Fa , Fb sem is therefore strictly larger than U3 , of which it sees the relations only after restriction to the saturated slice: a quotient of a subobject, which is precisely a division, and the reason Lemmas 26 and 28 assert ≺ where Lemma 24 could assert an isomorphism onto a subobject.
D
Semigroup Decomposition Beyond Krohn–Rhodes
Krohn–Rhodes theory (Krohn and Rhodes 1965) describes the decomposition of any aperiodic transformation semigroup into a wreath product of transformation semigroups whose semigroup is U3 . However, transformers may not be able to instantiate U3 , meaning none of the basic constituents of such a decomposition is attainable. Therefore, we utilize a refinement of Krohn–Rhodes due to Stiffler (1973) that further decomposes aperiodic semigroups into smaller semigroups U1 , U2 ≤ U3 , which we will show can be realized by different types of attention heads. Theorem 46 (Krohn and Rhodes (1965), semigroup version). Every finite transformation semigroup (S, Z) divides a finite wreath product with factors alternating between copies of U 3 and simple group factors. Corollary 47. Let (S, Z) be a finite transformation semigroup. Then the semigroup S is aperiodic, S ∈ Ap, if and only if (S, Z) divides a finite wreath product of copies of U 3 : S ∈ Ap
⇐⇒
∃ Z : (S, Z) ≺ U 3 ≀ · · · ≀ U 3 .
(61)
Theorem 48 (Stiffler (1973), Thm 3.4 (a) and Fact 1.9). For every finite semigroup S, S ∈ Def
⇐⇒
∃ Z : (S, Z) ≺ U 1 ≀ · · · ≀ U 1 .
(62)
Moreover, Def is closed under finite wreath products and division. Consequently, if a finite transformation semigroup (S, Z) divides a finite cascade whose component semigroups are definite, then S ∈ Def . Theorem 49 (Stiffler (1973), Thm. 3.4(b) and Fact 1.9). For every finite semigroup S, S∈R
⇐⇒
∃ Z : (S, Z) ≺ U 2 ≀ · · · ≀ U 2 .
(63)
Moreover, R is closed under finite wreath products and division. Consequently, if a finite transformation semigroup (S, Z) divides a finite cascade whose component semigroups are R-trivial, then S ∈ R. Theorem 50 (Stiffler (1973), Thm 3.4 (c), Fact 1.9, Cor. 12 (c) and Rem. 2.13). For every finite semigroup S, S ∈ LR
⇐⇒
∃ Z : (S, Z) ≺ U 1 ≀ · · · ≀ U 1 ≀ U 2 ≀ · · · ≀ U 2 . (64) Furthermore, Def and R are closed under finite wreath products and division. Therefore, if a finite transformation semigroup (S, Z) divides a finite cascade whose component semigroups are R-trivial and definite, then S ∈ LR.
Remark 51. Note the different notational conventions: 1. Whereas Stiffler (1973) uses right wreath products, we define wreath factors to act from the left to better match the common indexing of layers in neural networks. Hence, our restatement of Theorem 50 has U 1 s on the left (think: closer to the transformer input) and U 2 s on the right (higher up in the layers), the reverse of Stiffler (1973). 2. We adopt the notation of Stiffler (1973) for the prime semigroups U1 , U2 , U3 . Note that these have different names elsewhere; for instance, our U3 is called U2 in Eilenberg (1976), etc.