Jonathan Mosheiff

We say that a deterministic finite automaton (DFA) A is composite if there are DFAs A₁,...,A_t such that L(A) = ∩_i=1^t L(A_i) and the index of every A_i is strictly smaller than the index of A. Otherwise, A 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.