sec-stochastic-krohn-rhodes
5.4.3 Toward stochastic and coalgebraic prime decomposition
5.4.3 Toward stochastic and coalgebraic prime decomposition
The preceding account raises a question with direct consequences for compositional learning: can prime decomposition survive when transitions are stochastic? There is already an important partial answer. Carlsson and Yu [ 2015 ] define a probabilistic automaton by extending the action of a finite deterministic transition semigroup from states and letters to probability distributions. Convolution then gives a compact semigroup of distributions on the finite transition semigroup, and the classical Krohn–Rhodes theorem supplies its underlying prime decomposition. Their result shows that probability does not erase the group–reset architecture when randomness is distributed over a finite deterministic action semigroup.
That qualification matters. A general finite-state controlled Markov system is more naturally a coalgebra
where \(\mathcal D\) is the finite-distribution monad and each action determines a stochastic kernel \(K_a:X\to \mathcal D X\). Its transitions compose in the Kleisli category \(\mathbf{Kl}(\mathcal D)\), not in the finite transformation monoid \(X^X\). Even when \(X\) and \(A\) are finite, the stochastic matrices generated by composition can form an infinite, indeed continuously parameterized, semigroup. The finiteness hypothesis that drives the classical induction has disappeared.
There is nevertheless a clean bridge for rational systems.
Let \(X\) and \(A\) be finite, and suppose every entry of every controlled kernel \(K_a\) is rational. Then there are a finite noise set \(E\), the uniform distribution \(u_E\), and deterministic maps \(f_{a,e}:X\to X\) such that
Consequently the transition dynamics admit an exact randomized realization by a finite cascade of group and flip-flop components.
Choose a common denominator \(N\) for the finitely many entries of the kernels and let \(E=\{ 1,\ldots ,N\} \). For each pair \((x,a)\), partition \(E\) into subsets of cardinality \(N K_a(x,y)\), one subset for each \(y\in X\), and set \(f_{a,e}(x)=y\) on the corresponding subset. Uniformly sampling \(e\) gives exactly \(K_a(x,-)\). Apply Theorem 5.8 to the finite transformation monoid generated by the maps \(f_{a,e}\), then sample the noise inputs and forget them.
Thus a finite rational MDP has a Krohn–Rhodes realization at the level of its transition dynamics. Rewards may be carried as output maps or included in an enlarged state–output system. The construction is useful but not yet intrinsic: different deterministic dilations of the same kernels may have very different prime cascades. A genuine stochastic theorem should therefore define a wreath or cascade product inside \(\mathbf{Kl}(\mathcal D)\), a stochastic notion of division or simulation, and a complexity invariant independent of the chosen noise realization.
Once a deterministic dilation has been fixed, the Transformer construction of Liu et al. [ 2023 ] supplies shallow parallel simulators for its finite semiautomaton, including constant-depth shortcuts when its group factors are solvable. The resulting pipeline
is an exact realization scheme for rational kernels. It also compounds the nonuniqueness: behavioral success of the final Transformer need not identify either an intrinsic stochastic factorization or the dilation through which it was compiled.
Real-valued kernels suggest an approximate version. On a finite state and action space, approximate each kernel in total variation by a rational kernel. If the one-step error is at most \(\eta \), a standard coupling argument bounds the discrepancy of length-\(T\) trajectory distributions by at most \(T\eta \). Proposition 5.9 then gives a finite prime cascade for the rational approximation. This is a natural meeting point with PACC UOCL: the learner need not identify a unique stochastic mechanism, but should find, with high probability, a cascade whose admitted finite-horizon queries are within the declared tolerance.
PSRs point toward a second generalization. Their unnormalized predictive updates are linear operators on a space of tests, followed by normalization; the relevant factors need not themselves be stochastic state transitions. Plotkin and Plotkin [ 2015 ] develop decompositions of linear automata using triangular products together with wreath products, and characterize these products as terminal objects among appropriate cascade connections. This does not by itself yield a decomposition theorem for PSRs. It suggests that an ORACLE learner should decompose the observable operator system modulo predictive equivalence, while preserving positivity and normalization, rather than first reconstructing a latent MDP.
For an arbitrary endofunctor \(F\), an unrestricted Krohn–Rhodes theorem for \(F\)-coalgebras is too much to expect. The functor selects the admissible branching, observation, and transition structure, and hence also determines what a cascade and a prime could mean. A workable theorem must be relative to such data as a finitary or accessible \(F\), finite behavioral quotients, a simulation factorization system, and a distributive law supporting cascade composition. Final semantics supplies behavioral equivalence, but not by itself a prime factorization of realizations.
Stochastic compositional learning should factor observable dynamics before it enumerates latent states. Deterministic dilation gives an exact starting point for finite rational kernels; an intrinsic theory must make the factors invariant under changes of noise realization and relative to the learner’s query doctrine.
This produces a concrete ladder of research problems for ORACLE:
exact randomized cascade realizations for finite rational kernels;
PACC cascade identification for real-valued kernels, evaluated by finite-horizon queries;
an intrinsic Kleisli–Krohn–Rhodes theorem for stochastic automata and MDPs;
positivity-preserving linear or operator decompositions for PSRs; and
functor-relative prime decompositions for finite behavioral quotients of \(F\)-coalgebras.
The conceptual payoff is larger than an automata generalization. A learned world model would come with a compositional anatomy: reversible symmetries, irreversible resets, stochastic mixing, and predictive linear structure. Those factors are reusable hypotheses for transfer, accommodation, and causal intervention, rather than merely a smaller encoding of one task.
A finite UOCL learner should seek not only the smallest observational realization, but the smallest compositional explanation of that realization. Diversity controls the number of separating tests; cascade complexity controls how the induced transformations are assembled from reversible and irreversible components.
Guiding question.
Under which presentation and query conditions can an online learner identify a categorical wreath-product decomposition up to division or behavioral equivalence? Can the decomposition be chosen persistently, so that new evidence refines local factors without reconstructing the entire cascade?
Let the admitted query doctrine factor through the behavior maps into a final \(F\)-coalgebra. If two pointed coalgebras have the same final behavior, no learner receiving only answers to those queries can distinguish them. Consequently, the strongest identifiable target is their behavioral quotient; identification of a particular internal machine requires intensional probes or an additional realization prior.
Every admitted query is, by assumption, a function of final behavior. Equal final behaviors therefore induce identical answers under every possible interaction transcript. A learner driven by such transcripts must evolve identically on the two targets, so it cannot be guaranteed to select distinct internal realizations. Quotienting by equality of final behavior removes exactly this observational ambiguity.
Turing-machine inference fits the same pattern, but with an important qualification. A Turing machine has a finite description, yet its operational coalgebra of configurations is generally infinite: a configuration records the control state, tape contents, and head position, and one transition exposes its next observable event and configuration. Learning the computed language, partial function, or stream behavior is therefore coinductive identification of this configuration dynamics. It is not automatically identification of a unique program. Distinct machines can compute the same behavior, and passive finite data cannot in general settle all future computation. Computability, finite description, halting conventions, and the permitted presentation must be declared as categorical priors and success conditions. Gold’s limiting recursion and language identification mark the classical boundary between what stabilizes from a presentation and what remains unidentifiable [ Gold , 1965 , 1967 ] .
This is also the closest established ancestor of universal imitation games. There, the target was a universal coalgebra recovered coinductively from its observable behavior [ Mahadevan , 2024 ] . ORACLE retains that branch but allows the learner to revise the endofunctor, type system, and ambient category when the observed interaction cannot be represented by the initial machine doctrine. Automata learning is thus not merely an analogy: it is a sharply bounded coalgebra-learning laboratory in which presentations, separating queries, behavioral equivalence, minimization, and impossibility are all visible.
Doctrinal boundary.
Adding states or correcting transitions remains internal to the fixed coalgebraic doctrine. Evidence for stochastic evolution, unbounded memory, new input types, partial transitions, or a different behavioral endofunctor calls for doctrinal accommodation. General ORACLE permits those changes; classical machine inference normally does not.