2026-09-08T01:21:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26581 2026-09-05T19:48:19Z ddc:004 open_access

Deciding DFA-Primality Is NP-Hard Spenner, Daniel Alexander Deterministic finite automaton (DFA) Regular languages Finite languages Decomposition Primality NP-Hardness A DFA 𝒜 is composite if there exist DFAs 𝒜_1,…,𝒜_t with ℒ(𝒜) = ⋂_{i=1}^t ℒ(𝒜_i) such that each 𝒜_i has strictly less states than the minimal DFA deciding ℒ(𝒜). 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Alexander Spenner 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.192 urn:nbn:de:0030-drops-265819 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.192 eng https://creativecommons.org/licenses/by/4.0/legalcode