DROPS

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2026.192

Deciding DFA-Primality Is NP-Hard

Authors: Daniel Alexander Spenner

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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.

Cite as

Daniel Alexander Spenner. Deciding DFA-Primality Is NP-Hard. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 192:1-192:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{spenner:LIPIcs.ICALP.2026.192,
  author =	{Spenner, Daniel Alexander},
  title =	{{Deciding DFA-Primality Is NP-Hard}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{192:1--192:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.192},
  URN =		{urn:nbn:de:0030-drops-265819},
  doi =		{10.4230/LIPIcs.ICALP.2026.192},
  annote =	{Keywords: Deterministic finite automaton (DFA), Regular languages, Finite languages, Decomposition, Primality, NP-Hardness}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2023.83

Decomposing Finite Languages

Authors: Daniel Alexander Spenner

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract

The paper completely characterizes the primality of acyclic DFAs, where a DFA 𝒜 is prime if there do not exist DFAs 𝒜_1,… ,𝒜_t with ℒ(𝒜) = ⋂_{i=1}^t ℒ(𝒜_i) such that each 𝒜_i has strictly less states than the minimal DFA recognizing the same language as 𝒜. A regular language is prime if its minimal DFA is prime. Thus, this result also characterizes the primality of finite languages. Further, the NL-completeness of the corresponding decision problem Prime-DFA_fin is proven. The paper also characterizes the primality of acyclic DFAs under two different notions of compositionality, union and union-intersection compositionality. Additionally, the paper introduces the notion of S-primality, where a DFA 𝒜 is S-prime if there do not exist DFAs 𝒜₁,… ,𝒜_t with ℒ(𝒜) = ⋂_{i=1}^t ℒ(𝒜_i) such that each 𝒜_i has strictly less states than 𝒜 itself. It is proven that the problem of deciding S-primality for a given DFA is NL-hard. To do so, the NL-completeness of 2Minimal-DFA, the basic problem of deciding minimality for a DFA with at most two letters, is proven.

Cite as

Daniel Alexander Spenner. Decomposing Finite Languages. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 83:1-83:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{spenner:LIPIcs.MFCS.2023.83,
  author =	{Spenner, Daniel Alexander},
  title =	{{Decomposing Finite Languages}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{83:1--83:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.83},
  URN =		{urn:nbn:de:0030-drops-186173},
  doi =		{10.4230/LIPIcs.MFCS.2023.83},
  annote =	{Keywords: Deterministic finite automaton (DFA), Regular languages, Finite languages, Decomposition, Primality, Minimality}
}

Search Results

Documents authored by Spenner, Daniel Alexander

Deciding DFA-Primality Is NP-Hard

Abstract

Cite as

Decomposing Finite Languages

Abstract

Cite as

Thanks for your feedback!

Could not send message