Automata Cascades: Expressivity and Sample Complexity

Abstract

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 complexity is linear in the number of components and the maximum com- plexity of a single component. This opens to the possibil- ity for learning automata representing large dynamic systems Figure 1: Diagram of a fully-connected cascade of three consisting of many parts interacting with each other. It is in components—based on a figure in (Maler 1990). sharp contrast with the established understanding of the sam- ple complexity of automata, described in terms of the overall number of states and input letters, which in turn implies that it is only possible to learn automata where the number of states strongly based on the theory of Krohn and Rhodes, which and letters is linear in the amount of data available. Instead says that every automaton can be decomposed into a cascade our results show that one can in principle learn automata with of basic components called prime automata. Furthermore, it infinite input alphabets and a number of states that is expo- identifies large classes of automata that can be decomposed nential in the amount of data available. using only one kind of prime automaton (Krohn and Rhodes 1965). One such class has the expressivity of star-free reg- ular languages, and hence it captures well-known temporal