License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.83
URN: urn:nbn:de:0030-drops-186173
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18617/
Go to the corresponding LIPIcs Volume Portal

Spenner, Daniel Alexander

Decomposing Finite Languages

pdf-format:
LIPIcs-MFCS-2023-83.pdf (0.8 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2023/18617},
  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}
}

Keywords: Deterministic finite automaton (DFA), Regular languages, Finite languages, Decomposition, Primality, Minimality
Collection: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Issue Date: 2023
Date of publication: 21.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI