Deciding DFA-Primality is NP-Hard

2026/05/07 by Daniel Alexander Spenner · 1 voice
Computer Science · #cs.FL

paper · pdf · doi:10.48550/arxiv.2605.07031

Abstract

A DFA A is composite if there exist DFAs A₁,…,A_t with L(A) = \bigcap_i=1^t L(A_i) such that each A_i has strictly less states than the minimal DFA deciding L(A). Otherwise, it is prime. Prime-DFA is the problem of deciding primality for a given DFA. It was defined by Kupferman and Mosheiff in 2015 and it was shown to be NL-hard and in ExpSpace. This paper proves the NP-hardness of Prime-DFA, thereby making the first progress in closing this doubly-exponential gap. It proves the NP-hardness by a reduction from the propositional logic satisfiability problem. The correctness of the reduction relies on an involved characterization of primality for a class of DFAs which contains those that can occur in the reduction.

Citations

• Decomposing Finite Languages
• Learning Deterministic Finite Automata Decompositions from Examples and Demonstrations
• Decomposing Permutation Automata
• The complexity of theorem-proving procedures

Cited by

• Decomposition of Automata recognizing Ideals

Discussions

• Daniel Alexander Spenner: Deciding DFA-Primality is NP-Hard https://arxiv.org/abs/2605.07031 https://arxiv.org/pdf/2605.07031 https://arxiv.org/html/2605.07031 [bsky, 0 points, 0 comments]

Related

• Decomposing Finite Languages
• Decomposing Permutation Automata
• Four primality testing algorithms
• Sharpening "Primes is in P" for a large family of numbers
• A Lower Bound for Primality of Finite Languages