Prime languages

We say that a deterministic finite automaton (DFA) A is composite if there are DFAs A 1, …, 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.

Authors

• Orna Kupferman
• Jonathan Mosheiff

Keywords

• Deterministic finite automaton (DFA)
• Regular languages
• DFA decomposition
• Prime DFA
• Prime regular languages