| Abstract: | We already know how to decompose any finite automaton with a strongly connected state diagram into a strongly connected version of what we call a synchronizable cascade decomposition. This is a two component cascade decomposition whose first component has a synchronizer and whose second component is a permutation automaton. Here, we give a simpler procedure for constructing such a decomposition and show that the constructed decomposition is a homomorphic image of a subautomaton of any other synchronizable cascade decomposition. The constructed decomposition is then of minimal size, and all minimal synchronizable cascade decompositions are isomorphic, including all decompositions constructed by the old procedure. This means that their first components are isomorphic, but their second components need not be. In analyzing learning systems, we can use a synchronizable cascade decomposition to model a finite automaton environment, and in these analytical applications, the second component has equiprobable states and can often be ignored in analysis. There are many ways of constructing synchronizable cascade decompositions and we will want to use the construction that is easiest for the analytical application. The isomorphism result says that two different construction methods produce isomorphic decompositions provided the decompositions produced have the minimal number of states, and it is often easy to show this by a simple counting argument. This paper confines itself to giving the simpler procedure and proving the homomorphism result. It does not discuss analytical applications. |
