5.4.2 Krohn–Rhodes decomposition: learning cascades instead of states

5.4.2 Krohn–Rhodes decomposition: learning cascades instead of states

The diversity construction compresses what the learner must observe. Krohn–Rhodes theory asks a complementary question: once a finite transformation system has been identified, from which elementary machines can its dynamics be composed? For a deterministic automaton with state set \(X\) and input alphabet \(A\), let

be its transformation monoid. A monoid \(M\) divides a monoid \(N\), written \(M\prec N\), when \(M\) is a homomorphic image of a submonoid of \(N\). Division is the appropriate notion of simulation here: the larger machine may contain additional states and distinctions, provided a stable subsystem maps onto the behavior to be represented.

The formulation suppresses a useful technical distinction. The three-element flip-flop monoid consists of an identity together with the two constant transformations of a two-state set. It is therefore a one-bit set–reset device, not a counter in the usual numerical sense. More general statements first decompose a finite monoid into group and aperiodic factors; the aperiodic factors can in turn be divided by iterated wreath products of flip-flops. The theorem is an existence and simulation result, not a claim that the decomposition is unique or easy to infer [ Krohn and Rhodes , 1965 ] .

Example 1.21 gives this algebraic dichotomy a simplicial reading. A group factor, regarded as a one-object category, has a Kan nerve: its transitions are reversible and its outer horns can be filled. A reset factor has noninvertible arrows; its nerve retains inner composition but generally fails the outer-horn condition. A wreath product does more than place these factors side by side. It arranges them as a directed cascade in which the input received by a later component may depend on the states and outputs of earlier components. Krohn–Rhodes theory therefore separates a finite compositional world into reversible memory, irreversible memory update, and hierarchical dependency.

This suggests an explicit UOCL objective. First infer a finite observational quotient \(\widehat M_{\mathcal Q}\) from a separating query doctrine \(\mathcal Q\), as in the diversity construction. Then search for a cascade presentation

that preserves the admitted tests. Instead of penalizing the number of global states, the learner can penalize the number and complexity of the prime factors, their dependency pattern, and especially the number of nontrivial group factors. The classical minimum number of group layers is the Krohn–Rhodes group complexity. In ORACLE it becomes one candidate measure of the structural depth required to explain an observed finite world.

Ronca et al. [ 2023 ] provide a modern learning-theoretic step in this direction. They treat automata cascades as modular hypothesis classes and derive sample-complexity bounds that, up to logarithmic factors, scale with the number of components and the maximum complexity of a component rather than with the potentially exponential global state space. Their result does not yet solve the ORACLE problem of discovering the right prime cascade from an unrestricted interaction presentation. It does demonstrate that a correct compositional prior can change the statistical scale of automata learning.

There is also a genuine categorical lineage rather than a merely suggestive analogy. Wells [ 1980 ] established a Krohn–Rhodes theorem for finite categories and set-valued functors. Wells later decomposed category-valued functors by categorical wreath products, explicitly motivating state-transition systems with structured, typed states [ Wells , 1988 ] . Thérien [ 1991 ] defined a two-sided wreath construction, or block product, directly on categories. These results suggest replacing a one-object transformation monoid by a typed action category and replacing a flat state set by a functor of structured state fibers.