Prime languages

We say that a deterministic finite automaton (DFA) AA is composite   if there are DFAs A1,…,AtA1,…,At such that L(A)=⋂i=1tL(Ai) and the index of every AiAi is strictly smaller than the index of AA. Otherwise, AA is prime.We study the problem of deciding whether a given DFA is composite, the number of DFAs required in a decomposition, decompositions that are based on abstractions, methods to prove primality, and structural properties of DFAs that make the problem simpler or are retained in a decomposition. We also provide an algebraic view of the problem and demonstrate its usefulness for the special case of permutation DFAs.