2026-08-18T02:52:25Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:18617 2024-03-06T11:02:16Z ddc:004 open_access
Decomposing Finite Languages Spenner, Daniel Alexander Deterministic finite automaton (DFA) Regular languages Finite languages Decomposition Primality Minimality 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. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Daniel Alexander Spenner 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.83 urn:nbn:de:0030-drops-186173 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.83 eng https://creativecommons.org/licenses/by/4.0/legalcode