Prime Languages

Abstract We say that a deterministic finite automaton (DFA) \(\mathcal{A}\) is composite if there are DFAs \(\mathcal{A}_1, \ldots, \mathcal{A}_t\) such that \(L(\mathcal{A}) = \bigcap_{i=1}^t L(\mathcal{A}_i)\) and the index of every \(\mathcal{A}_i\) is strictly smaller than the index of \(\mathcal{A}\). Otherwise, \(\mathcal{A}\) 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.

Authors

• Orna Kupferman
• Jonathan Mosheiff

Keywords

No keywords are indexed for this paper.