Approximate Homomorphisms and Convergent Representations in Transducers

# Approximate Homomorphisms and Convergent Representations in Transducers
Source: [https://arxiv.org/html/2608.20428](https://arxiv.org/html/2608.20428)
Santiago Cifuentes

August 2026

###### Abstract

We study the stability of minimal representations of controlled stochastic processes \(in particular,transducers\) under perturbations\. This question is motivated by recent experiments finding predictive\-state structure in the latent representations of neural networks\. We consider standard, linear and predictive transducers\. We introduce notions of approximate homomorphism capturing local structural similarity between them, together with metrics comparing their induced dynamics \(which we refer to asinterfaces\), and prove properties such as composability of the approximate homomorphisms\. For standard transducers, we show that there exist simple interfaces for which there is no approximate homomorphism between the different implementations of the dynamics\. In contrast, for every finite\-rank interfaceℐ\\mathcal\{I\}, we prove that all minimal linear transducers implementing interfaces sufficiently close toℐ\\mathcal\{I\}have an approximate homomorphism to the minimal implementation ofℐ\\mathcal\{I\}, with error linear in the perturbation size\. We prove an analogous stability result for predictive transducers under a residual metric using some mild hypothesis regarding the indistinguishability of the belief states\. These results identify conditions under which canonical transducer representations are robust to perturbations, while showing that such convergence fails without additional structural restrictions\. Under the assumption that these type of abstractions are embedded into the hidden layers of modern AI models, this gives some theoretical support to the hypothesis that their latent representations exhibit structural convergence\.

## 1Introduction

Since the beginning of neural networks, many AI architectures have included some type of hidden or intermediate layers between the input and output gates in which the models can encode partial results of their computation\. In these layers the models usually learn, through training, to represent latent variables and general information useful for their goals\[[4](https://arxiv.org/html/2608.20428#bib.bib45),[6](https://arxiv.org/html/2608.20428#bib.bib12),[31](https://arxiv.org/html/2608.20428#bib.bib46)\]\.

Although the training process is not deterministic and depends on things such as the training algorithm, the initial parameters and the choice of hyperparameters, it has been observed from the beginning of the deep learning revolution that some structure of these hidden layers coincides between different models\[[33](https://arxiv.org/html/2608.20428#bib.bib13),[37](https://arxiv.org/html/2608.20428#bib.bib47)\], even when they are implemented in different architectures\. There are different ways of measuring this similarity, but for most of them this “convergent phenomenon” can be found\[[28](https://arxiv.org/html/2608.20428#bib.bib19)\]\. To name a few of these metrics, similarity can be measured by comparing the distribution of latent vectors inside each layer\[[9](https://arxiv.org/html/2608.20428#bib.bib17),[29](https://arxiv.org/html/2608.20428#bib.bib14)\], by comparing functional aspects of the different layers\[[28](https://arxiv.org/html/2608.20428#bib.bib19)\], or by finding a linear transformation able to transfer features from one model to another\[[2](https://arxiv.org/html/2608.20428#bib.bib18),[9](https://arxiv.org/html/2608.20428#bib.bib17),[13](https://arxiv.org/html/2608.20428#bib.bib50),[18](https://arxiv.org/html/2608.20428#bib.bib16)\]\. These experimental results have motivated the recent proposal of the “Platonic Representation Hypothesis”\[[23](https://arxiv.org/html/2608.20428#bib.bib15)\]: the idea that “Neural networks, trained with different objectives on different data and modalities, are converging to a shared statistical model of reality in their representation spaces”\. Although it is unclear to what extent this hypothesis may hold\[[10](https://arxiv.org/html/2608.20428#bib.bib51),[15](https://arxiv.org/html/2608.20428#bib.bib49),[19](https://arxiv.org/html/2608.20428#bib.bib20)\], most results suggest that some kind of convergence can sometimes be found in different models trained for a similar task\.

Overall, there are three core hypotheses which can help to understand this situation\[[23](https://arxiv.org/html/2608.20428#bib.bib15)\]\. First, thesimplicity biashypothesis states that deep AI architectures trained through stochastic gradient descent have a tendency to converge to structurally simple representations which usually generalize well\[[5](https://arxiv.org/html/2608.20428#bib.bib21),[25](https://arxiv.org/html/2608.20428#bib.bib52),[51](https://arxiv.org/html/2608.20428#bib.bib22)\]\. Meanwhile, thecapacity hypothesisstates that as models include more parameters they encompass a larger set of possible behaviours, and thus it is more likely for different architectures to have a non\-empty intersection regarding the instantiations they allow\[[23](https://arxiv.org/html/2608.20428#bib.bib15)\]\. Finally, themultitask hypothesisstates that there are fewer representations capable of performing multiple tasks at the same time\[[8](https://arxiv.org/html/2608.20428#bib.bib23),[39](https://arxiv.org/html/2608.20428#bib.bib48)\], and thus as we train models for more complex goals the optimal configurations become sparser\.

There exists an ongoing theoretical program trying to give support to these hypotheses\. For instance, ideas such as implicit regularization\[[22](https://arxiv.org/html/2608.20428#bib.bib24)\]or neural collapse\[[24](https://arxiv.org/html/2608.20428#bib.bib25)\], or entire frameworks such as singular learning theory\[[52](https://arxiv.org/html/2608.20428#bib.bib26)\]try to explain how modern gradient descent finds robust representations in current deep learning architectures although the number of model parameters allows for overfitting\. A different approach relies on the idea of aworld model\[[20](https://arxiv.org/html/2608.20428#bib.bib27),[21](https://arxiv.org/html/2608.20428#bib.bib28),[44](https://arxiv.org/html/2608.20428#bib.bib1)\]\. More precisely, different empirical and theoretical results support the idea that modern agents develop an internal mechanism equivalent to a description of the dynamics of the environment surrounding them\[[11](https://arxiv.org/html/2608.20428#bib.bib31),[38](https://arxiv.org/html/2608.20428#bib.bib32),[43](https://arxiv.org/html/2608.20428#bib.bib4),[46](https://arxiv.org/html/2608.20428#bib.bib30)\]\. If we formalize these structures using some mathematical abstraction, then we can ask the question of whether the set of these abstractions implementing the same dynamics has some shared structure\[[44](https://arxiv.org/html/2608.20428#bib.bib1)\]\. If the answer is positive, this provides some support for the idea that agents learning from a similar data distribution should share some aspects of their internal representations\. See Figure[1](https://arxiv.org/html/2608.20428#S1.F1)for a diagrammatic sketch of this idea\.

![Refer to caption](https://arxiv.org/html/2608.20428v1/diagram/diagram_main_idea.png)Figure 1:The world model\-based approach for understanding convergent structure\. We expect that each internal layer of a neural network architecture encodes a world model through some mathematical abstraction \(such as a transducer\)\. Then, we search for convergent structure in these abstractions by looking for a minimal model representing the dynamics\.In this work we investigate this idea using*transducers*as an abstraction of world models\. A transducer is a controlled stochastic system with hidden states, inputs, and outputs, which induces an*interface*: for every finite sequence of interventions, the interface specifies a probability distribution over the corresponding sequence of observations in the real world\. These types of structures have been studied recently as tools to formalize world models\[[7](https://arxiv.org/html/2608.20428#bib.bib3),[44](https://arxiv.org/html/2608.20428#bib.bib1)\], and different experimental results support the idea that modern AI agents implement this type of structure in their residual stream\[[46](https://arxiv.org/html/2608.20428#bib.bib30),[47](https://arxiv.org/html/2608.20428#bib.bib29)\]\. Moreover, in\[[44](https://arxiv.org/html/2608.20428#bib.bib1)\]it was proven that in some situations the set of transducers implementing a specified behaviour has a unique minimal implementation such that all other implementations can be structurally mapped into the minimal one\. From our perspective, this is a positive result encouraging the possibility of convergent structure\.

Our goal is to improve this type of result by weakening some of its hypotheses\. More precisely, we aim to improve the result by making it robust to noise and approximation\. Consider that we have two transducers implementing asimilarbehaviour \(measured through some proper metric\)\. Then, is it the case that they share some structure, measured through some other metric? Note that in practical scenarios we expect different models to learn from slightly different datasets, and thus we need the convergence of transducers to hold also in the case in which they implement slightly different interfaces\.

#### Our Contributions\.

We consider three types of transducers: the “standard” ones, linear transducers and predictive transducers, and do the following:

1. 1\.We give a notion of approximate homomorphism for all types of transducers that allows to decide when a transducer isε\\varepsilon\-similar to another one\. Our notion is robust with respect to composition and preserves the dynamics that the transducers represent up to an error that scales asO⁡\(ε\)O\(\\varepsilon\)under discounted metrics \(i\.e\. metrics that weight differences in long\-horizon predictions using a discount factor that decays exponentially with the number of steps\)\.
2. 2\.In the context of standard transducers, we show that there exist interfaces such that the standard transducer implementing these interfaces are structurally far away \(using our notion of approximate homomorphism to measure distance\)\. This result shows that the result from\[[44](https://arxiv.org/html/2608.20428#bib.bib1)\]regarding the non\-existence of a minimal representation for normal transducers cannot be salvaged by introducing an error term in the homomorphism\.
3. 3\.For linear transducers, we show that for a significant subset of interfaces it is the case that all minimal linear transducers implementing an interfaceε\\varepsilon\-similar \(for a sufficiently smallε\>0\\varepsilon\>0\) to interfaceℐ\\mathcal\{I\}can be mapped to a common linear transducer introducing some error that scales asΓℐ​ε\\Gamma\_\{\\mathcal\{I\}\}\\varepsilon, whereΓℐ\\Gamma\_\{\\mathcal\{I\}\}represents a constant depending only onℐ\\mathcal\{I\}\. This shows that the minimality of linear implementations is robust to noise in a small neighbourhood of the interface\. This result is obtained by inspecting the canonical construction of the minimal linear transducer, which is obtained by working with theHankel matrixof the interface\.
4. 4\.Finally, we obtain an analogous result for predictive transducers by leveraging the construction of the minimal predictive implementation based on the notion of aϵ\\epsilon\-machine from computational mechanics\[[3](https://arxiv.org/html/2608.20428#bib.bib2)\]\.

Taken together, these results show that the existence of minimal representations \(and thus of potential convergent structure\) is robust to error for the family of linear and predictive transducers\. Thus, we provide more theoretical support for the Platonic Representation Hypothesis under the hypothesis that world models show up inside the internal structure of modern AI architectures in the form of these types of abstractions\. In the case of predictive transducers, this was partially observed empirically\[[46](https://arxiv.org/html/2608.20428#bib.bib30),[47](https://arxiv.org/html/2608.20428#bib.bib29)\]\. Meanwhile, although there is no previous experiment finding linear transducers within the hidden layers of modern models, we suspect that these architectures should leverage the fact that any representation they contain is embedded in a linear space, and thus it is natural for them to prefer linear transducers over predictive ones\. We believe that a fruitful direction for future work would be to reproduce the set\-up of\[[47](https://arxiv.org/html/2608.20428#bib.bib29)\]but looking for a minimal linear transducer \(or a functionally equivalent mechanism\) inside the residual stream\.

The remainder of the paper is organized as follows\. Section[2](https://arxiv.org/html/2608.20428#S2)reviews standard, linear, and predictive transducers together with their exact notions of reduction and minimality\. Section[3](https://arxiv.org/html/2608.20428#S3)introduces approximate homomorphisms, metrics on interfaces, and the composability and continuity results\. Section[4](https://arxiv.org/html/2608.20428#S4)studies approximate common minima for nearby interfaces, giving respectively the negative result for unrestricted transducers and the positive results for linear and predictive transducers\. Finally, in Section[5](https://arxiv.org/html/2608.20428#S5)we conclude the paper by summarizing our results, discussing their limitations and describing future lines of research\. All proofs are deferred to the Appendix to improve readability\.

#### Related work\.

Finite\-state transducers have a long history in automata theory, beginning with the Mealy and Moore machines\[[34](https://arxiv.org/html/2608.20428#bib.bib33),[36](https://arxiv.org/html/2608.20428#bib.bib34)\]\. In their deterministic form, they describe systems whose internal state is updated in response to an input while producing an output\. Weighted and probabilistic variants replace deterministic transitions by numerical weights or stochastic kernels, and have been extensively studied in formal language theory\[[35](https://arxiv.org/html/2608.20428#bib.bib35)\]\. The stochastic transducers considered here are closely related to controlled Markov models, and in particular they resemble Markov Decision Processes \(MDPs\)\[[40](https://arxiv.org/html/2608.20428#bib.bib36)\]\.

To identify convergent structure we use the notion of homomorphism, which corresponds to a map from one transducer to another that preserves local structure\. This type of “coarse\-graining” operations have a long history in the different abstractions we mentioned before\. For Markov chains, classical lumpability identifies states whose transition probabilities agree after aggregation\[[26](https://arxiv.org/html/2608.20428#bib.bib37)\]\. Probabilistic bisimulation gives a related behavioural equivalence for labelled probabilistic transition systems\[[30](https://arxiv.org/html/2608.20428#bib.bib5)\]\. In the MDP literature,\[[17](https://arxiv.org/html/2608.20428#bib.bib7)\]develops exact state equivalences and model minimization based on bisimulation, while\[[41](https://arxiv.org/html/2608.20428#bib.bib8)\]formulates MDP and semi\-MDP homomorphisms as maps that preserve rewards and aggregate transition probabilities\. These notions have subsequently been organized into broader taxonomies of state abstraction\[[32](https://arxiv.org/html/2608.20428#bib.bib38)\]\.

We will study notions of homomorphism that allow for some error, and thus we refer to them as approximate homomorphisms\. In the context of MDPs, such approximate reductions have already been considered\[[1](https://arxiv.org/html/2608.20428#bib.bib41),[42](https://arxiv.org/html/2608.20428#bib.bib9),[50](https://arxiv.org/html/2608.20428#bib.bib10)\], and our definitions as well as our robustness results \(regarding composition and preservation of the interface up to discounted metrics\) have analogues in the literature\. In probabilistic transition systems, the notion of approximate bisimulation has a long history\[[14](https://arxiv.org/html/2608.20428#bib.bib39),[16](https://arxiv.org/html/2608.20428#bib.bib6)\]and remains an active area of research\[[27](https://arxiv.org/html/2608.20428#bib.bib40),[49](https://arxiv.org/html/2608.20428#bib.bib11)\]\.

The notion of the Hankel matrix of a process was introduced in the context of weighted automata to construct minimal linear implementations\[[45](https://arxiv.org/html/2608.20428#bib.bib42)\]\. In that setting, the minimal realizations obtained are unique up to an invertible linear change of coordinates \(i\.e\. a base change\)\. Regarding predictive transducers, we use tools from computational mechanics\[[12](https://arxiv.org/html/2608.20428#bib.bib43),[48](https://arxiv.org/html/2608.20428#bib.bib44)\]to obtain minimal representations\. In particular, the extension of computational mechanics to input\-output processes\[[3](https://arxiv.org/html/2608.20428#bib.bib2)\]can be applied almost directly to our context\.

## 2Types of transducers

In this section we describe the different types of transducers that we will consider in this paper\.

### 2\.1“Standard” Transducers

We usetransducersto model world models\.

###### Definition 1\.

Atransduceris given by a tuple\(𝒮,𝒜,𝒪,κ,p\)\(\\mathcal\{S\},\\mathcal\{A\},\\mathcal\{O\},\\kappa,p\)where𝒮\\mathcal\{S\}is a set of states,𝒜\\mathcal\{A\}is a set of actions \(or inputs\),𝒪\\mathcal\{O\}is a set of reactions \(or outputs\),κ\\kappais a Markov kernel111In this context, a Markov kernel is simply a set of conditional distributions\.of the form\{κτ\(s′,o\|s,a\):s,s′∈𝒮,a∈𝒜,o∈𝒪,τ∈ℕ\}\\\{\\kappa\_\{\\tau\}\(s^\{\\prime\},o\|s,a\):s,s^\{\\prime\}\\in\\mathcal\{S\},a\\in\\mathcal\{A\},o\\in\\mathcal\{O\},\\tau\\in\\mathbb\{N\}\\\}andp∈Δ⁡\(𝒮\)p\\in\\Delta\(\\mathcal\{S\}\)is an initial distribution over the set of states\.

Transducers represent a world model indicating, for every possible sequence of actionsa1​…​ana\_\{1\}\\ldots a\_\{n\}, a distribution on the reactiono1​…​ono\_\{1\}\\ldots o\_\{n\}of the environment\. They use \(hidden\) states to keep track of the previous events, and the functionκ\\kappadescribes the relation between actions and outputs and how the state is updated\. This function can depend on the timestepτ∈ℕ\\tau\\in\\mathbb\{N\}, but for simplicity we will assume thatκτ=κ0\\kappa\_\{\\tau\}=\\kappa\_\{0\}for everyτ\\tau\(this corresponds to assumingstationarydynamics\)\. Also, we may omitκ\\kappain the notation and simply talk about the probabilities of the events\. For example, we writePr\(o\|s,a\)T\\Pr\{\}\_\{T\}\\left\(o\|s,a\\right\)to denote the value∑s′∈𝒮κ\(s′,o\|s,a\)\\sum\_\{s^\{\\prime\}\\in\\mathcal\{S\}\}\\kappa\(s^\{\\prime\},o\|s,a\), or similarlyPr\(s′\|s,a,o\)T\\Pr\{\}\_\{T\}\\left\(s^\{\\prime\}\|s,a,o\\right\)to denoteκ\(s′,o\|s,a\)/Pr\(o\|s,a\)T\\kappa\(s^\{\\prime\},o\|s,a\)/\\Pr\{\}\_\{T\}\(o\|s,a\)whenever the denominator is positive\. We will assume for simplicity that𝒮,𝒜\\mathcal\{S\},\\mathcal\{A\}and𝒪\\mathcal\{O\}are countable\.

AtraceoverTTis a finite or infinite sequence of outputs\. As mentioned, any transducer defines a probability for each traceconditionedon each sequence of actions\. We refer to such a description \(i\.e\. a list of probabilitiesPr⁡\(o1​…​on\|a\)\\Pr\\left\(o\_\{1\}\\ldots o\_\{n\}\|\\textbf\{a\}\\right\)for every finite sequenceo1​…​on∈𝒪no\_\{1\}\\ldots o\_\{n\}\\in\\mathcal\{O\}^\{n\}and infinite sequence𝐚∈𝒜ω\\mathbf\{a\}\\in\\mathcal\{A\}^\{\\omega\}\) as aninterfaceℐ\\mathcal\{I\}\. We will only be interested in anticipation\-free interfaces, i\.e\. those that satisfyPr⁡\(o1​…​on\|a\)=Pr⁡\(o1​…​on\|a1​…​an\)\\Pr\\left\(o\_\{1\}\\ldots o\_\{n\}\|\\textbf\{a\}\\right\)=\\Pr\\left\(o\_\{1\}\\ldots o\_\{n\}\|a\_\{1\}\\ldots a\_\{n\}\\right\)\. Anticipation\-free interfaces coincide exactly with interfaces “implementable” by transducers\[[44](https://arxiv.org/html/2608.20428#bib.bib1)\]\[Lemma 4\]\.

More precisely, giveno1​…​ono\_\{1\}\\ldots o\_\{n\}anda1​…​ana\_\{1\}\\ldots a\_\{n\}the \(conditioned\) probability that the transducerTTinduces can be computed as

Pr\(o1…on\|a1…an\)T=∑s0​…​sn∈𝒮n\+1p\(s0\)∏t=1nκ\(st,ot\|st−1,at\)\\displaystyle\\Pr\{\}\_\{T\}\\left\(o\_\{1\}\\ldots o\_\{n\}\|a\_\{1\}\\ldots a\_\{n\}\\right\)=\\sum\_\{s\_\{0\}\\ldots s\_\{n\}\\in\\mathcal\{S\}^\{n\+1\}\}p\(s\_\{0\}\)\\prod\_\{t=1\}^\{n\}\\kappa\(s\_\{t\},o\_\{t\}\|s\_\{t\-1\},a\_\{t\}\)\(1\)
Whenever\|𝒮\|,\|𝒜\|,\|𝒪\|<∞\|\\mathcal\{S\}\|,\|\\mathcal\{A\}\|,\|\\mathcal\{O\}\|<\\inftythis computation can be simplified: ifMa,o∈ℝ\|𝒮\|×\|𝒮\|M\_\{a,o\}\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\times\|\\mathcal\{S\}\|\}is given byMa,o\(s,s′\)=κ\(s′,o\|s,a\)M\_\{a,o\}\(s,s^\{\\prime\}\)=\\kappa\(s^\{\\prime\},o\|s,a\), then

Pr\(o1…on\|a1…an\)T=pMa1,o1…Man,on𝟏\\displaystyle\\Pr\{\}\_\{T\}\(o\_\{1\}\\ldots o\_\{n\}\|a\_\{1\}\\ldots a\_\{n\}\)=pM\_\{a\_\{1\},o\_\{1\}\}\\ldots M\_\{a\_\{n\},o\_\{n\}\}\\mathbf\{1\}
###### Example 1\.

Figure[2](https://arxiv.org/html/2608.20428#S2.F2)shows a transducer with deterministic dynamics \(i\.e\. for everys∈𝒮,a∈𝒜s\\in\\mathcal\{S\},a\\in\\mathcal\{A\}there is somes′∈𝒮s^\{\\prime\}\\in\\mathcal\{S\}ando∈𝒪o\\in\\mathcal\{O\}such thatκ\(s′,o\|s,a\)=1\\kappa\(s^\{\\prime\},o\|s,a\)=1\)\. The states are𝒮=\{s0,s1\}\\mathcal\{S\}=\\\{s\_\{0\},s\_\{1\}\\\}, the actions𝒜=\{continue,stay\}\\mathcal\{A\}=\\\{\\texttt\{continue\},\\texttt\{stay\}\\\}, and the possible outputs𝒪=\{0,1\}\\mathcal\{O\}=\\\{0,1\\\}\. The initial distribution is concentrated in states0s\_\{0\}\. It represents a system that outputs010101​…010101\\ldotsindefinitely as long as the actioncontinueis chosen at each step\. Ifstayis employed instead, the dynamics are “frozen” for one step\.

s0s\_\{0\}s1s\_\{1\}stay/0stay/1continue/0continue/1Figure 2:Example of a “deterministic” transducer\. Each edge contains an actionaafollowed by an outputoo\. An edge fromsstos′s^\{\\prime\}with labela/oa/oindicates thatκ\(s′,o\|s,a\)=1\\kappa\(s^\{\\prime\},o\|s,a\)=1\.
We will assume that all the states of a transducer are reachable from some state with initial positive probability\. Namely, for every statessthere must exist a states0s\_\{0\}such thatp⁡\(s0\)\>0p\(s\_\{0\}\)\>0and a sequence of actionsa1​…​aka\_\{1\}\\ldots a\_\{k\}such thatPrT⁡\(s\|s0,a1​…​ak\)\>0\\Pr\_\{T\}\\left\(s\|s\_\{0\},a\_\{1\}\\ldots a\_\{k\}\\right\)\>0\. Also, we will sometimes useΣ=𝒜×𝒪\\Sigma=\\mathcal\{A\}\\times\\mathcal\{O\}\.

There is a well\-defined notion ofhomomorphismfor these objects, which allows us to coarse\-grain states as well as input and output symbols\.

###### Definition 2\.

Given two transducersT1=\(𝒮1,𝒜1,𝒪1,κ1,p1\)T\_\{1\}=\(\\mathcal\{S\}\_\{1\},\\mathcal\{A\}\_\{1\},\\mathcal\{O\}\_\{1\},\\kappa\_\{1\},p\_\{1\}\)andT2=\(𝒮2,𝒜2,𝒪2,κ2,p2\)T\_\{2\}=\(\\mathcal\{S\}\_\{2\},\\mathcal\{A\}\_\{2\},\\mathcal\{O\}\_\{2\},\\kappa\_\{2\},p\_\{2\}\), ahomomorphismis given by three mappings⟨ϕ:𝒮1→𝒮2,f:𝒜1→𝒜2,g:𝒪1→𝒪2⟩\\langle\\phi:\\mathcal\{S\}\_\{1\}\\to\\mathcal\{S\}\_\{2\},f:\\mathcal\{A\}\_\{1\}\\to\\mathcal\{A\}\_\{2\},g:\\mathcal\{O\}\_\{1\}\\to\\mathcal\{O\}\_\{2\}\\ranglesatisfying

κ2\(s2,o2\|ϕ\(s1\),f\(a1\)\)\\displaystyle\\kappa\_\{2\}\(s\_\{2\},o\_\{2\}\|\\phi\(s\_\{1\}\),f\(a\_\{1\}\)\)=∑s′∈ϕ−1​\(s2\)o′∈g−1​\(o2\)κ1\(s′,o′\|s1,a1\),\\displaystyle=\\sum\_\{\\begin\{subarray\}\{c\}s^\{\\prime\}\\in\\phi^\{\-1\}\(s\_\{2\}\)\\\\ o^\{\\prime\}\\in g^\{\-1\}\(o\_\{2\}\)\\end\{subarray\}\}\\kappa\_\{1\}\(s^\{\\prime\},o^\{\\prime\}\|s\_\{1\},a\_\{1\}\),\(2\)p2​\(s2\)\\displaystyle p\_\{2\}\(s\_\{2\}\)=∑s1∈ϕ−1​\(s2\)p1​\(s1\),\\displaystyle=\\sum\_\{s\_\{1\}\\in\\phi^\{\-1\}\(s\_\{2\}\)\}p\_\{1\}\(s\_\{1\}\),\(3\)for everys1∈𝒮1s\_\{1\}\\in\\mathcal\{S\}\_\{1\},a1∈𝒜1a\_\{1\}\\in\\mathcal\{A\}\_\{1\},s2∈𝒮2s\_\{2\}\\in\\mathcal\{S\}\_\{2\}, ando2∈𝒪2o\_\{2\}\\in\\mathcal\{O\}\_\{2\}\.

Condition \([2](https://arxiv.org/html/2608.20428#S2.E2)\) says that the joint one\-step distribution on the next state and output is preserved after applying the coarse\-grainingsϕ\\phiandgg\(and translating actions throughff\)\. Condition \([3](https://arxiv.org/html/2608.20428#S2.E3)\) makes sure that the initial distributions are equivalent up toϕ\\phi\.

If we require𝒪1=𝒪2\\mathcal\{O\}\_\{1\}=\\mathcal\{O\}\_\{2\}and𝒜1=𝒜2\\mathcal\{A\}\_\{1\}=\\mathcal\{A\}\_\{2\}then both transducers have the same “type”\. Moreover, if alsof=g=idf=g=\\texttt\{id\}\{\}andϕ\\phiis surjective we say that the homomorphism is areduction\.

###### Example 2\.

Consider the transducer from Figure[3](https://arxiv.org/html/2608.20428#S2.F3)\. There is a reduction from this transducer to the one from Figure[2](https://arxiv.org/html/2608.20428#S2.F2): defineϕ\\phiasϕ⁡\(s0\)=ϕ⁡\(s2\)=s0\\phi\(s\_\{0\}\)=\\phi\(s\_\{2\}\)=s\_\{0\}andϕ⁡\(s1\)=ϕ⁡\(s3\)=s1\\phi\(s\_\{1\}\)=\\phi\(s\_\{3\}\)=s\_\{1\}, while takingf=g=idf=g=\\texttt\{id\}\{\}\. In some sense, the transducer from Figure[3](https://arxiv.org/html/2608.20428#S2.F3)implements the interface in an “inefficient” manner\.

s0s\_\{0\}s1s\_\{1\}s2s\_\{2\}s3s\_\{3\}stay/0\\texttt\{stay\}/0stay/1\\texttt\{stay\}/1stay/0\\texttt\{stay\}/0stay/1\\texttt\{stay\}/1continue/0\\texttt\{continue\}/0continue/1\\texttt\{continue\}/1continue/0\\texttt\{continue\}/0continue/1\\texttt\{continue\}/1Figure 3:Example of a “deterministic” transducer that implements the same interface as the one from Figure[2](https://arxiv.org/html/2608.20428#S2.F2)\. An edge fromsstos′s^\{\\prime\}with labela/oa/oindicates thatκ\(s′,o\|s,a\)=1\\kappa\(s^\{\\prime\},o\|s,a\)=1\.
Reductions can be composed\. Thus, after fixing an interfaceℐ\\mathcal\{I\}we can look at the set of transducers implementingℐ\\mathcal\{I\}, and if we quotient them properly \(identifying transducersT1T\_\{1\}andT2T\_\{2\}such that there are reductions both fromT1T\_\{1\}toT2T\_\{2\}and fromT2T\_\{2\}toT1T\_\{1\}\) then the reduction relation gives the set aposetstructure\.

In\[[44](https://arxiv.org/html/2608.20428#bib.bib1)\]some properties of these posets are proven, and in particular the fact that in general they need not have a unique minimum\. This situation can be salvaged in at least two ways\. First, if we consider linear transducers \(which allow for “negative” probabilities\), then uniqueness of the minimum can be proven\[[44](https://arxiv.org/html/2608.20428#bib.bib1)\]\[Theorem 2\]\. Second, we can restrict attention to the subposet ofpredictivetransducers \(intuitively, those whose state transitions are deterministic given the last state, action and output\): in that case, there is a unique minimum, and it coincides with theϵ\\epsilon\-machine from computational mechanics\[[3](https://arxiv.org/html/2608.20428#bib.bib2)\]representing the dynamics\[[44](https://arxiv.org/html/2608.20428#bib.bib1)\]\[Theorem 3\]\.

Before proceeding, we note that the definition of homomorphism we introduced is not exactly the same as the one from\[[44](https://arxiv.org/html/2608.20428#bib.bib1)\]\. In Appendix[A\.1](https://arxiv.org/html/2608.20428#A1.SS1)we compare them and show nonetheless that they coincide when we restrict to reductions\. Later we will see that our proposal is easier to extend to the approximate setting\. In particular, Condition \([2](https://arxiv.org/html/2608.20428#S2.E2)\) states thatκ2\\kappa\_\{2\}must be equal to the pushforward ofκ1\\kappa\_\{1\}throughϕ\\phiandgg\. Thus, we can introduce an error term in the homomorphism by comparingκ2\\kappa\_\{2\}to this pushforward using any distance between distributions\.

### 2\.2Linear transducers

We will also considerlinear transducers: a model of a transducer in which the states are embedded in a vector space\. From now on we define, for every interfaceℐ\\mathcal\{I\}, its associated formal series: for everyw∈Σ∗=\(𝒜×𝒪\)∗w\\in\\Sigma^\{\*\}=\(\\mathcal\{A\}\\times\\mathcal\{O\}\)^\{\*\}let

Fℐ\(w\)=Fℐ\(\(a1,o1\)…\(an,on\)\)=Pr\(o1⋯on∣a1⋯an\)ℐ,Fℐ\(ϵ\)=1,F\_\{\\mathcal\{I\}\}\(w\)=F\_\{\\mathcal\{I\}\}\(\(a\_\{1\},o\_\{1\}\)\\ldots\(a\_\{n\},o\_\{n\}\)\)=\\Pr\{\}\_\{\\mathcal\{I\}\}\(o\_\{1\}\\cdots o\_\{n\}\\mid a\_\{1\}\\cdots a\_\{n\}\),\\qquad F\_\{\\mathcal\{I\}\}\(\\epsilon\)=1,whereϵ\\epsilondenotes the empty word\.

###### Definition 3\.

Alinear transducerover\(𝒜,𝒪\)\(\\mathcal\{A\},\\mathcal\{O\}\)is a tupleG=\(V,ξ,λ,\{Mσ\}σ∈Σ\)G=\(V,\\xi,\\lambda,\\\{M\_\{\\sigma\}\\\}\_\{\\sigma\\in\\Sigma\}\), whereVVis a real vector space,ξ∈V\\xi\\in Vis an initial vector,λ∈V∗\\lambda\\in V^\{\*\}is a linear functional, and eachMσ:V→VM\_\{\\sigma\}:V\\to Vis a linear map\. For a wordw=σ1⋯σnw=\\sigma\_\{1\}\\cdots\\sigma\_\{n\}we defineMwM\_\{w\}recursively by

Mϵ=idV,Mw​σ=Mσ​Mw\.M\_\{\\epsilon\}=\\mathrm\{id\}\_\{V\},\\qquad M\_\{w\\sigma\}=M\_\{\\sigma\}M\_\{w\}\.The linear transducer generates the formal series

FG​\(w\)=λ⁡\(Mw​ξ\)\.F\_\{G\}\(w\)=\\lambda\(M\_\{w\}\\xi\)\.We say thatGGimplements an interfaceℐ\\mathcal\{I\}ifFG=FℐF\_\{G\}=F\_\{\\mathcal\{I\}\}\. We will assume without loss of generality thatV=span⁡\{Mw​ξ:w∈Σ∗\}V=\\operatorname\{span\}\\\{M\_\{w\}\\xi:w\\in\\Sigma^\{\*\}\\\}, i\.e\. that the whole spaceVVis ‘‘used’’ by the transducer222We add this hypothesis to improve the clarity of our exposition\. All results still hold when removing this condition\.\.

The size of a linear transducer is measured by the dimension of the linear space needed to represent the series, which can be infinite\.

We now introduce the concept of theHankel matrixof the interface\.

###### Definition 4\.

TheHankel matrixofℐ\\mathcal\{I\}is the infinite matrix

Hℐ​\(u,v\)=Fℐ​\(u​v\),u,v∈Σ∗\.H\_\{\\mathcal\{I\}\}\(u,v\)=F\_\{\\mathcal\{I\}\}\(uv\),\\qquad u,v\\in\\Sigma^\{\*\}\.For each prefixu∈Σ∗u\\in\\Sigma^\{\*\}define the rowhℐ​\(u\):Σ∗→ℝh\_\{\\mathcal\{I\}\}\(u\):\\Sigma^\{\*\}\\to\\mathbb\{R\}such thathℐ​\(u\)​\(v\)=Fℐ​\(u​v\)h\_\{\\mathcal\{I\}\}\(u\)\(v\)=F\_\{\\mathcal\{I\}\}\(uv\)\. Then, the dimension ofℐ\\mathcal\{I\}is

dim\(ℐ\)=rank⁡\(Hℐ\)=dimspan⁡\{hℐ​\(u\):u∈Σ∗\}\.\\dim\(\\mathcal\{I\}\)=\\operatorname\{rank\}\(H\_\{\\mathcal\{I\}\}\)=\\dim\\operatorname\{span\}\\\{h\_\{\\mathcal\{I\}\}\(u\):u\\in\\Sigma^\{\*\}\\\}\.If this rank is finite, we callℐ\\mathcal\{I\}a finite\-rank interface\.

A linear transducer implementing an interface can be obtained from its Hankel matrix\. Let

Vℐ=span⁡\{hℐ​\(u\):u∈Σ∗\}\.V\_\{\\mathcal\{I\}\}=\\operatorname\{span\}\\\{h\_\{\\mathcal\{I\}\}\(u\):u\\in\\Sigma^\{\*\}\\\}\.Pickξℐ=hℐ​\(ϵ\)\\xi\_\{\\mathcal\{I\}\}=h\_\{\\mathcal\{I\}\}\(\\epsilon\)and letλℐ:Vℐ→ℝ\\lambda\_\{\\mathcal\{I\}\}:V\_\{\\mathcal\{I\}\}\\to\\mathbb\{R\}be evaluation at the empty suffix as

λℐ​\(r\)=r​\(ϵ\)\.\\lambda\_\{\\mathcal\{I\}\}\(r\)=r\(\\epsilon\)\.For everyσ∈Σ\\sigma\\in\\Sigma, define the shift operatorRσℐ:Vℐ→VℐR^\{\\mathcal\{I\}\}\_\{\\sigma\}:V\_\{\\mathcal\{I\}\}\\to V\_\{\\mathcal\{I\}\}by

Rσℐ​hℐ​\(u\)=hℐ​\(u​σ\),R^\{\\mathcal\{I\}\}\_\{\\sigma\}h\_\{\\mathcal\{I\}\}\(u\)=h\_\{\\mathcal\{I\}\}\(u\\sigma\),and extend linearly\. This is well\-defined: if∑iαi​hℐ​\(ui\)=0\\sum\_\{i\}\\alpha\_\{i\}h\_\{\\mathcal\{I\}\}\(u\_\{i\}\)=0, then for every suffixvv,

∑iαi​hℐ​\(ui​σ\)​\(v\)=∑iαi​Fℐ​\(ui​σ​v\)=∑iαi​hℐ​\(ui\)​\(σ​v\)=0\.\\sum\_\{i\}\\alpha\_\{i\}h\_\{\\mathcal\{I\}\}\(u\_\{i\}\\sigma\)\(v\)=\\sum\_\{i\}\\alpha\_\{i\}F\_\{\\mathcal\{I\}\}\(u\_\{i\}\\sigma v\)=\\sum\_\{i\}\\alpha\_\{i\}h\_\{\\mathcal\{I\}\}\(u\_\{i\}\)\(\\sigma v\)=0\.Thus, it follows thatGℐ=\(Vℐ,ξℐ,λℐ,\{Rσℐ\}σ∈Σ\)G\_\{\\mathcal\{I\}\}=\(V\_\{\\mathcal\{I\}\},\\xi\_\{\\mathcal\{I\}\},\\lambda\_\{\\mathcal\{I\}\},\\\{R^\{\\mathcal\{I\}\}\_\{\\sigma\}\\\}\_\{\\sigma\\in\\Sigma\}\)is a linear transducer, andλℐ​\(Rwℐ​ξℐ\)=Fℐ​\(w\)\\lambda\_\{\\mathcal\{I\}\}\(R^\{\\mathcal\{I\}\}\_\{w\}\\xi\_\{\\mathcal\{I\}\}\)=F\_\{\\mathcal\{I\}\}\(w\)for every wordww\.

This representation is minimal: ifG=\(V,ξ,λ,\{Mσ\}\)G=\(V,\\xi,\\lambda,\\\{M\_\{\\sigma\}\\\}\)implementsℐ\\mathcal\{I\}, then

hℐ​\(u\)​\(v\)=Fℐ​\(u​v\)=λ⁡\(Mv​Mu​ξ\)\.h\_\{\\mathcal\{I\}\}\(u\)\(v\)=F\_\{\\mathcal\{I\}\}\(uv\)=\\lambda\(M\_\{v\}M\_\{u\}\\xi\)\.for every wordu,vu,v\. Hence all Hankel rows are obtained from vectorsMu​ξ∈VM\_\{u\}\\xi\\in V, so

rank⁡\(Hℐ\)≤dimV\.\\operatorname\{rank\}\(H\_\{\\mathcal\{I\}\}\)\\leq\\dim V\.Note that minimal linear transducers are unique up to invertible linear changes of coordinates\.

In the context of linear transducers we will uselinear reductionsto formalize the idea of homomorphisms between models\.

###### Definition 5\.

LetG=\(V,ξ,λ,\{Mσ\}σ∈Σ\)G=\(V,\\xi,\\lambda,\\\{M\_\{\\sigma\}\\\}\_\{\\sigma\\in\\Sigma\}\)andG′=\(W,ξ′,λ′,\{Nσ\}σ∈Σ\)G^\{\\prime\}=\(W,\\xi^\{\\prime\},\\lambda^\{\\prime\},\\\{N\_\{\\sigma\}\\\}\_\{\\sigma\\in\\Sigma\}\)be linear transducers over the same input and output alphabets\. Alinear reductionfromGGtoG′G^\{\\prime\}is a surjective linear mapL:V→WL:V\\to Wsatisfying

1. 1\.L​ξ=ξ′L\\xi=\\xi^\{\\prime\}\.
2. 2\.L​Mσ=Nσ​L​for every​σ∈ΣLM\_\{\\sigma\}=N\_\{\\sigma\}L\\text\{ for every \}\\sigma\\in\\Sigma\.
3. 3\.λ′​L=λ\\lambda^\{\\prime\}L=\\lambda\.

The first condition preserves the initial vector, the second says thatLLtranslates the internal dynamics, and the third preserves the “reading” of the vectors\. These conditions imply thatλ′​\(Nw​ξ′\)=λ⁡\(Mw​ξ\)\\lambda^\{\\prime\}\(N\_\{w\}\\xi^\{\\prime\}\)=\\lambda\(M\_\{w\}\\xi\)for every wordww\.

By the construction above, it can be proven that any linear transducerGGimplementingℐ\\mathcal\{I\}can be reduced toGℐG\_\{\\mathcal\{I\}\}\.

###### Lemma 1\.

LetG=\(V,ξ,λ,\{Mσ\}\)G=\(V,\\xi,\\lambda,\\\{M\_\{\\sigma\}\\\}\)be a linear transducer implementing an interfaceℐ\\mathcal\{I\}\. Then there is a linear reductionρG:G→Gℐ\\rho\_\{G\}:G\\to G\_\{\\mathcal\{I\}\}given by

ρG​\(Mw​ξ\)=hℐ​\(w\)\.\\rho\_\{G\}\(M\_\{w\}\\xi\)=h\_\{\\mathcal\{I\}\}\(w\)\.

###### Example 3\.

The deterministic transducerTTfrom Figure[2](https://arxiv.org/html/2608.20428#S2.F2)admits a simple linear representation\. Let

V=ℝ2,ξ=\(10\),λ⁡\(x0,x1\)=x0\+x1,V=\\mathbb\{R\}^\{2\},\\qquad\\xi=\\begin\{pmatrix\}1\\\\ 0\\end\{pmatrix\},\\qquad\\lambda\(x\_\{0\},x\_\{1\}\)=x\_\{0\}\+x\_\{1\},where the two standard basis vectors represent the statess0s\_\{0\}ands1s\_\{1\}\. Consider the transition maps

M𝖼𝗈𝗇𝗍𝗂𝗇𝗎𝖾,0=\(0010\),M𝖼𝗈𝗇𝗍𝗂𝗇𝗎𝖾,1=\(0100\),M\_\{\\mathsf\{continue\},0\}=\\begin\{pmatrix\}0&0\\\\ 1&0\\end\{pmatrix\},\\qquad M\_\{\\mathsf\{continue\},1\}=\\begin\{pmatrix\}0&1\\\\ 0&0\\end\{pmatrix\},and

M𝗌𝗍𝖺𝗒,0=\(1000\),M𝗌𝗍𝖺𝗒,1=\(0001\)\.M\_\{\\mathsf\{stay\},0\}=\\begin\{pmatrix\}1&0\\\\ 0&0\\end\{pmatrix\},\\qquad M\_\{\\mathsf\{stay\},1\}=\\begin\{pmatrix\}0&0\\\\ 0&1\\end\{pmatrix\}\.Then, the linear transducerG=\(V,ξ,λ,\(Mσ\)σ∈Σ\)G=\(V,\\xi,\\lambda,\(M\_\{\\sigma\}\)\_\{\\sigma\\in\\Sigma\}\)implements the same interface asTT\.

In general, every standard transducerTTcan be transformed into a linear transducer whose underlying space has dimension equal to the number of states ofTT\.

### 2\.3Predictive transducers

We finally consider predictive transducers, which correspond to transducers whose internal states do not contain predictive information that is unavailable from the observable input–output history\. From now on, we say that a historyh=\(a1,o1\)​…​\(an,on\)∈Σ∗h=\(a\_\{1\},o\_\{1\}\)\\ldots\(a\_\{n\},o\_\{n\}\)\\in\\Sigma^\{\*\}is*admissible*for an interfaceℐ\\mathcal\{I\}ifPrℐ\(o1⋯on∣a1⋯an\)\>0\\Pr\_\{\\mathcal\{I\}\}\(o\_\{1\}\\cdots o\_\{n\}\\mid a\_\{1\}\\cdots a\_\{n\}\)\>0\. The empty history is always admissible\. For any admissible historyh=\(a1,o1\)​…​\(an,on\)h=\(a\_\{1\},o\_\{1\}\)\\ldots\(a\_\{n\},o\_\{n\}\)of an interfaceℐ\\mathcal\{I\}, we consider theresidual interfaceℐh\\mathcal\{I\}^\{h\}as the interface obtained by conditioning onhh: for everyu∈𝒜mu\\in\\mathcal\{A\}^\{m\}andv∈𝒪mv\\in\\mathcal\{O\}^\{m\},

Pr\(v∣u\)ℐh:=Prℐ\(o1⋯onv∣a1⋯anu\)Prℐ\(o1⋯on∣a1⋯an\)\.\\displaystyle\\Pr\{\}\_\{\\mathcal\{I\}^\{h\}\}\(v\\mid u\):=\\frac\{\\Pr\{\}\_\{\\mathcal\{I\}\}\(o\_\{1\}\\cdots o\_\{n\}v\\mid a\_\{1\}\\cdots a\_\{n\}u\)\}\{\\Pr\{\}\_\{\\mathcal\{I\}\}\(o\_\{1\}\\cdots o\_\{n\}\\mid a\_\{1\}\\cdots a\_\{n\}\)\}\.\(4\)
For a transducerT=\(𝒮,𝒜,𝒪,κ,p\)T=\(\\mathcal\{S\},\\mathcal\{A\},\\mathcal\{O\},\\kappa,p\)and a states∈𝒮s\\in\\mathcal\{S\}, letℐT,s\\mathcal\{I\}\_\{T,s\}denote the interface generated by the same kernelκ\\kappawith initial distributionδs\\delta\_\{s\}\(i\.e\. when all probability mass is concentrated onss\)\. For an admissible historyh=\(a1,o1\)​…​\(an,on\)h=\(a\_\{1\},o\_\{1\}\)\\ldots\(a\_\{n\},o\_\{n\}\), also write

qT\(s∣h\):=Pr\(Sn=s∣o1:n,a1:n\)Tq\_\{T\}\(s\\mid h\):=\\Pr\{\}\_\{T\}\(S\_\{n\}=s\\mid o\_\{1:n\},a\_\{1:n\}\)for the posterior distribution over the internal state at stepnnafter observinghh\.

###### Definition 6\.

LetTTbe a transducer\. We say thatTTispredictiveif, for every admissible historyhhand every statesssuch thatqT​\(s∣h\)\>0q\_\{T\}\(s\\mid h\)\>0,

ℐT,s=ℐTh\.\\displaystyle\\mathcal\{I\}\_\{T,s\}=\\mathcal\{I\}\_\{T\}^\{h\}\.\(5\)Equivalently, conditional on the observable history, knowing the current internal state does not change the expected distribution for future events\.

For this class of transducers there is always a minimal implementation of each interface, and it can be constructed explicitly\. To do this, identify histories that make exactly the same predictions: for admissible historieshhandh′h^\{\\prime\}, define thepredictive equivalence relationas

h∼ℐh′⟺ℐh=ℐh′\.\\displaystyle h\\sim\_\{\\mathcal\{I\}\}h^\{\\prime\}\\quad\\Longleftrightarrow\\quad\\mathcal\{I\}^\{h\}=\\mathcal\{I\}^\{h^\{\\prime\}\}\.Denote the equivalence class ofhhby\[h\]ℐ\[h\]\_\{\\mathcal\{I\}\}and let

𝒮ϵ​\(ℐ\):=\{\[h\]ℐ:h​is admissible for​ℐ\}\.\\mathcal\{S\}\_\{\\epsilon\}\(\\mathcal\{I\}\):=\\\{\[h\]\_\{\\mathcal\{I\}\}:h\\text\{ is admissible for \}\\mathcal\{I\}\\\}\.The transitions are defined in the expected way in the next definition\. This construction corresponds to the notion of anϵ\\epsilon\-machine from computational mechanics\[[3](https://arxiv.org/html/2608.20428#bib.bib2)\]\.

###### Definition 7\.

Letℐ\\mathcal\{I\}be an interface\. Itsϵ\\epsilon\-transduceris given by

E⁡\(ℐ\)=\(𝒮ϵ​\(ℐ\),𝒜,𝒪,κϵ,δ\[ϵ\]ℐ\),E\(\\mathcal\{I\}\)=\(\\mathcal\{S\}\_\{\\epsilon\}\(\\mathcal\{I\}\),\\mathcal\{A\},\\mathcal\{O\},\\kappa\_\{\\epsilon\},\\delta\_\{\[\\epsilon\]\_\{\\mathcal\{I\}\}\}\),where, for every admissible historyhh, actionaa, and outputoo, we set

κϵ\(s′,o∣\[h\]ℐ,a\)\\displaystyle\\kappa\_\{\\epsilon\}\(s^\{\\prime\},o\\mid\[h\]\_\{\\mathcal\{I\}\},a\):=μϵ\(o∣\[h\]ℐ,a\)𝟏\{s′=δϵ\(\[h\]ℐ,a,o\)\}\.\\displaystyle:=\\mu\_\{\\epsilon\}\(o\\mid\[h\]\_\{\\mathcal\{I\}\},a\)\\mathbf\{1\}\\\{s^\{\\prime\}=\\delta\_\{\\epsilon\}\(\[h\]\_\{\\mathcal\{I\}\},a,o\)\\\}\.\(6\)whereμϵ​\(o∣\[h\]ℐ,a\)=Prℐh⁡\(o∣a\)\\mu\_\{\\epsilon\}\(o\\mid\[h\]\_\{\\mathcal\{I\}\},a\)=\\Pr\_\{\\mathcal\{I\}^\{h\}\}\(o\\mid a\)andδϵ​\(\[h\]ℐ,a,o\)=\[h⁡\(a,o\)\]ℐ\\delta\_\{\\epsilon\}\(\[h\]\_\{\\mathcal\{I\}\},a,o\)=\[h\(a,o\)\]\_\{\\mathcal\{I\}\}\.

Observe that this transducer evolvesdeterministically: for every statess, inputaaand outputoothere is a unique next possible states′s^\{\\prime\}\. This ensures that Eq\. \([5](https://arxiv.org/html/2608.20428#S2.E5)\) is satisfied\.

The next proposition states that this implementation is the minimal one among the predictive ones\.

###### Proposition 1\.

The transducerE⁡\(ℐ\)E\(\\mathcal\{I\}\)implementsℐ\\mathcal\{I\}and is predictive\. Moreover, ifT=\(𝒮,𝒜,𝒪,κ,p\)T=\(\\mathcal\{S\},\\mathcal\{A\},\\mathcal\{O\},\\kappa,p\)is any predictive transducer implementingℐ\\mathcal\{I\}, then there is a reduction fromTTtoE⁡\(ℐ\)E\(\\mathcal\{I\}\)\.

###### Example 4\.

The transducer from Figure[2](https://arxiv.org/html/2608.20428#S2.F2)is predictive\. Moreover, it is also the minimal predictive transducer for that interface\.

See Figure[4](https://arxiv.org/html/2608.20428#S2.F4)for a diagram showcasing the structure of the poset of standard, linear and predictive transducers\. As already mentioned, due to Lemma[1](https://arxiv.org/html/2608.20428#Thmlemma1)and Proposition[1](https://arxiv.org/html/2608.20428#Thmproposition1)the poset for linear and predictive transducers each has a minimum for every interface\. Meanwhile, for the case of standard transducers there are interfaces for which there is no unique minimum\.

![Refer to caption](https://arxiv.org/html/2608.20428v1/diagram/diagram_minimal_models.png)Figure 4:A diagram of the lattice of transducers for standard, linear and predictive implementations\. Due to Lemma[1](https://arxiv.org/html/2608.20428#Thmlemma1)and Proposition[1](https://arxiv.org/html/2608.20428#Thmproposition1)the lattice of linear and predictive transducers has a unique minimum, while the one of standard transducers can have more than one minimal element\.

## 3Approximate homomorphisms and the space of interfaces

In this section we provide approximate variants of the notions of homomorphisms introduced in the previous section, and prove some basic properties\.

### 3\.1The case of “standard” transducers

The type of coarse\-grainings that Definition[2](https://arxiv.org/html/2608.20428#Thmdefinition2)allows is exact in a strong structural sense\. It says that the whole one\-step mechanism ofT2T\_\{2\}is obtained by pushing forward the one\-step mechanism ofT1T\_\{1\}along the mapsϕ\\phi,ff, andgg\. Thus, if two states ofT1T\_\{1\}are identified byϕ\\phi, they must have exactly the same coarse\-grained output law and exactly the same coarse\-grained transition law\.

For real world models obtained through learning or other iterative procedures we don’t expect them to be structurally identical\. Thus, the purpose of approximate homomorphisms is to introduce some degree of error in this notion\. We keep the mapsϕ\\phi,ff, andgg; but we now allow the push\-forward dynamics to differ by someε\>0\\varepsilon\>0\.

###### Definition 8\.

Given two transducersT1=\(𝒮1,𝒜1,𝒪1,κ1,p1\)T\_\{1\}=\(\\mathcal\{S\}\_\{1\},\\mathcal\{A\}\_\{1\},\\mathcal\{O\}\_\{1\},\\kappa\_\{1\},p\_\{1\}\)andT2=\(𝒮2,𝒜2,𝒪2,κ2,p2\)T\_\{2\}=\(\\mathcal\{S\}\_\{2\},\\mathcal\{A\}\_\{2\},\\mathcal\{O\}\_\{2\},\\kappa\_\{2\},p\_\{2\}\), aε\\varepsilon\-homomorphismis given by three mappings⟨ϕ:𝒮1→𝒮2,f:𝒜1→𝒜2,g:𝒪1→𝒪2⟩\\langle\\phi:\\mathcal\{S\}\_\{1\}\\to\\mathcal\{S\}\_\{2\},f:\\mathcal\{A\}\_\{1\}\\to\\mathcal\{A\}\_\{2\},g:\\mathcal\{O\}\_\{1\}\\to\\mathcal\{O\}\_\{2\}\\ranglesatisfying

‖\(ϕ×g\)∗κ1\(⋅,⋅\|s1,a1\)−κ2\(⋅,⋅\|ϕ\(s1\),f\(a1\)\)‖TV\\displaystyle\\left\\\|\(\\phi\\times g\)\_\{\*\}\\kappa\_\{1\}\(\\cdot,\\cdot\|s\_\{1\},a\_\{1\}\)\-\\kappa\_\{2\}\(\\cdot,\\cdot\|\\phi\(s\_\{1\}\),f\(a\_\{1\}\)\)\\right\\\|\_\{\\mathrm\{TV\}\}≤ε\\displaystyle\\leq\\varepsilon\(7\)‖ϕ∗​p1−p2‖TV\\displaystyle\\left\\\|\\phi\_\{\*\}p\_\{1\}\-p\_\{2\}\\right\\\|\_\{\\mathrm\{TV\}\}≤ε,\\displaystyle\\leq\\varepsilon,\(8\)for everys1∈𝒮1s\_\{1\}\\in\\mathcal\{S\}\_\{1\}anda1∈𝒜1a\_\{1\}\\in\\mathcal\{A\}\_\{1\}333Here\(ϕ×g\)∗\(\\phi\\times g\)\_\{\*\}andϕ∗\\phi\_\{\*\}denote the push\-forwards of the distributions\. See Appendix[A\.2](https://arxiv.org/html/2608.20428#A1.SS2)for a precise definition\.\.

The choice of total variation is not completely arbitrary: we will see that due to its properties \(which are enumerated in the Appendix[A\.2](https://arxiv.org/html/2608.20428#A1.SS2)\) approximate homomorphisms are composable\.

###### Example 5\.

Consider the actionless transducers from Figure[5](https://arxiv.org/html/2608.20428#S3.F5)withε∈\(0,1\]\\varepsilon\\in\(0,1\]\. Each edge has a label\(o,p\)\(o,p\)indicating the probabilityppof transitioning using that edge and outputtingooin the process\. There is aε\\varepsilon\-reduction from the transducer on the left to the one on the right: takeϕ⁡\(s0\)=t0\\phi\(s\_\{0\}\)=t\_\{0\}andϕ⁡\(s1\)=ϕ⁡\(s2\)=t1\\phi\(s\_\{1\}\)=\\phi\(s\_\{2\}\)=t\_\{1\}\. Meanwhile, there is no 0\-reduction \(i\.e\. exact reduction\) between them\.

s0s\_\{0\}s1s\_\{1\}s2s\_\{2\}$,12\\frac\{1\}\{2\}0,10,1$,12\\frac\{1\}\{2\}0,1−ε0,1\-\\varepsilon1,ε1,\\varepsilont0t\_\{0\}t1t\_\{1\}$,110,10,\\,1Figure 5:Two actionless transducers \(or rather, transducers with a single actionaa\), with outputs𝒪=\{0,1,$\}\\mathcal\{O\}=\\\{0,1,\\$\\\}\. An edge fromsstos′s^\{\\prime\}with labelo,po,pindicates thatκ\(s′,o\|s,a\)=p\\kappa\(s^\{\\prime\},o\|s,a\)=p\.
This notion of approximate homomorphism ensures each states∈𝒮1s\\in\\mathcal\{S\}\_\{1\}gets mapped to a state whose one\-step dynamics are similar after coarse\-graining\. Thus, if we look atapproximate reductions\(enforcing that𝒜1=𝒜2\\mathcal\{A\}\_\{1\}=\\mathcal\{A\}\_\{2\},𝒪1=𝒪2\\mathcal\{O\}\_\{1\}=\\mathcal\{O\}\_\{2\},f=g=idf=g=\\texttt\{id\}\{\}, andϕ\\phiis surjective\), one transducerT1T\_\{1\}can be approximately reduced to another oneT2T\_\{2\}only if their states arelocallysimilar\. Does this imply that the interfaces they induce are also similar? We recall that for exact homomorphisms this is the case\.

###### Observation 1\.

If there is a reduction fromT1T\_\{1\}toT2T\_\{2\}thenℐT1=ℐT2\\mathcal\{I\}\_\{T\_\{1\}\}=\\mathcal\{I\}\_\{T\_\{2\}\}\[[44](https://arxiv.org/html/2608.20428#bib.bib1)\]\[Lemma 5\]\.

To approach this question in the approximate setting we need a way to compare different interfaces, i\.e\. a metric over this space\.

Observe that an interfaceℐ\\mathcal\{I\}is given essentially by a mapDℐ:𝒜∗→Δ⁡\(𝒪∗\)D\_\{\\mathcal\{I\}\}:\\mathcal\{A\}^\{\*\}\\to\\Delta\(\\mathcal\{O\}^\{\*\}\)such thatDℐ​\(a1​…​an\)D\_\{\\mathcal\{I\}\}\(a\_\{1\}\\ldots a\_\{n\}\)represents the distributionPr\(⋅\|a1…an\)ℐ\\Pr\{\}\_\{\\mathcal\{I\}\}\\left\(\\cdot\|a\_\{1\}\\ldots a\_\{n\}\\right\)which has support over𝒪n\\mathcal\{O\}^\{n\}\. Then, to define a metric for interfaces we can pick any metric for distributions and then aggregate it over all the possible action sequences in𝒜∗\\mathcal\{A\}^\{\*\}\. For instance, we can consider total variation to compare the distributions and aggregate them with the supremum, obtaining

d∞​\(ℐ1,ℐ2\)=supa∈𝒜∗‖Dℐ1​\(a\)−Dℐ2​\(a\)‖TV\\displaystyle d\_\{\\infty\}\(\\mathcal\{I\}\_\{1\},\\mathcal\{I\}\_\{2\}\)=\\sup\_\{\\textbf\{a\}\\in\\mathcal\{A\}^\{\*\}\}\|\|D\_\{\\mathcal\{I\}\_\{1\}\}\(\\textbf\{a\}\)\-D\_\{\\mathcal\{I\}\_\{2\}\}\(\\textbf\{a\}\)\|\|\_\{\\mathrm\{TV\}\}\(9\)
We could also weight each sequence of actions according to its length, reflecting the choice to place less weight on long\-horizon discrepancies\. Thus, we can consider

dγ​\(ℐ1,ℐ2\)=∑n=0∞γn​supa∈𝒜n‖Dℐ1​\(a\)−Dℐ2​\(a\)‖TV\\displaystyle d\_\{\\gamma\}\(\\mathcal\{I\}\_\{1\},\\mathcal\{I\}\_\{2\}\)=\\sum\_\{n=0\}^\{\\infty\}\\gamma^\{n\}\\sup\_\{\\textbf\{a\}\\in\\mathcal\{A\}^\{n\}\}\|\|D\_\{\\mathcal\{I\}\_\{1\}\}\(\\textbf\{a\}\)\-D\_\{\\mathcal\{I\}\_\{2\}\}\(\\textbf\{a\}\)\|\|\_\{\\mathrm\{TV\}\}\(10\)for someγ∈\(0,1\)\\gamma\\in\(0,1\)\. Note that the distances in Eqs\. \([9](https://arxiv.org/html/2608.20428#S3.E9)\) and \([10](https://arxiv.org/html/2608.20428#S3.E10)\) are indeed well\-defined metrics over the set of interfaces\.

Since each transducerTTinduces an interfaceℐT\\mathcal\{I\}\_\{T\}through Eq\. \([1](https://arxiv.org/html/2608.20428#S2.E1)\), any metric between interfaces can be seen as a pseudometric444It is a pseudo metric because different transducers implementing the same interface are at distance 0\.between transducers as

d⁡\(T1,T2\)=d⁡\(ℐT1,ℐT2\)\.\\displaystyle d\(T\_\{1\},T\_\{2\}\)=d\(\\mathcal\{I\}\_\{T\_\{1\}\},\\mathcal\{I\}\_\{T\_\{2\}\}\)\.
Are these metrics “continuous” with respect to the notion of reduction? Namely, is there a metricddand a functionf:ℝ\>0→ℝ≥0f:\\mathbb\{R\}\_\{\>0\}\\to\\mathbb\{R\}\_\{\\geq 0\}withf⁡\(x\)​→x→0​0f\(x\)\\underset\{x\\to 0\}\{\\rightarrow\}0such that, if there is anε\\varepsilon\-reduction fromT1T\_\{1\}toT2T\_\{2\}, thend⁡\(ℐT1,ℐT2\)≤f⁡\(ε\)d\(\\mathcal\{I\}\_\{T\_\{1\}\},\\mathcal\{I\}\_\{T\_\{2\}\}\)\\leq f\(\\varepsilon\)? We first observe that this is not the case for the supremum distance in Eq\. \([9](https://arxiv.org/html/2608.20428#S3.E9)\)\.

###### Example 6\.

Pickd∞d\_\{\\infty\}as in Eq\. \([9](https://arxiv.org/html/2608.20428#S3.E9)\), and consider the transducers from Example[5](https://arxiv.org/html/2608.20428#Thmexample5)\. Then, ifT1T\_\{1\}is the transducer on the left andT2T\_\{2\}the one on the right, it can be seen thatd⁡\(ℐT1,ℐT2\)=1d\(\\mathcal\{I\}\_\{T\_\{1\}\},\\mathcal\{I\}\_\{T\_\{2\}\}\)=1for everyε\>0\\varepsilon\>0\.

Intuitively, the supremum distance is not controlled by the approximate homomorphism notion because the error bound applies only to the one\-step dynamics\. Thus, the interfaces implemented by the two transducers at long horizons \(i\.e\. the distributionPr\(⋅\|a\)\\Pr\\left\(\\cdot\|\\textbf\{a\}\\right\)fora∈𝒜n\\textbf\{a\}\\in\\mathcal\{A\}^\{n\}withn→∞n\\to\\infty\) can be arbitrarily far away in metrics such as total variation\.

Nonetheless, this observation suggests that the discounted metrics from Eq\. \([10](https://arxiv.org/html/2608.20428#S3.E10)\) might be preserved by the approximate homomorphism notion, and indeed this is the case\.

###### Theorem 1\.

Suppose there is anε\\varepsilon\-reduction fromT1T\_\{1\}toT2T\_\{2\}\. Then, ifdγd\_\{\\gamma\}is the distance from Eq\. \([10](https://arxiv.org/html/2608.20428#S3.E10)\), it holds that

dγ​\(ℐT1,ℐT2\)≤ε\(1−γ\)2\.\\displaystyle d\_\{\\gamma\}\(\\mathcal\{I\}\_\{T\_\{1\}\},\\mathcal\{I\}\_\{T\_\{2\}\}\)\\leq\\frac\{\\varepsilon\}\{\(1\-\\gamma\)^\{2\}\}\.\(11\)

We writeT1​→𝜀​T2T\_\{1\}\\overset\{\\varepsilon\}\{\\rightarrow\{\}\}T\_\{2\}to indicate that there is anε\\varepsilon\-homomorphism fromT1T\_\{1\}toT2T\_\{2\}\. As already noted, exact homomorphisms can be composed, and thus the reduction relation is transitive\. For approximate homomorphisms we can prove the following additive version\.

###### Proposition 2\.

IfT1​→ε1​T2T\_\{1\}\\overset\{\\varepsilon\_\{1\}\}\{\\rightarrow\{\}\}T\_\{2\}andT2​→ε2​T3T\_\{2\}\\overset\{\\varepsilon\_\{2\}\}\{\\rightarrow\{\}\}T\_\{3\}, thenT1​→ε1\+ε2​T3T\_\{1\}\\overset\{\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}\}\{\\rightarrow\{\}\}T\_\{3\}\.

This proposition states the existence of the dashed arrow in the following diagram:

T1\{\\lx@inpgf@ignorespaces T\_\{1\}\}T2\{\\lx@inpgf@ignorespaces T\_\{2\}\}T3\{\\lx@inpgf@ignorespaces T\_\{3\}\}ε1\\scriptstyle\{\\lx@inpgf@ignorespaces\\varepsilon\_\{1\}\}ε1\+ε2\\scriptstyle\{\\lx@inpgf@ignorespaces\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}\}ε2\\scriptstyle\{\\lx@inpgf@ignorespaces\\varepsilon\_\{2\}\}
Theorem[1](https://arxiv.org/html/2608.20428#Thmtheorem1)and Proposition[2](https://arxiv.org/html/2608.20428#Thmproposition2)suggest that this notion of approximate homomorphism is natural and algebraically convenient\. We recall that composability can be shown because we use total variation to compare the one\-step dynamics: a different choice of distance to compare the distributions may not preserve this property\.

### 3\.2The case of linear transducers

To introduce an approximation error in the exact linear reduction we will equip each state vector space with a norm, which we will use to measure the distance between different vectors \(mainly, between the vector obtained through the reduction and the vectors from the transducer itself\)\. Throughout this subsection, we assume that the output alphabetOOis finite\. IfVVis a normed vector space, we denote its dual norm by∥⋅∥V∗\\\|\\cdot\\\|\_\{V^\{\*\}\}\. Given a linear operatorCC, we write‖C‖a→b\|\|C\|\|\_\{a\\to b\}to denote the normsupx:‖x‖a=1\|\|Cx\|\|b\\sup\_\{x:\|\|x\|\|\_\{a\}=1\}\|\|Cx\|\|\_\{b\}\.

An arbitrary linear transducer does not necessarily implement an interface\. In particular, there are some transducers for which the norm of the state vector tends to infinity as the transducer reads symbols\. Such a behaviour troubles our notion of approximate reduction, since a small margin of error in the one\-step dynamics can be amplified arbitrarily in the subsequent steps\. Thus, to rule out this situation, we introduce the notion ofcontractivetransducer\.

###### Definition 9\.

A linear transducerG=\(V,ξ,λ,\{Ma,o\}\(a,o\)∈A×O\)G=\(V,\\xi,\\lambda,\\\{M\_\{a,o\}\\\}\_\{\(a,o\)\\in A\\times O\}\)is*contractive*if

‖ξ‖V≤1,‖λ‖V∗≤1,‖Ma,o​x‖V≤‖x‖V,\\\|\\xi\\\|\_\{V\}\\leq 1,\\qquad\\\|\\lambda\\\|\_\{V^\{\*\}\}\\leq 1,\\qquad\\\|M\_\{a,o\}x\\\|\_\{V\}\\leq\\\|x\\\|\_\{V\},for everya∈Aa\\in A,o∈Oo\\in O, andx∈Vx\\in V\.

The last condition ensures that after applying an evolution operator the norm of the vector state does not increase\. Note that the canonical representation given by the Hankel matrix satisfies this definition\. Indeed, on the Hankel row spaceVℐV\_\{\\mathcal\{I\}\}, the prediction norm

‖r‖pred=supv∈Σ∗\|r⁡\(v\)\|\\\|r\\\|\_\{\\mathrm\{pred\}\}=\\sup\_\{v\\in\\Sigma^\{\*\}\}\|r\(v\)\|makes every shiftRa,oℐR^\{\\mathcal\{I\}\}\_\{a,o\}nonexpansive, because

‖Ra,oℐ​r‖pred=supv∈Σ∗\|r⁡\(\(a,o\)​v\)\|≤‖r‖pred\.\\\|R^\{\\mathcal\{I\}\}\_\{a,o\}r\\\|\_\{\\mathrm\{pred\}\}=\\sup\_\{v\\in\\Sigma^\{\*\}\}\|r\(\(a,o\)v\)\|\\leq\\\|r\\\|\_\{\\mathrm\{pred\}\}\.Moreover,‖ξℐ‖pred=1\\\|\\xi\_\{\\mathcal\{I\}\}\\\|\_\{\\mathrm\{pred\}\}=1, while‖λℐ‖Vℐ∗≤1\\\|\\lambda\_\{\\mathcal\{I\}\}\\\|\_\{V\_\{\\mathcal\{I\}\}^\{\*\}\}\\leq 1becauseλℐ​\(r\)=r​\(ϵ\)\\lambda\_\{\\mathcal\{I\}\}\(r\)=r\(\\epsilon\)\.

We now introduce our notion of approximate linear reduction\.

###### Definition 10\.

LetG=\(V,ξ,λ,\{Ma,o\}a,o\)G=\(V,\\xi,\\lambda,\\\{M\_\{a,o\}\\\}\_\{a,o\}\)andG′=\(W,ξ′,λ′,\{Na,o\}a,o\)G^\{\\prime\}=\(W,\\xi^\{\\prime\},\\lambda^\{\\prime\},\\\{N\_\{a,o\}\\\}\_\{a,o\}\)be contractive linear transducers over the same input and output alphabets, and letε≥0\\varepsilon\\geq 0\. A bounded surjective linear mapL:V→WL:V\\to Wis a*ε\\varepsilon\-linear reduction*fromGGtoG′G^\{\\prime\}if

‖L​ξ−ξ′‖W\\displaystyle\\\|L\\xi\-\\xi^\{\\prime\}\\\|\_\{W\}≤ε,\\displaystyle\\leq\\varepsilon,‖L​Ma,o​x−Na,o​L​x‖W\\displaystyle\\\|LM\_\{a,o\}x\-N\_\{a,o\}Lx\\\|\_\{W\}≤ε​‖x‖V,\\displaystyle\\leq\\varepsilon\\\|x\\\|\_\{V\},‖λ′​L−λ‖V∗\\displaystyle\\\|\\lambda^\{\\prime\}L\-\\lambda\\\|\_\{V^\{\*\}\}≤ε,\\displaystyle\\leq\\varepsilon,for every\(a,o\)∈A×O\(a,o\)\\in A\\times Oandx∈Vx\\in V\. We writeG→𝜀G′G\\xrightarrow\{\\varepsilon\}G^\{\\prime\}when such a map exists\.

WhenGGandG′G^\{\\prime\}are contractive, the conditions forε=0\\varepsilon=0are precisely the equations defining an exact linear reduction\. This definition extends approximate reductions between standard transducers\.

###### Proposition 3\.

LetT1T\_\{1\}andT2T\_\{2\}be finite standard transducers over the same alphabets, and suppose that a surjective state mapϕ:𝒮1→𝒮2\\phi:\\mathcal\{S\}\_\{1\}\\to\\mathcal\{S\}\_\{2\}is anε\\varepsilon\-reduction\. Then, ifG1G\_\{1\}andG2G\_\{2\}are the linear implementations corresponding toT1T\_\{1\}andT2T\_\{2\}equipped with theirℓ1\\ell\_\{1\}norms, there exists a2​ε2\\varepsilon\-linear reduction fromG1G\_\{1\}toG2G\_\{2\}induced byϕ\\phi\.

Approximate linear reductions can be composed in the same way as the standard approximate reductions\. From now on, for a bounded linear mapLL, writec⁡\(L\)=max⁡\{1,‖L‖\}c\(L\)=\\max\\\{1,\\\|L\\\|\\\}\. The following holds\.

###### Proposition 4\.

Suppose thatG0→ε1G1G\_\{0\}\\xrightarrow\{\\varepsilon\_\{1\}\}G\_\{1\}through the linear mapLLandG1→ε2G2G\_\{1\}\\xrightarrow\{\\varepsilon\_\{2\}\}G\_\{2\}through the linear mapKK\. ThenK​LKLis ac⁡\(K\)​ε1\+c⁡\(L\)​ε2c\(K\)\\varepsilon\_\{1\}\+c\(L\)\\varepsilon\_\{2\}linear reduction fromG0G\_\{0\}toG2G\_\{2\}\.

We next compare the interfaces implemented by approximately reduced linear transducers\. In the case of standard transducers we could prove in Theorem[1](https://arxiv.org/html/2608.20428#Thmtheorem1)that the discounted metrics were preserved after an approximate reduction\. For linear transducers we obtain a similar result, but with a weaker bound\.

###### Theorem 2\.

LetGGandG′G^\{\\prime\}be contractive linear transducers implementing interfacesℐG\\mathcal\{I\}\_\{G\}andℐG′\\mathcal\{I\}\_\{G^\{\\prime\}\}\. IfG→𝜀G′G\\xrightarrow\{\\varepsilon\}G^\{\\prime\}, then, for everyn≥1n\\geq 1,

supa∈𝒜n‖DℐG​\(a\)−DℐG′​\(a\)‖TV≤min⁡\{1,n\+22​\|O\|n​ε\}\.\\sup\_\{\\textbf\{a\}\\in\\mathcal\{A\}^\{n\}\}\\\|D\_\{\\mathcal\{I\}\_\{G\}\}\(\\textbf\{a\}\)\-D\_\{\\mathcal\{I\}\_\{G^\{\\prime\}\}\}\(\\textbf\{a\}\)\\\|\_\{\\mathrm\{TV\}\}\\leq\\min\\left\\\{1,\\frac\{n\+2\}\{2\}\|O\|^\{n\}\\varepsilon\\right\\\}\.\(12\)Consequently, for everyγ∈\(0,1\)\\gamma\\in\(0,1\),

dγ​\(ℐG,ℐG′\)≤∑n≥0γn​min⁡\{1,n\+22​\|O\|n​ε\},d\_\{\\gamma\}\(\\mathcal\{I\}\_\{G\},\\mathcal\{I\}\_\{G^\{\\prime\}\}\)\\leq\\sum\_\{n\\geq 0\}\\gamma^\{n\}\\min\\left\\\{1,\\frac\{n\+2\}\{2\}\|O\|^\{n\}\\varepsilon\\right\\\},\(13\)which converges to 0 asε→0\\varepsilon\\to 0\.

Note that this implies that for small enoughε\\varepsilonboth transducers implement a similar interface\. The bound is somewhat weaker when compared to the one from Theorem[1](https://arxiv.org/html/2608.20428#Thmtheorem1)because the notion of approximate reduction for standard transducers is stronger with respect to the one\-step equivalence of the dynamics\. For instance, Eq\. \([7](https://arxiv.org/html/2608.20428#S3.E7)\) requires that the overall error \(i\.e\. total variation\) is bounded, while in Definition[10](https://arxiv.org/html/2608.20428#Thmdefinition10)we bound each error independently\. This is the reason why a term\|𝒪\|\|\\mathcal\{O\}\|shows up in the bound\. We could fix this by changing the definition of approximate linear reduction, but it would require us to also modify the notion of contractive transducer\. Moreover, the required change gives a notion of contractive transducer which does not include the canonical Hankel representations, which we want to use in later proofs\.

Nonetheless, we want to highlight the fact that there are many other valid choices regarding these definitions\. In our case, we wanted to prioritize the fact that our abstractions should extend the notion of approximate reduction for standard transducers \(proven in Proposition[3](https://arxiv.org/html/2608.20428#Thmproposition3)\), should allow to represent the canonical Hankel constructions and should satisfy the simple and basic properties already seen for standard transducers \(composability in Proposition[4](https://arxiv.org/html/2608.20428#Thmproposition4)and continuity with regard to the discounted metrics in Theorem[2](https://arxiv.org/html/2608.20428#Thmtheorem2)\)\.

## 4Approximate reductions between implementations of similar interfaces

In this section we will study the set of transducers which implement a given interfaceℐ\\mathcal\{I\}, and we will try to relate them through approximate homomorphisms\. Moreover, we will look at the set of transducers implementing asimilarinterface \(using one of the distances for interfaces mentioned previously\)\. Ideally, we would like for this set of transducers to share some property, since that would indicate anemergentproperty related to the representation of the interfaces\.

The following definition formalizes this set\.

###### Definition 11\.

Letℐ\\mathcal\{I\}be an interface,ε≥0\\varepsilon\\geq 0andddsome metric over the set of interfaces\. We define

ℒℐε,d=\{T:T​is a transducer and​d​\(ℐT,ℐ\)≤ε\}\.\\displaystyle\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{\\varepsilon,d\}=\\left\\\{T:T\\text\{ is a transducer and \}d\(\\mathcal\{I\}\_\{T\},\\mathcal\{I\}\)\\leq\\varepsilon\\right\\\}\.as the set of transducers thatε\\varepsilon\-approximateℐ\\mathcal\{I\}\.

For every setℒℐε,d\\mathcal\{L\}\_\{\\mathcal\{I\}\{\}\}^\{\\varepsilon,d\}we would like to understand whether there is someT∈ℒℐε,dT\\in\\mathcal\{L\}\_\{\\mathcal\{I\}\{\}\}^\{\\varepsilon,d\}such that, for every otherT′∈ℒℐε,dT^\{\\prime\}\\in\\mathcal\{L\}\_\{\\mathcal\{I\}\{\}\}^\{\\varepsilon,d\}, it holds thatT′​→𝛿​TT^\{\\prime\}\\overset\{\\delta\}\{\\rightarrow\}Tfor some smallδ\\delta, ideally scaling asδ=O⁡\(ε\)\\delta=O\(\\varepsilon\)\. We call such a transducer aδ\\delta\-minima ofℒℐε,d\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{\\varepsilon,d\}\. We define

δε​\(ℐ\)=inf\{δ∈ℝ≥0:ℒℐε,d​has aδ\-minima\}\.\\displaystyle\\delta\_\{\\varepsilon\}\(\\mathcal\{I\}\)=\\inf\\left\\\{\\delta\\in\\mathbb\{R\}\_\{\\geq 0\}:\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{\\varepsilon,d\}\\text\{ has a $\\delta$\-minima\}\\right\\\}\.With this notation, our goal is to find bounds forδε​\(ℐ\)\\delta\_\{\\varepsilon\}\(\\mathcal\{I\}\)in terms ofε\\varepsilon\. Is there a subset of interfaces which is well\-behaved in this sense? Does it matter which type of transducers we consider? See Figure[6](https://arxiv.org/html/2608.20428#S4.F6)for a sketch of the type of behaviour that we aim for\.

In the next subsections we will consider the setℒℐε,d\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{\\varepsilon,d\}restricted to different types of transducers\. To avoid cluttering the notation we won’t add any more indices to this symbol, but rather take the convention that in each respective subsection this set is restricted to the set of transducers studied in the corresponding subsection\.

![Refer to caption](https://arxiv.org/html/2608.20428v1/diagram/idea_minimizar.png)Figure 6:Schematic description of the type of convergence result we would like to prove\. After fixing an interface of interestℐ\\mathcal\{I\}, we look at all interfacesε\\varepsilon\-close toℐ\\mathcal\{I\}in some distance\. For each of these interfaces \(such as𝒥1\\mathcal\{J\}\_\{1\}and𝒥2\\mathcal\{J\}\_\{2\}\) there are many transducers implementing the dynamics \(respectively,T1T\_\{1\}andT2T\_\{2\}\)\. We say that there is aO⁡\(ε\)O\(\\varepsilon\)\-minimum if there is some transducerTm​i​nT\_\{min\}implementing an interface fromBε​\(ℐ\)B\_\{\\varepsilon\}\(\\mathcal\{I\}\)such that for any transducerTTimplementing an interface inBε​\(ℐ\)B\_\{\\varepsilon\}\(\\mathcal\{I\}\)it holds thatT​→O⁡\(ε\)​Tm​i​nT\\overset\{O\(\\varepsilon\)\}\{\\rightarrow\}T\_\{min\}\. In the diagram this is represented by the transducerTm​i​nT\_\{min\}implementing the interfaceℐ\\mathcal\{I\}, and there areO⁡\(ε\)O\(\\varepsilon\)\-reductions from bothT1T\_\{1\}andT2T\_\{2\}\.### 4\.1Non\-existence ofδ\\delta\-minima for standard transducers

As mentioned before, there exist anℐ\\mathcal\{I\}such thatℒℐ0,d\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{0,d\}does not have a 0\-minimum when considering only standard transducers555Note that ifε=0\\varepsilon=0the choice of distance is irrelevant\.\. Can this situation be avoided usingδ\\deltareductions? Note that asδ\\deltaincreases we allow more reductions \(in the limit, takingδ=1\\delta=1allows every possible reduction\), and thus it should make it simpler for convergent structures to arise\.

In the next proposition we show that this is not the case\.

###### Proposition 5\.

There exists an interfaceℐ\\mathcal\{I\}such that, for everyδ<1\\delta<1, the setℒℐ0,d\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{0,d\}does not have aδ\\delta\-minima\.

Even thoughℒℐ0,d\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{0,d\}does not have a common representation, it might be the case that when looking at approximate implementations ofℐ\\mathcal\{I\}there is some convergent structure\. Again, the answer is negative\.

###### Proposition 6\.

Letℐ\\mathcal\{I\}be the interface from Proposition[5](https://arxiv.org/html/2608.20428#Thmproposition5)\. Then, for everyε≥0\\varepsilon\\geq 0, every transducerCC, and everyδ<1/2\\delta<1/2, it is not true thatT′T^\{\\prime\}δ\\delta\-reduces toCCfor everyT′∈ℒℐε,d∞T^\{\\prime\}\\in\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{\\varepsilon,d\_\{\\infty\}\}\. In particular,ℒℐε,d∞\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{\\varepsilon,d\_\{\\infty\}\}does not have aδ\\delta\-minima\.

These two results show that, in the case of standard transducers, there are interfaces for which no convergent structure exists between the different implementations of the interface, at least when we formalize this structure through our local notion of approximate homomorphism\. This result is robust even when nearby interfaces are considered\. Moreover, the counterexample is simple \(it is a low\-dimensional finite\-rank interface\), and the result can be proven for other distances \(such as the discounted onedγd\_\{\\gamma\}\)\. Thus, we don’t believe that there is a reasonable restricted set of interfaces for which we could boundδε​\(ℐ\)\\delta\_\{\\varepsilon\}\(\\mathcal\{I\}\)byO⁡\(ε\)O\(\\varepsilon\)\. We remark that these results are an extension of the ones from\[[44](https://arxiv.org/html/2608.20428#bib.bib1)\]in the context of approximate homomorphisms and approximate implementations of interfaces\.

### 4\.2Existence ofδ\\delta\-minima for linear transducers

We now show a positive result for linear transducers\. We will show that for all finite\-rank interfacesℐ\\mathcal\{I\}all nearby interfaces have a canonical representation which is similar to the one fromℐ\\mathcal\{I\}\. This is intuitive: note that the canonical construction is induced by the rows of the Hankel matrix\. If an interface is slightly perturbed then the Hankel matrix is slightly perturbed as well\. Thus, we can map the new Hankel matrix to the original one identifying each row with the corresponding one from the original matrix\.

To obtain the strongest result possible we will give a norm to the canonical representation which dominates the predictive one\.

###### Definition 12\.

Letℐ\\mathcal\{I\}be an interface and letVℐ=span⁡\{hℐ​\(w\):w∈Σ∗\}V\_\{\\mathcal\{I\}\}=\\operatorname\{span\}\\\{h\_\{\\mathcal\{I\}\}\(w\):w\\in\\Sigma^\{\*\}\\\}be its Hankel row space\. Forr∈Vℐr\\in V\_\{\\mathcal\{I\}\}, define the atomic norm as

‖r‖at,ℐ:=inf\{∑i=1m\|αi\|:r=∑i=1mαi​hℐ​\(wi\)\}\.\\\|r\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}:=\\inf\\left\\\{\\sum\_\{i=1\}^\{m\}\|\\alpha\_\{i\}\|:r=\\sum\_\{i=1\}^\{m\}\\alpha\_\{i\}h\_\{\\mathcal\{I\}\}\(w\_\{i\}\)\\right\\\}\.We writeGℐatG\_\{\\mathcal\{I\}\}^\{\\mathrm\{at\}\}for the canonical Hankel implementation equipped with this norm\.

We are using the wordatomto refer to each row of the Hankel matrix\. We formally show that\|\|⋅\|\|at\|\|\\cdot\|\|\_\{\\mathrm\{at\}\}is a norm\.

###### Lemma 2\.

Letℐ\\mathcal\{I\}be an interface and equip its Hankel row spaceVℐV\_\{\\mathcal\{I\}\}with the atomic norm\. Then‖⋅‖at,ℐ\\\|\\mathord\{\\cdot\}\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}is a norm and, for everyr∈Vℐr\\in V\_\{\\mathcal\{I\}\},

‖r‖pred≤‖r‖at,ℐ\.\\\|r\\\|\_\{\\mathrm\{pred\}\}\\leq\\\|r\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\.Moreover,

‖ξℐ‖at,ℐ=1,‖λℐ‖\(Vℐ,‖⋅‖at,ℐ\)∗=1,\\\|\\xi\_\{\\mathcal\{I\}\}\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}=1,\\qquad\\\|\\lambda\_\{\\mathcal\{I\}\}\\\|\_\{\(V\_\{\\mathcal\{I\}\},\\\|\\mathord\{\\cdot\}\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\)^\{\*\}\}=1,and every shiftRσℐR^\{\\mathcal\{I\}\}\_\{\\sigma\}is nonexpansive\. Consequently,GℐatG\_\{\\mathcal\{I\}\}^\{\\mathrm\{at\}\}is a contractive linear transducer\.

This norm measures what is the best way to writerras a linear sum of the rows of the Hankel matrix, where we weight each sum with the sum of the absolute values of its coefficients\.

Our notion of linear reduction requires the mapping to be surjective\. Thus, to ensure this property we will look at invertible minors of the Hankel matrix\. Letℐ\\mathcal\{I\}be a finite\-rank interface withd=rank⁡\(Hℐ\)d=\\operatorname\{rank\}\(H\_\{\\mathcal\{I\}\}\)\. We can choose prefixesp1,…,pdp\_\{1\},\\ldots,p\_\{d\}and suffixesq1,…,qdq\_\{1\},\\ldots,q\_\{d\}such that

Cℐ:=\(Fℐ​\(pi​qj\)\)i,j=1dC\_\{\\mathcal\{I\}\}:=\\bigl\(F\_\{\\mathcal\{I\}\}\(p\_\{i\}q\_\{j\}\)\\bigr\)\_\{i,j=1\}^\{d\}\(14\)is invertible andq1=ϵq\_\{1\}=\\epsilon\. Put

Bℐ=\(hℐ​\(p1\)hℐ​\(pd\)\),Γℐ:=‖Cℐ−1‖∞→1\.B\_\{\\mathcal\{I\}\}=\\begin\{pmatrix\}h\_\{\\mathcal\{I\}\}\(p\_\{1\}\)\\\\\[\-2\.84526pt\] \\vdots\\\\\[\-2\.84526pt\] h\_\{\\mathcal\{I\}\}\(p\_\{d\}\)\\end\{pmatrix\},\\qquad\\Gamma\_\{\\mathcal\{I\}\}:=\\\|C\_\{\\mathcal\{I\}\}^\{\-1\}\\\|\_\{\\infty\\to 1\}\.For any interface𝒥\\mathcal\{J\}, define analogouslyC𝒥:=\(F𝒥​\(pi​qj\)\)i,j=1dC\_\{\\mathcal\{J\}\}:=\\bigl\(F\_\{\\mathcal\{J\}\}\(p\_\{i\}q\_\{j\}\)\\bigr\)\_\{i,j=1\}^\{d\}andev𝒥:V𝒥→ℝd\\operatorname\{ev\}\_\{\\mathcal\{J\}\}:V\_\{\\mathcal\{J\}\}\\to\\mathbb\{R\}^\{d\}given by

ev𝒥⁡\(r\):=\(r⁡\(q1\),…,r⁡\(qd\)\),\\operatorname\{ev\}\_\{\\mathcal\{J\}\}\(r\):=\\bigl\(r\(q\_\{1\}\),\\ldots,r\(q\_\{d\}\)\\bigr\),\. Finally, letΠ𝒥→ℐ:V𝒥⟶Vℐ\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}:V\_\{\\mathcal\{J\}\}\\longrightarrow V\_\{\\mathcal\{I\}\}be the linear map

Π𝒥→ℐ​\(r\):=ev𝒥⁡\(r\)​Cℐ−1​Bℐ\.\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}\(r\):=\\operatorname\{ev\}\_\{\\mathcal\{J\}\}\(r\)C\_\{\\mathcal\{I\}\}^\{\-1\}B\_\{\\mathcal\{I\}\}\.The mappingΠ𝒥→ℐ\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}translatesr∈V𝒥r\\in V\_\{\\mathcal\{J\}\}into a vector fromVℐV\_\{\\mathcal\{I\}\}by first evaluating the suffixes\{qi\}1≤i≤d\\\{q\_\{i\}\\\}\_\{1\\leq i\\leq d\}, then doing a change of coordinates usingCℐC\_\{\\mathcal\{I\}\}and finally projecting the result into the rows fromVℐV\_\{\\mathcal\{I\}\}indexed by\{pi\}1≤i≤d\\\{p\_\{i\}\\\}\_\{1\\leq i\\leq d\}\.

The following lemma shows that this mapping commutes with the shift operators up to a small error with respect to the\|\|⋅\|\|at\|\|\\cdot\|\|\_\{\\mathrm\{at\}\}norm if the interfaces are close\. Moreover, wheneverC𝒥C\_\{\\mathcal\{J\}\}is invertible the mapping is surjective\.

###### Lemma 3\.

Ifd∞​\(ℐ,𝒥\)≤εd\_\{\\infty\}\(\\mathcal\{I\},\\mathcal\{J\}\)\\leq\\varepsilon, then, for everyw∈Σ∗w\\in\\Sigma^\{\*\},

‖Π𝒥→ℐ​h𝒥​\(w\)−hℐ​\(w\)‖at,ℐ≤Γℐ​ε\.\\\|\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}h\_\{\\mathcal\{J\}\}\(w\)\-h\_\{\\mathcal\{I\}\}\(w\)\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\\leq\\Gamma\_\{\\mathcal\{I\}\}\\varepsilon\.Moreover, ifC𝒥C\_\{\\mathcal\{J\}\}is invertible, thenΠ𝒥→ℐ\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}is surjective\.

It is a well\-known fact that if a finite matrixMMis invertible, then adding a small amount of noise toMMkeeps it invertible\. We apply this observation toCℐC\_\{\\mathcal\{I\}\}to guarantee thatC𝒥C\_\{\\mathcal\{J\}\{\}\}remains invertible\.

###### Theorem 3\.

Letℐ\\mathcal\{I\}be a finite\-rank interface and choose the minorCℐC\_\{\\mathcal\{I\}\}as in \([14](https://arxiv.org/html/2608.20428#S4.E14)\), withq1=ϵq\_\{1\}=\\epsilon\. Then, there existsε¯​\(ℐ\)\>0\\overline\{\\varepsilon\}\(\\mathcal\{I\}\)\>0such that, for every interface𝒥\\mathcal\{J\}satisfying

d∞​\(ℐ,𝒥\)≤ε<ε¯​\(ℐ\),d\_\{\\infty\}\(\\mathcal\{I\},\\mathcal\{J\}\)\\leq\\varepsilon<\\overline\{\\varepsilon\}\(\\mathcal\{I\}\),the mapΠ𝒥→ℐ:G𝒥at→Gℐat\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}:G\_\{\\mathcal\{J\}\}^\{\\mathrm\{at\}\}\\to G\_\{\\mathcal\{I\}\}^\{\\mathrm\{at\}\}is a2​Γℐ​ε2\\Gamma\_\{\\mathcal\{I\}\}\\varepsilon\-linear reduction\.

From this theorem we get as an immediate corollary the existence ofδ\\delta\-minima for a small enough neighbourhood of every finite\-rank interface\.

###### Corollary 1\.

For every finite\-rank interfaceℐ\\mathcal\{I\}, its canonical realizationGℐG\_\{\\mathcal\{I\}\}, equipped with the atomic norm, is a2​Γℐ​ε2\\Gamma\_\{\\mathcal\{I\}\}\\varepsilon\-minimum ofℒℐε,d∞\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{\\varepsilon,d\_\{\\infty\}\}for every0≤ε<ε¯​\(ℐ\)0\\leq\\varepsilon<\\overline\{\\varepsilon\}\(\\mathcal\{I\}\), when restrictingℒℐε,d∞\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{\\varepsilon,d\_\{\\infty\}\}to contain only the canonical linear realizations with the atomic norm\.

Note that our main theorem has to boundε\\varepsilonto ensure that the reduction is surjective\. Even though this requirement is reasonable \(otherwise, we could reduce small transducers into subcomponents of bigger ones\), in many applications it might make sense to ignore this restriction\. That’s why we phrased Theorem[3](https://arxiv.org/html/2608.20428#Thmtheorem3)in an independent way\.

The results in this section are in some sense satisfactory: we observed that convergent structure \(i\.e\. aδ\\delta\-minima forδ=O⁡\(ε\)\\delta=O\(\\varepsilon\)\) exists for every finite rank interface in a neighbourhood of the interface\. Observe that in our statements we have to pick a norm and a distance in a somewhat arbitrary way\. However, a similar result can be proven using the predictive norm\. Conceptually, we believe that these result indicate that the convergent structure exists at the level of linear transducers even in the presence of perturbations in the implementations\.

We remark that in Corollary[1](https://arxiv.org/html/2608.20428#Thmcorollary1)we restrict the lattice to the minimal linear implementations\. If we don’t do this, we still can prove the existence of a reduction from any linear transducerGGin the set by composing the mapρG\\rho\_\{G\}from Lemma[1](https://arxiv.org/html/2608.20428#Thmlemma1)with the one from Theorem[3](https://arxiv.org/html/2608.20428#Thmtheorem3)wheneverρG\\rho\_\{G\}is bounded\. Then, using Proposition[4](https://arxiv.org/html/2608.20428#Thmproposition4)we would obtain an error that depends on‖ρG‖\\\|\\rho\_\{G\}\\\|\. However, there is no uniform bound on this value when using the atomic norm\. There are other choices of norms which can solve this problem but they seem quite unnatural, and therefore we prefer to keep the corollary as stated, applying only to the lattice of “optimal” implementations\.

### 4\.3Existence ofδ\\delta\-minima for predictive transducers under a specific metric

As already mentioned, restricting to predictive transducers restores a canonical minimum for each fixed interface, which we denote by𝖤⁡\(ℐ\)\\mathsf\{E\}\(\\mathcal\{I\}\)\(see Proposition[1](https://arxiv.org/html/2608.20428#Thmproposition1)\)\. This exact statement is not stable under the supremum metric\.

###### Proposition 7\.

There is an interfaceℐ\\mathcal\{I\}and a sequence of interfaces\(𝒥n\)n≥1\(\\mathcal\{J\}\_\{n\}\)\_\{n\\geq 1\}such that

d∞​\(ℐ,𝒥n\)=2−n⟶0,d\_\{\\infty\}\(\\mathcal\{I\},\\mathcal\{J\}\_\{n\}\)=2^\{\-n\}\\longrightarrow 0,but every approximate reduction𝖤⁡\(𝒥n\)​→𝛿​𝖤​\(ℐ\)\\mathsf\{E\}\(\\mathcal\{J\}\_\{n\}\)\\overset\{\\delta\}\{\\rightarrow\{\}\}\\mathsf\{E\}\(\\mathcal\{I\}\)satisfiesδ≥1/2\\delta\\geq 1/2\. Moreover, if a transducerCCreceivesδ\\delta\-reductions from both𝖤⁡\(ℐ\)\\mathsf\{E\}\(\\mathcal\{I\}\)and𝖤⁡\(𝒥n\)\\mathsf\{E\}\(\\mathcal\{J\}\_\{n\}\), thenδ≥1/4\\delta\\geq 1/4\.

This counterexample also applies to the discounted metric, and we believe it highlights a limitation of predictive transducers\. More precisely, if there is a historyhhsuch that the interfaceℐ\\mathcal\{I\}conditioned onhhbehaves in an extremely different way from the interface𝒥\\mathcal\{J\}conditioned onhh, then the local structure related to both predictive states will be different, even ifhhis highly unlikely \(and thus, it is ignored by most reasonable metrics\)\. We now show that, as one would expect, this problem can be avoided by using precisely a notion of distance between interfaces that values every possible conditioning independently of its probability\.

For a positive probability historyhh, letℐh\\mathcal\{I\}^\{h\}denote the residual interface after conditioning onhh\(see Eq\. \([4](https://arxiv.org/html/2608.20428#S2.E4)\) for the exact definition\)\. Writesupp⁡\(ℐ\)\\operatorname\{supp\}\(\\mathcal\{I\}\)for the set of positive probability histories and define

dres​\(ℐ,𝒥\)=\{suph∈supp⁡\(ℐ\)d∞​\(ℐh,𝒥h\),supp⁡\(ℐ\)=supp⁡\(𝒥\),1,otherwise\.d\_\{\\mathrm\{res\}\}\(\\mathcal\{I\},\\mathcal\{J\}\)=\\begin\{cases\}\\displaystyle\\sup\_\{h\\in\\operatorname\{supp\}\(\\mathcal\{I\}\)\}d\_\{\\infty\}\(\\mathcal\{I\}^\{h\},\\mathcal\{J\}^\{h\}\),&\\operatorname\{supp\}\(\\mathcal\{I\}\)=\\operatorname\{supp\}\(\\mathcal\{J\}\),\\\\\[5\.16663pt\] 1,&\\text\{otherwise\.\}\\end\{cases\}This metric compares the predictive laws after every history, including the ones with low probability\. Let\[h\]ℐ\[h\]\_\{\\mathcal\{I\}\}denote the state of𝖤⁡\(ℐ\)\\mathsf\{E\}\(\\mathcal\{I\}\)reached afterhh, and put

Δℐ=inf\{d∞\(ℐh,ℐu\):h,u∈supp\(ℐ\),\[h\]ℐ≠\[u\]ℐ\}\.\\Delta\_\{\\mathcal\{I\}\}=\\inf\\left\\\{d\_\{\\infty\}\(\\mathcal\{I\}^\{h\},\\mathcal\{I\}^\{u\}\):h,u\\in\\operatorname\{supp\}\(\\mathcal\{I\}\),\[h\]\_\{\\mathcal\{I\}\}\\neq\[u\]\_\{\\mathcal\{I\}\}\\right\\\}\.We use the conventionΔℐ=\+∞\\Delta\_\{\\mathcal\{I\}\}=\+\\inftyif there is only one predictive state\. If𝖤⁡\(ℐ\)\\mathsf\{E\}\(\\mathcal\{I\}\)is finite, thenΔℐ\>0\\Delta\_\{\\mathcal\{I\}\}\>0\. Intuitively,Δℐ\\Delta\_\{\\mathcal\{I\}\}is a lower bound on the difference between the interfaces induced by each of the predictive states\.

If there is an interface𝒥\\mathcal\{J\}such thatdres​\(ℐ,𝒥\)d\_\{\\mathrm\{res\}\}\(\\mathcal\{I\},\\mathcal\{J\}\)is much smaller thanΔℐ\\Delta\_\{\\mathcal\{I\}\}then the predictive transducers implementingℐ\\mathcal\{I\}and𝒥\\mathcal\{J\}will be similar\. We formalize this in our last theorem\.

###### Theorem 4\.

Letℐ\\mathcal\{I\}and𝒥\\mathcal\{J\}be interfaces over the same input and output alphabets\. Suppose thatΔℐ\>0\\Delta\_\{\\mathcal\{I\}\}\>0and that

dres​\(ℐ,𝒥\)≤ε<min⁡\{1,Δℐ2\}\.d\_\{\\mathrm\{res\}\}\(\\mathcal\{I\},\\mathcal\{J\}\)\\leq\\varepsilon<\\min\\left\\\{1,\\frac\{\\Delta\_\{\\mathcal\{I\}\}\}\{2\}\\right\\\}\.Then the assignment

ϕ⁡\(\[h\]𝒥\):=\[h\]ℐ,\\phi\(\[h\]\_\{\\mathcal\{J\}\}\):=\[h\]\_\{\\mathcal\{I\}\},is a well\-defined surjective state map and determines anε\\varepsilon\-reductionE⁡\(𝒥\)⟶E⁡\(ℐ\)E\(\\mathcal\{J\}\)\\longrightarrow E\(\\mathcal\{I\}\)\. Consequently, every predictive transducer implementing𝒥\\mathcal\{J\}admits anε\\varepsilon\-reduction toE⁡\(ℐ\)E\(\\mathcal\{I\}\)\.

The intuition for the conditionε<Δℐ2\\varepsilon<\\frac\{\\Delta\_\{\\mathcal\{I\}\}\}\{2\}comes from the triangle inequality: if we want to prove thatϕ\\phiis well defined, we need to ensure that ifh1∼h2h\_\{1\}\\sim h\_\{2\}in𝒥\\mathcal\{J\}thenh1∼h2h\_\{1\}\\sim h\_\{2\}inℐ\\mathcal\{I\}\. This is equivalent to verifying thatℐh1=ℐh2\\mathcal\{I\}^\{h\_\{1\}\}=\\mathcal\{I\}^\{h\_\{2\}\}, and by triangle inequality we see that

d∞​\(ℐh1,ℐh2\)\\displaystyle d\_\{\\infty\}\(\\mathcal\{I\}^\{h\_\{1\}\},\\mathcal\{I\}^\{h\_\{2\}\}\)≤d∞​\(ℐh1,𝒥h1\)\+d∞​\(𝒥h1,𝒥h2\)\+d∞​\(𝒥h2,ℐh2\)\\displaystyle\\leq d\_\{\\infty\}\(\\mathcal\{I\}^\{h\_\{1\}\},\\mathcal\{J\}^\{h\_\{1\}\}\)\+d\_\{\\infty\}\(\\mathcal\{J\}^\{h\_\{1\}\},\\mathcal\{J\}^\{h\_\{2\}\}\)\+d\_\{\\infty\}\(\\mathcal\{J\}^\{h\_\{2\}\},\\mathcal\{I\}^\{h\_\{2\}\}\)≤2​ε<Δℐ\.\\displaystyle\\leq 2\\varepsilon<\\Delta\_\{\\mathcal\{I\}\}\.Then, by definition ofΔℐ\\Delta\_\{\\mathcal\{I\}\}it must be the case thatℐh1=ℐh2\\mathcal\{I\}^\{h\_\{1\}\}=\\mathcal\{I\}^\{h\_\{2\}\}\.

As a corollary, we obtain the existence ofδ\\delta\-minimums for the set of predictive transducers\.

###### Corollary 2\.

Letℐ\\mathcal\{I\}be an interface such thatΔℐ\>0\\Delta\_\{\\mathcal\{I\}\}\>0\. Then, for every0<ε<min⁡\{1,Δℐ2\}0<\\varepsilon<\\min\\left\\\{1,\\frac\{\\Delta\_\{\\mathcal\{I\}\}\}\{2\}\\right\\\}and every predictive transducerTTimplementing an interface𝒥\\mathcal\{J\}withdres​\(ℐ,𝒥\)≤εd\_\{\\mathrm\{res\}\}\(\\mathcal\{I\},\\mathcal\{J\}\)\\leq\\varepsilonthere is aε\\varepsilon\-reduction fromTTto𝖤⁡\(ℐ\)\\mathsf\{E\}\(\\mathcal\{I\}\)\.

This is a positive result regarding convergent structure, but its application is restricted to scenarios where the residual distance makes sense\. In the following we describe an example of a situation in which two different stochastic systems can induce interfaces which are close according todresd\_\{\\mathrm\{res\}\}\.

###### Example 7\.

Let𝒮=𝒪=\{0,1,2\}\\mathcal\{S\}=\\mathcal\{O\}=\\\{0,1,2\\\}and𝒜=\{⋆\}\\mathcal\{A\}=\\\{\\star\\\}\(i\.e\. the dynamics are actionless because there is a single action\)\. and consider the transition matrix

P=\(1/21/41/41/41/21/41/41/41/2\)\.P=\\begin\{pmatrix\}1/2&1/4&1/4\\\\ 1/4&1/2&1/4\\\\ 1/4&1/4&1/2\\end\{pmatrix\}\.Let stateiioutputiibefore making a transition\. Thus, the transition kernel is

κ\(j,o∣i\)=P\(i,j\)𝟏\{o=i\}\.\\kappa\(j,o\\mid i\)=P\(i,j\)\\mathbf\{1\}\_\{\\\{o=i\\\}\}\.Consider two transducersTTandTεT\_\{\\varepsilon\}using the kernelκ\\kappa, but with different initial distributions given byp=\(13,13,13\)p=\\left\(\\frac\{1\}\{3\},\\frac\{1\}\{3\},\\frac\{1\}\{3\}\\right\)forTTandpε=\(13\+ε,13−ε,13\)p\_\{\\varepsilon\}=\\left\(\\frac\{1\}\{3\}\+\\varepsilon,\\frac\{1\}\{3\}\-\\varepsilon,\\frac\{1\}\{3\}\\right\)forTεT\_\{\\varepsilon\}\. See Figure[7](https://arxiv.org/html/2608.20428#S4.F7)for a visual description\.

Transition matrixs0s\_\{0\}s1s\_\{1\}s2s\_\{2\}14\\frac\{1\}\{4\}14\\frac\{1\}\{4\}14\\frac\{1\}\{4\}12\\frac\{1\}\{2\}12\\frac\{1\}\{2\}12\\frac\{1\}\{2\}Initial distributionsTTp=\(13,13,13\)\\displaystyle p=\\left\(\\frac\{1\}\{3\},\\frac\{1\}\{3\},\\frac\{1\}\{3\}\\right\)TεT\_\{\\varepsilon\}pε=\(13\+ε,13−ε,13\)\\displaystyle p\_\{\\varepsilon\}=\\left\(\\frac\{1\}\{3\}\+\\varepsilon,\\frac\{1\}\{3\}\-\\varepsilon,\\frac\{1\}\{3\}\\right\)Figure 7:We consider two transducersTTandTεT\_\{\\varepsilon\}with the same transition kernel described by the Markov process on the left but different initial distributions given on the right side\. It can be seen that for small enoughε\>0\\varepsilon\>0the induced interfaces satisfydres​\(ℐT,ℐTε\)≤ε<Δℐ/2d\_\{\\mathrm\{res\}\}\(\\mathcal\{I\}\_\{T\},\\mathcal\{I\}\_\{T\_\{\\varepsilon\}\}\)\\leq\\varepsilon<\\Delta\_\{\\mathcal\{I\}\}/2\.It can be seen thatdres​\(ℐT,ℐTε\)≤εd\_\{\\mathrm\{res\}\}\(\\mathcal\{I\}\_\{T\},\\mathcal\{I\}\_\{T\_\{\\varepsilon\}\}\)\\leq\\varepsilon: note that conditioning on any non\-empty historyhhthe interfacesℐTh\\mathcal\{I\}^\{h\}\_\{T\}andℐTεh\\mathcal\{I\}^\{h\}\_\{T\_\{\\varepsilon\}\}are equal, and moreoverd∞​\(ℐT,ℐTε\)≤εd\_\{\\infty\}\(\\mathcal\{I\}\_\{T\},\\mathcal\{I\}\_\{T\_\{\\varepsilon\}\}\)\\leq\\varepsilon\. Moreover, it can be seen thatΔℐT=16\\Delta\_\{\\mathcal\{I\}\_\{T\}\}=\\frac\{1\}\{6\}\. Thus, due to Theorem[4](https://arxiv.org/html/2608.20428#Thmtheorem4)we conclude that ifε<112\\varepsilon<\\frac\{1\}\{12\}it holds that the minimal predictive implementation ofℐT\\mathcal\{I\}\_\{T\}and ofℐTε\\mathcal\{I\}\_\{T\_\{\\varepsilon\}\}areε\\varepsilon\-close through an approximate reduction\.

More generally, different processes with the same transition dynamics but different initial distributions can be close in thedresd\_\{\\mathrm\{res\}\}metric whenever the effect of conditioning ensures that the current state for both processes is the same\.

## 5Conclusion

Summary\.In this work we looked for theoretical evidence supporting the empirical observation that different neural network models, sometimes even supported on different architectures, tend to converge to similar representations in their internal layers\. To investigate this idea we proposed the approach described in Figure[1](https://arxiv.org/html/2608.20428#S1.F1): we assumed that the reasoning inside the internal layers can be represented through some abstraction, and then we tried to prove some convergence at the level of these objects\. In our case, we considered transducers to capture these world models, and to find convergent structure we looked for homomorphisms between them\. Previous work had already proven that for the case of linear and predictive transducers there always exists a minimal transducer implementing a given dynamics, and that for all other non\-minimal transducers there is a homomorphism to this minimal one\[[44](https://arxiv.org/html/2608.20428#bib.bib1)\]\. In this paper we improved this result by showing that the existence of such an homomorphism remains even when we consider transducers that do not implementexactlythe same dynamics\.

To do this, we first introduced a notion of approximate homomorphism for standard transducers \(Definition[8](https://arxiv.org/html/2608.20428#Thmdefinition8)\) as well as for the linear ones \(Definition[9](https://arxiv.org/html/2608.20428#Thmdefinition9)\)\. We showed that, although there are many ways to define such a family of homomorphisms, the ones proposed here have good algebraic properties: they preserve the dynamics under discounted metrics \(Theorems[1](https://arxiv.org/html/2608.20428#Thmtheorem1)and[2](https://arxiv.org/html/2608.20428#Thmtheorem2)\), are composable \(Propositions[2](https://arxiv.org/html/2608.20428#Thmproposition2)and[4](https://arxiv.org/html/2608.20428#Thmproposition4)\), and the linear approximate homomorphism is a direct extension of the standard one \(Proposition[3](https://arxiv.org/html/2608.20428#Thmproposition3)\)\.

With these tools developed, we looked for convergence theorems in the approximate setting: we looked for conditions under which all transducers implementing similar dynamics share some common structure, which we aimed to capture through approximate homomorphisms \(see Figure[6](https://arxiv.org/html/2608.20428#S4.F6)for a visual sketch of the idea\)\. In particular, we showed that \(1\) For standard transducers, this type of convergence seems to not be possible, even when considering simple dynamics \(Propositions[5](https://arxiv.org/html/2608.20428#Thmproposition5)and[6](https://arxiv.org/html/2608.20428#Thmproposition6)\), \(2\) For linear transducers, simple enough dynamics \(more technically, finite\-rank interfaces\) always admit a type of convergence between all the minimal linear implementations ofε\\varepsilon\-close dynamics \(Theorem[3](https://arxiv.org/html/2608.20428#Thmtheorem3)\), and, finally, that \(3\) For predictive transducer, there is a metric such that all transducer implementing dynamics close enough according to this metric will share structural properties between them \(Theorem[4](https://arxiv.org/html/2608.20428#Thmtheorem4)\)\.

We believe these are positive theoretical results regarding the existence of convergent structure, in the context of both both linear and predictive transducers\. The former family seems to be the natural model for capturing latent representation in modern neural networks, considering especially that the model parameters live in a vector space\. The latter one, although less natural, still has been seen to show up inside the residual stream of transformers\[[46](https://arxiv.org/html/2608.20428#bib.bib30),[47](https://arxiv.org/html/2608.20428#bib.bib29)\], and thus understanding these representational properties might shed light into the behaviour of modern LLMs\.

Limitations\.Through the development of this work we discovered that there are many ways to formalize approximate convergence in the context of transducers\. Although the proposals here satisfy good properties and extend previous ones\[[41](https://arxiv.org/html/2608.20428#bib.bib8)\]there is still room for developing a more general theory of approximate homomorphisms\. Moreover, in the context of linear transducers we had to equip the underlying vector space with a norm to measure distance between vectors, thus introducing another “parameter” to our theory\. Although many of our main theorems can be proven for other choices of norms and distances \(such as Theorem[3](https://arxiv.org/html/2608.20428#Thmtheorem3)\), it would be great to have a more robust understanding of the precise hypothesis required to conclude structural convergence in the approximate setting\.

Future work\.We describe some future lines of work starting from the developments in this paper\.

- •Experimental validation: these results give predictions on the structural convergence of deep neural networks under the hypothesis that they use transducers in their latent space\. In particular, for models trained on similar data it must be the case that their internal representation can be translated with a linear map \(such type of translation scheme is usually referred to as “stitching”, and has been studied in the literature\[[2](https://arxiv.org/html/2608.20428#bib.bib18),[9](https://arxiv.org/html/2608.20428#bib.bib17)\]\)\. To validate these hypotheses, it would be interesting to train modern models with data generated from specific linear transducers and then see whether these transducers can be found in the learned representations\. To do this, one could reproduce the setting from\[[46](https://arxiv.org/html/2608.20428#bib.bib30),[47](https://arxiv.org/html/2608.20428#bib.bib29)\]\.
- •Poset structure: the original goal of this project was to study the poset of approximate homomorphism between world models\. More precisely, we would like to understand how this poset looks like when we order it through the relation induced by the existence of an approximate homomorphism\. A central and simple question is: under which hypothesis can we guarantee that this poset has cut\-points, in the sense of intermediate modelsMMsuch that, for any other modelM′M^\{\\prime\}, it holds thatMMhas an homomorphism toM′M^\{\\prime\}or the other way around\. Given the introduced notions of approximate homomorphisms, this question can now be approached in the context of transducers\.
- •Improved abstractions: Our abstractions are still limited and do not represent the myriad of forms on which “abstraction” and “reasoning” can occur inside modern AI models\. Two recognizable improvement would be \(1\) introducing some non\-linearity in the notion of linear transducers, to model the effect of the activation functions between layers, and \(2\) introducing a global error inside the notion of approximate homomorphism to allow homomorphisms that preserve the local structure of most of the states but fail completely in a small subset \(such a notion would capture more faithfully what happens during model stitching when the target network is a bigger model than the source network\)\.

## 6Acknowledgements

This work was funded by the Advanced Research \+ Invention Agency \(ARIA\) through project code MSAI\-SE01\-P005\. We would like to thank the Dovetail Research team666[https://dovetailresearch\.org/](https://dovetailresearch.org/)\.for comments and suggestions on the draft of this paper, and we are especially grateful to Alex Altair, Alfred Harwood, Jose Faustino and Neal Batra for fruitful discussions\.

AI disclosure: We used ChatGPT 5\.5 and 5\.6 for proofreading, creating diagrams, writing down simple proofs \(such as the proof from Lemma[2](https://arxiv.org/html/2608.20428#Thmlemma2)\) and quickly exploring variants of the results \(such as checking whether the proof of Theorem[3](https://arxiv.org/html/2608.20428#Thmtheorem3)holds for other choices of distances and norms\)\. All content created by AI was revised and rewritten to improve readability and clarity of exposition\.

## Appendix AAppendix

### A\.1Comparison of notions of exact homomorphisms

We describe the original formulation of homomorphism and see how it differs from ours\.

###### Definition 13\(Homomorphism from\[[44](https://arxiv.org/html/2608.20428#bib.bib1)\]\)\.

Given two transducersT1=\(𝒮1,𝒜1,𝒪1,κ1,p1\)T\_\{1\}=\(\\mathcal\{S\}\_\{1\},\\mathcal\{A\}\_\{1\},\\mathcal\{O\}\_\{1\},\\kappa\_\{1\},p\_\{1\}\)andT2=\(𝒮2,𝒜2,𝒪2,κ2,p2\)T\_\{2\}=\(\\mathcal\{S\}\_\{2\},\\mathcal\{A\}\_\{2\},\\mathcal\{O\}\_\{2\},\\kappa\_\{2\},p\_\{2\}\), a homomorphism is given by three mappings⟨ϕ:𝒮1→𝒮2,f:𝒜1→𝒜2,g:𝒪1→𝒪2⟩\\langle\\phi:\\mathcal\{S\}\_\{1\}\\to\\mathcal\{S\}\_\{2\},f:\\mathcal\{A\}\_\{1\}\\to\\mathcal\{A\}\_\{2\},g:\\mathcal\{O\}\_\{1\}\\to\\mathcal\{O\}\_\{2\}\\ranglesatisfying \([3](https://arxiv.org/html/2608.20428#S2.E3)\), the condition

Pr\(o2\|ϕ\(s1\),f\(a1\)\)T2=∑o1∈g−1​\(o2\)Pr\(o1\|s1,a1\)T1\.\\displaystyle\\Pr\{\}\_\{T\_\{2\}\}\(o\_\{2\}\|\\phi\(s\_\{1\}\),f\(a\_\{1\}\)\)=\\sum\_\{o\_\{1\}\\in g^\{\-1\}\(o\_\{2\}\)\}\\Pr\{\}\_\{T\_\{1\}\}\(o\_\{1\}\|s\_\{1\},a\_\{1\}\)\.\(15\)for everys1∈𝒮1,a1∈𝒜1s\_\{1\}\\in\\mathcal\{S\}\_\{1\},a\_\{1\}\\in\\mathcal\{A\}\_\{1\}ando2∈𝒪2o\_\{2\}\\in\\mathcal\{O\}\_\{2\}, and wheneverPr\(o1\|s1,a1\)T1\>0\\Pr\{\}\_\{T\_\{1\}\}\(o\_\{1\}\|s\_\{1\},a\_\{1\}\)\>0the condition

Pr\(s2\|ϕ\(s1\),f\(a1\),g\(o1\)\)T2=∑s′∈ϕ−1​\(s2\)Pr\(s′\|s1,a1,o1\)T1\\displaystyle\\Pr\{\}\_\{T\_\{2\}\}\(s\_\{2\}\|\\phi\(s\_\{1\}\),f\(a\_\{1\}\),g\(o\_\{1\}\)\)=\\sum\_\{s^\{\\prime\}\\in\\phi^\{\-1\}\(s\_\{2\}\)\}\\Pr\{\}\_\{T\_\{1\}\}\(s^\{\\prime\}\|s\_\{1\},a\_\{1\},o\_\{1\}\)\(16\)for everyo1∈𝒪1o\_\{1\}\\in\\mathcal\{O\}\_\{1\}ands2∈𝒮2s\_\{2\}\\in\\mathcal\{S\}\_\{2\}\.

We now show that this definition and ours coincide whenggis injective\.

###### Proposition 8\.

Definitions[2](https://arxiv.org/html/2608.20428#Thmdefinition2)and[13](https://arxiv.org/html/2608.20428#Thmdefinition13)coincide ifggis injective\.

###### Proof\.

LetT1=\(𝒮1,𝒜1,𝒪1,κ1,p1\)T\_\{1\}=\(\\mathcal\{S\}\_\{1\},\\mathcal\{A\}\_\{1\},\\mathcal\{O\}\_\{1\},\\kappa\_\{1\},p\_\{1\}\)andT2=\(𝒮2,𝒜2,𝒪2,κ2,p2\)T\_\{2\}=\(\\mathcal\{S\}\_\{2\},\\mathcal\{A\}\_\{2\},\\mathcal\{O\}\_\{2\},\\kappa\_\{2\},p\_\{2\}\)be transducers, and let⟨ϕ,f,g⟩\\langle\\phi,f,g\\ranglebe mapsϕ:𝒮1→𝒮2\\phi:\\mathcal\{S\}\_\{1\}\\to\\mathcal\{S\}\_\{2\},f:𝒜1→𝒜2f:\\mathcal\{A\}\_\{1\}\\to\\mathcal\{A\}\_\{2\}andg:𝒪1→𝒪2g:\\mathcal\{O\}\_\{1\}\\to\\mathcal\{O\}\_\{2\}\. We will prove that this tuple satisfies Definition[2](https://arxiv.org/html/2608.20428#Thmdefinition2)if and only if it satisfies Definition[13](https://arxiv.org/html/2608.20428#Thmdefinition13)\.

Assume first that the joint\-kernel condition \([2](https://arxiv.org/html/2608.20428#S2.E2)\) holds\. Summing both sides overs2∈𝒮2s\_\{2\}\\in\\mathcal\{S\}\_\{2\}gives

Pr\(o2\|ϕ\(s1\),f\(a1\)\)T2\\displaystyle\\Pr\{\}\_\{T\_\{2\}\}\(o\_\{2\}\|\\phi\(s\_\{1\}\),f\(a\_\{1\}\)\)=∑s2∈𝒮2κ2\(s2,o2\|ϕ\(s1\),f\(a1\)\)\\displaystyle=\\sum\_\{s\_\{2\}\\in\\mathcal\{S\}\_\{2\}\}\\kappa\_\{2\}\(s\_\{2\},o\_\{2\}\|\\phi\(s\_\{1\}\),f\(a\_\{1\}\)\)=∑s2∈𝒮2∑s′∈ϕ−1​\(s2\)o′∈g−1​\(o2\)κ1\(s′,o′\|s1,a1\)\\displaystyle=\\sum\_\{s\_\{2\}\\in\\mathcal\{S\}\_\{2\}\}\\sum\_\{\\begin\{subarray\}\{c\}s^\{\\prime\}\\in\\phi^\{\-1\}\(s\_\{2\}\)\\\\ o^\{\\prime\}\\in g^\{\-1\}\(o\_\{2\}\)\\end\{subarray\}\}\\kappa\_\{1\}\(s^\{\\prime\},o^\{\\prime\}\|s\_\{1\},a\_\{1\}\)=∑o′∈g−1​\(o2\)Pr\(o′\|s1,a1\)T1,\\displaystyle=\\sum\_\{o^\{\\prime\}\\in g^\{\-1\}\(o\_\{2\}\)\}\\Pr\{\}\_\{T\_\{1\}\}\(o^\{\\prime\}\|s\_\{1\},a\_\{1\}\),which is exactly \([15](https://arxiv.org/html/2608.20428#A1.E15)\)\. Now fixo1∈𝒪1o\_\{1\}\\in\\mathcal\{O\}\_\{1\}such thatPr\(o1\|s1,a1\)T1\>0\\Pr\{\}\_\{T\_\{1\}\}\(o\_\{1\}\|s\_\{1\},a\_\{1\}\)\>0\. Sinceggis injective,g−1​\(g⁡\(o1\)\)=\{o1\}g^\{\-1\}\(g\(o\_\{1\}\)\)=\\\{o\_\{1\}\\\}\. Hence

Pr\(s2\|ϕ\(s1\),f\(a1\),g\(o1\)\)T2\\displaystyle\\Pr\{\}\_\{T\_\{2\}\}\(s\_\{2\}\|\\phi\(s\_\{1\}\),f\(a\_\{1\}\),g\(o\_\{1\}\)\)=κ2\(s2,g\(o1\)\|ϕ\(s1\),f\(a1\)\)PrT2\(g\(o1\)\|ϕ\(s1\),f\(a1\)\)\\displaystyle=\\frac\{\\kappa\_\{2\}\(s\_\{2\},g\(o\_\{1\}\)\|\\phi\(s\_\{1\}\),f\(a\_\{1\}\)\)\}\{\\Pr\{\}\_\{T\_\{2\}\}\(g\(o\_\{1\}\)\|\\phi\(s\_\{1\}\),f\(a\_\{1\}\)\)\}=∑s′∈ϕ−1​\(s2\)κ1\(s′,o1\|s1,a1\)PrT1\(o1\|s1,a1\)\\displaystyle=\\frac\{\\sum\_\{s^\{\\prime\}\\in\\phi^\{\-1\}\(s\_\{2\}\)\}\\kappa\_\{1\}\(s^\{\\prime\},o\_\{1\}\|s\_\{1\},a\_\{1\}\)\}\{\\Pr\{\}\_\{T\_\{1\}\}\(o\_\{1\}\|s\_\{1\},a\_\{1\}\)\}=∑s′∈ϕ−1​\(s2\)Pr\(s′\|s1,a1,o1\)T1\.\\displaystyle=\\sum\_\{s^\{\\prime\}\\in\\phi^\{\-1\}\(s\_\{2\}\)\}\\Pr\{\}\_\{T\_\{1\}\}\(s^\{\\prime\}\|s\_\{1\},a\_\{1\},o\_\{1\}\)\.Thus the original conditional formulation follows\. The initial condition is the same in both definitions\.

Conversely, assume Definition[13](https://arxiv.org/html/2608.20428#Thmdefinition13)\. We prove \([2](https://arxiv.org/html/2608.20428#S2.E2)\)\. Ifo2∉g⁡\(𝒪1\)o\_\{2\}\\notin g\(\\mathcal\{O\}\_\{1\}\), then the right\-hand side of \([15](https://arxiv.org/html/2608.20428#A1.E15)\) is zero\. ThereforePr\(o2\|ϕ\(s1\),f\(a1\)\)T2=0\\Pr\{\}\_\{T\_\{2\}\}\(o\_\{2\}\|\\phi\(s\_\{1\}\),f\(a\_\{1\}\)\)=0, and thenκ2\(s2,o2\|ϕ\(s1\),f\(a1\)\)=0\\kappa\_\{2\}\(s\_\{2\},o\_\{2\}\|\\phi\(s\_\{1\}\),f\(a\_\{1\}\)\)=0for everys2s\_\{2\}\.

It remains to considero2∈g⁡\(𝒪1\)o\_\{2\}\\in g\(\\mathcal\{O\}\_\{1\}\)\. By injectivity there is a uniqueo1∈𝒪1o\_\{1\}\\in\\mathcal\{O\}\_\{1\}such thatg⁡\(o1\)=o2g\(o\_\{1\}\)=o\_\{2\}\. IfPr\(o1\|s1,a1\)T1\>0\\Pr\{\}\_\{T\_\{1\}\}\(o\_\{1\}\|s\_\{1\},a\_\{1\}\)\>0, multiplying \([16](https://arxiv.org/html/2608.20428#A1.E16)\) by \([15](https://arxiv.org/html/2608.20428#A1.E15)\) gives

κ2\(s2,o2\|ϕ\(s1\),f\(a1\)\)\\displaystyle\\kappa\_\{2\}\(s\_\{2\},o\_\{2\}\|\\phi\(s\_\{1\}\),f\(a\_\{1\}\)\)=Pr\(o2\|ϕ\(s1\),f\(a1\)\)T2Pr\(s2\|ϕ\(s1\),f\(a1\),o2\)T2\\displaystyle=\\Pr\{\}\_\{T\_\{2\}\}\(o\_\{2\}\|\\phi\(s\_\{1\}\),f\(a\_\{1\}\)\)\\Pr\{\}\_\{T\_\{2\}\}\(s\_\{2\}\|\\phi\(s\_\{1\}\),f\(a\_\{1\}\),o\_\{2\}\)=Pr\(o1\|s1,a1\)T1∑s′∈ϕ−1​\(s2\)Pr\(s′\|s1,a1,o1\)T1\\displaystyle=\\Pr\{\}\_\{T\_\{1\}\}\(o\_\{1\}\|s\_\{1\},a\_\{1\}\)\\sum\_\{s^\{\\prime\}\\in\\phi^\{\-1\}\(s\_\{2\}\)\}\\Pr\{\}\_\{T\_\{1\}\}\(s^\{\\prime\}\|s\_\{1\},a\_\{1\},o\_\{1\}\)=∑s′∈ϕ−1​\(s2\)κ1\(s′,o1\|s1,a1\)\\displaystyle=\\sum\_\{s^\{\\prime\}\\in\\phi^\{\-1\}\(s\_\{2\}\)\}\\kappa\_\{1\}\(s^\{\\prime\},o\_\{1\}\|s\_\{1\},a\_\{1\}\)=∑s′∈ϕ−1​\(s2\)o′∈g−1​\(o2\)κ1\(s′,o′\|s1,a1\)\.\\displaystyle=\\sum\_\{\\begin\{subarray\}\{c\}s^\{\\prime\}\\in\\phi^\{\-1\}\(s\_\{2\}\)\\\\ o^\{\\prime\}\\in g^\{\-1\}\(o\_\{2\}\)\\end\{subarray\}\}\\kappa\_\{1\}\(s^\{\\prime\},o^\{\\prime\}\|s\_\{1\},a\_\{1\}\)\.IfPr\(o1\|s1,a1\)T1=0\\Pr\{\}\_\{T\_\{1\}\}\(o\_\{1\}\|s\_\{1\},a\_\{1\}\)=0, then \([15](https://arxiv.org/html/2608.20428#A1.E15)\) givesPr\(o2\|ϕ\(s1\),f\(a1\)\)T2=0\\Pr\{\}\_\{T\_\{2\}\}\(o\_\{2\}\|\\phi\(s\_\{1\}\),f\(a\_\{1\}\)\)=0\. Again nonnegativity forces both sides of \([2](https://arxiv.org/html/2608.20428#S2.E2)\) to be zero\. The kernel condition therefore holds in all cases, and the initial condition is shared by the two definitions\. ∎

Whenggis not injective, the two formulations need not agree\. In the original definition, the only outputs that can be coarse\-grained are those with the same output laws for each state\. Meanwhile, our formulation only requires equality after averaging over the whole fiberg−1​\(o\)g^\{\-1\}\(o\)andϕ−1​\(s\)\\phi^\{\-1\}\(s\)\. As already mentioned, since we focus on reductions this distinction is irrelevant\.

### A\.2Total variation

We collect here some relevant facts about total variation\. All probability spaces in the sequel are finite or countable\.

###### Definition 14\(Total variation\)\.

Letμ,ν∈Δ⁡\(X\)\\mu,\\nu\\in\\Delta\(X\)\. Their total variation distance is

‖μ−ν‖TV=supA⊆X\|μ⁡\(A\)−ν⁡\(A\)\|=12​∑x∈X\|μ⁡\(x\)−ν⁡\(x\)\|\.\\\|\\mu\-\\nu\\\|\_\{\\mathrm\{TV\}\}=\\sup\_\{A\\subseteq X\}\|\\mu\(A\)\-\\nu\(A\)\|=\\frac\{1\}\{2\}\\sum\_\{x\\in X\}\|\\mu\(x\)\-\\nu\(x\)\|\.

Ifh:X→Yh:X\\to Yis a map andμ∈Δ⁡\(X\)\\mu\\in\\Delta\(X\), we writeh∗​μ∈Δ⁡\(Y\)h\_\{\*\}\\mu\\in\\Delta\(Y\)for the push\-forward distribution,

\(h∗​μ\)​\(y\)=∑x∈h−1​\(y\)μ⁡\(x\)\.\(h\_\{\*\}\\mu\)\(y\)=\\sum\_\{x\\in h^\{\-1\}\(y\)\}\\mu\(x\)\.IfK:X→Δ⁡\(Y\)K:X\\to\\Delta\(Y\)is a Markov kernel andμ∈Δ⁡\(X\)\\mu\\in\\Delta\(X\), we writeμ​K∈Δ⁡\(Y\)\\mu K\\in\\Delta\(Y\)for the distribution

\(μ​K\)​\(y\)=∑x∈Xμ⁡\(x\)​K​\(y\|x\)\.\(\\mu K\)\(y\)=\\sum\_\{x\\in X\}\\mu\(x\)K\(y\|x\)\.
###### Lemma 4\.

Letμ,ν∈Δ⁡\(X\)\\mu,\\nu\\in\\Delta\(X\), leth:X→Yh:X\\to Yandr:Y→Zr:Y\\to Zbe maps, and letK,L:X→Δ⁡\(Y\)K,L:X\\to\\Delta\(Y\)be Markov kernels\. Then, the following properties hold:

1. 1\.Convexity\.Ifλi≥0\\lambda\_\{i\}\\geq 0,∑iλi=1\\sum\_\{i\}\\lambda\_\{i\}=1, andμi,νi∈Δ⁡\(X\)\\mu\_\{i\},\\nu\_\{i\}\\in\\Delta\(X\), then ‖∑iλi​μi−∑iλi​νi‖TV≤∑iλi​‖μi−νi‖TV\.\\left\\\|\\sum\_\{i\}\\lambda\_\{i\}\\mu\_\{i\}\-\\sum\_\{i\}\\lambda\_\{i\}\\nu\_\{i\}\\right\\\|\_\{\\mathrm\{TV\}\}\\leq\\sum\_\{i\}\\lambda\_\{i\}\\\|\\mu\_\{i\}\-\\nu\_\{i\}\\\|\_\{\\mathrm\{TV\}\}\.
2. 2\.Push\-forwards compose\. \(r∘h\)∗​μ=r∗​\(h∗​μ\)\.\(r\\circ h\)\_\{\*\}\\mu=r\_\{\*\}\(h\_\{\*\}\\mu\)\.
3. 3\.Push\-forward contraction\. ‖h∗​μ−h∗​ν‖TV≤‖μ−ν‖TV\.\\\|h\_\{\*\}\\mu\-h\_\{\*\}\\nu\\\|\_\{\\mathrm\{TV\}\}\\leq\\\|\\mu\-\\nu\\\|\_\{\\mathrm\{TV\}\}\.In particular, marginalization contracts total\-variation\.
4. 4\.Kernel contraction\. ‖μ​K−ν​K‖TV≤‖μ−ν‖TV\.\\\|\\mu K\-\\nu K\\\|\_\{\\mathrm\{TV\}\}\\leq\\\|\\mu\-\\nu\\\|\_\{\\mathrm\{TV\}\}\.
5. 5\.Kernel perturbation bound\.If supx∈X∥K\(⋅\|x\)−L\(⋅\|x\)∥TV≤ε,\\sup\_\{x\\in X\}\\\|K\(\\cdot\|x\)\-L\(\\cdot\|x\)\\\|\_\{\\mathrm\{TV\}\}\\leq\\varepsilon,then ‖μ​K−ν​L‖TV≤‖μ−ν‖TV\+ε\.\\\|\\mu K\-\\nu L\\\|\_\{\\mathrm\{TV\}\}\\leq\\\|\\mu\-\\nu\\\|\_\{\\mathrm\{TV\}\}\+\\varepsilon\.

###### Proof\.

Convexity follows directly from theℓ1\\ell^\{1\}expression for total variation and the triangle inequality:

‖∑iλi​μi−∑iλi​νi‖T​V\\displaystyle\\left\\\|\\sum\_\{i\}\\lambda\_\{i\}\\mu\_\{i\}\-\\sum\_\{i\}\\lambda\_\{i\}\\nu\_\{i\}\\right\\\|\_\{TV\}=12​∑x\|∑iλi​\(μi​\(x\)−νi​\(x\)\)\|\\displaystyle=\\frac\{1\}\{2\}\\sum\_\{x\}\\left\|\\sum\_\{i\}\\lambda\_\{i\}\(\\mu\_\{i\}\(x\)\-\\nu\_\{i\}\(x\)\)\\right\|≤∑iλi​12​∑x\|μi​\(x\)−νi​\(x\)\|\\displaystyle\\leq\\sum\_\{i\}\\lambda\_\{i\}\\frac\{1\}\{2\}\\sum\_\{x\}\|\\mu\_\{i\}\(x\)\-\\nu\_\{i\}\(x\)\|=∑iλi​‖μi−νi‖TV\.\\displaystyle=\\sum\_\{i\}\\lambda\_\{i\}\\\|\\mu\_\{i\}\-\\nu\_\{i\}\\\|\_\{\\mathrm\{TV\}\}\.The composition identity is immediate from the definition of push\-forward\. For push\-forward contraction, use the supremum characterization:

‖h∗​μ−h∗​ν‖TV=supB⊆Y\|μ⁡\(h−1​\(B\)\)−ν⁡\(h−1​\(B\)\)\|≤supA⊆X\|μ⁡\(A\)−ν⁡\(A\)\|=‖μ−ν‖TV\.\\\|h\_\{\*\}\\mu\-h\_\{\*\}\\nu\\\|\_\{\\mathrm\{TV\}\}=\\sup\_\{B\\subseteq Y\}\|\\mu\(h^\{\-1\}\(B\)\)\-\\nu\(h^\{\-1\}\(B\)\)\|\\leq\\sup\_\{A\\subseteq X\}\|\\mu\(A\)\-\\nu\(A\)\|=\\\|\\mu\-\\nu\\\|\_\{\\mathrm\{TV\}\}\.Kernel contraction follows from theℓ1\\ell^\{1\}expression:

‖μ​K−ν​K‖TV\\displaystyle\\\|\\mu K\-\\nu K\\\|\_\{\\mathrm\{TV\}\}=12​∑y\|∑x\(μ⁡\(x\)−ν⁡\(x\)\)​K​\(y\|x\)\|\\displaystyle=\\frac\{1\}\{2\}\\sum\_\{y\}\\left\|\\sum\_\{x\}\(\\mu\(x\)\-\\nu\(x\)\)K\(y\|x\)\\right\|≤12​∑x\|μ⁡\(x\)−ν⁡\(x\)\|​∑yK⁡\(y\|x\)=‖μ−ν‖TV\.\\displaystyle\\leq\\frac\{1\}\{2\}\\sum\_\{x\}\|\\mu\(x\)\-\\nu\(x\)\|\\sum\_\{y\}K\(y\|x\)=\\\|\\mu\-\\nu\\\|\_\{\\mathrm\{TV\}\}\.Finally,

‖μ​K−ν​L‖TV≤‖μ​K−ν​K‖TV\+‖ν​K−ν​L‖TV\.\\\|\\mu K\-\\nu L\\\|\_\{\\mathrm\{TV\}\}\\leq\\\|\\mu K\-\\nu K\\\|\_\{\\mathrm\{TV\}\}\+\\\|\\nu K\-\\nu L\\\|\_\{\\mathrm\{TV\}\}\.The first term is bounded by‖μ−ν‖TV\\\|\\mu\-\\nu\\\|\_\{\\mathrm\{TV\}\}by kernel contraction, and the second by

∑xν\(x\)∥K\(⋅\|x\)−L\(⋅\|x\)∥TV≤ε\\sum\_\{x\}\\nu\(x\)\\\|K\(\\cdot\|x\)\-L\(\\cdot\|x\)\\\|\_\{\\mathrm\{TV\}\}\\leq\\varepsilonby convexity\. This proves the perturbation bound\. ∎

### A\.3Deferred proofs

###### Proof of Lemma[1](https://arxiv.org/html/2608.20428#Thmlemma1)\.

We first check thatρG\\rho\_\{G\}is well\-defined\. Suppose that∑iαi​Mwi​ξ=0\\sum\_\{i\}\\alpha\_\{i\}M\_\{w\_\{i\}\}\\xi=0\. Then, for every suffixv∈Σ∗v\\in\\Sigma^\{\*\},

∑iαi​hℐ​\(wi\)​\(v\)=∑iαi​Fℐ​\(wi​v\)=∑iαi​λ​\(Mv​Mwi​ξ\)=λ⁡\(Mv​∑iαi​Mwi​ξ\)=0\.\\sum\_\{i\}\\alpha\_\{i\}h\_\{\\mathcal\{I\}\}\(w\_\{i\}\)\(v\)=\\sum\_\{i\}\\alpha\_\{i\}F\_\{\\mathcal\{I\}\}\(w\_\{i\}v\)=\\sum\_\{i\}\\alpha\_\{i\}\\lambda\(M\_\{v\}M\_\{w\_\{i\}\}\\xi\)=\\lambda\\\!\\left\(M\_\{v\}\\sum\_\{i\}\\alpha\_\{i\}M\_\{w\_\{i\}\}\\xi\\right\)=0\.Hence∑iαi​hℐ​\(wi\)=0\\sum\_\{i\}\\alpha\_\{i\}h\_\{\\mathcal\{I\}\}\(w\_\{i\}\)=0, so the assignment is well\-defined\. Linearity is immediate from the definition\. It is surjective becauseVℐV\_\{\\mathcal\{I\}\}is spanned by the rowshℐ​\(w\)h\_\{\\mathcal\{I\}\}\(w\)\. The identitiesρG​ξ=ξℐ\\rho\_\{G\}\\xi=\\xi\_\{\\mathcal\{I\}\},ρG​Mσ=Rσℐ​ρG\\rho\_\{G\}M\_\{\\sigma\}=R^\{\\mathcal\{I\}\}\_\{\\sigma\}\\rho\_\{G\}andλℐ​ρG=λ\\lambda\_\{\\mathcal\{I\}\}\\rho\_\{G\}=\\lambdafollow directly\. ∎

###### Proof of Proposition[1](https://arxiv.org/html/2608.20428#Thmproposition1)\.

Starting from\[ϵ\]ℐ\[\\epsilon\]\_\{\\mathcal\{I\}\}, Eq\. \([6](https://arxiv.org/html/2608.20428#S2.E6)\) reproduces the conditional output probabilities ofℐ\\mathcal\{I\}after every admissible history\. HenceE⁡\(ℐ\)E\(\\mathcal\{I\}\)implementsℐ\\mathcal\{I\}\. Its state after observinghhis\[h\]ℐ\[h\]\_\{\\mathcal\{I\}\}, so the residual future law is determined by the current state\. Thus, it is predictive\.

Now letTTbe a predictive transducer implementingℐ\\mathcal\{I\}\. For each reachables∈𝒮s\\in\\mathcal\{S\}, choose an admissible historyhhsuch thatqT​\(s∣h\)\>0q\_\{T\}\(s\\mid h\)\>0and define

ϕT​\(s\)=\[h\]ℐ\.\\displaystyle\\phi\_\{T\}\(s\)=\[h\]\_\{\\mathcal\{I\}\}\.\(17\)This is well defined: if bothhhandh′h^\{\\prime\}are compatible withss, predictivity givesℐh=ℐT,s=ℐh′\\mathcal\{I\}^\{h\}=\\mathcal\{I\}\_\{T,s\}=\\mathcal\{I\}^\{h^\{\\prime\}\}\. It is surjective because every admissible history has at least one state in the support of its posterior\. Also, every state with positive initial probability is compatible with the empty history, so\(ϕT\)∗​p=δ\[ϵ\]ℐ\(\\phi\_\{T\}\)\_\{\*\}p=\\delta\_\{\[\\epsilon\]\_\{\\mathcal\{I\}\}\}\.

Fixssand choose a compatible historyhh\. Predictivity givesPr\(o∣s,a\)T=Pr\(o∣a\)ℐh\\Pr\{\}\_\{T\}\(o\\mid s,a\)=\\Pr\{\}\_\{\\mathcal\{I\}^\{h\}\}\(o\\mid a\)\. Moreover, wheneverκ\(s′,o∣s,a\)\>0\\kappa\(s^\{\\prime\},o\\mid s,a\)\>0, the states′s^\{\\prime\}is compatible with the extended historyh⁡\(a,o\)h\(a,o\), and thereforeϕT​\(s′\)=\[h⁡\(a,o\)\]ℐ\\phi\_\{T\}\(s^\{\\prime\}\)=\[h\(a,o\)\]\_\{\\mathcal\{I\}\}\. Thus all the probability mass associated with outputoois pushed forward to the unique state prescribed by Eq\. \([6](https://arxiv.org/html/2608.20428#S2.E6)\), and

\(ϕT×id\)∗κ\(⋅,⋅∣s,a\)=κϵ\(⋅,⋅∣ϕT\(s\),a\)\.\(\\phi\_\{T\}\\times\\texttt\{id\}\)\_\{\*\}\\kappa\(\\cdot,\\cdot\\mid s,a\)=\\kappa\_\{\\epsilon\}\(\\cdot,\\cdot\\mid\\phi\_\{T\}\(s\),a\)\.HenceϕT\\phi\_\{T\}is a reduction\. ∎

###### Proof of Theorem[1](https://arxiv.org/html/2608.20428#Thmtheorem1)\.

Letϕ:𝒮1→𝒮2\\phi:\\mathcal\{S\}\_\{1\}\\to\\mathcal\{S\}\_\{2\}be the map of theε\\varepsilon\-reduction\. Since a reduction preserves the input and output alphabets, let’s write the common alphabets of both transducers as𝒜\\mathcal\{A\}and𝒪\\mathcal\{O\}\. Fix a sectionr:𝒮2→𝒮1r:\\mathcal\{S\}\_\{2\}\\to\\mathcal\{S\}\_\{1\}ofϕ\\phi, so thatϕ⁡\(r⁡\(u\)\)=u\\phi\(r\(u\)\)=ufor everyu∈𝒮2u\\in\\mathcal\{S\}\_\{2\}\.

For𝐚∈𝒜n\\mathbf\{a\}\\in\\mathcal\{A\}^\{n\}, define two probability distributionsP𝐚P\_\{\\mathbf\{a\}\}andQ𝐚Q\_\{\\mathbf\{a\}\}on𝒪n×𝒮2\\mathcal\{O\}^\{n\}\\times\\mathcal\{S\}\_\{2\}by

P𝐚​\(𝐨,u\)\\displaystyle P\_\{\\mathbf\{a\}\}\(\\mathbf\{o\},u\)=∑s∈ϕ−1​\(u\)Pr\(O1:n=𝐨,Sn1=s∣A1:n=𝐚\)T1,\\displaystyle=\\sum\_\{s\\in\\phi^\{\-1\}\(u\)\}\\Pr\{\}\_\{T\_\{1\}\}\\\!\\left\(O\_\{1:n\}=\\mathbf\{o\},\\,S\_\{n\}^\{1\}=s\\mid A\_\{1:n\}=\\mathbf\{a\}\\right\),Q𝐚​\(𝐨,u\)\\displaystyle Q\_\{\\mathbf\{a\}\}\(\\mathbf\{o\},u\)=Pr\(O1:n=𝐨,Sn2=u∣A1:n=𝐚\)T2,\\displaystyle=\\Pr\{\}\_\{T\_\{2\}\}\\\!\\left\(O\_\{1:n\}=\\mathbf\{o\},\\,S\_\{n\}^\{2\}=u\\mid A\_\{1:n\}=\\mathbf\{a\}\\right\),whereSniS\_\{n\}^\{i\}is a random variable denoting the state of the transducerTiT\_\{i\}at stepnn,O1:nO\_\{1:n\}denotes the firstnnobserved outputs andA1:nA\_\{1:n\}the firstnninputs\. Thus,P𝐚P\_\{\\mathbf\{a\}\}is the joint law of the output prefix and the coarse\-grained stateϕ⁡\(Sn1\)\\phi\(S\_\{n\}^\{1\}\)underT1T\_\{1\}assuming inputsa, whereasQ𝐚Q\_\{\\mathbf\{a\}\}is the corresponding joint law underT2T\_\{2\}\. We prove by induction onnnthat, for every𝐚∈𝒜n\\mathbf\{a\}\\in\\mathcal\{A\}^\{n\},

‖P𝐚−Q𝐚‖TV≤\(n\+1\)​ε\.\\\|P\_\{\\mathbf\{a\}\}\-Q\_\{\\mathbf\{a\}\}\\\|\_\{\\mathrm\{TV\}\}\\leq\(n\+1\)\\varepsilon\.\(18\)This is intuitive: initially the two distribution differ by at mostε\\varepsilonbecause of the error in the initial distribution, and after each step this error increases by at mostε\\varepsilonbecause the one\-step transitions betweenT1T\_\{1\}andT2T\_\{2\}differ locally \(i\.e\. when comparings∈𝒮1s\\in\\mathcal\{S\}\_\{1\}withϕ⁡\(s\)\\phi\(s\)\) by at mostε\\varepsilon

Forn=0n=0, the output prefix is empty and

Pϵ​\(ϵ,u\)=\(ϕ∗​p1\)​\(u\),Qϵ​\(ϵ,u\)=p2​\(u\)\.P\_\{\\epsilon\}\(\\epsilon,u\)=\(\\phi\_\{\*\}p\_\{1\}\)\(u\),\\qquad Q\_\{\\epsilon\}\(\\epsilon,u\)=p\_\{2\}\(u\)\.Consequently, the initial\-distribution condition in the definition of anε\\varepsilon\-reduction gives

‖Pϵ−Qϵ‖TV=‖ϕ∗​p1−p2‖TV≤ε\.\\\|P\_\{\\epsilon\}\-Q\_\{\\epsilon\}\\\|\_\{\\mathrm\{TV\}\}=\\\|\\phi\_\{\*\}p\_\{1\}\-p\_\{2\}\\\|\_\{\\mathrm\{TV\}\}\\leq\\varepsilon\.
Now fix𝐚∈𝒜n\\mathbf\{a\}\\in\\mathcal\{A\}^\{n\}, a next actionb∈𝒜b\\in\\mathcal\{A\}, and\(𝐨,u\)∈𝒪n×𝒮2\(\\mathbf\{o\},u\)\\in\\mathcal\{O\}^\{n\}\\times\\mathcal\{S\}\_\{2\}\. Define a probability distributionλ𝐚,𝐨,u\\lambda\_\{\\mathbf\{a\},\\mathbf\{o\},u\}onϕ−1​\(u\)\\phi^\{\-1\}\(u\)as follows\. IfP𝐚​\(𝐨,u\)\>0P\_\{\\mathbf\{a\}\}\(\\mathbf\{o\},u\)\>0, let

λ𝐚,𝐨,u\(s\)=PrT1\(O1:n=𝐨,Sn1=s∣𝒜1:n=𝐚\)P𝐚​\(𝐨,u\)\.\\lambda\_\{\\mathbf\{a\},\\mathbf\{o\},u\}\(s\)=\\frac\{\\Pr\{\}\_\{T\_\{1\}\}\\\!\\left\(O\_\{1:n\}=\\mathbf\{o\},\\,S\_\{n\}^\{1\}=s\\mid\\mathcal\{A\}\_\{1:n\}=\\mathbf\{a\}\\right\)\}\{P\_\{\\mathbf\{a\}\}\(\\mathbf\{o\},u\)\}\.IfP𝐚​\(𝐨,u\)=0P\_\{\\mathbf\{a\}\}\(\\mathbf\{o\},u\)=0, set arbitrarilyλ𝐚,𝐨,u=δr⁡\(u\)\\lambda\_\{\\mathbf\{a\},\\mathbf\{o\},u\}=\\delta\_\{r\(u\)\}\. Then,λa,o,u​\(s\)\\lambda\_\{\\textbf\{a\},\\textbf\{o\},u\}\(s\)represents the probability for the state of transducerT1T\_\{1\}to bessat stepnnconditioned onT1T\_\{1\}being at a state inϕ−1​\(u\)\\phi^\{\-1\}\(u\)\.

For𝐨∈𝒪n\\mathbf\{o\}\\in\\mathcal\{O\}^\{n\}, let

j𝐨:𝒮2×𝒪⟶𝒪n\+1×𝒮2,j𝐨​\(u′,o\)=\(𝐨​o,u′\),j\_\{\\mathbf\{o\}\}:\\mathcal\{S\}\_\{2\}\\times\\mathcal\{O\}\\longrightarrow\\mathcal\{O\}^\{n\+1\}\\times\\mathcal\{S\}\_\{2\},\\qquad j\_\{\\mathbf\{o\}\}\(u^\{\\prime\},o\)=\(\\mathbf\{o\}o,u^\{\\prime\}\),where𝐨​o\\mathbf\{o\}odenotes concatenation\. Consider the Markov kernelsK^1,𝐚,b\\widehat\{K\}\_\{1,\\mathbf\{a\},b\}andK^2,b\\widehat\{K\}\_\{2,b\}from𝒪n×𝒮2\\mathcal\{O\}^\{n\}\\times\\mathcal\{S\}\_\{2\}to𝒪n\+1×𝒮2\\mathcal\{O\}^\{n\+1\}\\times\\mathcal\{S\}\_\{2\}given by

K^1,𝐚,b​\(⋅∣𝐨,u\)\\displaystyle\\widehat\{K\}\_\{1,\\mathbf\{a\},b\}\\bigl\(\\mathord\{\\cdot\}\\mid\\mathbf\{o\},u\\bigr\)=\(j𝐨\)∗\[∑s∈ϕ−1​\(u\)λ𝐚,𝐨,u\(s\)\(ϕ×id𝒪\)∗κ1\(⋅,⋅∣s,b\)\],\\displaystyle=\(j\_\{\\mathbf\{o\}\}\)\_\{\*\}\\left\[\\sum\_\{s\\in\\phi^\{\-1\}\(u\)\}\\lambda\_\{\\mathbf\{a\},\\mathbf\{o\},u\}\(s\)\\,\(\\phi\\times\\operatorname\{id\}\_\{\\mathcal\{O\}\}\)\_\{\*\}\\kappa\_\{1\}\(\\mathord\{\\cdot\},\\mathord\{\\cdot\}\\mid s,b\)\\right\],K^2,b​\(⋅∣𝐨,u\)\\displaystyle\\widehat\{K\}\_\{2,b\}\\bigl\(\\mathord\{\\cdot\}\\mid\\mathbf\{o\},u\\bigr\)=\(j𝐨\)∗κ2\(⋅,⋅∣u,b\)\.\\displaystyle=\(j\_\{\\mathbf\{o\}\}\)\_\{\*\}\\kappa\_\{2\}\(\\mathord\{\\cdot\},\\mathord\{\\cdot\}\\mid u,b\)\.The first kernel performs one step ofT1T\_\{1\}, coarse\-grains the next state throughϕ\\phi, and retains the already observed output prefix\. The second kernel performs the corresponding operation forT2T\_\{2\}\.

For every\(𝐨,u\)\(\\mathbf\{o\},u\), push\-forward contraction, convexity of total variation, and the one\-step condition of theε\\varepsilon\-reduction give

‖K^1,𝐚,b​\(⋅∣𝐨,u\)−K^2,b​\(⋅∣𝐨,u\)‖TV\\displaystyle\\left\\\|\\widehat\{K\}\_\{1,\\mathbf\{a\},b\}\(\\mathord\{\\cdot\}\\mid\\mathbf\{o\},u\)\-\\widehat\{K\}\_\{2,b\}\(\\mathord\{\\cdot\}\\mid\\mathbf\{o\},u\)\\right\\\|\_\{\\mathrm\{TV\}\}≤‖∑s∈ϕ−1​\(u\)λ𝐚,𝐨,u\(s\)\(ϕ×id𝒪\)∗κ1\(⋅,⋅∣s,b\)−κ2\(⋅,⋅∣u,b\)‖TV\\displaystyle\\quad\\leq\\left\\\|\\sum\_\{s\\in\\phi^\{\-1\}\(u\)\}\\lambda\_\{\\mathbf\{a\},\\mathbf\{o\},u\}\(s\)\(\\phi\\times\\operatorname\{id\}\_\{\\mathcal\{O\}\}\)\_\{\*\}\\kappa\_\{1\}\(\\mathord\{\\cdot\},\\mathord\{\\cdot\}\\mid s,b\)\-\\kappa\_\{2\}\(\\mathord\{\\cdot\},\\mathord\{\\cdot\}\\mid u,b\)\\right\\\|\_\{\\mathrm\{TV\}\}≤∑s∈ϕ−1​\(u\)λ𝐚,𝐨,u\(s\)‖\(ϕ×id𝒪\)∗κ1\(⋅,⋅∣s,b\)−κ2\(⋅,⋅∣ϕ\(s\),b\)‖TV\\displaystyle\\quad\\leq\\sum\_\{s\\in\\phi^\{\-1\}\(u\)\}\\lambda\_\{\\mathbf\{a\},\\mathbf\{o\},u\}\(s\)\\left\\\|\(\\phi\\times\\operatorname\{id\}\_\{\\mathcal\{O\}\}\)\_\{\*\}\\kappa\_\{1\}\(\\mathord\{\\cdot\},\\mathord\{\\cdot\}\\mid s,b\)\-\\kappa\_\{2\}\(\\mathord\{\\cdot\},\\mathord\{\\cdot\}\\mid\\phi\(s\),b\)\\right\\\|\_\{\\mathrm\{TV\}\}≤ε\.\\displaystyle\\quad\\leq\\varepsilon\.\(19\)Moreover, by construction of the conditional distributionsλ𝐚,𝐨,u\\lambda\_\{\\mathbf\{a\},\\mathbf\{o\},u\}it follows that

P𝐚​b=P𝐚​K^1,𝐚,b,Q𝐚​b=Q𝐚​K^2,b\.P\_\{\\mathbf\{a\}b\}=P\_\{\\mathbf\{a\}\}\\widehat\{K\}\_\{1,\\mathbf\{a\},b\},\\qquad Q\_\{\\mathbf\{a\}b\}=Q\_\{\\mathbf\{a\}\}\\widehat\{K\}\_\{2,b\}\.Thus, applying the kernel perturbation bound from Lemma[4](https://arxiv.org/html/2608.20428#Thmlemma4)and then the induction hypothesis yields

‖P𝐚​b−Q𝐚​b‖TV\\displaystyle\\\|P\_\{\\mathbf\{a\}b\}\-Q\_\{\\mathbf\{a\}b\}\\\|\_\{\\mathrm\{TV\}\}≤‖P𝐚−Q𝐚‖TV\+sup\(𝐨,u\)‖K^1,𝐚,b​\(⋅∣𝐨,u\)−K^2,b​\(⋅∣𝐨,u\)‖TV\\displaystyle\\leq\\\|P\_\{\\mathbf\{a\}\}\-Q\_\{\\mathbf\{a\}\}\\\|\_\{\\mathrm\{TV\}\}\+\\sup\_\{\(\\mathbf\{o\},u\)\}\\left\\\|\\widehat\{K\}\_\{1,\\mathbf\{a\},b\}\(\\mathord\{\\cdot\}\\mid\\mathbf\{o\},u\)\-\\widehat\{K\}\_\{2,b\}\(\\mathord\{\\cdot\}\\mid\\mathbf\{o\},u\)\\right\\\|\_\{\\mathrm\{TV\}\}≤\(n\+1\)​ε\+ε=\(n\+2\)​ε\.\\displaystyle\\leq\(n\+1\)\\varepsilon\+\\varepsilon=\(n\+2\)\\varepsilon\.This completes the induction\.

The output distributionDℐT1​\(𝐚\)D\_\{\\mathcal\{I\}\_\{T\_\{1\}\}\}\(\\mathbf\{a\}\)is the marginal ofP𝐚P\_\{\\mathbf\{a\}\}on𝒪n\\mathcal\{O\}^\{n\}, andDℐT2​\(𝐚\)D\_\{\\mathcal\{I\}\_\{T\_\{2\}\}\}\(\\mathbf\{a\}\)is the corresponding marginal ofQ𝐚Q\_\{\\mathbf\{a\}\}\. Since marginalization contracts total variation,

‖DℐT1​\(𝐚\)−DℐT2​\(𝐚\)‖TV≤\(n\+1\)​ε\\left\\\|D\_\{\\mathcal\{I\}\_\{T\_\{1\}\}\}\(\\mathbf\{a\}\)\-D\_\{\\mathcal\{I\}\_\{T\_\{2\}\}\}\(\\mathbf\{a\}\)\\right\\\|\_\{\\mathrm\{TV\}\}\\leq\(n\+1\)\\varepsilonfor every𝐚∈𝒜n\\mathbf\{a\}\\in\\mathcal\{A\}^\{n\}\. Therefore

dγ​\(ℐT1,ℐT2\)\\displaystyle d\_\{\\gamma\}\(\\mathcal\{I\}\_\{T\_\{1\}\},\\mathcal\{I\}\_\{T\_\{2\}\}\)=∑n=0∞γn​sup𝐚∈𝒜n‖DℐT1​\(𝐚\)−DℐT2​\(𝐚\)‖TV\\displaystyle=\\sum\_\{n=0\}^\{\\infty\}\\gamma^\{n\}\\sup\_\{\\mathbf\{a\}\\in\\mathcal\{A\}^\{n\}\}\\left\\\|D\_\{\\mathcal\{I\}\_\{T\_\{1\}\}\}\(\\mathbf\{a\}\)\-D\_\{\\mathcal\{I\}\_\{T\_\{2\}\}\}\(\\mathbf\{a\}\)\\right\\\|\_\{\\mathrm\{TV\}\}≤ε​∑n=0∞\(n\+1\)​γn=ε\(1−γ\)2\.\\displaystyle\\leq\\varepsilon\\sum\_\{n=0\}^\{\\infty\}\(n\+1\)\\gamma^\{n\}=\\frac\{\\varepsilon\}\{\(1\-\\gamma\)^\{2\}\}\.∎

###### Proof of Proposition[2](https://arxiv.org/html/2608.20428#Thmproposition2)\.

Let⟨ϕ1,f1,g1⟩\\langle\\phi\_\{1\},f\_\{1\},g\_\{1\}\\ranglebe theε1\\varepsilon\_\{1\}\-homomorphism fromT1T\_\{1\}toT2T\_\{2\}and⟨ϕ2,f2,g2⟩\\langle\\phi\_\{2\},f\_\{2\},g\_\{2\}\\rangletheε2\\varepsilon\_\{2\}\-homomorphism fromT2T\_\{2\}toT3T\_\{3\}\. Define the homomorphism⟨ϕ=ϕ2∘ϕ1,f=f2∘f1,g=g2∘g1⟩\\langle\\phi=\\phi\_\{2\}\\circ\\phi\_\{1\},f=f\_\{2\}\\circ f\_\{1\},g=g\_\{2\}\\circ g\_\{1\}\\ranglefromT1T\_\{1\}toT3T\_\{3\}\. We will prove that this is a\(ε1\+ε2\)\(\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}\)\-homomorphism\.

Fixs∈𝒮1s\\in\\mathcal\{S\}\_\{1\}anda∈𝒜1a\\in\\mathcal\{A\}\_\{1\}\. By the composition rule for push\-forwards, the triangle inequality, and contraction of total variation under push\-forwards,

‖\(ϕ×g\)∗κ1\(⋅,⋅∣s,a\)−κ3\(⋅,⋅∣ϕ\(s\),f\(a\)\)‖TV\\displaystyle\\left\\\|\(\\phi\\times g\)\_\{\*\}\\kappa\_\{1\}\(\\mathord\{\\cdot\},\\mathord\{\\cdot\}\\mid s,a\)\-\\kappa\_\{3\}\(\\mathord\{\\cdot\},\\mathord\{\\cdot\}\\mid\\phi\(s\),f\(a\)\)\\right\\\|\_\{\\mathrm\{TV\}\}≤‖\(ϕ2×g2\)∗\(\(ϕ1×g1\)∗κ1\(⋅,⋅∣s,a\)−κ2\(⋅,⋅∣ϕ1\(s\),f1\(a\)\)\)‖TV\\displaystyle\\quad\\leq\\left\\\|\(\\phi\_\{2\}\\times g\_\{2\}\)\_\{\*\}\\left\(\(\\phi\_\{1\}\\times g\_\{1\}\)\_\{\*\}\\kappa\_\{1\}\(\\mathord\{\\cdot\},\\mathord\{\\cdot\}\\mid s,a\)\-\\kappa\_\{2\}\(\\mathord\{\\cdot\},\\mathord\{\\cdot\}\\mid\\phi\_\{1\}\(s\),f\_\{1\}\(a\)\)\\right\)\\right\\\|\_\{\\mathrm\{TV\}\}\+‖\(ϕ2×g2\)∗κ2\(⋅,⋅∣ϕ1\(s\),f1\(a\)\)−κ3\(⋅,⋅∣ϕ2\(ϕ1\(s\)\),f2\(f1\(a\)\)\)‖TV\\displaystyle\\qquad\\quad\+\\left\\\|\(\\phi\_\{2\}\\times g\_\{2\}\)\_\{\*\}\\kappa\_\{2\}\(\\mathord\{\\cdot\},\\mathord\{\\cdot\}\\mid\\phi\_\{1\}\(s\),f\_\{1\}\(a\)\)\-\\kappa\_\{3\}\(\\mathord\{\\cdot\},\\mathord\{\\cdot\}\\mid\\phi\_\{2\}\(\\phi\_\{1\}\(s\)\),f\_\{2\}\(f\_\{1\}\(a\)\)\)\\right\\\|\_\{\\mathrm\{TV\}\}≤ε1\+ε2\.\\displaystyle\\quad\\leq\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}\.The initial distributions satisfy

‖ϕ∗​p1−p3‖TV\\displaystyle\\\|\\phi\_\{\*\}p\_\{1\}\-p\_\{3\}\\\|\_\{\\mathrm\{TV\}\}≤‖\(ϕ2\)∗​\(\(ϕ1\)∗​p1\)−\(ϕ2\)∗​p2‖TV\+‖\(ϕ2\)∗​p2−p3‖TV\\displaystyle\\leq\\\|\(\\phi\_\{2\}\)\_\{\*\}\(\(\\phi\_\{1\}\)\_\{\*\}p\_\{1\}\)\-\(\\phi\_\{2\}\)\_\{\*\}p\_\{2\}\\\|\_\{\\mathrm\{TV\}\}\+\\\|\(\\phi\_\{2\}\)\_\{\*\}p\_\{2\}\-p\_\{3\}\\\|\_\{\\mathrm\{TV\}\}≤‖\(ϕ1\)∗​p1−p2‖TV\+‖\(ϕ2\)∗​p2−p3‖TV\\displaystyle\\leq\\\|\(\\phi\_\{1\}\)\_\{\*\}p\_\{1\}\-p\_\{2\}\\\|\_\{\\mathrm\{TV\}\}\+\\\|\(\\phi\_\{2\}\)\_\{\*\}p\_\{2\}\-p\_\{3\}\\\|\_\{\\mathrm\{TV\}\}≤ε1\+ε2\.\\displaystyle\\leq\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}\.Thus⟨ϕ2∘ϕ1,f2∘f1,g2∘g1⟩\\langle\\phi\_\{2\}\\circ\\phi\_\{1\},f\_\{2\}\\circ f\_\{1\},g\_\{2\}\\circ g\_\{1\}\\rangleis an\(ε1\+ε2\)\(\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}\)\-homomorphism\.

If both original maps are reductions, then the action and output maps are identities andϕ1,ϕ2\\phi\_\{1\},\\phi\_\{2\}are surjective\. Henceϕ2∘ϕ1\\phi\_\{2\}\\circ\\phi\_\{1\}is surjective, so the composition is an\(ε1\+ε2\)\(\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}\)\-reduction\. ∎

###### Proof of Proposition[3](https://arxiv.org/html/2608.20428#Thmproposition3)\.

Fori∈\{1,2\}i\\in\\\{1,2\\\}, letVi=ℝSiV\_\{i\}=\\mathbb\{R\}^\{S\_\{i\}\}with theℓ1\\ell\_\{1\}norm, letξi=pi\\xi\_\{i\}=p\_\{i\}, and define

λi\(x\)=∑s∈Sixs,Ma,oies=∑t∈Siκi\(t,o∣s,a\)et\.\\lambda\_\{i\}\(x\)=\\sum\_\{s\\in S\_\{i\}\}x\_\{s\},\\qquad M^\{i\}\_\{a,o\}e\_\{s\}=\\sum\_\{t\\in S\_\{i\}\}\\kappa\_\{i\}\(t,o\\mid s,a\)e\_\{t\}\.EachMa,oiM^\{i\}\_\{a,o\}is nonnegative and column\-substochastic, and hence is anℓ1\\ell\_\{1\}contraction\. Moreover,‖ξi‖1=‖λi‖Vi∗=1\\\|\\xi\_\{i\}\\\|\_\{1\}=\\\|\\lambda\_\{i\}\\\|\_\{V\_\{i\}^\{\*\}\}=1, so these linearizations are contractive\.

DefineLϕ​es=eϕ⁡\(s\)L\_\{\\phi\}e\_\{s\}=e\_\{\\phi\(s\)\}and extend linearly\. Sinceϕ\\phiis surjective, so isLϕL\_\{\\phi\}, and‖Lϕ‖1→1=1\\\|L\_\{\\phi\}\\\|\_\{1\\to 1\}=1\. The initial\-state condition of the ordinary reduction gives

‖Lϕ​ξ1−ξ2‖1=2​‖ϕ∗​p1−p2‖TV≤2​ε\.\\\|L\_\{\\phi\}\\xi\_\{1\}\-\\xi\_\{2\}\\\|\_\{1\}=2\\\|\\phi\_\{\*\}p\_\{1\}\-p\_\{2\}\\\|\_\{\\mathrm\{TV\}\}\\leq 2\\varepsilon\.For a fixeds∈𝒮1s\\in\\mathcal\{S\}\_\{1\}anda∈𝒜a\\in\\mathcal\{A\}, the vector\(Lϕ​Ma,o1−Ma,o2​Lϕ\)​es\(L\_\{\\phi\}M^\{1\}\_\{a,o\}\-M^\{2\}\_\{a,o\}L\_\{\\phi\}\)e\_\{s\}is theoo\-component of the difference between the two joint laws on𝒮2×𝒪\\mathcal\{S\}\_\{2\}\\times\\mathcal\{O\}appearing in the definition of an ordinaryε\\varepsilon\-reduction\. Namely,

\(Lϕ​Ma,o1−Ma,o2​Lϕ\)​es\\displaystyle\(L\_\{\\phi\}M^\{1\}\_\{a,o\}\-M^\{2\}\_\{a,o\}L\_\{\\phi\}\)e\_\{s\}=∑t1∈𝒮1κ1\(t1,o\|s,a\)eϕ⁡\(t1\)−∑t2∈𝒮2κ2\(t2,o\|ϕ\(s\),a\)et2\\displaystyle=\\sum\_\{t\_\{1\}\\in\\mathcal\{S\}\_\{1\}\}\\kappa\_\{1\}\(t\_\{1\},o\|s,a\)e\_\{\\phi\(t\_\{1\}\)\}\-\\sum\_\{t\_\{2\}\\in\\mathcal\{S\}\_\{2\}\}\\kappa\_\{2\}\(t\_\{2\},o\|\\phi\(s\),a\)e\_\{t\_\{2\}\}=∑t2∈𝒮2\[∑t1∈ϕ−1​\(t2\)κ1\(t1,o\|s,a\)−κ2\(t2,o\|ϕ\(s\),a\)\]et2\\displaystyle=\\sum\_\{t\_\{2\}\\in\\mathcal\{S\}\_\{2\}\}\\left\[\\sum\_\{t\_\{1\}\\in\\phi^\{\-1\}\(t\_\{2\}\)\}\\kappa\_\{1\}\(t\_\{1\},o\|s,a\)\-\\kappa\_\{2\}\(t\_\{2\},o\|\\phi\(s\),a\)\\right\]e\_\{t\_\{2\}\}Consequently,

‖\(Lϕ​Ma,o1−Ma,o2​Lϕ\)​es‖1≤2​ε\.\\\|\(L\_\{\\phi\}M^\{1\}\_\{a,o\}\-M^\{2\}\_\{a,o\}L\_\{\\phi\}\)e\_\{s\}\\\|\_\{1\}\\leq 2\\varepsilon\.Taking the maximum over the columns gives

‖Lϕ​Ma,o1−Ma,o2​Lϕ‖1→1≤2​ε\.\\\|L\_\{\\phi\}M^\{1\}\_\{a,o\}\-M^\{2\}\_\{a,o\}L\_\{\\phi\}\\\|\_\{1\\to 1\}\\leq 2\\varepsilon\.Finally,λ2​Lϕ=λ1\\lambda\_\{2\}L\_\{\\phi\}=\\lambda\_\{1\}\. ThusLϕL\_\{\\phi\}is a2​ε2\\varepsilon\-linear reduction\. The factor22shows up because of the normalization12\\frac\{1\}\{2\}in total variation\. ∎

###### Proof of Proposition[4](https://arxiv.org/html/2608.20428#Thmproposition4)\.

WriteGi=\(Vi,ξi,λi,\{Ma,oi\}a,o\)G\_\{i\}=\(V\_\{i\},\\xi\_\{i\},\\lambda\_\{i\},\\\{M^\{i\}\_\{a,o\}\\\}\_\{a,o\}\)\. SinceLLandKKare bounded and surjective, so isK​LKL\. For the initial vectors,

‖K​L​ξ0−ξ2‖≤‖K‖​‖L​ξ0−ξ1‖\+‖K​ξ1−ξ2‖≤‖K‖​ε1\+ε2\.\\begin\{split\}\\\|KL\\xi\_\{0\}\-\\xi\_\{2\}\\\|&\\leq\\\|K\\\|\\,\\\|L\\xi\_\{0\}\-\\xi\_\{1\}\\\|\+\\\|K\\xi\_\{1\}\-\\xi\_\{2\}\\\|\\\\ &\\leq\\\|K\\\|\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}\.\\end\{split\}For each symbol\(a,o\)\(a,o\),

K​L​Ma,o0−Ma,o2​K​L=K⁡\(L​Ma,o0−Ma,o1​L\)\+\(K​Ma,o1−Ma,o2​K\)​L,\\begin\{split\}KLM^\{0\}\_\{a,o\}\-M^\{2\}\_\{a,o\}KL=\{\}&K\(LM^\{0\}\_\{a,o\}\-M^\{1\}\_\{a,o\}L\)\\\\ &\+\(KM^\{1\}\_\{a,o\}\-M^\{2\}\_\{a,o\}K\)L,\\end\{split\}and hence the operator norm of this difference is at most‖K‖​ε1\+‖L‖​ε2\\\|K\\\|\\varepsilon\_\{1\}\+\\\|L\\\|\\varepsilon\_\{2\}\. Finally,

λ2​K​L−λ0=\(λ2​K−λ1\)​L\+\(λ1​L−λ0\),\\lambda\_\{2\}KL\-\\lambda\_\{0\}=\(\\lambda\_\{2\}K\-\\lambda\_\{1\}\)L\+\(\\lambda\_\{1\}L\-\\lambda\_\{0\}\),whose dual norm is at most‖L‖​ε2\+ε1\\\|L\\\|\\varepsilon\_\{2\}\+\\varepsilon\_\{1\}\. All three quantities are bounded byc⁡\(K\)​ε1\+c⁡\(L\)​ε2c\(K\)\\varepsilon\_\{1\}\+c\(L\)\\varepsilon\_\{2\}\. ∎

###### Proof of Theorem[2](https://arxiv.org/html/2608.20428#Thmtheorem2)\.

LetL:V→WL:V\\to Wbe theε\\varepsilon\-linear reduction\. Fora=a1⋯an∈𝒜na=a\_\{1\}\\cdots a\_\{n\}\\in\\mathcal\{A\}^\{n\}ando=o1⋯on∈𝒪no=o\_\{1\}\\cdots o\_\{n\}\\in\\mathcal\{O\}^\{n\}, writeMa,o=Man,on⋯Ma1,o1M\_\{a,o\}=M\_\{a\_\{n\},o\_\{n\}\}\\cdots M\_\{a\_\{1\},o\_\{1\}\}andNa,o=Nan,on⋯Na1,o1N\_\{a,o\}=N\_\{a\_\{n\},o\_\{n\}\}\\cdots N\_\{a\_\{1\},o\_\{1\}\}\. Symbol\-wise contractivity implies‖Ma,o​ξ‖≤1\\\|M\_\{a,o\}\\xi\\\|\\leq 1\. We claim that

‖L​Ma,o​ξ−Na,o​ξ′‖≤\(n\+1\)​ε\.\\\|LM\_\{a,o\}\\xi\-N\_\{a,o\}\\xi^\{\\prime\}\\\|\\leq\(n\+1\)\\varepsilon\.\(20\)Forn=0n=0, this is the initial\-vector condition\. If the claim holds at lengthnnandσ=\(an\+1,on\+1\)\\sigma=\(a\_\{n\+1\},o\_\{n\+1\}\), then

‖L​Mσ​Ma,o​ξ−Nσ​Na,o​ξ′‖≤‖\(L​Mσ−Nσ​L\)​Ma,o​ξ‖\+‖Nσ​\(L​Ma,o​ξ−Na,o​ξ′\)‖≤ε\+\(n\+1\)​ε\.\\begin\{split\}&\\\|LM\_\{\\sigma\}M\_\{a,o\}\\xi\-N\_\{\\sigma\}N\_\{a,o\}\\xi^\{\\prime\}\\\|\\\\ &\\quad\\leq\\\|\(LM\_\{\\sigma\}\-N\_\{\\sigma\}L\)M\_\{a,o\}\\xi\\\|\+\\\|N\_\{\\sigma\}\(LM\_\{a,o\}\\xi\-N\_\{a,o\}\\xi^\{\\prime\}\)\\\|\\\\ &\\quad\\leq\\varepsilon\+\(n\+1\)\\varepsilon\.\\end\{split\}This proves \([20](https://arxiv.org/html/2608.20428#A1.E20)\) by induction\.

For every output wordo∈𝒪no\\in\\mathcal\{O\}^\{n\},

\|λ⁡\(Ma,o​ξ\)−λ′​\(Na,o​ξ′\)\|≤\|\(λ−λ′​L\)​\(Ma,o​ξ\)\|\+\|λ′​\(L​Ma,o​ξ−Na,o​ξ′\)\|≤\(n\+2\)​ε\.\\begin\{split\}&\|\\lambda\(M\_\{a,o\}\\xi\)\-\\lambda^\{\\prime\}\(N\_\{a,o\}\\xi^\{\\prime\}\)\|\\\\ &\\quad\\leq\|\(\\lambda\-\\lambda^\{\\prime\}L\)\(M\_\{a,o\}\\xi\)\|\+\|\\lambda^\{\\prime\}\(LM\_\{a,o\}\\xi\-N\_\{a,o\}\\xi^\{\\prime\}\)\|\\\\ &\\quad\\leq\(n\+2\)\\varepsilon\.\\end\{split\}Summing over the\|𝒪\|n\|\\mathcal\{O\}\|^\{n\}output words and dividing by two gives the second quantity in the minimum in \([12](https://arxiv.org/html/2608.20428#S3.E12)\), the bound by one holds because both sides are probability distributions\.

Equation \([13](https://arxiv.org/html/2608.20428#S3.E13)\) follows by summing the finite horizon bounds\. For each fixednn, the remaining summand tends to zero withε\\varepsilonand is bounded byγn\\gamma^\{n\}\. Since∑nγn<∞\\sum\_\{n\}\\gamma^\{n\}<\\infty, we conclude that the right hand side converges to 0\. ∎

###### Proof of Proposition[5](https://arxiv.org/html/2608.20428#Thmproposition5)\.

Fix𝒜=\{ℓ,g\}\\mathcal\{A\}=\\\{\\ell,g\\\}and𝒪=\{$,0,1\}\\mathcal\{O\}=\\\{\\$,0,1\\\}\. Defineℐ\\mathcal\{I\}as follows: in the first step, the output is the symbol$\\$with probability 1\. Then, a fair coin is thrown, and the output is always00or11for all the next steps, depending on this coin\. Thus, for everya1⋯ak∈𝒜ka\_\{1\}\\cdots a\_\{k\}\\in\\mathcal\{A\}^\{k\}withk≥2k\\geq 2, we have

Pr\($∣a1\)ℐ=1\\Pr\{\}\_\{\\mathcal\{I\}\}\(\\$\\mid a\_\{1\}\)=1and

Pr\($0k−1∣a1⋯ak\)ℐ=Pr\($1k−1∣a1⋯ak\)ℐ=12,\\Pr\{\}\_\{\\mathcal\{I\}\}\(\\$0^\{k\-1\}\\mid a\_\{1\}\\cdots a\_\{k\}\)=\\Pr\{\}\_\{\\mathcal\{I\}\}\(\\$1^\{k\-1\}\\mid a\_\{1\}\\cdots a\_\{k\}\)=\\frac\{1\}\{2\},Note that the interface isindependentof the actions taken\.

Consider the three\-state transducerWWwith statesSW=\{r,t0,t1\}S\_\{W\}=\\\{r,t\_\{0\},t\_\{1\}\\\}and initial distribution centred atrrand with kernel

κW\(t0,$∣r,a\)=12,κW\(t1,$∣r,a\)=12,\\kappa\_\{W\}\(t\_\{0\},\\$\\mid r,a\)=\\frac\{1\}\{2\},\\qquad\\kappa\_\{W\}\(t\_\{1\},\\$\\mid r,a\)=\\frac\{1\}\{2\},κW\(t0,0∣t0,a\)=1,κW\(t1,1∣t1,a\)=1\.\\kappa\_\{W\}\(t\_\{0\},0\\mid t\_\{0\},a\)=1,\\qquad\\kappa\_\{W\}\(t\_\{1\},1\\mid t\_\{1\},a\)=1\.for everya∈𝒜a\\in\\mathcal\{A\}\. ClearlyWWimplementsℐ\\mathcal\{I\}, and it can be proven that there is no transducer with less than 3 states implementing this interface\.

Now, let’s define another implementationUU\. Its states areSU=\{r,c00,c01,c10,c11,z0,z1\}S\_\{U\}=\\\{r,c\_\{00\},c\_\{01\},c\_\{10\},c\_\{11\},z\_\{0\},z\_\{1\}\\\}with initial distribution centered atrr\. We describe the kernel by steps\. First, we state that

κU\(ci​j,$∣r,a\)=14\(i,j∈\{0,1\}\)\.\\kappa\_\{U\}\(c\_\{ij\},\\$\\mid r,a\)=\\frac\{1\}\{4\}\\qquad\(i,j\\in\\\{0,1\\\}\)\.for everya∈𝒜a\\in\\mathcal\{A\}\. Namely, in the first step the transducer transitions with uniform probability to any of the statesci​jc\_\{ij\}\.

Fromci​jc\_\{ij\}, the actionℓ\\ellreads the first coordinate, while actionggreads the second one\. More precisely, we have

κU\(zi,i∣ci​j,ℓ\)=1,κU\(zj,j∣ci​j,g\)=1\.\\kappa\_\{U\}\(z\_\{i\},i\\mid c\_\{ij\},\\ell\)=1,\\qquad\\kappa\_\{U\}\(z\_\{j\},j\\mid c\_\{ij\},g\)=1\.
Finally, for everya∈𝒜a\\in\\mathcal\{A\}we set

κU\(z0,0∣z0,a\)=1,κU\(z1,1∣z1,a\)=1\.\\kappa\_\{U\}\(z\_\{0\},0\\mid z\_\{0\},a\)=1,\\qquad\\kappa\_\{U\}\(z\_\{1\},1\\mid z\_\{1\},a\)=1\.
It can be checked that the transducerUUalso implementsℐ\\mathcal\{I\}: after the first output$\\$, the pair\(i,j\)\(i,j\)is uniformly chosen; and whichever coordinate is read by the second action the final result is a fair bit\. Afterwards, the machine moves toz0z\_\{0\}orz1z\_\{1\}, where the same bit is repeated forever\.

Now suppose, towards a contradiction, that someT∈ℒℐ0,dT\\in\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{0,d\}receives aδ\\delta\-reduction from every element ofℒℐ0,d\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{0,d\}, withδ<1\\delta<1\. SinceW∈ℒℐ0,dW\\in\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{0,d\}, there is a surjective state mapSW→STS\_\{W\}\\to S\_\{T\}\. Hence\|ST\|≤\|SW\|=3\|S\_\{T\}\|\\leq\|S\_\{W\}\|=3, and the fact that any implementation ofℐ\\mathcal\{I\}must have at least three states implies that\|ST\|=3\|S\_\{T\}\|=3\.

The three states ofTTcan be labelledx$,x0,x1x\_\{\\$\},x\_\{0\},x\_\{1\}depending on which node fromWWis the one mapped to them through theδ\\delta\-reduction\. Note that it must be the case that

Pr\(⋆\|x⋆,a\)T=1\\Pr\{\}\_\{T\}\(\\star\|x\_\{\\star\},a\)=1for every⋆∈𝒪\\star\\in\\mathcal\{O\}\. To see this, first note that there must be some state which outputs$\\$with probability one\. Otherwise, it would be impossible forTTto implementℐ\\mathcal\{I\}exactly\. With the same reasoning we can see that there must be some state that always outputs00and another one that always outputs11\. Then, we conclude that there is only one possibility for the reduction fromWWtoTTconsidering thatδ<1\\delta<1\.

SinceU∈ℒℐ0,dU\\in\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{0,d\}, there is aδ\\delta\-reductionψ:U​→𝛿​T\\psi:U\\overset\{\\delta\}\{\\rightarrow\{\}\}T\. Consider the statec01∈SUc\_\{01\}\\in S\_\{U\}\. There are three possible images, and we go through them one by one\.

Ifψ⁡\(c01\)=x$\\psi\(c\_\{01\}\)=x\_\{\\$\}we reach an absurd, since the distributions between those states are at distance11:c01c\_\{01\}assigns 0 probability to outputting$\\$\. Ifψ⁡\(c01\)=x0\\psi\(c\_\{01\}\)=x\_\{0\}, then, under actiongg, the statec01c\_\{01\}outputs11with probability one, whilex0x\_\{0\}outputs00with probability one\. Thusψ\\psiis not a properδ\\delta\-reduction withδ<1\\delta<1\. Ifψ⁡\(c01\)=x1\\psi\(c\_\{01\}\)=x\_\{1\}, we can argue in the same way\.

Therefore, no such transducerT∈ℒℐ0,dT\\in\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{0,d\}exists\. ∎

###### Proof of Proposition[6](https://arxiv.org/html/2608.20428#Thmproposition6)\.

LetWWandUUbe the two exact implementations ofℐ\\mathcal\{I\}constructed in the proof of Proposition[5](https://arxiv.org/html/2608.20428#Thmproposition5)\. SinceℐW=ℐU=ℐ\\mathcal\{I\}\_\{W\}=\\mathcal\{I\}\_\{U\}=\\mathcal\{I\}, we haveW,U∈ℒℐε,d∞W,U\\in\\mathcal\{L\}\_\{\\mathcal\{I\}\}^\{\\varepsilon,d\_\{\\infty\}\}for everyε≥0\\varepsilon\\geq 0\. Thus it is enough to prove the following claim: ifWWδ\\delta\-reduces toCCandUUδ\\delta\-reduces toCC, thenδ≥12\\delta\\geq\\frac\{1\}\{2\}\.

Letφ:SW→SC\\varphi:S\_\{W\}\\to S\_\{C\}be the state map of aδ\\delta\-reduction fromWWtoCC\. Since ordinary reductions are surjective on states, we have\|SC\|≤\|SW\|=3\|S\_\{C\}\|\\leq\|S\_\{W\}\|=3\.

First suppose that\|SC\|≤2\|S\_\{C\}\|\\leq 2\. The three statesr,t0,t1r,t\_\{0\},t\_\{1\}ofWWhave one\-step output marginalsδ$\\delta\_\{\\$\},δ0\\delta\_\{0\}andδ1\\delta\_\{1\}respectively, under every action\. Since there are at most two states inCC, two ofr,t0,t1r,t\_\{0\},t\_\{1\}must have the same imagex∈SCx\\in S\_\{C\}\. Hence, for two distinct outputso≠o′o\\neq o^\{\\prime\}, the output marginaloutC⁡\(x,a\)\\operatorname\{out\}\_\{C\}\(x,a\)is within total variation distanceδ\\deltaof bothδo\\delta\_\{o\}andδo′\\delta\_\{o^\{\\prime\}\}\. Marginalization cannot increase total variation, so

1=‖δo−δo′‖TV≤‖δo−outC⁡\(x,a\)‖TV\+‖outC⁡\(x,a\)−δo′‖TV≤2​δ\.1=\\\|\\delta\_\{o\}\-\\delta\_\{o^\{\\prime\}\}\\\|\_\{\\mathrm\{TV\}\}\\leq\\\|\\delta\_\{o\}\-\\operatorname\{out\}\_\{C\}\(x,a\)\\\|\_\{\\mathrm\{TV\}\}\+\\\|\\operatorname\{out\}\_\{C\}\(x,a\)\-\\delta\_\{o^\{\\prime\}\}\\\|\_\{\\mathrm\{TV\}\}\\leq 2\\delta\.Thusδ≥1/2\\delta\\geq 1/2\.

It remains to consider the case\|SC\|=3\|S\_\{C\}\|=3, whereφ\\varphiis bijective\. Write

x$=φ⁡\(r\),x0=φ⁡\(t0\),x1=φ⁡\(t1\)\.x\_\{\\$\}=\\varphi\(r\),\\qquad x\_\{0\}=\\varphi\(t\_\{0\}\),\\qquad x\_\{1\}=\\varphi\(t\_\{1\}\)\.as before\. The reductionW​→𝛿​CW\\overset\{\\delta\}\{\\rightarrow\{\}\}Cimplies that, for every actionaa,

‖outC⁡\(x$,a\)−δ$‖TV≤δ,\\\|\\operatorname\{out\}\_\{C\}\(x\_\{\\$\},a\)\-\\delta\_\{\\$\}\\\|\_\{\\mathrm\{TV\}\}\\leq\\delta,‖outC⁡\(x0,a\)−δ0‖TV≤δ,‖outC⁡\(x1,a\)−δ1‖TV≤δ\.\\\|\\operatorname\{out\}\_\{C\}\(x\_\{0\},a\)\-\\delta\_\{0\}\\\|\_\{\\mathrm\{TV\}\}\\leq\\delta,\\qquad\\\|\\operatorname\{out\}\_\{C\}\(x\_\{1\},a\)\-\\delta\_\{1\}\\\|\_\{\\mathrm\{TV\}\}\\leq\\delta\.
Letψ:SU→SC\\psi:S\_\{U\}\\to S\_\{C\}be the map of aδ\\delta\-reduction fromUUtoCC\. Consider the statec01∈SUc\_\{01\}\\in S\_\{U\}\. There are three possibilities\.

Ifψ⁡\(c01\)=x$\\psi\(c\_\{01\}\)=x\_\{\\$\}, then under actionℓ\\ell, the statec01c\_\{01\}outputs00with probability one\. The reductionU​→𝛿​CU\\overset\{\\delta\}\{\\rightarrow\{\}\}Cgives

‖δ0−outC⁡\(x$,ℓ\)‖TV≤δ\.\\\|\\delta\_\{0\}\-\\operatorname\{out\}\_\{C\}\(x\_\{\\$\},\\ell\)\\\|\_\{\\mathrm\{TV\}\}\\leq\\delta\.Together with the estimate coming fromφ\\varphi, we have

‖outC⁡\(x$,ℓ\)−δ$‖TV≤δ,\\\|\\operatorname\{out\}\_\{C\}\(x\_\{\\$\},\\ell\)\-\\delta\_\{\\$\}\\\|\_\{\\mathrm\{TV\}\}\\leq\\delta,and then

1=‖δ0−δ$‖TV≤2​δ\.1=\\\|\\delta\_\{0\}\-\\delta\_\{\\$\}\\\|\_\{\\mathrm\{TV\}\}\\leq 2\\delta\.
Ifψ⁡\(c01\)=x0\\psi\(c\_\{01\}\)=x\_\{0\}, then under actiongg, the statec01c\_\{01\}outputs11with probability one\. Hence

‖δ1−outC⁡\(x0,g\)‖TV≤δ\.\\\|\\delta\_\{1\}\-\\operatorname\{out\}\_\{C\}\(x\_\{0\},g\)\\\|\_\{\\mathrm\{TV\}\}\\leq\\delta\.Butx0x\_\{0\}isδ\\delta\-close to a00\-state, so

‖outC⁡\(x0,g\)−δ0‖TV≤δ\.\\\|\\operatorname\{out\}\_\{C\}\(x\_\{0\},g\)\-\\delta\_\{0\}\\\|\_\{\\mathrm\{TV\}\}\\leq\\delta\.Therefore

1=‖δ1−δ0‖TV≤2​δ\.1=\\\|\\delta\_\{1\}\-\\delta\_\{0\}\\\|\_\{\\mathrm\{TV\}\}\\leq 2\\delta\.
The last case can be treated in the same way\. ∎

###### Proof of Lemma[2](https://arxiv.org/html/2608.20428#Thmlemma2)\.

For everyw,v∈Σ∗w,v\\in\\Sigma^\{\*\}it is the case that0≤hℐ​\(w\)​\(v\)=Fℐ​\(w​v\)≤10\\leq h\_\{\\mathcal\{I\}\}\(w\)\(v\)=F\_\{\\mathcal\{I\}\}\(wv\)\\leq 1\. Hence, ifr=∑i=1mαi​hℐ​\(wi\)r=\\sum\_\{i=1\}^\{m\}\\alpha\_\{i\}h\_\{\\mathcal\{I\}\}\(w\_\{i\}\), then

‖r‖pred\\displaystyle\\\|r\\\|\_\{\\mathrm\{pred\}\}=supv∈Σ∗\|∑i=1mαi​hℐ​\(wi\)​\(v\)\|\\displaystyle=\\sup\_\{v\\in\\Sigma^\{\*\}\}\\left\|\\sum\_\{i=1\}^\{m\}\\alpha\_\{i\}h\_\{\\mathcal\{I\}\}\(w\_\{i\}\)\(v\)\\right\|≤∑i=1m\|αi\|​supv∈Σ∗\|Fℐ​\(wi​v\)\|\\displaystyle\\leq\\sum\_\{i=1\}^\{m\}\|\\alpha\_\{i\}\|\\sup\_\{v\\in\\Sigma^\{\*\}\}\|F\_\{\\mathcal\{I\}\}\(w\_\{i\}v\)\|≤∑i=1m\|αi\|\.\\displaystyle\\leq\\sum\_\{i=1\}^\{m\}\|\\alpha\_\{i\}\|\.Taking the infimum over all atomic decompositions ofrrgives‖r‖pred≤‖r‖at,ℐ\\\|r\\\|\_\{\\mathrm\{pred\}\}\\leq\\\|r\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\.

It is straightforward to prove that‖λ​r‖at,ℐ=\|λ\|​‖r‖at,ℐ\\\|\\lambda r\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}=\|\\lambda\|\\\|r\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}, and the triangle inequality is also easy to prove by concatenating atomic decompositions of the two summands\. Finally, if‖r‖at,ℐ=0\\\|r\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}=0, the preceding inequality implies that‖r‖pred=0\\\|r\\\|\_\{\\mathrm\{pred\}\}=0\. Thusr⁡\(v\)=0r\(v\)=0for everyv∈Σ∗v\\in\\Sigma^\{\*\}, and hencer=0r=0\. Therefore‖⋅‖at,ℐ\\\|\\mathord\{\\cdot\}\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}is a norm\.

We now check that‖ξℐ‖at,ℐ=1\\\|\\xi\_\{\\mathcal\{I\}\}\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}=1\. Sinceξℐ=hℐ​\(ϵ\)\\xi\_\{\\mathcal\{I\}\}=h\_\{\\mathcal\{I\}\}\(\\epsilon\)is itself an atom,‖ξℐ‖at,ℐ≤1\\\|\\xi\_\{\\mathcal\{I\}\}\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\\leq 1\. On the other hand, we have‖ξℐ‖pred≥\|ξℐ​\(ϵ\)\|=Fℐ​\(ϵ\)=1\\\|\\xi\_\{\\mathcal\{I\}\}\\\|\_\{\\mathrm\{pred\}\}\\geq\|\\xi\_\{\\mathcal\{I\}\}\(\\epsilon\)\|=F\_\{\\mathcal\{I\}\}\(\\epsilon\)=1\. Thus, using the previous shown relation between the atomic and predictive norms we conclude that‖ξℐ‖at,ℐ=1\\\|\\xi\_\{\\mathcal\{I\}\}\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}=1\.

For the readout functional, recall thatλℐ​\(r\)=r​\(ϵ\)\\lambda\_\{\\mathcal\{I\}\}\(r\)=r\(\\epsilon\)\. Thus

\|λℐ​\(r\)\|=\|r⁡\(ϵ\)\|≤‖r‖pred≤‖r‖at,ℐ,\|\\lambda\_\{\\mathcal\{I\}\}\(r\)\|=\|r\(\\epsilon\)\|\\leq\\\|r\\\|\_\{\\mathrm\{pred\}\}\\leq\\\|r\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\},and consequently‖λℐ‖\(Vℐ,‖⋅‖at,ℐ\)∗≤1\\\|\\lambda\_\{\\mathcal\{I\}\}\\\|\_\{\(V\_\{\\mathcal\{I\}\},\\\|\\mathord\{\\cdot\}\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\)^\{\*\}\}\\leq 1\. Sinceλℐ​\(ξℐ\)=Fℐ​\(ϵ\)=1\\lambda\_\{\\mathcal\{I\}\}\(\\xi\_\{\\mathcal\{I\}\}\)=F\_\{\\mathcal\{I\}\}\(\\epsilon\)=1and‖ξℐ‖at,ℐ=1\\\|\\xi\_\{\\mathcal\{I\}\}\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}=1the reverse inequality also holds, and we obtain‖λℐ‖\(Vℐ,‖⋅‖at,ℐ\)∗=1\\\|\\lambda\_\{\\mathcal\{I\}\}\\\|\_\{\(V\_\{\\mathcal\{I\}\},\\\|\\mathord\{\\cdot\}\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\)^\{\*\}\}=1\.

Finally, we prove that the shift operators are nonexpansive in the atomic norm\. For any atomic decompositionr=∑i=1mαi​hℐ​\(wi\)r=\\sum\_\{i=1\}^\{m\}\\alpha\_\{i\}h\_\{\\mathcal\{I\}\}\(w\_\{i\}\), the definition of the shift gives

Rσℐ​r=∑i=1mαi​hℐ​\(wi​σ\)\.R\_\{\\sigma\}^\{\\mathcal\{I\}\}r=\\sum\_\{i=1\}^\{m\}\\alpha\_\{i\}h\_\{\\mathcal\{I\}\}\(w\_\{i\}\\sigma\)\.Everyhℐ​\(wi​σ\)h\_\{\\mathcal\{I\}\}\(w\_\{i\}\\sigma\)is again a Hankel\-row atom, and hence

‖Rσℐ​r‖at,ℐ≤∑i=1m\|αi\|\.\\\|R\_\{\\sigma\}^\{\\mathcal\{I\}\}r\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\\leq\\sum\_\{i=1\}^\{m\}\|\\alpha\_\{i\}\|\.Taking the infimum over all atomic decompositions ofrrproves‖Rσℐ​r‖at,ℐ≤‖r‖at,ℐ\\\|R\_\{\\sigma\}^\{\\mathcal\{I\}\}r\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\\leq\\\|r\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\.

Using all the results, we can conclude thatGℐatG\_\{\\mathcal\{I\}\}^\{\\mathrm\{at\}\}is a contractive transducer\. ∎

###### Proof of Lemma[3](https://arxiv.org/html/2608.20428#Thmlemma3)\.

Because the vectorshℐ​\(p1\),…,hℐ​\(pd\)h\_\{\\mathcal\{I\}\}\(p\_\{1\}\),\\ldots,h\_\{\\mathcal\{I\}\}\(p\_\{d\}\)form a basis ofVℐV\_\{\\mathcal\{I\}\}, every Hankel row ofℐ\\mathcal\{I\}is reconstructed from its values on the selected suffixes\. Namely,

hℐ​\(w\)=evℐ⁡\(hℐ​\(w\)\)​Cℐ−1​Bℐ\.h\_\{\\mathcal\{I\}\}\(w\)=\\operatorname\{ev\}\_\{\\mathcal\{I\}\}\(h\_\{\\mathcal\{I\}\}\(w\)\)C\_\{\\mathcal\{I\}\}^\{\-1\}B\_\{\\mathcal\{I\}\}\.Consequently,

Π𝒥→ℐ​h𝒥​\(w\)−hℐ​\(w\)=ew​Cℐ−1​Bℐ\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}h\_\{\\mathcal\{J\}\}\(w\)\-h\_\{\\mathcal\{I\}\}\(w\)=e\_\{w\}C\_\{\\mathcal\{I\}\}^\{\-1\}B\_\{\\mathcal\{I\}\}whereew=ev𝒥⁡\(h𝒥​\(w\)\)−evℐ⁡\(hℐ​\(w\)\)e\_\{w\}=\\operatorname\{ev\}\_\{\\mathcal\{J\}\}\(h\_\{\\mathcal\{J\}\}\(w\)\)\-\\operatorname\{ev\}\_\{\\mathcal\{I\}\}\(h\_\{\\mathcal\{I\}\}\(w\)\)\. The conditiond∞​\(ℐ,𝒥\)≤εd\_\{\\infty\}\(\\mathcal\{I\},\\mathcal\{J\}\)\\leq\\varepsilonimplies‖ew‖∞≤ε\\\|e\_\{w\}\\\|\_\{\\infty\}\\leq\\varepsilon\. Since the rows ofBℐB\_\{\\mathcal\{I\}\}are atoms for∥⋅∥at,ℐ\\\|\\cdot\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\},

‖ew​Cℐ−1​Bℐ‖at,ℐ≤‖ew​Cℐ−1‖1≤Γℐ​ε\.\\begin\{split\}\\\|e\_\{w\}C\_\{\\mathcal\{I\}\}^\{\-1\}B\_\{\\mathcal\{I\}\}\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}&\\leq\\\|e\_\{w\}C\_\{\\mathcal\{I\}\}^\{\-1\}\\\|\_\{1\}\\\\ &\\leq\\Gamma\_\{\\mathcal\{I\}\}\\varepsilon\.\\end\{split\}
The images ofh𝒥​\(p1\),…,h𝒥​\(pd\)h\_\{\\mathcal\{J\}\}\(p\_\{1\}\),\\ldots,h\_\{\\mathcal\{J\}\}\(p\_\{d\}\)have coordinate matrixC𝒥​Cℐ−1C\_\{\\mathcal\{J\}\}C\_\{\\mathcal\{I\}\}^\{\-1\}in the basis given by the rows ofBℐB\_\{\\mathcal\{I\}\}\. IfC𝒥C\_\{\\mathcal\{J\}\}is invertible, these images spanVℐV\_\{\\mathcal\{I\}\}, proving surjectivity\. ∎

###### Proof of Theorem[3](https://arxiv.org/html/2608.20428#Thmtheorem3)\.

Chooseε¯​\(ℐ\)\>0\\overline\{\\varepsilon\}\(\\mathcal\{I\}\)\>0so thatd​ε¯​\(ℐ\)<σmin​\(Cℐ\)d\\overline\{\\varepsilon\}\(\\mathcal\{I\}\)<\\sigma\_\{\\min\}\(C\_\{\\mathcal\{I\}\}\), whereσmin​\(Cℐ\)\\sigma\_\{\\min\}\(C\_\{\\mathcal\{I\}\}\)denotes the minimal singular value ofCℐC\_\{\\mathcal\{I\}\}\. Then, using standard perturbation arguments we may conclude thatC𝒥C\_\{\\mathcal\{J\}\}is invertible, and Lemma[3](https://arxiv.org/html/2608.20428#Thmlemma3)shows thatΠ𝒥→ℐ\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}is surjective\. More precisely, note that, becaused∞​\(ℐ,𝒥\)≤εd\_\{\\infty\}\(\\mathcal\{I\},\\mathcal\{J\}\)\\leq\\varepsilon,

‖C𝒥−Cℐ‖2≤‖C𝒥−Cℐ‖F≤d​ε<σmin​\(Cℐ\),\\\|C\_\{\\mathcal\{J\}\}\-C\_\{\\mathcal\{I\}\}\\\|\_\{2\}\\leq\\\|C\_\{\\mathcal\{J\}\}\-C\_\{\\mathcal\{I\}\}\\\|\_\{F\}\\leq d\\varepsilon<\\sigma\_\{\\min\}\(C\_\{\\mathcal\{I\}\}\),and therefore, for everyx≠0x\\neq 0,

‖C𝒥​x‖2\\displaystyle\\\|C\_\{\\mathcal\{J\}\}x\\\|\_\{2\}≥‖Cℐ​x‖2−‖\(C𝒥−Cℐ\)​x‖2\\displaystyle\\geq\\\|C\_\{\\mathcal\{I\}\}x\\\|\_\{2\}\-\\\|\(C\_\{\\mathcal\{J\}\}\-C\_\{\\mathcal\{I\}\}\)x\\\|\_\{2\}≥σmin​\(Cℐ\)​‖x‖2−‖C𝒥−Cℐ‖2​‖x‖2\\displaystyle\\geq\\sigma\_\{\\min\}\(C\_\{\\mathcal\{I\}\}\)\\\|x\\\|\_\{2\}\-\\\|C\_\{\\mathcal\{J\}\}\-C\_\{\\mathcal\{I\}\}\\\|\_\{2\}\\\|x\\\|\_\{2\}≥\(σmin​\(Cℐ\)−d​ε\)​‖x‖2\>0\.\\displaystyle\\geq\(\\sigma\_\{\\min\}\(C\_\{\\mathcal\{I\}\}\)\-d\\varepsilon\)\\\|x\\\|\_\{2\}\>0\.
Applying Lemma[3](https://arxiv.org/html/2608.20428#Thmlemma3)to the empty word gives

‖Π𝒥→ℐ​ξ𝒥−ξℐ‖at,ℐ≤Γℐ​ε\.\\\|\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}\\xi\_\{\\mathcal\{J\}\}\-\\xi\_\{\\mathcal\{I\}\}\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\\leq\\Gamma\_\{\\mathcal\{I\}\}\\varepsilon\.Forσ∈Σ\\sigma\\in\\Sigmaandw∈Σ∗w\\in\\Sigma^\{\*\}, letEw=Π𝒥→ℐ​h𝒥​\(w\)−hℐ​\(w\)E\_\{w\}=\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}h\_\{\\mathcal\{J\}\}\(w\)\-h\_\{\\mathcal\{I\}\}\(w\)\. SinceRσℐ​hℐ​\(w\)=hℐ​\(w​σ\)R^\{\\mathcal\{I\}\}\_\{\\sigma\}h\_\{\\mathcal\{I\}\}\(w\)=h\_\{\\mathcal\{I\}\}\(w\\sigma\), we have

\(Π𝒥→ℐ​Rσ𝒥−Rσℐ​Π𝒥→ℐ\)​h𝒥​\(w\)=Ew​σ−Rσℐ​Ew\.\\begin\{split\}&\(\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}R^\{\\mathcal\{J\}\}\_\{\\sigma\}\-R^\{\\mathcal\{I\}\}\_\{\\sigma\}\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}\)h\_\{\\mathcal\{J\}\}\(w\)\\\\ &\\qquad=E\_\{w\\sigma\}\-R^\{\\mathcal\{I\}\}\_\{\\sigma\}E\_\{w\}\.\\end\{split\}By Lemma[2](https://arxiv.org/html/2608.20428#Thmlemma2), the shifts ofGℐG\_\{\\mathcal\{I\}\}are non\-expansive with respect to the atomic norm, so

‖\(Π𝒥→ℐ​Rσ𝒥−Rσℐ​Π𝒥→ℐ\)​h𝒥​\(w\)‖at,ℐ≤2​Γℐ​ε\.\\\|\(\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}R^\{\\mathcal\{J\}\}\_\{\\sigma\}\-R^\{\\mathcal\{I\}\}\_\{\\sigma\}\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}\)h\_\{\\mathcal\{J\}\}\(w\)\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\\leq 2\\Gamma\_\{\\mathcal\{I\}\}\\varepsilon\.\(21\)Ifr=∑iαi​h𝒥​\(wi\)r=\\sum\_\{i\}\\alpha\_\{i\}h\_\{\\mathcal\{J\}\}\(w\_\{i\}\), linearity and \([21](https://arxiv.org/html/2608.20428#A1.E21)\) give

‖\(Π𝒥→ℐ​Rσ𝒥−Rσℐ​Π𝒥→ℐ\)​r‖at,ℐ≤2​Γℐ​ε​∑i\|αi\|\.\\begin\{split\}&\\\|\(\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}R^\{\\mathcal\{J\}\}\_\{\\sigma\}\-R^\{\\mathcal\{I\}\}\_\{\\sigma\}\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}\)r\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\\\\ &\\qquad\\leq 2\\Gamma\_\{\\mathcal\{I\}\}\\varepsilon\\sum\_\{i\}\|\\alpha\_\{i\}\|\.\\end\{split\}Taking the infimum over all atomic decompositions ofrrproves the required bound\.

The choiceq1=ϵq\_\{1\}=\\epsilonmakes the readout exact\. Indeed, the first column ofCℐC\_\{\\mathcal\{I\}\}isBℐ​\(ϵ\)B\_\{\\mathcal\{I\}\}\(\\epsilon\), and hence

λℐ​\(Π𝒥→ℐ​r\)=\(Π𝒥→ℐ​r\)​\(ϵ\)=ev𝒥⁡\(r\)​Cℐ−1​Bℐ​\(ϵ\)=ev𝒥⁡\(r\)​e1=r⁡\(ϵ\)=λ𝒥​\(r\)\.\\begin\{split\}\\lambda\_\{\\mathcal\{I\}\}\(\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}r\)&=\(\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}r\)\(\\epsilon\)\\\\ &=\\operatorname\{ev\}\_\{\\mathcal\{J\}\}\(r\)C\_\{\\mathcal\{I\}\}^\{\-1\}B\_\{\\mathcal\{I\}\}\(\\epsilon\)\\\\ &=\\operatorname\{ev\}\_\{\\mathcal\{J\}\}\(r\)e\_\{1\}=r\(\\epsilon\)=\\lambda\_\{\\mathcal\{J\}\}\(r\)\.\\end\{split\}Thus all three defects are bounded by2​Γℐ​ε2\\Gamma\_\{\\mathcal\{I\}\}\\varepsilon\.

Finally, we show thatΠ𝒥→ℐ\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}is bounded\. For everyw∈Σ∗w\\in\\Sigma^\{\*\},

‖Π𝒥→ℐ​h𝒥​\(w\)‖at,ℐ≤‖hℐ​\(w\)‖at,ℐ\+‖Π𝒥→ℐ​h𝒥​\(w\)−hℐ​\(w\)‖at,ℐ≤1\+Γℐ​ε\.\\\|\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}h\_\{\\mathcal\{J\}\}\(w\)\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\\leq\\\|h\_\{\\mathcal\{I\}\}\(w\)\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\+\\\|\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}h\_\{\\mathcal\{J\}\}\(w\)\-h\_\{\\mathcal\{I\}\}\(w\)\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\\leq 1\+\\Gamma\_\{\\mathcal\{I\}\}\\varepsilon\.Consequently, ifr=∑i=1mαi​h𝒥​\(wi\)r=\\sum\_\{i=1\}^\{m\}\\alpha\_\{i\}h\_\{\\mathcal\{J\}\}\(w\_\{i\}\), then

‖Π𝒥→ℐ​r‖at,ℐ≤\(1\+Γℐ​ε\)​∑i=1m\|αi\|\.\\\|\\Pi\_\{\\mathcal\{J\}\\to\\mathcal\{I\}\}r\\\|\_\{\\mathrm\{at\},\\mathcal\{I\}\}\\leq\(1\+\\Gamma\_\{\\mathcal\{I\}\}\\varepsilon\)\\sum\_\{i=1\}^\{m\}\|\\alpha\_\{i\}\|\.Taking the infimum over all atomic decompositions ofrrwe conclude that‖ΠJ→I‖≤1\+ΓI​ε\\\|\\Pi\_\{J\\to I\}\\\|\\leq 1\+\\Gamma\_\{I\}\\varepsilon\. ∎

###### Proof of Proposition[7](https://arxiv.org/html/2608.20428#Thmproposition7)\.

Let𝒪=\{0,1\}\\mathcal\{O\}=\\\{0,1\\\},𝒜=\{⋆\}\\mathcal\{A\}=\\\{\\star\\\}\(i\.e\. the dynamics are actionless\) and letℐ\\mathcal\{I\}be the process of independent fair bits\. WriteD𝒦\(m\)D\_\{\\mathcal\{K\}\}^\{\(m\)\}for the length\-mmoutput law of an interface𝒦\\mathcal\{K\}\. Forn≥1n\\geq 1, define𝒥n\\mathcal\{J\}\_\{n\}as follows\. Its firstnnoutputs are independent fair bits\. If these outputs are0n0^\{n\}, then every later output is00; otherwise, all later outputs continue to be independent fair bits\.

The length\-mmdistributions agree form≤nm\\leq n\. Form\>nm\>nthey differ only on strings beginning with0n0^\{n\}, and a direct calculation gives

‖Dℐ\(m\)−D𝒥n\(m\)‖TV=2−n−2−m\.\\left\\\|D\_\{\\mathcal\{I\}\}^\{\(m\)\}\-D\_\{\\mathcal\{J\}\_\{n\}\}^\{\(m\)\}\\right\\\|\_\{\\mathrm\{TV\}\}=2^\{\-n\}\-2^\{\-m\}\.Taking the supremum overmmgivesd∞​\(ℐ,𝒥n\)=2−nd\_\{\\infty\}\(\\mathcal\{I\},\\mathcal\{J\}\_\{n\}\)=2^\{\-n\}\.

The transducer𝖤⁡\(ℐ\)\\mathsf\{E\}\(\\mathcal\{I\}\)has one state, whose output law is12​δ0\+12​δ1\\frac\{1\}\{2\}\\delta\_\{0\}\+\\frac\{1\}\{2\}\\delta\_\{1\}\. In𝖤⁡\(𝒥n\)\\mathsf\{E\}\(\\mathcal\{J\}\_\{n\}\), the state reached after0n0^\{n\}outputs00deterministically\. Any state map to the one\-state target must send this state to the unique state of𝖤⁡\(ℐ\)\\mathsf\{E\}\(\\mathcal\{I\}\)\. Marginalizing the joint one\-step kernels to outputs therefore gives

δ≥‖δ0−\(12​δ0\+12​δ1\)‖TV=12\.\\delta\\geq\\left\\\|\\delta\_\{0\}\-\\left\(\\tfrac\{1\}\{2\}\\delta\_\{0\}\+\\tfrac\{1\}\{2\}\\delta\_\{1\}\\right\)\\right\\\|\_\{\\mathrm\{TV\}\}=\\frac\{1\}\{2\}\.
For the last claim, surjectivity of a reduction from the one\-state transducer𝖤⁡\(ℐ\)\\mathsf\{E\}\(\\mathcal\{I\}\)forcesCCto have one state\. Letν\\nube its output law\. The two reductions imply

‖ν−\(12​δ0\+12​δ1\)‖TV≤δ,‖ν−δ0‖TV≤δ\.\\left\\\|\\nu\-\\left\(\\tfrac\{1\}\{2\}\\delta\_\{0\}\+\\tfrac\{1\}\{2\}\\delta\_\{1\}\\right\)\\right\\\|\_\{\\mathrm\{TV\}\}\\leq\\delta,\\qquad\\\|\\nu\-\\delta\_\{0\}\\\|\_\{\\mathrm\{TV\}\}\\leq\\delta\.Then, the triangle inequality gives1/2≤2​δ1/2\\leq 2\\delta\. ∎

###### Proof of Theorem[4](https://arxiv.org/html/2608.20428#Thmtheorem4)\.

Sincedres​\(ℐ,𝒥\)≤ε<1d\_\{\\mathrm\{res\}\}\(\\mathcal\{I\},\\mathcal\{J\}\)\\leq\\varepsilon<1, the definition ofdresd\_\{\\mathrm\{res\}\}implies thatsupp⁡\(ℐ\)=supp⁡\(𝒥\)\\operatorname\{supp\}\(\\mathcal\{I\}\)=\\operatorname\{supp\}\(\\mathcal\{J\}\)\. Moreover, for everyhhin this common support we haved∞​\(ℐh,𝒥h\)≤εd\_\{\\infty\}\(\\mathcal\{I\}^\{h\},\\mathcal\{J\}^\{h\}\)\\leq\\varepsilon\.

We first prove thatϕ\\phiis well defined\. Suppose that\[h\]𝒥=\[u\]𝒥\[h\]\_\{\\mathcal\{J\}\}=\[u\]\_\{\\mathcal\{J\}\}\. By definition of predictive equivalence,𝒥h=𝒥u\\mathcal\{J\}^\{h\}=\\mathcal\{J\}^\{u\}\. Therefore, by the triangle inequality,

d∞​\(ℐh,ℐu\)\\displaystyle d\_\{\\infty\}\(\\mathcal\{I\}^\{h\},\\mathcal\{I\}^\{u\}\)≤d∞​\(ℐh,𝒥h\)\+d∞​\(𝒥h,𝒥u\)\+d∞​\(𝒥u,ℐu\)\\displaystyle\\leq d\_\{\\infty\}\(\\mathcal\{I\}^\{h\},\\mathcal\{J\}^\{h\}\)\+d\_\{\\infty\}\(\\mathcal\{J\}^\{h\},\\mathcal\{J\}^\{u\}\)\+d\_\{\\infty\}\(\\mathcal\{J\}^\{u\},\\mathcal\{I\}^\{u\}\)≤2​ε<Δℐ\.\\displaystyle\\leq 2\\varepsilon<\\Delta\_\{\\mathcal\{I\}\}\.If\[h\]ℐ≠\[u\]ℐ\[h\]\_\{\\mathcal\{I\}\}\\neq\[u\]\_\{\\mathcal\{I\}\}, the definition ofΔℐ\\Delta\_\{\\mathcal\{I\}\}would instead gived∞​\(ℐh,ℐu\)≥Δℐd\_\{\\infty\}\(\\mathcal\{I\}^\{h\},\\mathcal\{I\}^\{u\}\)\\geq\\Delta\_\{\\mathcal\{I\}\}, which is a contradiction\. Hence\[h\]ℐ=\[u\]ℐ\[h\]\_\{\\mathcal\{I\}\}=\[u\]\_\{\\mathcal\{I\}\}, proving thatϕ\\phiis well defined\.

The map is surjective\. Indeed, every state ofE⁡\(ℐ\)E\(\\mathcal\{I\}\)is of the form\[h\]ℐ\[h\]\_\{\\mathcal\{I\}\}for someh∈supp⁡\(ℐ\)h\\in\\operatorname\{supp\}\(\\mathcal\{I\}\)\. Since the interfaces have the same support,h∈supp⁡\(𝒥\)h\\in\\operatorname\{supp\}\(\\mathcal\{J\}\), and therefore

\[h\]ℐ=ϕ⁡\(\[h\]𝒥\)\.\[h\]\_\{\\mathcal\{I\}\}=\\phi\(\[h\]\_\{\\mathcal\{J\}\}\)\.
It remains to verify the approximate one\-step condition\. For an interfaceKK, write

μKh\(o∣a\)=Pr\(o∣a\)Kh\\mu\_\{K\}^\{h\}\(o\\mid a\)=\\Pr\{\}\_\{K^\{h\}\}\(o\\mid a\)for the one\-step output law afterhh\. Fixh∈supp⁡\(ℐ\)=supp⁡\(𝒥\)h\\in\\operatorname\{supp\}\(\\mathcal\{I\}\)=\\operatorname\{supp\}\(\\mathcal\{J\}\)anda∈𝒜a\\in\\mathcal\{A\}\. For everyoohaving positive conditional probability, the canonical transducers move respectively to\[h⁡\(a,o\)\]𝒥\[h\(a,o\)\]\_\{\\mathcal\{J\}\}and\[h⁡\(a,o\)\]ℐ\[h\(a,o\)\]\_\{\\mathcal\{I\}\}\. By definition ofϕ\\phi, it holds thatϕ⁡\(\[h⁡\(a,o\)\]𝒥\)=\[h⁡\(a,o\)\]ℐ\\phi\(\[h\(a,o\)\]\_\{\\mathcal\{J\}\}\)=\[h\(a,o\)\]\_\{\\mathcal\{I\}\}\. Furthermore, equality of supports implies thatμℐh​\(o∣a\)\>0\\mu\_\{\\mathcal\{I\}\}^\{h\}\(o\\mid a\)\>0if and only ifμ𝒥h​\(o∣a\)\>0\\mu\_\{\\mathcal\{J\}\}^\{h\}\(o\\mid a\)\>0\. Consequently, after pushing the kernel ofE⁡\(𝒥\)E\(\\mathcal\{J\}\)forward throughϕ\\phi, both joint kernels place their mass corresponding toooon the same pair\(\[h⁡\(a,o\)\]ℐ,o\)\\bigl\(\[h\(a,o\)\]\_\{\\mathcal\{I\}\},o\\bigr\)\. It follows that

‖\(ϕ×id𝒪\)∗κϵ,𝒥\(⋅,⋅∣\[h\]𝒥,a\)−κϵ,ℐ\(⋅,⋅∣\[h\]ℐ,a\)‖TV\\displaystyle\\left\\\|\(\\phi\\times\\operatorname\{id\}\_\{\\mathcal\{O\}\}\)\_\{\*\}\\kappa\_\{\\epsilon,\\mathcal\{J\}\}\(\\mathord\{\\cdot\},\\mathord\{\\cdot\}\\mid\[h\]\_\{\\mathcal\{J\}\},a\)\-\\kappa\_\{\\epsilon,\\mathcal\{I\}\}\(\\mathord\{\\cdot\},\\mathord\{\\cdot\}\\mid\[h\]\_\{\\mathcal\{I\}\},a\)\\right\\\|\_\{\\mathrm\{TV\}\}=‖μ𝒥h​\(⋅∣a\)−μℐh​\(⋅∣a\)‖TV\\displaystyle\\hskip 40\.00006pt=\\left\\\|\\mu\_\{\\mathcal\{J\}\}^\{h\}\(\\mathord\{\\cdot\}\\mid a\)\-\\mu\_\{\\mathcal\{I\}\}^\{h\}\(\\mathord\{\\cdot\}\\mid a\)\\right\\\|\_\{\\mathrm\{TV\}\}≤d∞​\(𝒥h,ℐh\)≤ε\.\\displaystyle\\hskip 40\.00006pt\\leq d\_\{\\infty\}\(\\mathcal\{J\}^\{h\},\\mathcal\{I\}^\{h\}\)\\leq\\varepsilon\.The initial state is preserved exactly:

ϕ∗​δ\[ϵ\]𝒥=δ\[ϵ\]ℐ\.\\phi\_\{\*\}\\delta\_\{\[\\epsilon\]\_\{\\mathcal\{J\}\}\}=\\delta\_\{\[\\epsilon\]\_\{\\mathcal\{I\}\}\}\.Thusϕ\\phidetermines anε\\varepsilon\-reductionE⁡\(𝒥\)→E⁡\(ℐ\)E\(\\mathcal\{J\}\)\\to E\(\\mathcal\{I\}\)\. ∎

###### Proof of Corollary[2](https://arxiv.org/html/2608.20428#Thmcorollary2)\.

LetTTbe a predictive transducer from the statement\. By Proposition[1](https://arxiv.org/html/2608.20428#Thmproposition1)there is an exact reduction fromTTto𝖤⁡\(𝒥\)\\mathsf\{E\}\(\\mathcal\{J\}\)\. Then, by Theorem[4](https://arxiv.org/html/2608.20428#Thmtheorem4)there is aε\\varepsilon\-reduction fromE⁡\(𝒥\)E\(\\mathcal\{J\}\)toE⁡\(ℐ\)E\(\\mathcal\{I\}\)\. Composing them we get the desired result, using Proposition[2](https://arxiv.org/html/2608.20428#Thmproposition2)to bound the error of the composition\. ∎

## References

- \[1\]D\. Abel, D\. Hershkowitz, and M\. Littman\(2016\)Near optimal behavior via approximate state abstraction\.InInternational Conference on Machine Learning,pp\. 2915–2923\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p3.1)\.
- \[2\]Y\. Bansal, P\. Nakkiran, and B\. Barak\(2021\)Revisiting model stitching to compare neural representations\.Advances in neural information processing systems34,pp\. 225–236\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p2.1),[1st item](https://arxiv.org/html/2608.20428#S5.I1.i1.p1.1)\.
- \[3\]N\. Barnett and J\. P\. Crutchfield\(2015\)Computational mechanics of input–output processes: structured transformations and theϵ\\epsilon\-transducer\.Journal of Statistical Physics161\(2\),pp\. 404–451\.Cited by:[item 4](https://arxiv.org/html/2608.20428#S1.I1.i4.p1.1),[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p4.1),[§2\.1](https://arxiv.org/html/2608.20428#S2.SS1.p11.1),[§2\.3](https://arxiv.org/html/2608.20428#S2.SS3.p3.3)\.
- \[4\]Y\. Bengio, A\. Courville, and P\. Vincent\(2013\)Representation learning: a review and new perspectives\.IEEE transactions on pattern analysis and machine intelligence35\(8\),pp\. 1798–1828\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p1.1)\.
- \[5\]Y\. Berchenko\(2024\)Simplicity bias in overparameterized machine learning\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,pp\. 11052–11060\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p3.1)\.
- \[6\]L\. Bereska and E\. Gavves\(2024\)Mechanistic interpretability for ai safety–a review\.arXiv preprint arXiv:2404\.14082\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p1.1)\.
- \[7\]A\. Boyd, F\. Nowak, D\. Hyland, M\. Baltieri, and F\. E\. Rosas\(2025\)From monoliths to modules: Decomposing transducers for efficient world modelling\.External Links:2512\.02193,[Document](https://dx.doi.org/10.48550/arXiv.2512.02193)Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p5.1)\.
- \[8\]R\. Cao and D\. Yamins\(2021\)Explanatory models in neuroscience: part 2–constraint\-based intelligibility\.arXiv preprint arXiv:2104\.01489\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p3.1)\.
- \[9\]A\. Chen, J\. Merullo, A\. Stolfo, and E\. Pavlick\(2026\)Transferring linear features across language models with model stitching\.Advances in Neural Information Processing Systems38,pp\. 48531–48563\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p2.1),[1st item](https://arxiv.org/html/2608.20428#S5.I1.i1.p1.1)\.
- \[10\]L\. Ciernik, L\. Linhardt, M\. Morik, J\. Dippel, S\. Kornblith, and L\. Muttenthaler\(2024\)Objective drives the consistency of representational similarity across datasets\.arXiv preprint arXiv:2411\.05561\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p2.1)\.
- \[11\]S\. Cifuentes\(2026\)General agents contain world models, even under partial observability and stochasticity\.arXiv preprint arXiv:2602\.03146\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p4.1)\.
- \[12\]J\. P\. Crutchfield\(1989\)Inferring the dynamic, quantifying physical complexity\.InMeasures of Complexity and Chaos,pp\. 327–338\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p4.1)\.
- \[13\]A\. Csiszárik, P\. Kőrösi\-Szabó, A\. Matszangosz, G\. Papp, and D\. Varga\(2021\)Similarity and matching of neural network representations\.Advances in Neural Information Processing Systems34,pp\. 5656–5668\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p2.1)\.
- \[14\]J\. Desharnais, V\. Gupta, R\. Jagadeesan, and P\. Panangaden\(2004\)Metrics for labelled markov processes\.Theoretical computer science318\(3\),pp\. 323–354\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p3.1)\.
- \[15\]F\. Ding, J\. Denain, and J\. Steinhardt\(2021\)Grounding representation similarity through statistical testing\.Advances in neural information processing systems34,pp\. 1556–1568\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p2.1)\.
- \[16\]N\. Ferns, P\. Panangaden, and D\. Precup\(2004\)Metrics for finite Markov decision processes\.InProceedings of the Twentieth Conference on Uncertainty in Artificial Intelligence,pp\. 162–169\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p3.1)\.
- \[17\]R\. Givan, T\. Dean, and M\. Greig\(2003\)Equivalence notions and model minimization in Markov decision processes\.Artificial Intelligence147\(1–2\),pp\. 163–223\.External Links:[Document](https://dx.doi.org/10.1016/S0004-3702%2802%2900376-4)Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p2.1)\.
- \[18\]M\. Gorbett and S\. Jana\(2026\)Characterizing linear alignment across language models\.arXiv preprint arXiv:2603\.18908\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p2.1)\.
- \[19\]F\. Gröger, S\. Wen, and M\. Brbić\(2026\)Revisiting the platonic representation hypothesis: an aristotelian view\.arXiv preprint arXiv:2602\.14486\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p2.1)\.
- \[20\]D\. Ha and J\. Schmidhuber\(2018\)World models\.arXiv preprint arXiv:1803\.101222\(3\),pp\. 440\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p4.1)\.
- \[21\]D\. Hafner, J\. Pasukonis, J\. Ba, and T\. Lillicrap\(2023\)Mastering diverse domains through world models\.arXiv preprint arXiv:2301\.04104\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p4.1)\.
- \[22\]W\. Hu\(2024\)Understanding surprising generalization phenomena in deep learning\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,pp\. 22669–22669\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p4.1)\.
- \[23\]M\. Huh, B\. Cheung, T\. Wang, and P\. Isola\(2024\)The platonic representation hypothesis\.arXiv preprint arXiv:2405\.07987\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p2.1),[§1](https://arxiv.org/html/2608.20428#S1.p3.1)\.
- \[24\]J\. Jiang, J\. Zhou, P\. Wang, Q\. Qu, D\. Mixon, C\. You, and Z\. Zhu\(2023\)Generalized neural collapse for a large number of classes\.arXiv preprint arXiv:2310\.05351\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p4.1)\.
- \[25\]D\. Kalimeris, G\. Kaplun, P\. Nakkiran, B\. Edelman, T\. Yang, B\. Barak, and H\. Zhang\(2019\)Sgd on neural networks learns functions of increasing complexity\.Advances in neural information processing systems32\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p3.1)\.
- \[26\]J\. G\. Kemeny J\. L\. Snellet al\.\(1969\)Finite markov chains\.Vol\.26,van Nostrand Princeton, NJ\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p2.1)\.
- \[27\]S\. Kiefer and Q\. Tang\(2021\)Approximate bisimulation minimisation\.arXiv preprint arXiv:2110\.00326\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p3.1)\.
- \[28\]M\. Klabunde, T\. Schumacher, M\. Strohmaier, and F\. Lemmerich\(2025\)Similarity of neural network models: a survey of functional and representational measures\.ACM Computing Surveys57\(9\),pp\. 1–52\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p2.1)\.
- \[29\]S\. Kornblith, M\. Norouzi, H\. Lee, and G\. Hinton\(2019\)Similarity of neural network representations revisited\.InInternational conference on machine learning,pp\. 3519–3529\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p2.1)\.
- \[30\]K\. G\. Larsen and A\. Skou\(1991\)Bisimulation through probabilistic testing\.Information and Computation94\(1\),pp\. 1–28\.External Links:[Document](https://dx.doi.org/10.1016/0890-5401%2891%2990030-6)Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p2.1)\.
- \[31\]Y\. LeCun, Y\. Bengio, and G\. Hinton\(2015\)Deep learning\.nature521\(7553\),pp\. 436–444\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p1.1)\.
- \[32\]L\. Li, T\. J\. Walsh, and M\. L\. Littman\(2006\)Towards a unified theory of state abstraction for mdps\.\.AI&M1\(2\),pp\. 3\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p2.1)\.
- \[33\]Y\. Li, J\. Yosinski, J\. Clune, H\. Lipson, and J\. Hopcroft\(2015\)Convergent learning: do different neural networks learn the same representations?\.arXiv preprint arXiv:1511\.07543\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p2.1)\.
- \[34\]G\. H\. Mealy\(1955\)A method for synthesizing sequential circuits\.The Bell System Technical Journal34\(5\),pp\. 1045–1079\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p1.1)\.
- \[35\]M\. Mohri\(1997\)Finite\-state transducers in language and speech processing\.Computational linguistics23\(2\),pp\. 269–311\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p1.1)\.
- \[36\]E\. F\. Mooreet al\.\(1956\)Gedanken\-experiments on sequential machines\.Automata studies34\(129\-153\),pp\. 129–153\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p1.1)\.
- \[37\]A\. Morcos, M\. Raghu, and S\. Bengio\(2018\)Insights on representational similarity in neural networks with canonical correlation\.Advances in neural information processing systems31\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p2.1)\.
- \[38\]A\. Nayebi\(2026\)What capable agents must know: selection theorems for robust decision\-making under uncertainty\.arXiv preprint arXiv:2603\.02491\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p4.1)\.
- \[39\]T\. Nguyen, M\. Raghu, and S\. Kornblith\(2020\)Do wide and deep networks learn the same things? uncovering how neural network representations vary with width and depth\.arXiv preprint arXiv:2010\.15327\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p3.1)\.
- \[40\]M\. L\. Puterman\(2014\)Markov decision processes: discrete stochastic dynamic programming\.John Wiley & Sons\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p1.1)\.
- \[41\]B\. Ravindran and A\. G\. Barto\(2003\)SMDP homomorphisms: An algebraic approach to abstraction in semi\-Markov decision processes\.InProceedings of the Eighteenth International Joint Conference on Artificial Intelligence,pp\. 1011–1016\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p2.1),[§5](https://arxiv.org/html/2608.20428#S5.p5.1)\.
- \[42\]B\. Ravindran and A\. G\. Barto\(2004\)Approximate homomorphisms: A framework for non\-exact minimization in Markov Decision Processes\.Note:ManuscriptExternal Links:[Link](https://www.cse.iitm.ac.in/~ravi/papers/KBCS04.pdf)Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p3.1)\.
- \[43\]J\. Richens, D\. Abel, A\. Bellot, and T\. Everitt\(2025\)General agents contain world models\.Note:Accepted at ICML 2025External Links:2506\.01622,[Document](https://dx.doi.org/10.48550/arXiv.2506.01622)Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p4.1)\.
- \[44\]F\. Rosas, A\. Boyd, and M\. Baltieri\(2025\)AI in a vat: fundamental limits of efficient world modelling for agent sandboxing and interpretability\.arXiv preprint arXiv:2504\.04608\.Cited by:[item 2](https://arxiv.org/html/2608.20428#S1.I1.i2.p1.1),[§1](https://arxiv.org/html/2608.20428#S1.p4.1),[§1](https://arxiv.org/html/2608.20428#S1.p5.1),[§2\.1](https://arxiv.org/html/2608.20428#S2.SS1.p11.1),[§2\.1](https://arxiv.org/html/2608.20428#S2.SS1.p12.1),[§2\.1](https://arxiv.org/html/2608.20428#S2.SS1.p3.1),[§4\.1](https://arxiv.org/html/2608.20428#S4.SS1.p4.1),[§5](https://arxiv.org/html/2608.20428#S5.p1.1),[Definition 13](https://arxiv.org/html/2608.20428#Thmdefinition13),[Observation 1](https://arxiv.org/html/2608.20428#Thmobservation1.p1.1.1)\.
- \[45\]M\. P\. Schützenberger\(1961\)On the definition of a family of automata\.Inf\. Control\.4\(2\-3\),pp\. 245–270\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p4.1)\.
- \[46\]A\. Shai, L\. Amdahl\-Culleton, C\. L\. Christensen, H\. R\. Bigelow, F\. E\. Rosas, A\. B\. Boyd, E\. A\. Alt, K\. J\. Ray, and P\. M\. Riechers\(2026\)Transformers learn factored representations\.arXiv preprint arXiv:2602\.02385\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px1.p3.1),[§1](https://arxiv.org/html/2608.20428#S1.p4.1),[§1](https://arxiv.org/html/2608.20428#S1.p5.1),[1st item](https://arxiv.org/html/2608.20428#S5.I1.i1.p1.1),[§5](https://arxiv.org/html/2608.20428#S5.p4.1)\.
- \[47\]A\. S\. Shai, S\. E\. Marzen, L\. Teixeira, A\. G\. Oldenziel, and P\. M\. Riechers\(2024\)Transformers represent belief state geometry in their residual stream\.Advances in Neural Information Processing Systems37,pp\. 75012–75034\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px1.p3.1),[§1](https://arxiv.org/html/2608.20428#S1.p5.1),[1st item](https://arxiv.org/html/2608.20428#S5.I1.i1.p1.1),[§5](https://arxiv.org/html/2608.20428#S5.p4.1)\.
- \[48\]C\. R\. Shalizi and J\. P\. Crutchfield\(2001\)Computational mechanics: pattern and prediction, structure and simplicity\.Journal of statistical physics104\(3\),pp\. 817–879\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p4.1)\.
- \[49\]T\. Spork, C\. Baier, J\. Katoen, J\. Piribauer, and T\. Quatmann\(2024\)A spectrum of approximate probabilistic bisimulations\.In35th International Conference on Concurrency Theory \(CONCUR 2024\),Leibniz International Proceedings in Informatics \(LIPIcs\), Vol\.311,pp\. 37:1–37:19\.External Links:[Document](https://dx.doi.org/10.4230/LIPIcs.CONCUR.2024.37)Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p3.1)\.
- \[50\]J\. J\. Taylor, D\. Precup, and P\. Panangaden\(2008\)Bounding performance loss in approximate MDP homomorphisms\.InAdvances in Neural Information Processing Systems 21,pp\. 1649–1656\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.SS0.SSS0.Px2.p3.1)\.
- \[51\]G\. Valle\-Perez, C\. Q\. Camargo, and A\. A\. Louis\(2018\)Deep learning generalizes because the parameter\-function map is biased towards simple functions\.arXiv preprint arXiv:1805\.08522\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p3.1)\.
- \[52\]S\. Watanabe\(2018\)Mathematical theory of bayesian statistics\.CRC press\.Cited by:[§1](https://arxiv.org/html/2608.20428#S1.p4.1)\.