2022
Automata Cascades: Expressivity and Sample Complexity
Every automaton can be decomposed into a cascade of ba- sic automata. This is the Prime Decomposition Theorem by Krohn and Rhodes. We show that cascades allow for describ- ing the sample complexity of automata in terms of their com- ponents. In particular, we show that the sample...