A Linear-size Cascade Decomposition for Wheeler Automata

The Krohn-Rhodes Decomposition Theorem (KRDT) is a central result in automata and semigroup theories: it states that any (deterministic) finite-state automaton can be disassembled into a collection of automata of two simple types, that can be arranged into a combination - cascade - that simulates the original automaton. The elementary building blocks of the decomposition are either resets or permutations. The full-fledged theorem features two orthogonal dimensions of complexity: the type and the number of building blocks appearing in the cascade, and a deep step in the proof is the characterization of the permutations appearing in the decomposition. This characterization implies, in the case of counter-free automata, that the resulting cascade contains no permutations. In this paper we start analysing KRDT for two compression-oriented classes of automata: (i) path- coherent: state-ordered automata mapping state-intervals to state-intervals; (ii) Wheeler: a subclass of path-coherent automata whose order is the one induced by the co-lexicographic order of words. These classes were recently defined and studied and they turn out to be efficiently encodable and indexable. We prove that each automata in these classes can be decomposed as a cascade with a number of components which is linear in the number of states of the original automaton and, for the Wheeler class, we prove that only two-state resets are needed. Our line of reasoning avoids the necessity of using full KRDT and proves our results directly by a simple inductive argument.