DROPS

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

Decomposing Finite Languages

Abstract

Cite as