יונתן מושיוב

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 is strictly smaller than the index of . Otherwise, is prime. We study the problem of deciding whether a given DFA is composite, the number of DFAs required in a decomposition, methods to prove primality, and structural properties of DFAs that make the problem simpler or are retained in a decomposition.